1.4 Linear Independence

A spanning list tells us that every vector of a space can be built. It says nothing about waste. The list $((1, 0), (0, 1), (1, 1))$ spans $\mathbb{R}^2$ , but its third vector adds nothing that the first two did not already reach. To measure a space by the length of a list, we need lists with no such waste. This section makes “no vector is wasted” precise, proves the lemma that finds a wasted vector whenever there is one, and shows that lists without waste give every vector in their span a unique description.

1.4.1. Redundant vectors

The previous section gave a way to shorten a list: if a vector lies in the span of the others, we may delete it without changing the span (Theorem 1.3.5). Call such a vector redundant. We want a test for “this list has no redundant vector”.

A first guess is that a vector is wasted when it repeats the direction of another one, so the test would be “no vector is a scalar multiple of another”. This guess fails. In $\mathbb{R}^3$ , take $\mathbf{u} = (1, 0, 1), \qquad \mathbf{v} = (0, 1, 1), \qquad \mathbf{w} = (1, 1, 2).$ No one of them is a multiple of another: a multiple of $\mathbf{u}$ has second entry $0$ , a multiple of $\mathbf{v}$ has first entry $0$ , a multiple $(c, c, 2c)$ of $\mathbf{w}$ has equal first and second entries, and in each case neither of the other two vectors has that shape. Yet $\mathbf{w} = \mathbf{u} + \mathbf{v}$ . All three lie in the plane $z = x + y$ , and by Theorem 1.3.5, $\operatorname{span}(\mathbf{u}, \mathbf{v}, \mathbf{w}) = \operatorname{span}(\mathbf{u}, \mathbf{v})$ . The vector $\mathbf{w}$ is redundant even though it is not parallel to anything.

A second guess is correct but clumsy: “no vector is a linear combination of the others”. For a list of length $k$ this is $k$ separate conditions, one for each vector. Here is a way to fold them into one. Move everything in $\mathbf{w} = \mathbf{u} + \mathbf{v}$ to one side: $1\mathbf{u} + 1\mathbf{v} + (-1)\mathbf{w} = \mathbf{0} .$ This is a way to build $\mathbf{0}$ from the list with coefficients that are not all zero. Conversely, suppose $a\mathbf{u} + b\mathbf{v} + c\mathbf{w} = \mathbf{0}$ with, say, $c \neq 0$ . Then $\mathbf{w} = -\tfrac{a}{c}\mathbf{u} - \tfrac{b}{c}\mathbf{v}$ , so $\mathbf{w}$ is redundant. The same works whichever coefficient is non-zero. So a redundant vector exists exactly when $\mathbf{0}$ can be built in a non-trivial way. Building $\mathbf{0}$ trivially, with every coefficient $0$ , is always possible, so the condition we want is that this is the only way.

A list is independent when the only way to build the zero vector from it is the trivial way.

1.4.2. Definition and examples

Definition 1.4.1 (Linear Independence)

Let $V$ be a vector space over $F$ and let $(\mathbf{v}_1, \dots, \mathbf{v}_k)$ be a list of vectors in $V$ , where $k \ge 0$ . The list is linearly independent (over $F$ ) if, for all $a_1, \dots, a_k \in F$ , $a_1\mathbf{v}_1 + a_2\mathbf{v}_2 + \dots + a_k\mathbf{v}_k = \mathbf{0} \quad \Longrightarrow \quad a_1 = a_2 = \dots = a_k = 0 .$ The list is linearly dependent if it is not linearly independent: that is, if there exist $a_1, \dots, a_k \in F$ , not all zero, with $a_1\mathbf{v}_1 + \dots + a_k\mathbf{v}_k = \mathbf{0}$ . Such an equation is a linear relation among the vectors. The empty list is linearly independent.

In words: the hypothesis is an arbitrary linear combination that happens to equal $\mathbf{0}$ . The conclusion says that every coefficient in it is $0$ . Dependence is the negation, obtained by the rules of Definition 0.1.4: “for all $a$ , (combination $= \mathbf{0}$ $\Rightarrow$ all $a_i = 0$ )” becomes “there exist $a$ with combination $= \mathbf{0}$ and not all $a_i = 0$ ”. This is exactly the negation worked out in Example (Negating “only the zero combination”). The empty list is independent because the condition is vacuous: there are no coefficients, so “all of them are $0$ ” holds automatically.

The definition also dictates how every independence proof starts. It is a “for all” statement about coefficients, so we take arbitrary coefficients and assume the hypothesis:

Let $a_1\mathbf{v}_1 + \dots + a_k\mathbf{v}_k = \mathbf{0}$ . Then … hence all $a_i = 0$ .

Between “Let” and “hence”, the work is to turn one vector equation into scalar equations. How we do that depends on what $\mathbf{0}$ means in the space: in $F^n$ we compare entries, in $F[x]$ we compare coefficients, in a function space we evaluate at points, and in $M_{m \times n}(F)$ we compare entries.

Example (Independent Lists in Four Families)

Show that each list is linearly independent.

(a) $(\mathbf{e}_1, \dots, \mathbf{e}_n)$ in $F^n$ .
(b) $(1, x, x^2)$ in $F[x]$ .
(c) $((1, 1), (1, -1))$ in $\mathbb{R}^2$ .
(d) $(\sin, \cos)$ in the space $\mathbb{R}^\mathbb{R}$ of all functions $\mathbb{R} \to \mathbb{R}$ .

Solution.

