Finite Dimensional Linearly Independent Set of Vectors Theorem

# Finite Dimensional Linearly Independent Set of Vectors Theorem

We will now look at a very important theorem that tells us that given a linearly independent set of $m$ vectors $\{ u_1, u_2, ..., u_m \}$ and that if $V$ has a finite dimensional spanning set of vectors $\{ v_1, v_2, ..., v_n \}$ such that $V = \mathrm{span} (v_1, v_2, ..., v_n)$, then $m ≤ n$.

 Theorem 1: Let $V$ be a finite dimensional vector space over the field $\mathbb{F}$, that is $V$ contains a finite dimensional spanning set such that $V = \mathrm{span} \{ v_1, v_2, ..., v_n \} = \bigoplus_{i=1}^{n} \mathbb{F} v_i$. If the set of vectors $\{ u_1, u_2, ..., u_m \}$ from $V$ is linearly independent, then $m ≤ n$.
• Proof: Since the set of vectors $\{ v_1, v_2, ..., v_m \}$ is a spanning set for the vector space $V$, then the nonzero vector $u_1 \in V$ can be written as a linear combination of this set of vectors, that is:
(1)
\begin{align} u_1 = \sum_{i=1}^{n} c_iv_i \\ u_1 - \sum_{i=1}^{n} c_iv_i = 0 \end{align}
• Therefore $1 \cdot u_1 - c_1v_1 - c_2v_2 - ... - c_nv_n = 0$ which implies that the set of vectors $\{ u_1, v_1, v_2, ..., v_n \}$ is linearly DEPENDENT since not all coefficients of these vectors need to be zero to make their sum equal to zero. Since $u_1$ is not equal to the zero vector, then by the Linear Dependence Lemma we have that some vector in the set $\{ v_1, v_2, ..., v_n \}$ is a linear combination of $u_1$. Without loss of generality, assume that $v_1$ is the vector that is a linear combination of $u_1$, and so $V = \mathrm{span} \{ u_1, v_1, v_2, ..., v_m \} = \mathrm{span} \{ u_1, v_2, v_3, ..., v_m \}$.
 Note: We can assume $v_1$ is the vector that is a linear combination of $u_1$. If it wasn't, we could just relabel the indices since the order of the set of vectors $\{ v_1, v_2, ..., v_m \}$ does not matter.
• Now we repeat the same process. Since $V = \mathrm{span} \{ u_1, v_2, v_3, ..., v_m \}$, if the nonzero vector $u_2 \in V$ then $u_2$ can be written as a linear combination of this set of vectors, namely:
(2)
\begin{align} u_2 = d_1u_1 + d_2v_2 + ... + d_nv_n \\ u_2 - [d_1u_1 + d_2v_2 + ... + d_nv_n] = 0 \end{align}
• Once again we have that $u_2 \neq 0$, and so by the linear dependence lemma we have that some vector in the set $\{u_1, v_2, v_3, ..., v_m \}$ is a linear combination of $u_2$. We know that $u_2$ cannot be a linear combination of $u_1$ since the set $\{ u_1, u_2, ..., u_m \}$ was given to be a linearly independence set of vectors. Without loss of generality again, assume that $v_2$ is the vector that is a linear combination of $u_2$. Therefore $V = \mathrm{span} \{ u_1, u_2, v_2, ... v_m \} = \mathrm{span} \{u_1, u_2, v_3, ..., v_m \}$.
• We now repeat this process over and over again under we have that $V = \mathrm{span} \{ u_1, u_2, ..., u_m, v_{m+1}, ..., v_n \}$. We note that there will be no point at which we run out of $v$'s entirely. If so, then we would have a contradiction, because the set of vectors $\{ v_1, v_2, ..., v_n \}$ would not be a spanning set for $V$. Therefore we have that $m ≤ n$, that is the size of any linearly independent set of vectors is less than or equal to the size of any spanning set of vectors of a vector space. $\blacksquare$