The Dimension Bound Theorem

Spanning controls independence

1. If $V$ has a spanning set $T=\{y_1,\dots ,y_k\}$
2. If $S=\{x_1,\dots ,x_n\}$ is a linearly independent subset of V
3. Then, $n\le k$

Proof

Intuition

Suppose $k>n$ represent $x_i$ using $y_j$ to create a Homogenous Systems

Proof

1. Every $x_i$ can be represented using $span(T)$
2. This means $\overrightarrow{x_i}=a_{i1}{\vec{y}}_1+\cdots +a_{ik}{\vec{y}}_k$
3. Consider $b_1{\vec{x}}_1+\cdots +b_x{\vec{x}}_n=\vec{0}$
4. This gives:

$$\begin{array}{rl}& b_1(a_{11}{\vec{y}}_1+\cdots +a_{1k}{\vec{y}}_k)\\ & +⋮\\ & +b_n(a_{n1}{\vec{y}}_1+\cdots +a_{nk}{\vec{y}}_k)=\vec{0}\end{array}$$

As we know that each of $x_1,\dots ,x_n$ is linearly independent, we can say that the only way for them to be zero is if $b_1=\cdots =b_n=0$

Down to Earth Example

This theorem is good if you want to prove that any set of vectors more than the size of your spanning set is linearly dependent.

We know ${\mathbb{R}}^n=span\{e_1,e_2\}$ Consider any 3 vectors $\{v_1,v_2,v_3\}\subset {\mathbb{R}}^2$ $(0,0)=a_1{v}_1+a_2{v}_2+a_3{v}_3$ $=a_1(c_{11}{e}_1+c_{12}{e}_2)+a_2(c_{21}{e}_1+c_{22}{e}_2)+a_3(c_{31}{e}_1+c_{32}{e}_2)$ $=(a_1{c}_{11}+a_2{c}_{21}+a_3{c}_{31})e_1+(a_1{c}_{12}+a_2{c}_{22}+a_3{c}_{32})e_2$ This gives us a linear system:

$$\left[\begin{array}{cc}{a}_1{c}_{11}+a_2{c}_{21}+a_3{c}_{31}& 0\\ a_1{c}_{12}+a_2{c}_{22}+a_3{c}_{32}& 0\end{array}\right]$$

Note that they must have a non-trivial solution $(a_1,a_2,a_3)$ Thus, $\{v_1,v_2,v_3\}$ must be dep