(a) Let $a_1\mathbf{e}_1 + \dots + a_n\mathbf{e}_n = \mathbf{0}$ . The left side is the vector $(a_1, \dots, a_n)$ , and $\mathbf{0} = (0, \dots, 0)$ . Comparing entries, $a_1 = \dots = a_n = 0$ . Hence the list is independent.
(b) Let $a + bx + cx^2 = 0$ , where $0$ is the zero polynomial, the polynomial with every coefficient $0$ . Two polynomials are equal exactly when all their coefficients agree (Definition 0.8.1). Comparing the coefficients of $1, x, x^2$ gives $a = b = c = 0$ . Hence the list is independent.
(c) Let $a(1, 1) + b(1, -1) = (0, 0)$ . Comparing entries, $a + b = 0$ and $a - b = 0$ . Adding the two equations gives $2a = 0$ , so $a = 0$ since $2 \neq 0$ in $\mathbb{R}$ ; then $b = -a = 0$ . Hence the list is independent.
(d) Let $a\sin + b\cos = 0$ , where $0$ is the zero function. Equality of functions means equality at every point (Definition 0.4.1), so $a\sin t + b\cos t = 0$ for every $t \in \mathbb{R}$ . We may choose convenient points. At $t = 0$ : $a \cdot 0 + b \cdot 1 = 0$ , so $b = 0$ . At $t = \pi/2$ : $a \cdot 1 + b \cdot 0 = 0$ , so $a = 0$ . Hence the list is independent.

In (d) we did not need the equation at every point, only at two well-chosen ones. That is the general move for functions: choose good points, where most terms vanish. Note the logic. Evaluating at a point can only prove independence; if the equations at our chosen points had allowed non-zero solutions, we would have learned nothing, and would have to try other points or another method.

The degenerate cases are worth settling once, because they come up inside every later argument.

Example (Degenerate Lists)

Let $V$ be a vector space over $F$ . Decide whether each list is independent.

(a) A list $(\mathbf{v}_1, \dots, \mathbf{v}_k)$ with some $\mathbf{v}_j = \mathbf{0}$ .
(b) A list $(\mathbf{v})$ of length one.
(c) A list $(\mathbf{v}_1, \dots, \mathbf{v}_k)$ with a repeat: $\mathbf{v}_i = \mathbf{v}_j$ for some $i \neq j$ .

Solution.

(a) Dependent. Take $a_j = 1$ and every other coefficient $0$ . By Theorem 1.1.5 and Theorem 1.1.6, every term is $\mathbf{0}$ , so the combination is $\mathbf{0}$ , and the coefficient $a_j = 1$ is not zero.
(b) Independent if and only if $\mathbf{v} \neq \mathbf{0}$ . If $\mathbf{v} = \mathbf{0}$ , use (a). If $\mathbf{v} \neq \mathbf{0}$ , let $a\mathbf{v} = \mathbf{0}$ ; by Theorem 1.1.9, $a = 0$ or $\mathbf{v} = \mathbf{0}$ , and the second is false, so $a = 0$ .
(c) Dependent. Take $a_i = 1$ , $a_j = -1$ , and every other coefficient $0$ . The combination is $\mathbf{v}_i + (-1)\mathbf{v}_j = \mathbf{v}_i - \mathbf{v}_j = \mathbf{0}$ by Theorem 1.1.7, since $\mathbf{v}_i = \mathbf{v}_j$ , and $a_i = 1 \neq 0$ .

Now the non-example, by a minimal change. Add one vector to the independent list $((1, 0), (0, 1))$ of Example (Independent Lists in Four Families) (a), to get $((1, 0), (0, 1), (1, 1))$ . Each vector is still non-zero, and any two of the three still form an independent list. But $1(1, 0) + 1(0, 1) + (-1)(1, 1) = (0, 0)$ with coefficients not all zero, so the clause “ $\Longrightarrow a_1 = \dots = a_k = 0$ ” fails, and the list is dependent. The polynomial version behaves the same way: $(1, x)$ is independent, but $(1, x, 1 + x)$ is dependent, because $1 \cdot 1 + 1 \cdot x + (-1)(1 + x) = 0$ .

Quick check. Is the list $((1, 2, 0), (0, 1, 1), (1, 0, -2))$ in $\mathbb{R}^3$ linearly independent?

Solution. No. Let $a(1, 2, 0) + b(0, 1, 1) + c(1, 0, -2) = \mathbf{0}$ . Comparing entries: $a + c = 0$ , $2a + b = 0$ , $b - 2c = 0$ . The first two give $c = -a$ and $b = -2a$ , and then the third reads $-2a + 2a = 0$ , which holds for every $a$ . Taking $a = 1$ gives the relation $(1, 2, 0) - 2(0, 1, 1) - (1, 0, -2) = \mathbf{0}$ , with coefficients not all zero.

Two more kinds of question come up constantly: lists that depend on a parameter, and lists of matrices. The method does not change.

Example (A Parameter and a List of Matrices)

(a) For which $k \in \mathbb{R}$ is the list $((1, 1, 0), (1, 0, 1), (0, 1, k))$ in $\mathbb{R}^3$ linearly independent?
(b) Is the list $\left( \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix} \right)$ in $M_2(\mathbb{R})$ linearly independent?

Solution.

(a) Let $a(1, 1, 0) + b(1, 0, 1) + c(0, 1, k) = \mathbf{0}$ . Comparing entries gives $a + b = 0$ , $a + c = 0$ and $b + kc = 0$ . The first two give $b = -a$ and $c = -a$ ; substituting into the third, $-a - ka = -(1 + k)a = 0$ .

If $k \neq -1$ , then $1 + k \neq 0$ , so $a = 0$ by Theorem 0.7.1, and then $b = c = 0$ . The list is independent.

If $k = -1$ , the equations hold for every $a$ ; taking $a = 1$ gives $(1, 1, 0) - (1, 0, 1) - (0, 1, -1) = \mathbf{0}$ with coefficients not all zero. The list is dependent.

