Past exam of the mathematics course of the University of Oxford / 2017 / Prelims / Mathematics I / 1 / a / ii / Solution

The Steinitz exchange lemma states that if $u_1,\dots ,u_r$ are linearly independent and $w_1,\dots ,w_s$ span a vector space $V$, then $r\le s$ and some $r$ of the $w_j$ can be replaced by $u_1,\dots ,u_r$ while preserving the spanning set property.

Here is the exchange argument. Suppose that after $k$ replacements, a spanning set iswhere the remaining $w_j$ have been relabelled if necessary. Express $u_{k+1}$ as a linear combination of this family. At least one remaining $w_j$ has a nonzero coefficient; otherwise $u_{k+1}$ belongs to the span of $u_1,\dots ,u_k$, contradicting linear independence. Relabel this entry $w_{k+1}$. Solving for $w_{k+1}$ shows that it lies in the span ofThe new family therefore still spans $V$. Starting at $k=0$ repeats this step until all $r$ independent vectors have been inserted. If $r>s$, after $s$ steps the next $u_{s+1}$ would lie in the span of $u_1,\dots ,u_s$, a contradiction. Thus $r\le s$, and the construction proves the replacement assertion as well.