Lema da troca

O texto-fonte do card, para propor uma correção ou escrever um card no mesmo formato. copiar

\cardid{lem-troca}
\cardtipo{lema}
\cardtitulo{Lema da troca}
\cardtags{}
\cardautor{}

\cardrequer{def-li, def-ger}
\cardrequerdem{lem-sist, lem-sobra}
\cardveja{}

\begin{cartao}

\emph{Se $V = [u_1,\ldots,u_m]$ e
$v_1,\ldots,v_k\in V$ são LI, então $k\leq m$.}

\noindent Em palavras: \emph{mais vetores do que geradores significa mais incógnitas do que
equações}.

\begin{demonstracao}

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 \vejacard{lem-sist}, 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.

\begin{center}
\begin{tikzpicture}[scale=1,every node/.style={scale=1}]
 \draw[line width=0.9pt] (0.15,-0.1)--(-0.1,-0.1)--(-0.1,1.9)--(0.15,1.9);
 \draw[line width=0.9pt] (5.05,-0.1)--(5.3,-0.1)--(5.3,1.9)--(5.05,1.9);
 \foreach \cc in {0,1,2,3,4}{
   \fill[Fazul!10] ({0.2+\cc},0.0) rectangle ({0.9+\cc},1.8);}
 \foreach \cc/\lab in {0/1,1/2,2/3,3/4,4/5}{
   \node[cxs,Fazul,anchor=south] at ({0.55+\cc},1.95) {$v_{\lab}$};}
 \foreach \rr in {0,1,2}{
   \foreach \cc in {0,1,2,3,4}{
     \node[cxs] at ({0.55+\cc},{1.5-0.6*\rr}) {$a_{\ast\ast}$};}}
 \foreach \rr/\lab in {0/1,1/2,2/3}{
   \node[cxs,Flaranja,anchor=east] at (-0.2,{1.5-0.6*\rr}) {$u_{\lab}$};}
 \draw[decorate,decoration={brace,amplitude=4pt,mirror},line width=0.6pt]
   (0.2,-0.25)--(5.0,-0.25);
 \node[cxs,anchor=north] at (2.6,-0.4) {$k$ colunas (os $v_j$)};
 \draw[decorate,decoration={brace,amplitude=4pt},line width=0.6pt]
   (5.45,1.8)--(5.45,0.0);
 \node[cxs,anchor=west] at (5.6,0.9) {$m$ linhas (os $u_i$)};
 \node[cx,anchor=west,align=left] at (8.1,0.9)
  {$k>m$: mais colunas\\ do que linhas $\Rightarrow$\\ uma relação não trivial\\ entre as colunas};
\end{tikzpicture}
\end{center}

{\footnotesize\itshape 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
\vejacard{lem-sist} dá uma combinação não trivial das colunas que se anula; a mesma
combinação dos $v_j$ se anula.\par}

\medskip
\noindent\textbf{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$.

\smallskip
\noindent\emph{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.\]
\emph{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 \vejacard{lem-sobra} trocar
$u_r$ por $v_r$ não altera o subespaço gerado, que continua sendo $V$.

\smallskip
\noindent\emph{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.

\begin{center}
\begin{tikzpicture}[scale=1,every node/.style={scale=1}]
 \foreach \rr/\lista in {0/{u_1,u_2,u_3,u_4},1/{v_1,u_2,u_3,u_4},2/{v_1,v_2,u_3,u_4},3/{v_1,v_2,v_3,u_4}}{
   \foreach \ee [count=\cc] in \lista{
     \node[cel,Aazul,fill=Aazul!8] at ({0.78*\cc},{-0.75*\rr}) {$\ee$};}}
 \foreach \rr/\tx in {0/{geram $V$},1/{ainda geram},2/{ainda geram},3/{ainda geram}}{
   \node[cxs,Aazul,anchor=west] at (3.6,{-0.75*\rr}) {\tx};}
 \foreach \rr in {1,2,3}{
   \node[cxs,Aazul,anchor=east] at (0.3,{-0.75*\rr}) {troca $\rr$:};}
\end{tikzpicture}
\end{center}

{\footnotesize\itshape 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.\par}

\end{demonstracao}

\end{cartao}