So the list is independent exactly when $k \neq -1$ . Notice the shape of the argument: the parameter ends up as a factor multiplying one unknown, and the only question is when that factor can be zero.
(b) Let $a\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} + b\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} + c\begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix}$ . The left side is $\begin{pmatrix} a & b + c \\ b & a \end{pmatrix}$ . Two matrices are equal when their entries agree (Definition 0.9.1), so $a = 0$ , $b + c = 0$ and $b = 0$ ; hence $c = 0$ too. The list is independent.

For matrices, “compare entries” turns one matrix equation into four scalar equations, one per entry.

1.4.3. Why lists, and why this definition

Remark. Why lists, not sets. In a set, repeats disappear: $\{ \mathbf{v}, \mathbf{v} \} = \{ \mathbf{v} \}$ . If independence were defined for sets, the “list” $(\mathbf{v}, \mathbf{v})$ , which has the obvious relation $\mathbf{v} - \mathbf{v} = \mathbf{0}$ , would silently become the independent set $\{ \mathbf{v} \}$ when $\mathbf{v} \neq \mathbf{0}$ . The repeat can also be hidden: $x + 1$ and $1 + x$ look different on the page but are the same vector. A list keeps both entries and so records the dependence. The second reason is order. Coordinates with respect to a basis (next section) are read off in order, so $(\mathbf{e}_1, \mathbf{e}_2)$ and $(\mathbf{e}_2, \mathbf{e}_1)$ must be different objects. The Linear Dependence Lemma below also refers to “the vectors before $\mathbf{v}_j$ ”, which needs an order. Reordering a list does not change whether it is independent, since a relation can be rearranged term by term.

For an arbitrary subset $S \subseteq V$ , finite or infinite, we say $S$ is linearly independent if every finite list of distinct vectors of $S$ is linearly independent. The word “distinct” is essential: without it, the list $(\mathbf{s}, \mathbf{s})$ would make every non-empty set dependent. For a finite set $S = \{ \mathbf{v}_1, \dots, \mathbf{v}_k \}$ with the $\mathbf{v}_i$ distinct, this agrees with independence of the list $(\mathbf{v}_1, \dots, \mathbf{v}_k)$ : every list of distinct vectors of $S$ is a reordered sub-list, and a sub-list of an independent list is independent (Exercise (B3: Sub-Lists)). Together with “ $S$ spans $V$ ” from the previous section, this is the language section 8 of this chapter uses for spaces with no finite spanning list.

Why “all $a_i = 0$ ”, and why is the empty list independent? Suppose we only asked that some $a_i$ be $0$ . The list $((1, 0), (0, 1), (0, 2))$ has the redundant vector $(0, 2) = 2(0, 1)$ . But in any relation $a(1, 0) + b(0, 1) + c(0, 2) = \mathbf{0}$ , comparing first entries forces $a = 0$ , so every relation has a zero coefficient, and the list would pass the weaker test. Only “all $a_i = 0$ ” rules out every non-trivial relation. The empty list is independent because it wastes nothing, and this convention makes the empty list a basis of the zero space in the next section, just as $\operatorname{span}() = \{ \mathbf{0} \}$ makes it a spanning list.

Warning. “Not all zero” is not “all non-zero”. A dependence relation needs one non-zero coefficient, not every coefficient non-zero. The list $((1, 0), (0, 1), (0, 2))$ is dependent, by $0(1, 0) + 2(0, 1) - (0, 2) = \mathbf{0}$ . But no relation has all three coefficients non-zero: comparing first entries in $a(1, 0) + b(0, 1) + c(0, 2) = \mathbf{0}$ forces $a = 0$ . Hunting for a relation with no zero coefficient would wrongly conclude that the list is independent.

Warning. Pairwise independence is not independence. Checking pairs is not enough. In the list $((1, 0, 1), (0, 1, 1), (1, 1, 2))$ from the start of the section, every two of the three vectors form an independent list, but the three together are dependent, since $(1, 0, 1) + (0, 1, 1) - (1, 1, 2) = \mathbf{0}$ . For three or more vectors, independence is a condition on all of them at once.

1.4.4. The Linear Dependence Lemma

The definition says that a dependent list has a relation. It does not say which vector is redundant, and the discussion at the start of the section only found a redundant vector where the coefficient was non-zero. The next lemma makes a definite choice, and chooses it so that the redundant vector depends only on vectors before it in the list. This one-directional form is what later proofs need, because they build lists from left to right.

Theorem 1.4.1 (Linear Dependence Lemma)

Let $V$ be a vector space over $F$ , and let $(\mathbf{v}_1, \dots, \mathbf{v}_k)$ be a linearly dependent list in $V$ . Then:

(1) there is an index $j \in \{ 1, \dots, k \}$ with $\mathbf{v}_j \in \operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_{j-1})$ . For $j = 1$ this means $\mathbf{v}_1 = \mathbf{0}$ , so if $\mathbf{v}_1 \neq \mathbf{0}$ , then $j \ge 2$ ;
(2) for any such $j$ , removing $\mathbf{v}_j$ does not change the span: $\operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_{j-1}, \mathbf{v}_{j+1}, \dots, \mathbf{v}_k) = \operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_k).$

Idea. Take a relation with coefficients not all zero. We want to solve for one vector in terms of the vectors before it, so we need a vector whose coefficient is non-zero and which comes after every other vector with a non-zero coefficient. That is the largest index $j$ with $a_j \neq 0$ . Everything after it has coefficient zero and drops out, and we divide by $a_j$ . Part (2) is then Theorem 1.3.5 read backwards.

Proof.

