Past exam of the mathematics course of the University of Cambridge / 2014 / ib / Paper 1 / 1G (Linear Algebra)

The Steinitz exchange lemma says that if $u_1,\dots ,u_r$ are linearly independent and $v_1,\dots ,v_s$ span the same vector space, then $r\le s$ and, after reordering the $v_j$, the list $u_1,\dots ,u_r,v_{r+1},\dots ,v_s$ still spans it.

To prove this, suppose $u_1,\dots ,u_k$ have already replaced $k$ of the spanning vectors. Express $u_{k+1}$ in that spanning list. At least one coefficient of an unreplaced $v_j$ is nonzero: otherwise $u_{k+1}$ lies in the span of $u_1,\dots ,u_k$, contradicting linear independence. Solve this expression for that $v_j$ and replace it by $u_{k+1}$. The new list still spans. If all $s$ vectors were replaced before the $u_i$ were exhausted, the next $u_i$ would be dependent on its predecessors. Hence $r\le s$, and the replacement can continue through $u_r$.

For two bases of sizes $r,s$, apply the Steinitz exchange lemma in both directions to get $r\le s\le r$. Thus every basis has the same size. Given a linearly independent set and any finite basis, the replacement procedure produces a finite spanning list containing that set. Successively delete any remaining vector dependent on the others; none of the prescribed independent vectors need be deleted, since one can instead delete a dependent supplementary vector. Equivalently, greedily retain only supplementary vectors outside the span already built. The resulting list is a basis containing the prescribed set.

For the three-dimensional example, the columns have matrixTherefore the three vectors are a basis. For the four-dimensional example,This is a nontrivial linear dependence, so the four vectors are not a basis. The distinction is an instance of the adjacent sums of a cyclic basis criterion: alternating coefficients close consistently around an even cycle, but not an odd one.