05 - Size Inequality for Independent vs Spanning Sets

Size Inequality for Independent vs Spanning Sets

Let $V$ be a vector space
Let $S,T$ be finite subsets of $V$

Suppose $S$ is linearly independent and $T$ spans $V$ then

$$|S|\le |T|$$

Proof

Assume that $S$ is linearly independent and $T$ spans $V$
Let the elements of $S$ be $u_1,u_2,\cdots ,u_m$
Let the elements of $T$ be $v_1,v_2,\cdots ,v_n$

Then we use Steinitz Exchange Lemma to swap the elements of $T$ with those of $S$, exhausting $S$ as follows

Let $T_0=\{v_1,\cdots ,v_n\}$
Since $⟨T_0⟩=V$, then $u_1\in ⟨v_1,\cdots ,v_i⟩$ for some $1\le i\le n$ and choose $i$ to be minimal
Note that then $u_1\notin ⟨v_1,\cdots ,v_{i-1}⟩$
Using the Steinitz Exchange Lemma then

$$⟨v_1,\cdots ,v_i⟩=⟨u_1,v_1,\cdots ,v_{i-1}⟩$$

Hence

$$\begin{array}{rl}V& =⟨v_1,\cdots v_n⟩\\ & =⟨v_1,\cdots ,v_i⟩+⟨v_{i+1},\cdots ,v_n⟩\\ & =⟨u_1,v_1,\cdots ,v_{i-1}⟩+⟨v_{i+1},\cdots ,v_n⟩\\ & =⟨u_1,v_1,\cdots ,v_{i-1},v_{i+1},\cdots ,v_n⟩\end{array}$$

By relabelling the elements of $T$ we can assume without loss of generality assume that

$$u_1\text{ has been exchange for }{v}_1$$

Then set

$$T_1=\{u_1,v_2,\cdots ,v_n\}\text{noting that }⟨T_1⟩=V$$

This can be inductively repeated creating sets

$$T_k=\{u_1,\cdots ,u_k,v_{k+1},\cdots ,v_n\}\text{ such that }⟨T_K⟩=V$$

(Note that $u_{k+1}\in ⟨T_k⟩$ but $u_{k+1}\notin ⟨u_1,\cdots ,u_k⟩$ as $S$ is independent)
This repeats until $S$ is exhausted (as you replace elements of $T$ with elements of $S$)

Hence

$$m\le n$$