Since the list is dependent, there are $a_1, \dots, a_k \in F$ , not all zero, with $a_1\mathbf{v}_1 + \dots + a_k\mathbf{v}_k = \mathbf{0}$ . The set $\{ i : a_i \neq 0 \}$ is non-empty and finite, so it has a largest element; call it $j$ . Then $a_j \neq 0$ , and $a_i = 0$ for every $i > j$ . By Theorem 1.1.5 the terms with $i > j$ are $\mathbf{0}$ , so $a_1\mathbf{v}_1 + \dots + a_{j-1}\mathbf{v}_{j-1} + a_j\mathbf{v}_j = \mathbf{0} .$ Adding the negative of $a_1\mathbf{v}_1 + \dots + a_{j-1}\mathbf{v}_{j-1}$ to both sides gives $a_j\mathbf{v}_j = -(a_1\mathbf{v}_1 + \dots + a_{j-1}\mathbf{v}_{j-1})$ . Since $a_j \neq 0$ and $F$ is a field, $a_j$ has an inverse $a_j^{-1} \in F$ (Definition 0.7.1). Multiplying both sides by $a_j^{-1}$ , and using $a_j^{-1}(a_j\mathbf{v}_j) = (a_j^{-1}a_j)\mathbf{v}_j = 1\mathbf{v}_j = \mathbf{v}_j$ on the left, and $-\mathbf{x} = (-1)\mathbf{x}$ (Theorem 1.1.7) with the distributive laws on the right, we get $\mathbf{v}_j = (-a_j^{-1}a_1)\mathbf{v}_1 + \dots + (-a_j^{-1}a_{j-1})\mathbf{v}_{j-1} .$ Hence $\mathbf{v}_j \in \operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_{j-1})$ . When $j = 1$ the right side is the empty sum, so $\mathbf{v}_1 = \mathbf{0}$ ; therefore if $\mathbf{v}_1 \neq \mathbf{0}$ , then $j \ge 2$ .
Let $j$ be any index with $\mathbf{v}_j \in \operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_{j-1})$ , and let $L = (\mathbf{v}_1, \dots, \mathbf{v}_{j-1}, \mathbf{v}_{j+1}, \dots, \mathbf{v}_k)$ . Each of $\mathbf{v}_1, \dots, \mathbf{v}_{j-1}$ is an entry of $L$ , so by monotonicity (Proposition 1.3.4 (2)) $\operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_{j-1}) \subseteq \operatorname{span}(L)$ , and hence $\mathbf{v}_j \in \operatorname{span}(L)$ . By Theorem 1.3.5, inserting $\mathbf{v}_j$ back into $L$ at position $j$ does not change the span. That is, $\operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_k) = \operatorname{span}(L)$ , as claimed.

The index $j$ need not be unique, and the lemma does not say that every vector depends on earlier ones. A small example shows both.

Example (The Lemma on a Concrete List)

In $\mathbb{R}^2$ , let $\mathbf{v}_1 = (1, 1)$ , $\mathbf{v}_2 = (1, -1)$ , $\mathbf{v}_3 = (2, 0)$ , $\mathbf{v}_4 = (0, 1)$ . Find two different linear relations, and the index $j$ that the proof of Theorem 1.4.1 extracts from each. Which indices $j$ satisfy $\mathbf{v}_j \in \operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_{j-1})$ ?

Solution. First relation: $\mathbf{v}_1 + \mathbf{v}_2 - \mathbf{v}_3 = (1 + 1 - 2, 1 - 1 - 0) = (0, 0)$ . The largest index with a non-zero coefficient is $j = 3$ , and solving gives $\mathbf{v}_3 = \mathbf{v}_1 + \mathbf{v}_2 \in \operatorname{span}(\mathbf{v}_1, \mathbf{v}_2)$ .

Second relation: $\mathbf{v}_1 - \mathbf{v}_2 - 2\mathbf{v}_4 = (1 - 1 - 0, 1 + 1 - 2) = (0, 0)$ . Here the largest index is $j = 4$ , and $\mathbf{v}_4 = \tfrac12 \mathbf{v}_1 - \tfrac12 \mathbf{v}_2 \in \operatorname{span}(\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3)$ .

So $j = 3$ and $j = 4$ both qualify, and by part (2) of the lemma either $\mathbf{v}_3$ or $\mathbf{v}_4$ can be removed without changing the span. On the other hand, $j = 2$ does not qualify: $\mathbf{v}_2 = (1, -1)$ is not a multiple of $\mathbf{v}_1 = (1, 1)$ , because a multiple $(c, c)$ has equal entries. And $j = 1$ does not occur since $\mathbf{v}_1 \neq \mathbf{0}$ . Removing $\mathbf{v}_3$ and then (by the lemma applied to $(\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_4)$ , which is still dependent by the second relation) $\mathbf{v}_4$ leaves $(\mathbf{v}_1, \mathbf{v}_2)$ , whose span is $\mathbb{R}^2$ by Example (Spanning Lists).

The lemma only locates vectors that depend on earlier ones. Here $\mathbf{v}_1$ and $\mathbf{v}_2$ could also be removed without changing the span, since $\mathbf{v}_1 = \mathbf{v}_3 - \mathbf{v}_2$ and $\mathbf{v}_2 = \mathbf{v}_3 - \mathbf{v}_1$ , but the lemma never points at them.

Read the other way round, part (1) is a test for independence that works left to right.

Remark. Independence, one vector at a time. A list $(\mathbf{v}_1, \dots, \mathbf{v}_k)$ is linearly independent if and only if no $\mathbf{v}_j$ lies in $\operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_{j-1})$ . The “if” direction is the contrapositive of part (1). For “only if”, suppose $\mathbf{v}_j = c_1\mathbf{v}_1 + \dots + c_{j-1}\mathbf{v}_{j-1}$ . Then $c_1\mathbf{v}_1 + \dots + c_{j-1}\mathbf{v}_{j-1} + (-1)\mathbf{v}_j = \mathbf{0}$ , with zero coefficients on $\mathbf{v}_{j+1}, \dots, \mathbf{v}_k$ , is a relation whose coefficient $-1$ is non-zero. So the list is dependent. In words: a list is independent exactly when each vector reaches something new beyond the vectors before it. For instance $(1, x, x^2)$ passes: $1 \neq 0$ , $x$ is not a constant, and $x^2$ has degree too high to be in $\operatorname{span}(1, x)$ .

