Linear Dependence Lemma

The linear dependence lemma is a useful tool. It states that given a linearly dependent list of vectors, one of the vectors is in the span of the previous ones. Furthermore, we can throw out that vector without changing the span of the original list.

Linear Dependence Lemma

Suppose $v_1,\dots ,v_m$ is a linearly dependent list in $V$. Then there exists $k\in (1,2,\dots ,m)$ such that

$$v_k\in \text{span}(v_1,\dots ,v_{k-1})$$

Furthermore, if $k$ satisfies the condition above and the $k$-th term is removed from $v_1,\dots ,v_m$, then the span of the remaining list equals $\text{span}(v_1,\dots ,v_m)$.

Proof. Because the list $v_1,\dots ,v_m$ is linearly dependent, there exist numbers $a_1,\dots ,a_m$, not all $0$, such that

$$a_1{v}_1+\cdots +a_m{v}_m=0$$

Let $k$ be the largest of $\{1,\dots ,m\}$ such that $a_k\ne 0$. Then, we can write $v_k$ as

$$v_k=-\frac{a_1}{a_k}{v}_1-\cdots -\frac{a_{k-1}}{a_k}{v}_{k-1}$$

which proves $v_k\in \text{span}(v_1,\dots v_{k-1})$ as desired.

Now suppose $k$ is any element of $\{1,\dots ,m\}$ such that $v_k\in \text{span}(v_1,\dots ,v_{k-1})$. That means we have $b_1,\dots ,b_{k-1}\in \mathbb{F}$ such that

$$v_k=b_1{v}_1+\cdots +b_{k-1}{v}_{k-1}$$

Suppose $u\in \text{span}(v_1,\dots v_m)$. Then there exist $c_1,\dots ,c_m\in \mathbb{F}$ such that

$$u=c_1{v}_1+\cdots +c_k{v}_k+\cdots +c_m{v}_m$$

In the equation above, we can replace $v_k$ with the right side of the our expression above for $v_k$:

$$u=c_1{v}_1+\cdots +c_1(b_1{v}_1+\cdots +b_{k-1}{v}_{k-1})+\cdots +c_m{v}_m$$

which shows that $u$ is in the span of the list obtained from removing the $k$th term from $v_1,\dots ,v_m$. Thus, removing the $k$th term of the list $v_1,\dots ,v_m$ does not change the span of the list.

If $k=1$ in the linear dependence lemma, then $v_k\in \text{span}(v_1,\dots ,v_{k-1})$ means $v_1=0$, because $\text{span}()=\{0\}$.

Example: Smallest $k$ in linear dependence lemma

Consider the list

$$(1,2,3),(6,5,4),(15,16,17),(8,9,7)$$

in ${\mathbb{R}}^3$. This list of four is linearly dependent. Thus, the linear dependence lemma implies that there exists $k\in \{1,2,3,4\}$ such that the $k^{\text{th}}$ vector in this list is a linear combination of the previous vectors in the list. How do we find the smallest value of $k$ that works?

Taking $k=1$ in the linear dependence lemma works if and only if the first vector in the list equals $0$. Because $(1,2,3)$ is not the $0$ vector, we cannot take $k=1$ for this list.

Taking $k=2$ in the linear dependence lemma works if and only if the second vector in the list is a scalar multiple of the first vector. In our example, there does not exist $c\in \mathbb{R}$ such that $(6,5,4)=c(1,2,3)$.

Taking $k=3$ in the linear dependence lemma works if and only if the third vector in the list is a linear combination of the first two vectors. Thus, we want to know whether there is $a,b\in \mathbb{R}$ such that

$$(15,16,17)=a(1,2,3)+b(6,5,4)$$

which is a system of three linear equations with two unknowns $a,b$. Solving gives us $a=3,b=2$. Thus, taking $k=3$ is the smallest value of $k$ that works in the linear dependence lemma. A key result states that no linearly independent list in $V$ is longer than a spanning list in $V$.

Length of linearly independent list $\le$ Length of spanning list

Now we come to a key result. It says that no linearly independent list in $V$ is longer than a spanning list in $V$.

Length of linearly independent list $\le$ Length of spanning list

In a finite-dimensional vector space, the length of every linearly independent list of vectors is less than or equal to the length of every spanning list of vectors.

Proof. Suppose that $u_1,\dots ,u_m$ is linearly independent in $V$. Suppose also that $w_1,\dots ,w_n$ spans $V$. We need to prove that $m\le n$. This is done through the process described below with $m$ steps; in each step, we add one of the $u$‘s and remove one of the $w$‘s.

Step 1: Let $B$ be the list $w_1,\dots ,w_n$, which spans $V$. Adjoining $u_1$ at the beginning of the list produces a linearly dependent list; this is because $w_1,\dots ,w_n$ is a spanning list, so $u_1$ can be written as a combination of $w_1,\dots ,w_n$. In other words, the list

$$u_1,w_1,\dots ,w_n$$

is linearly dependent.

Thus, by the linear dependence lemma, one of the vectors in the list above is a linear combination of the previous vectors in the list. We know that $u_1\ne 0$ because the list $u_1,\dots ,u_m$ is linearly independent. Obviously, $u_1$ is not in the span of the previous vectors in the list above; it is the first element, and $u_1$ is not in $\{0\}$, which is the span of the empty list. Hence, the linearly dependence lemma implies we can remove one of the $w$‘s so that the new list $B$ (of length $n$) consisting of $u_1$ and the remaining $w$‘s spans $V$.

Step $k$ for $k=2,\dots ,m$: The list $B$ (of length $n$) from step $k-1$ spans $V$. In particular, $u_k$ is in the span of the list $B$. Thus, the list of length $n+1$ obtained by adjoining $u_k$ to $B$, placing it just after $u_1,\dots ,u_{k-1}$ is linearly dependent. By the linear dependence lemma, one of the vectors in the list is in the span of the previous ones, and because $u_1,\dots u_k$ is linearly independent, this vector cannot be one of the $u$‘s.

Hence, there must still be at least one remaining $w$ at this step. We can remove from our list (after adjoining $u_k$ in the proper place) a $w$ that is a linear combination of the previous vectors in the list, so that the new list $B$ (of length $n$) consisting of $u_1,\dots ,u_k$ and the remaining $w$‘s spans $V$.

After step $m$, we have added all the $u$‘s and the process stops. At each step we add a $u$ to $B$, the linear dependence lemma implies that there is some $w$ to remove. Thus, there are at least as many $w$‘s as $u$‘s.

Examples

The next two examples show how the result above can be used to show, without any computations, that certain lists are not linearly independent and that certain lists do not span a given vector space.

Example: No list of length 4 is linearly independent in ${\mathbb{R}}^3$

The list $(1,0,0),(0,1,0),(0,0,1)$, which has length $3$, spans ${\mathbb{R}}^3$. Thus, no list of length larger than $3$ is linearly independent in ${\mathbb{R}}^3$.

For example, $(1,2,3),(4,5,8),(9,6,7),(-3,2,8)$ which is a list of length $4$, is not linearly independent in ${\mathbb{R}}^3$.

Example: No list of length 3 spans ${\mathbb{R}}^4$

The list $(1,0,0,0),(0,1,0,0),(0,0,1,0),(0,0,0,1)$, which has length $4$, is linearly independent in ${\mathbb{R}}^4$. Thus, no list of length less than four spans ${\mathbb{R}}^4$.

For example, $(1,2,3,-5),(4,5,8,3),(9,6,7,-1)$, which has length $3$, does not span ${\mathbb{R}}^4$.