= Solution
{c}
The <Steinitz exchange lemma> states that if $u_1,\ldots,u_r$ are <linearly independent> and $w_1,\ldots,w_s$ <span> a <vector space> $V$, then $r\leq s$ and some $r$ of the $w_j$ can be replaced by $u_1,\ldots,u_r$ while preserving the <spanning set> property.
Here is the exchange argument. Suppose that after $k$ replacements, a <spanning set> is
$$
u_1,\ldots,u_k,w_{k+1},\ldots,w_s,
$$
where 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,\ldots,u_k$, contradicting <linear independence>. Relabel this entry $w_{k+1}$. Solving for $w_{k+1}$ shows that it lies in the <span> of
$$
u_1,\ldots,u_{k+1},w_{k+2},\ldots,w_s.
$$
The 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,\ldots,u_s$, a contradiction. Thus $r\leq s$, and the construction proves the replacement assertion as well.
Back to article page