Combining the two parts of the lemma gives a clean statement about spans alone: a list is dependent exactly when it contains a vector that can be thrown away for free.

Theorem 1.4.2 (Span Preservation)

Let $V$ be a vector space and $(\mathbf{v}_1, \dots, \mathbf{v}_k)$ a list in $V$ with $k \ge 1$ . Then the list is linearly dependent if and only if there is an index $j$ such that $\operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_{j-1}, \mathbf{v}_{j+1}, \dots, \mathbf{v}_k) = \operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_k).$

Proof. $(\Rightarrow)$ By Theorem 1.4.1 (1) there is an index $j$ with $\mathbf{v}_j \in \operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_{j-1})$ , and by part (2) removing that $\mathbf{v}_j$ does not change the span.

$(\Leftarrow)$ Let $L$ be the list with $\mathbf{v}_j$ removed, and suppose $\operatorname{span}(L) = \operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_k)$ . By Theorem 1.3.1 (2), $\mathbf{v}_j \in \operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_k) = \operatorname{span}(L)$ . So $\mathbf{v}_j = \sum_{i \neq j} c_i\mathbf{v}_i$ for some scalars $c_i$ , and therefore $\sum_{i \neq j} c_i\mathbf{v}_i + (-1)\mathbf{v}_j = \mathbf{0}$ . The coefficient of $\mathbf{v}_j$ is $-1 \neq 0$ , so the list is dependent.

So a spanning list that is dependent can always be shortened and still span. Repeating this until the list becomes independent is the idea behind the next section’s proof that every finite spanning list contains a basis.

1.4.5. Unique representations

Independence was introduced to rule out waste. Its most useful consequence is about uniqueness. If a vector could be built from a list in two different ways, subtracting the two recipes would give a non-trivial way to build $\mathbf{0}$ . So for an independent list, every vector in the span has exactly one recipe.

Theorem 1.4.3 (Independence and Uniqueness of Coefficients)

Let $V$ be a vector space over $F$ and $(\mathbf{v}_1, \dots, \mathbf{v}_k)$ a list in $V$ . The following are equivalent:

(a) $(\mathbf{v}_1, \dots, \mathbf{v}_k)$ is linearly independent;
(b) every $\mathbf{v} \in \operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_k)$ has exactly one representation as a linear combination: if $a_1\mathbf{v}_1 + \dots + a_k\mathbf{v}_k = b_1\mathbf{v}_1 + \dots + b_k\mathbf{v}_k$ , then $a_i = b_i$ for every $i$ .

Proof. (a $\Rightarrow$ b) Suppose the list is independent, and let $a_1\mathbf{v}_1 + \dots + a_k\mathbf{v}_k = b_1\mathbf{v}_1 + \dots + b_k\mathbf{v}_k$ . Subtracting the right side from both sides and using $a\mathbf{v} - b\mathbf{v} = (a - b)\mathbf{v}$ (Theorem 1.1.8 and Definition 1.1.1) gives $(a_1 - b_1)\mathbf{v}_1 + \dots + (a_k - b_k)\mathbf{v}_k = \mathbf{0} .$ By independence, $a_i - b_i = 0$ for every $i$ , that is, $a_i = b_i$ .

(b $\Rightarrow$ a) Suppose (b) holds, and let $a_1\mathbf{v}_1 + \dots + a_k\mathbf{v}_k = \mathbf{0}$ . By Theorem 1.1.5, also $0\mathbf{v}_1 + \dots + 0\mathbf{v}_k = \mathbf{0}$ . These are two representations of $\mathbf{0} \in \operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_k)$ , so by (b), $a_i = 0$ for every $i$ . Hence the list is independent.

Every vector of a span has at least one representation, by definition of the span; independence is what makes it at most one. For a dependent list uniqueness fails: with the list $((1, 0), (0, 1), (1, 1))$ , $(1, 1) = 1(1, 0) + 1(0, 1) + 0(1, 1) = 0(1, 0) + 0(0, 1) + 1(1, 1).$ In the next section, a list that is independent and spans is called a basis. By this theorem every vector then has a unique list of coefficients, its coordinates.

1.4.6. Polynomials of distinct degrees

For polynomials there is a test that needs no equations at all. The list $(x^2 + x, x - 3, 5)$ is independent, and the reason is visible: the degrees are $2$ , $1$ and $0$ , and combining lower-degree polynomials can never produce a higher degree.

Theorem 1.4.4 (Polynomials of Distinct Degrees Are Independent)

Let $F$ be a field and let $p_1, \dots, p_k \in F[x]$ be non-zero polynomials whose degrees are pairwise distinct. Then the list $(p_1, \dots, p_k)$ is linearly independent.

Idea. Put the polynomials in order of increasing degree. If the list were dependent, the Linear Dependence Lemma would give a polynomial lying in the span of the ones before it. Those all have smaller degree, so their span consists of polynomials of smaller degree, and cannot contain it.

Proof. A linear relation among the $p_i$ can be rearranged term by term, so reordering the list does not affect independence. Hence we may assume $\deg p_1 < \deg p_2 < \dots < \deg p_k$ .

