Lema da troca

Suponha, por absurdo, \(k>m\). Cada \(v_j\) é combinação dos \(u_i\): \[v_j = a_{1j}u_1+a_{2j}u_2+\cdots+a_{mj}u_m,\qquad j = 1,\ldots,k.\] Para escalares \(c_1,\ldots,c_k\), \[\sum_{j=1}^kc_jv_j = \sum_{j=1}^kc_j\sum_{i=1}^ma_{ij}u_i = \sum_{i=1}^m\Big(\sum_{j=1}^ka_{ij}c_j\Big)u_i.\] O sistema \(\sum_ja_{ij}c_j = 0\) (\(i = 1,\ldots,m\)) tem \(m\) equações e \(k>m\) incógnitas; pelo Lema 2.52, tem solução \((c_1,\ldots,c_k)\neq0\). Para ela, todos os coeficientes dos \(u_i\) se anulam, e portanto \(\sum_jc_jv_j = 0\) com algum \(c_j\neq0\) — os \(v_j\) seriam LD. Absurdo.

A demonstração do lema da troca em uma matriz. A coluna \(j\) traz as coordenadas de \(v_j\) em relação a \(u_1,\ldots,u_m\). Com mais colunas do que linhas, o Lema 2.52 dá uma combinação não trivial das colunas que se anula; a mesma combinação dos \(v_j\) se anula.

Outra demonstração: substituição sucessiva (Steinitz). Esta demonstração não usa sistemas lineares, e explica o nome do lema: os \(v\) entram na lista geradora um de cada vez, cada um expulsando um \(u\).

Afirmação. Para cada \(r\leq\min(k,m)\), após renumerar os \(u_i\), \[[v_1,\ldots,v_r,\,u_{r+1},\ldots,u_m] = V.\] Passo. Suponha a afirmação para \(r-1\) (para \(r = 0\) é a hipótese). Então \[v_r = b_1v_1+\cdots+b_{r-1}v_{r-1}+c_ru_r+\cdots+c_mu_m.\] Algum \(c_i\) é não nulo: se todos fossem nulos, \(v_r\) seria combinação de \(v_1,\ldots,v_{r-1}\), e os \(v\) seriam LD. Renumerando, \(c_r\neq0\); isolando \(u_r\), ele é combinação de \(v_1,\ldots,v_r,u_{r+1},\ldots,u_m\), e pelo Lema 2.42 trocar \(u_r\) por \(v_r\) não altera o subespaço gerado, que continua sendo \(V\).

Conclusão. Se fosse \(k>m\), com \(r = m\) teríamos \([v_1,\ldots,v_m] = V\), e então \(v_{m+1}\in[v_1,\ldots,v_m]\), contra a independência.

A substituição de Steinitz. Em cada linha um \(v\) entra e um \(u\) sai, e a lista continua gerando \(V\). Se houvesse mais \(v\) do que \(u\), os \(u\) acabariam antes, e o \(v\) seguinte já estaria no espaço gerado pelos anteriores.