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 is a linearly dependent list in . Then there exists such that

Furthermore, if satisfies the condition above and the -th term is removed from , then the span of the remaining list equals .

Proof. Because the list is linearly dependent, there exist numbers , not all , such that

Let be the largest of such that . Then, we can write as

which proves as desired.

Now suppose is any element of such that . That means we have such that

Suppose . Then there exist such that

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

which shows that is in the span of the list obtained from removing the th term from . Thus, removing the th term of the list does not change the span of the list.

If in the linear dependence lemma, then means , because .

Example: Smallest in linear dependence lemma

Consider the list

in . This list of four is linearly dependent. Thus, the linear dependence lemma implies that there exists such that the vector in this list is a linear combination of the previous vectors in the list. How do we find the smallest value of that works?

Taking in the linear dependence lemma works if and only if the first vector in the list equals . Because is not the vector, we cannot take for this list.

Taking 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 such that .

Taking 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 such that

which is a system of three linear equations with two unknowns . Solving gives us . Thus, taking is the smallest value of that works in the linear dependence lemma.

Length of linearly independent list  Length of spanning list

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

Length of linearly independent list 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 is linearly independent in . Suppose also that spans . We need to prove that . This is done through the process described below with steps; in each step, we add one of the ‘s and remove one of the ‘s.

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

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 because the list is linearly independent. Obviously, is not in the span of the previous vectors in the list above; it is the first element, and is not in , which is the span of the empty list. Hence, the linearly dependence lemma implies we can remove one of the ‘s so that the new list (of length ) consisting of and the remaining ‘s spans .

Step for : The list (of length ) from step spans . In particular, is in the span of the list . Thus, the list of length obtained by adjoining to , placing it just after 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 is linearly independent, this vector cannot be one of the ‘s.

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

After step , we have added all the ‘s and the process stops. At each step we add a to , the linear dependence lemma implies that there is some to remove. Thus, there are at least as many ‘s as ‘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

The list , which has length , spans . Thus, no list of length larger than is linearly independent in .

For example, which is a list of length , is not linearly independent in .

Example: No list of length 3 spans

The list , which has length , is linearly independent in . Thus, no list of length less than four spans .

For example, , which has length , does not span .