Steinitz exchange lemma

Proof

Suppose ${\displaystyle U=\{u_1,\dots ,u_m\}}$ and ${\displaystyle W=\{w_1,\dots ,w_n\}}$. We wish to show that ${\displaystyle m\le n}$, and that after rearranging the ${\displaystyle w_j}$ if necessary, the set ${\displaystyle \{u_1,\dots ,u_m,w_{m+1},\dots ,w_n\}}$ spans ${\displaystyle V}$. We proceed by induction on ${\displaystyle m}$.

For the base case, suppose ${\displaystyle m}$ is zero. In this case, the claim holds because there are no vectors ${\displaystyle u_i}$, and the set ${\displaystyle \{w_1,\dots ,w_n\}}$ spans ${\displaystyle V}$ by hypothesis.

For the inductive step, assume the proposition is true for ${\displaystyle m-1}$. By the inductive hypothesis we may reorder the ${\displaystyle w_i}$ so that ${\displaystyle \{u_1,\dots ,u_{m-1},w_m,\dots ,w_n\}}$ spans ${\displaystyle V}$. Since ${\displaystyle u_m\in V}$, there exist coefficients ${\displaystyle {\mu }_1,\dots ,{\mu }_n}$ such that

${\displaystyle u_m=\sum _{i=1}^{m-1}{\mu }_i{u}_i+\sum _{j=m}^n{\mu }_j{w}_j}$.

At least one of the ${\displaystyle {\mu }_j}$ must be non-zero, since otherwise this equality would contradict the linear independence of ${\displaystyle \{u_1,\dots ,u_m\}}$; it follows that ${\displaystyle m\le n}$. By reordering ${\displaystyle {\mu }_m{w}_m,\dots ,{\mu }_n{w}_n}$ if necessary, we may assume that ${\displaystyle {\mu }_m}$ is nonzero. Therefore, we have

${\displaystyle w_m=\frac{1}{{\mu }_m}\left(u_m-\sum _{j=1}^{m-1}{\mu }_j{u}_j-\sum _{j=m+1}^n{\mu }_j{w}_j\right)}$.

In other words, ${\displaystyle w_m}$ is in the span of ${\displaystyle \{u_1,\dots ,u_m,w_{m+1},\dots ,w_n\}}$. Since this span contains each of the vectors ${\displaystyle u_1,\dots ,u_{m-1},w_m,w_{m+1},\dots ,w_n}$, by the inductive hypothesis it contains ${\displaystyle V}$.

Applications

The Steinitz exchange lemma is a basic result in computational mathematics, especially in linear algebra and in combinatorial algorithms.