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

The vectors are linearly independent ifThey span $V$ if every $v\in V$ is a linear combination $v={\sum }_{j=1}^n{a}_j{v}_j$ with real coefficients. They form a basis of $V$ if they are linearly independent and span $V$. Equivalently, every $v\in V$ has exactly one such representation: existence is the spanning set condition, and subtracting two representations shows that uniqueness is precisely linear independence.

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.

Put $w_1=v_1$ and $w_j=v_j-v_1$ for $j\ge 2$. Since $v_1=w_1$ and $v_j=w_j+w_1$, the two families have the same linear span. Moreover,If the $v_j$ are linearly independent, a vanishing expression forces $a_j=0$ for $j\ge 2$ and then $a_1=0$. Conversely,so linear independence of the $w_j$ forces all $b_j=0$. Thus both the spanning set condition and linear independence are equivalent for the two families, proving the desired equivalence of bases.