Steinitz exchange lemma If \( \{v_1,\ldots,v_m\} \) is a set of linearly independent vectors in vector space V, and \( \{w_1,\ldots,w_n\} \) spans V, then:
- Possibly after reordering the \( w_i \), \( \{v_1,\ldots,v_m,w_{m+1},\ldots,w_n\} \) spans V.
- \( m\,\leq\,n \)
- \( H_m \): Steinitz exchange lemma holds for all non-negative integers m.
- \( H_0 \): Steinitz exchange lemma holds when \( m=0 \) \( \emptyset \) is a set of linearly independent vectors in vector space V. Based on the conditions given \( \{w_1,\ldots,w_n\} \) spans V. And clearly, \( m=0\leq n \)
- \( H_k \): Steinitz exchange lemma holds for some non-negative integers \( k \)
- \( H_{k+1} \): Steinitz exchange lemma holds for \( (k+1) \).
Based on \( H_k \), \( \{v_1,\ldots,v_k,w_{k+1},\ldots,w_n\} \) spans V.
\[ v_{k+1}\in \textbf{V}\Leftrightarrow v_{k+1}=\sum_{i=1}^k{\lambda_i v_i}+\sum_{i=k+1}^n{\lambda_i w_i} \]
Since \( v_1,\ldots,v_{k+1} \) are linearly independent,
\begin{align*} \Rightarrow &v_{k+1}-\sum_{i=1}^k{\lambda_i v_i}\neq0\\ \Rightarrow &v_{k+1}\neq\sum_{i=1}^k{\lambda_i v_i}\\ \Rightarrow &\text{At least one of }\lambda_{k+1},\ldots\lambda_n~\text{is non-zero} \end{align*}Rearrange \( w_i \) so that \( \lambda_{k+1}\neq0 \)
\begin{align*} \Rightarrow &v_{k+1}=\sum_{i=1}^k{\lambda_i v_i}+\lambda_{k+1}w_{k+1}+\sum_{i=k+2}^n{\lambda_i w_i}\\ \Leftrightarrow &w_{k+1}=\frac{1}{-\lambda_{k+1}}(\sum_{i=1}^k{\lambda_i v_i}-v_{k+1}+\sum_{i=k+2}^n{\lambda_i w_i}) \end{align*}\( \forall v\in \)V, \( \exists \) a linear combination of\( ~\{v_1,\ldots,v_k,w_{k+1},\ldots,w_n\}=v \) Now we substitute \( w_{k+1}=\frac{1}{-\lambda_{k+1}}(\sum_{i=1}^k{\lambda_i v_i}-v_{k+1}+\sum_{i=k+2}^n{\lambda_i w_i}) \) into the linear combination. \( \Rightarrow\forall v\in \)V, \( \exists \) a linear combination of\( ~\{v_1,\ldots,v_k,v_{k+1},w_{k+2},\ldots,w_n\}=v \) Therefore \( H_{k+1} \) holds, if \( H_k \) is true.
- Based on M.I., \( H_m \) is true.