04 - Steinitz Exchange Lemma

Steinitz Exchange Lemma

Let $V$ be a vector space over a field $\mathbf{F}$
Let $X=\{v_1,v_2,\cdots ,v_n\}\subseteq V$
Suppose that $u\in ⟨X⟩$ but $u\notin ⟨X\setminus \{v_i\}⟩$ for some $i$

Let $Y=(X\setminus \{v_i\})\cup \{u\}$
Then

$$⟨Y⟩=⟨X⟩$$

In other words you exchange $u$ for $v_i$

Proof

Since $u\in ⟨X⟩$ then there are ${\alpha }_1,\cdots ,{\alpha }_n\in \mathbf{F}$ such that

$$u={\alpha }_1{v}_1+\cdots +{\alpha }_n{v}_n$$

There is $v_i\in X$ such that $u\notin \{X\setminus \{v_i\}\}$.
Without loss of generality, it is safe to assume that $i=n$
Since $u\notin ⟨X\setminus \{v_n\}⟩$, we see that $a_n\ne 0$
So by dividing by ${\alpha }_n$ and rearranging we get

$$v_n=\frac{1}{{\alpha }_n}(u-{\alpha }_1{v}_1-\cdots -{\alpha }_{n-1}{v}_{n-1})$$

Suppose for $w\in ⟨Y⟩$ then $w$ is a linear combination of the elements of $Y$
As we can replace $u$ by ${\alpha }_1{v}_1+\cdots +{\alpha }_n{v}_n$ so that $w$ is now a linear combination of the elements of $X$
Hence

$$⟨Y⟩\subseteq ⟨X⟩$$

Similarly if $w\in ⟨X⟩$ then $w$ is a linear combination of the elements of $X$
Substituting $v_n$ using the above then $w$ is now a linear combination of $Y$
Hence

$$⟨Y⟩\supseteq ⟨X⟩$$

Therefore

$$⟨X⟩=⟨Y⟩$$