Linear Dependence Lemma

We will now look at a very important lemma known as the linear dependence lemma.

Lemma (Linear Dependence Lemma): Let $\{ v_1, v_2, ..., v_m \}$ be a set of linearly dependent vectors in the vector space $V$ and $v_1 \neq 0$. Then there exists $j \in \{ 2, 3, ..., m \}$ such that: a) $v_j \in \mathrm{span} \{ v_1, ..., v_{j-1} \}$. b) $\mathrm{span} \{ v_1, ..., v_{j-1}, v_{j+1}, ..., v_m \} = \mathrm{span} \{ v_1, ..., v_m \}$.

The linear dependence lemma tells us that given a linear dependent set of vectors where the first vector is nonzero, then there exists a vector in the set $\{ v_1, v_2, ..., v_m \}$ such that $v_j$ can be written as a linear combination of $\{ v_1, v_2, ..., v_{j-1}$ (that is $v_j \in \mathrm{span} \{ v_1, v_2, ..., v_{j-1} \}$), and that the set of linear combinations of the set of vectors $\{ v_1, ..., v_{j-1}, v_{j+1}, ..., v_m \}$ is the same set as the combination of the set of vectors $\{ v_1, v_2, ..., v_m \}$.

• Proof: Let $\{ v_1, v_2, ..., v_m \}$ be a set of vectors that are linearly dependent where $v_1 \neq 0$, and let $a_1, a_2, ..., a_m \in \mathbb{F}$. Since this set of vectors is not linearly independent, then:

(1)

\begin{equation} a_1v_1 + a_2v_2 + ... + a_mv_m = 0 \end{equation}

• Where not all $a_i$ are zero (otherwise the set of vectors would be linearly independent). Now since $v_1 \neq 0$, it follows that not all $a_2, a_3, ..., a_m \in \mathbb{F}$ are equal to zero, and so there exists an $a_j \in \mathbb{F}$ such that $a_j \neq 0$ where $j$ is the largest index such that $a_j \neq 0$, in other words, $a_{j+1} = 0$, $a_{j+2} = 0$, etc…, and so so:

(2)

\begin{align} \quad a_jv_j = -a_1v_1 - a_2v_2 - ... - a_{j-1}v_{j-1} - \underbrace{a_{j+1}v_{j+1}}_{=0} + ... + \underbrace{a_{m}v_{m}}_{=0} \\ \quad a_jv_j = -a_1v_1 - a_2v_2 - ... - a_{j-1}v_{j-1} \\ \quad v_j = -\frac{a_1}{a_j}v_1 -\frac{a_2}{a_j}v_2 - ... - \frac{a_{j-1}}{a_j}v_{j-1} \end{align}

• Therefore $v_j$ can be written as a linear combination of the set of vectors $\{ v_1, v_2, ..., v_{j-1} \}$ so $v_j \in \mathrm{span} \{ v_1, v_2, ..., v_{j-1} \}$ which proves A.

• Now let $u \in \mathrm{span} \{ v_1, v_2, ..., v_m \}$, and so $u$ can be written as a linear combination of the vectors in this set, and so there exists $b_1, b_2, ..., b_m \in \mathbb{F}$ such that:

(3)

\begin{equation} u = b_1v_1 + b_2v_2 + ... + b_mv_m \end{equation}

• Now we substitute that $\quad v_j = -\frac{a_1}{a_j}v_1 -\frac{a_2}{a_j}v_2 - ... - \frac{a_{j-1}}{a_j}v_{j-1}$ and so:

(4)

\begin{align} \quad u = b_1v_1 + b_2v_2 + ... + b_{j-1}v_{j-1} + b_jv_j + b_{j+1}v_{j+1} + ... + b_mv_m \\ \quad u = b_1v_1 + b_2v_2 + ... + b_{j-1}v_{j-1} + b_j[-\frac{a_1}{a_j}v_1 -\frac{a_2}{a_j}v_2 - ... - \frac{a_{j-1}}{a_j}v_{j-1}] + b_{j+1}v_{j+1} + ... + b_mv_m \\ \quad u = (b_1 - a_1b_j)v_1 + (b_2 - a_2b_j)v_2 + ... + (b_{j-1} - a_{j-1}b_j)v_{j-1} + (b_{j+1} - a_{j+1}b_j)v_{j+1} + ... + (b_m - a_mb_j)v_m \end{align}

• Therefore $u$ can be written as a linear combination of the vectors $\{ v_1, ..., v_{j-1}, v_{j+1}, ..., v_m$ and so $u \in \mathrm{span} \{ v_1, ..., v_{j-1}, v_{j+1}, ..., v_m \}$. Therefore $\mathrm{span} \{ v_1, v_2, ..., v_m \} = \mathrm{span} \{ v_1, ..., v_{j-1}, v_{j+1}, ..., v_m \}$. $\blacksquare$