Suppose, for a contradiction, that the list is dependent. Since $p_1 \neq 0$ , Theorem 1.4.1 gives an index $j \ge 2$ with $p_j \in \operatorname{span}(p_1, \dots, p_{j-1})$ . Let $n = \deg p_{j-1}$ , a natural number since $p_{j-1} \neq 0$ . For every $i \le j - 1$ we have $\deg p_i \le n$ , so $p_1, \dots, p_{j-1}$ lie in $F[x]_{\le n}$ , which is a subspace of $F[x]$ by Example (Polynomials of Bounded Degree). By Theorem 1.3.1 (3), $\operatorname{span}(p_1, \dots, p_{j-1}) \subseteq F[x]_{\le n}$ . Hence $\deg p_j \le n = \deg p_{j-1}$ , contradicting $\deg p_{j-1} < \deg p_j$ . Therefore the list is linearly independent.

Both hypotheses matter. The zero polynomial must be excluded, because a list containing $0$ is dependent (Example (Degenerate Lists)). And the converse fails: distinct degrees are sufficient, not necessary. The list $(x, x + 1)$ has equal degrees but is independent, since $ax + b(x + 1) = (a + b)x + b = 0$ forces $b = 0$ and then $a = 0$ .

1.4.7. Independence depends on the field

The same set can be a vector space over two fields, and the answer to “independent?” can change with the field, because the field decides which coefficients are allowed.

Warning. Always ask: independent over which field? In $\mathbb{C}^2$ , let $\mathbf{v}_1 = (1, i)$ and $\mathbf{v}_2 = (i, -1)$ . Over $\mathbb{C}$ the list $(\mathbf{v}_1, \mathbf{v}_2)$ is dependent: $i\mathbf{v}_1 = (i, i^2) = (i, -1) = \mathbf{v}_2$ , so $i\mathbf{v}_1 + (-1)\mathbf{v}_2 = \mathbf{0}$ with coefficient $i \neq 0$ . Over $\mathbb{R}$ (the same addition, but only real scalars, as in Exercise (C2: The Span Depends on the Field)) the list is independent: if $a\mathbf{v}_1 + b\mathbf{v}_2 = (a + bi, ai - b) = (0, 0)$ with $a, b \in \mathbb{R}$ , then the first entry $a + bi = 0$ forces $a = b = 0$ , since a complex number is zero only when its real and imaginary parts are. The relation over $\mathbb{C}$ used the coefficient $i$ , which is not available over $\mathbb{R}$ .

A second example of the same phenomenon: $((1, 1), (1, -1))$ is independent in $\mathbb{R}^2$ (Example (Independent Lists in Four Families) (c)), but in $\mathbb{F}_2^2$ , where $-1 = 1$ , it is the list $((1, 1), (1, 1))$ with a repeat, hence dependent. The proof over $\mathbb{R}$ divided by $2$ , which is $0$ in $\mathbb{F}_2$ .

1.4.8. Exercises

A. Check your understanding

Exercise (A1)

(a) Define what it means for a list $(\mathbf{v}_1, \dots, \mathbf{v}_k)$ in a vector space over $F$ to be linearly independent, and what it means for it to be linearly dependent.
(b) Determine whether the following statement is true: “a list of vectors is linearly dependent if and only if one of its vectors is a scalar multiple of another.” Justify your answer.
(c) Is the empty list linearly independent? Is the list $(\mathbf{0})$ ?
(d) Determine whether the following statement is true: “if $(\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3)$ is linearly dependent, then $\mathbf{v}_3 \in \operatorname{span}(\mathbf{v}_1, \mathbf{v}_2)$ .” Justify your answer.
(e) To prove that a list of functions $\mathbb{R} \to \mathbb{R}$ is independent, what does “ $= 0$ ” mean, and what is a standard way to extract scalar equations?

Solution.

(a) It is independent if for all $a_1, \dots, a_k \in F$ , $a_1\mathbf{v}_1 + \dots + a_k\mathbf{v}_k = \mathbf{0}$ implies $a_1 = \dots = a_k = 0$ . It is dependent if there are $a_1, \dots, a_k \in F$ , not all zero, with $a_1\mathbf{v}_1 + \dots + a_k\mathbf{v}_k = \mathbf{0}$ .
(b) False. The list $((1, 0, 1), (0, 1, 1), (1, 1, 2))$ in $\mathbb{R}^3$ is dependent, since the third vector is the sum of the first two, but no vector is a multiple of another. (The “if” direction is true: $\mathbf{v}_i = c\mathbf{v}_j$ with $i \neq j$ gives the relation $\mathbf{v}_i - c\mathbf{v}_j = \mathbf{0}$ with coefficient $1 \neq 0$ .)
(c) The empty list is independent: there are no coefficients, so the condition holds vacuously. The list $(\mathbf{0})$ is dependent: $1 \cdot \mathbf{0} = \mathbf{0}$ with coefficient $1 \neq 0$ (Example (Degenerate Lists)).
(d) False. Take $\mathbf{v}_1 = (1, 0)$ , $\mathbf{v}_2 = (2, 0)$ , $\mathbf{v}_3 = (0, 1)$ in $\mathbb{R}^2$ . The list is dependent, since $2\mathbf{v}_1 - \mathbf{v}_2 = \mathbf{0}$ . But every combination of $\mathbf{v}_1, \mathbf{v}_2$ has second entry $0$ , so $\mathbf{v}_3 \notin \operatorname{span}(\mathbf{v}_1, \mathbf{v}_2)$ . Theorem 1.4.1 only promises some $j$ ; here $j = 2$ .
(e) It means the zero function: the combination takes the value $0$ at every point. Evaluating at well-chosen points turns it into scalar equations for the coefficients.

B. Practice

Exercise (B1: Independent or Not?)

Determine which of the following lists are linearly independent. Justify your answer.

(a) $((1, 0, 2), (0, 1, 1), (1, 1, 3))$ in $\mathbb{R}^3$ .
(b) $((1, 1, 0), (0, 1, 1), (1, 0, 1))$ in $\mathbb{R}^3$ .
(c) $(x^2 + 1, x^2 - 1, x)$ in $\mathbb{R}[x]$ .
(d) $\left( \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix} \right)$ in $M_2(\mathbb{R})$ .
(e) $(f, g)$ in $\mathbb{R}^\mathbb{R}$ , where $f(t) = e^t$ and $g(t) = e^{2t}$ .

Solution.

(a) Dependent. Since $(1, 0, 2) + (0, 1, 1) = (1, 1, 3)$ , we have $(1, 0, 2) + (0, 1, 1) - (1, 1, 3) = \mathbf{0}$ , with coefficients not all zero.
(b) Independent. Let $a(1, 1, 0) + b(0, 1, 1) + c(1, 0, 1) = \mathbf{0}$ . Comparing entries: $a + c = 0$ , $a + b = 0$ , $b + c = 0$ . The first two give $c = -a$ and $b = -a$ ; then the third gives $-2a = 0$ , so $a = 0$ , and hence $b = c = 0$ .
(c) Independent. Let $a(x^2 + 1) + b(x^2 - 1) + cx = 0$ . The left side is $(a + b)x^2 + cx + (a - b)$ . Comparing coefficients (Definition 0.8.1): $a + b = 0$ , $c = 0$ , $a - b = 0$ . Adding the first and third gives $2a = 0$ , so $a = 0$ , and then $b = 0$ .
(d) Dependent. The first two matrices add up to the third, so $1 \cdot \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} + 1 \cdot \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} + (-1) \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}$ is the zero matrix.
(e) Independent. Let $af + bg = 0$ , the zero function. Then $ae^t + be^{2t} = 0$ for every $t \in \mathbb{R}$ . At $t = 0$ : $a + b = 0$ . At $t = \ln 2$ : $2a + 4b = 0$ , so $a + 2b = 0$ . Subtracting the first equation gives $b = 0$ , and then $a = 0$ .

Exercise (B2: A Parameter)

For which $t \in \mathbb{R}$ is the list $((1, t), (t, 1))$ in $\mathbb{R}^2$ linearly independent? Justify your answer.

Solution. Let $a(1, t) + b(t, 1) = (0, 0)$ , that is, $a + tb = 0$ and $ta + b = 0$ . The first equation gives $a = -tb$ . Substituting into the second, $-t^2b + b = (1 - t^2)b = 0$ .

If $t \neq \pm 1$ , then $1 - t^2 \neq 0$ , so $b = 0$ by Theorem 0.7.1, and then $a = -tb = 0$ . The list is independent.

If $t = 1$ , the list is $((1, 1), (1, 1))$ , which has a repeat and is dependent. If $t = -1$ , the list is $((1, -1), (-1, 1))$ , and $1 \cdot (1, -1) + 1 \cdot (-1, 1) = (0, 0)$ , so it is dependent.

Hence the list is linearly independent exactly when $t \neq 1$ and $t \neq -1$ .

Exercise (B3: Sub-Lists)

A sub-list of $(\mathbf{v}_1, \dots, \mathbf{v}_k)$ is a list $(\mathbf{v}_{i_1}, \dots, \mathbf{v}_{i_m})$ with $1 \le i_1 < i_2 < \dots < i_m \le k$ .

(a) Prove that every sub-list of a linearly independent list is linearly independent.
(b) Deduce that if some sub-list of a list is linearly dependent, then the whole list is linearly dependent.

Solution.

(a) Let $(\mathbf{v}_1, \dots, \mathbf{v}_k)$ be independent, and let $b_1\mathbf{v}_{i_1} + \dots + b_m\mathbf{v}_{i_m} = \mathbf{0}$ . Define $a_i = b_r$ if $i = i_r$ for some $r$ (the indices $i_r$ are distinct, so this is well defined), and $a_i = 0$ otherwise. By Theorem 1.1.5 the extra terms are $\mathbf{0}$ , so $a_1\mathbf{v}_1 + \dots + a_k\mathbf{v}_k = b_1\mathbf{v}_{i_1} + \dots + b_m\mathbf{v}_{i_m} = \mathbf{0}$ . By independence, every $a_i = 0$ ; in particular every $b_r = a_{i_r} = 0$ . Hence the sub-list is independent.
(b) This is the contrapositive of (a): if the whole list were independent, every sub-list would be independent by (a).

C. Going deeper

Exercise (C1: Sums of Pairs, and the Field

\mathbb{F}_2

)

Let $V$ be a vector space over $F$ and $(\mathbf{u}, \mathbf{v}, \mathbf{w})$ a linearly independent list in $V$ .

(a) Suppose $F = \mathbb{R}$ . Prove that $(\mathbf{u} + \mathbf{v}, \mathbf{v} + \mathbf{w}, \mathbf{w} + \mathbf{u})$ is linearly independent.
(b) Suppose $F = \mathbb{F}_2$ . Prove that $(\mathbf{u} + \mathbf{v}, \mathbf{v} + \mathbf{w}, \mathbf{w} + \mathbf{u})$ is linearly dependent, and give an example of an independent list $(\mathbf{u}, \mathbf{v}, \mathbf{w})$ over $\mathbb{F}_2$ , so that the statement is not vacuous.
(c) Which property of $\mathbb{R}$ did (a) use that $\mathbb{F}_2$ lacks? Deduce that (a) holds over every field in which $1 + 1 \neq 0$ .

Solution.

(a) Let $a(\mathbf{u} + \mathbf{v}) + b(\mathbf{v} + \mathbf{w}) + c(\mathbf{w} + \mathbf{u}) = \mathbf{0}$ . Expanding and regrouping with the axioms of Definition 1.1.1 gives $(a + c)\mathbf{u} + (a + b)\mathbf{v} + (b + c)\mathbf{w} = \mathbf{0}$ . By independence of $(\mathbf{u}, \mathbf{v}, \mathbf{w})$ , $a + c = 0$ , $a + b = 0$ and $b + c = 0$ . The first two give $c = -a$ and $b = -a$ , and then the third gives $-2a = 0$ . Since $2 \neq 0$ in $\mathbb{R}$ , $a = 0$ , and hence $b = c = 0$ . This proves independence.
(b) Over $\mathbb{F}_2$ , $\begin{aligned} 1(\mathbf{u} + \mathbf{v}) + 1(\mathbf{v} + \mathbf{w}) + 1(\mathbf{w} + \mathbf{u}) &= (1 + 1)\mathbf{u} + (1 + 1)\mathbf{v} + (1 + 1)\mathbf{w} \\ &= 0\mathbf{u} + 0\mathbf{v} + 0\mathbf{w} = \mathbf{0} , \end{aligned}$ using $1 + 1 = 0$ in $\mathbb{F}_2$ and Theorem 1.1.5. The coefficients are $1 \neq 0$ , so the list is dependent. For an example, $(\mathbf{e}_1, \mathbf{e}_2, \mathbf{e}_3)$ in $\mathbb{F}_2^3$ is independent by the argument of Example (Independent Lists in Four Families) (a), which works over any field.
(c) Part (a) divided by $2 = 1 + 1$ , that is, used $2 \neq 0$ , to pass from $-2a = 0$ to $a = 0$ . In $\mathbb{F}_2$ , $2 = 0$ . In any field with $1 + 1 \neq 0$ , the element $2$ has an inverse, and the proof of (a) goes through word for word.

Exercise (C2: Adding a Vector outside the Span)

Let $(\mathbf{v}_1, \dots, \mathbf{v}_k)$ be a linearly independent list in $V$ , and let $\mathbf{v} \in V$ with $\mathbf{v} \notin \operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_k)$ . Prove that $(\mathbf{v}_1, \dots, \mathbf{v}_k, \mathbf{v})$ is linearly independent. Give an example showing that the hypothesis $\mathbf{v} \notin \operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_k)$ cannot be dropped.

Solution. Let $a_1\mathbf{v}_1 + \dots + a_k\mathbf{v}_k + a\mathbf{v} = \mathbf{0}$ . Suppose $a \neq 0$ . Then, as in the proof of Theorem 1.4.1, $\mathbf{v} = (-a^{-1}a_1)\mathbf{v}_1 + \dots + (-a^{-1}a_k)\mathbf{v}_k \in \operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_k)$ , contradicting the hypothesis. Hence $a = 0$ , and the relation becomes $a_1\mathbf{v}_1 + \dots + a_k\mathbf{v}_k = \mathbf{0}$ . By independence of $(\mathbf{v}_1, \dots, \mathbf{v}_k)$ , $a_1 = \dots = a_k = 0$ . So all coefficients are zero, and the longer list is independent.

For the example, take $(\mathbf{e}_1)$ in $\mathbb{R}^2$ and $\mathbf{v} = 2\mathbf{e}_1 \in \operatorname{span}(\mathbf{e}_1)$ . The list $(\mathbf{e}_1)$ is independent, but $(\mathbf{e}_1, 2\mathbf{e}_1)$ is dependent, by $2\mathbf{e}_1 - 2\mathbf{e}_1 = \mathbf{0}$ .

Exercise (C3:

1, \sqrt 2, \sqrt 3

over

\mathbb{Q}

)

Regard $\mathbb{R}$ as a vector space over $\mathbb{Q}$ . Prove that the list $(1, \sqrt 2, \sqrt 3)$ is linearly independent over $\mathbb{Q}$ . Is it linearly independent over $\mathbb{R}$ ?

Hint: you may use without proof that $\sqrt 3$ and $\sqrt 6$ are irrational (the proof of Theorem 0.2.3 adapts). Isolate one square root and square.

Solution. Let $a + b\sqrt 2 + c\sqrt 3 = 0$ with $a, b, c \in \mathbb{Q}$ . Then $a + b\sqrt 2 = -c\sqrt 3$ , and squaring both sides gives $a^2 + 2b^2 + 2ab\sqrt 2 = 3c^2$ .

If $ab \neq 0$ , then $\sqrt 2 = \dfrac{3c^2 - a^2 - 2b^2}{2ab} \in \mathbb{Q}$ , contradicting Theorem 0.2.3. Hence $ab = 0$ , so $a = 0$ or $b = 0$ .

Case 1: $b = 0$ . Then $a + c\sqrt 3 = 0$ . If $c \neq 0$ , then $\sqrt 3 = -a/c \in \mathbb{Q}$ , a contradiction. So $c = 0$ , and then $a = 0$ .

Case 2: $a = 0$ . Then $b\sqrt 2 + c\sqrt 3 = 0$ . Multiplying by $\sqrt 2$ gives $2b + c\sqrt 6 = 0$ . If $c \neq 0$ , then $\sqrt 6 = -2b/c \in \mathbb{Q}$ , a contradiction. So $c = 0$ , then $b\sqrt 2 = 0$ , and $b = 0$ since $\sqrt 2 \neq 0$ .

In both cases $a = b = c = 0$ , so the list is linearly independent over $\mathbb{Q}$ .

Over $\mathbb{R}$ it is dependent: $\sqrt 2 \cdot 1 + (-1) \cdot \sqrt 2 + 0 \cdot \sqrt 3 = 0$ , and the coefficient $\sqrt 2$ is a non-zero real number. Over $\mathbb{R}$ any two non-zero real numbers form a dependent list.