1.5 Linear independence · Matrix Theory

A linear combination of a list represents one vector, but one vector can be represented by many linear combinations. Section 1.3 asked which vectors the linear combinations of a list represent, and the span answered it. This section asks in how many ways. In Example 1.3.5, the vector $(1, - 1)$ has two different representations by the list $(0, 0),$ $(1, - 1),$ $(- 𝜋, 𝜋)$ , while every vector of $𝐹^{2}$ has exactly one representation by $(1, 0), (0, 1)$ . Lists of the second kind are called linearly independent. A linearly independent list that also spans $𝑉$ names every vector of $𝑉$ by a unique list of coefficients, and these coefficients are the coordinates of Section 1.6.

1.5.1Unique representations

Throughout, $𝑉$ is a vector space over a field $𝐹$ .

Definition 1.5.1 (Linear independence). A list

ℒ︀ = 𝐯_{1}, \dots, 𝐯_{𝑘}

𝑉

is linearly independent if every vector of

span (ℒ︀)

is represented by exactly one linear combination of

ℒ︀

. Otherwise

ℒ︀

is linearly dependent. We also say that the vectors

𝐯_{1}, \dots, 𝐯_{𝑘}

are linearly independent (or dependent), and we often drop the word “linearly”.

Every vector of $span (ℒ︀)$ is represented by at least one linear combination of $ℒ︀$ , by Definition 1.3.10, so independence asks for at most one. In terms of coefficients, $ℒ︀$ is linearly independent when, for all scalars $𝑎_{1}, \dots, 𝑎_{𝑘}$ and $𝑏_{1}, \dots, 𝑏_{𝑘}$ ,

\sum_{𝑖 = 1}^{𝑘} 𝑎_{𝑖} 𝐯_{𝑖} = \sum_{𝑖 = 1}^{𝑘} 𝑏_{𝑖} 𝐯_{𝑖} implies 𝑎_{1} = 𝑏_{1}, \dots, 𝑎_{𝑘} = 𝑏_{𝑘} .

This is the claim of Exercise 1.3.29, which holds for some lists and fails for others. Order and repetitions are part of a list, and independence is a property of the list, not of its set of entries: we will see that a list with a repeated entry is never independent (Proposition 1.5.15).

Example 1.5.2 (The lists ${ℒ︀}_{0}$ and ${ℒ︀}_{1}$ ). In $ℝ^{2}$ , let ${ℒ︀}_{0} = (1, 0), (0, 1)$ and ${ℒ︀}_{1} =$ $(0, 0),$ $(1, - 1),$ $(- 𝜋, 𝜋)$ .

${ℒ︀}_{0}$ is linearly independent. The linear combination with coefficients $𝑎_{1}, 𝑎_{2}$ represents $𝑎_{1} (1, 0) +$ $𝑎_{2} (0, 1) =$ $(𝑎_{1}, 𝑎_{2})$ . So if the linear combinations with coefficients $𝑎_{1}, 𝑎_{2}$ and $𝑏_{1}, 𝑏_{2}$ both represent $(𝑐_{1}, 𝑐_{2})$ , then $(𝑎_{1}, 𝑎_{2}) =$ $(𝑐_{1}, 𝑐_{2}) =$ $(𝑏_{1}, 𝑏_{2})$ , that is, $𝑎_{1} = 𝑐_{1} = 𝑏_{1}$ and $𝑎_{2} = 𝑐_{2} = 𝑏_{2}$ . The two linear combinations were the same all along. The same computation shows that $𝐞_{1}, \dots, 𝐞_{𝑛}$ is linearly independent in $𝐹^{𝑛}$ , since the linear combination with coefficients $𝑎_{1}, \dots, 𝑎_{𝑛}$ represents $(𝑎_{1}, \dots, 𝑎_{𝑛})$ (Example 1.3.7).

${ℒ︀}_{1}$ is linearly dependent. By Example 1.3.15, $span ({ℒ︀}_{1})$ consists of the vectors $(𝑐, - 𝑐)$ with $𝑐 \in ℝ$ . Each of them has the two representations

0 (0, 0) + 𝑐 (1, - 1) + 0 (- 𝜋, 𝜋) and \sqrt{87} (0, 0) + 0 (1, - 1) + (- \frac{𝑐}{𝜋}) (- 𝜋, 𝜋),

which are different linear combinations, as their first coefficients differ. So no vector of $span ({ℒ︀}_{1})$ has a unique representation.

Intuition (Independence as the absence of redundancy). The two representations of

(𝑐, - 𝑐)

{ℒ︀}_{1}

show where the redundancy lies. Any coefficient can be placed on

(0, 0)

at no cost, and since

(- 𝜋, 𝜋) =

- 𝜋 (1, - 1)

, an amount of

(1, - 1)

can be traded for a multiple of

(- 𝜋, 𝜋)

. An independent list allows no such trade. From the vector that a linear combination represents we can recover every coefficient, so no entry can be made up for by the others. Theorem 1.5.5 and Lemma 1.5.10 turn these two readings, “the coefficients can be recovered” and “no entry is made up for by the others”, into criteria we can check.

1.5.2Testing at zero

Checking Definition 1.5.1 directly means checking every vector of the span, usually infinitely many. One vector suffices.

Intuition. Two representations of the same vector

𝐰

differ by a representation of

𝟎

: subtracting coefficients gives a linear combination that represents

𝐰 - 𝐰 = 𝟎

. In the other direction, adding the coefficients of a representation of

𝟎

to those of a representation of

𝐰

gives another representation of

𝐰

(Exercise 1.3.6). So every vector of the span has as many representations as

𝟎

has, and

𝟎

is the vector to test. It always has the representation with all coefficients

0

; the question is whether it has any other.

Definition 1.5.3 (Linear relation). A linear relation of a list $ℒ︀ = 𝐯_{1}, \dots, 𝐯_{𝑘}$ is a linear combination of $ℒ︀$ that represents $𝟎$ , that is, a list of scalars $𝑎_{1}, \dots, 𝑎_{𝑘}$ with

𝑎_{1} 𝐯_{1} + \dots + 𝑎_{𝑘} 𝐯_{𝑘} = 𝟎 .

The trivial relation is the one with $𝑎_{1} = \dots = 𝑎_{𝑘} = 0$ ; it represents $𝟎$ by Lemma 1.3.9(c). A linear relation with at least one nonzero coefficient is nontrivial, and is also called a dependence relation of $ℒ︀$ .

The empty list has one linear combination, the empty one, which represents $𝟎$ and has no nonzero coefficient. So its only linear relation is the trivial one.

The lecture proves the equivalence below by proving one direction in a contrapositive form. The move deserves a name.

Technique 1.5.4 (Contrapositive). An implication “ $𝑃$ implies $𝑄$ ” is logically equivalent to its contrapositive, “not $𝑄$ implies not $𝑃$ ”. Prove the contrapositive when “not $𝑄$ ” gives you more to work with than $𝑃$ does. The typical case is a conclusion $𝑄$ asserting that something holds for every object, or that some object is unique. Then “not $𝑄$ ” hands you a specific object, a counterexample or a second candidate, and you can compute with it.

Reach for it when the hypothesis is hard to use directly and the conclusion is a “for all” or a uniqueness statement. The canonical example is (II) $\Rightarrow$ (I) in Theorem 1.5.5. Statement (I) asserts uniqueness for every vector of the span. Its negation provides one vector with two different representations, and subtracting them shows that (II) fails.

Used in 15 places

Theorem 1.5.5, Corollary 1.5.13, Corollary 1.5.17, Exercise 1.5.41, Problem 1.1, Problem 1.3, Corollary 2.5.11, Proposition 2.6.14, Proposition 3.4.15, Proposition 3.4.16, Corollary 4.1.13, Theorem 4.7.22, Theorem 5.4.7, Corollary 7.1.23, Exercise A.1.24.

Theorem 1.5.5 (Independence is decided at zero). Let

ℒ︀ = 𝐯_{1}, \dots, 𝐯_{𝑘}

be a list in

𝑉

. The following are equivalent.

(I) $ℒ︀$ is linearly independent.
(II) $ℒ︀$ has no nontrivial linear relation: if $𝑎_{1} 𝐯_{1} +$ $\dots +$ $𝑎_{𝑘} 𝐯_{𝑘} =$ $𝟎$ , then $𝑎_{1} = \dots = 𝑎_{𝑘} = 0$ .

Proof.routine

Uses. Definition 1.5.1 (Linear independence), Definition 1.5.3 (Linear relation), Lemma 1.3.9 (Arithmetic of linear combinations), Proposition 1.2.34 (Negatives and the scalar $- 1$ )

Techniques. Contrapositive (Technique 1.5.4)

Hint 1. (I)

\Rightarrow

(II) is a special case of the definition. Which vector of the span is in question, and which representation does it always have?

Hint 2. For (II)

\Rightarrow

(I), prove the contrapositive. If

ℒ︀

is dependent, some

𝐰 \in span (ℒ︀)

has two different representations.

Hint 3. Subtract the two representations: compute

𝐰 + (- 1) 𝐰

with Lemma 1.3.9. Why is one of the resulting coefficients nonzero?

Sketch. (I)

\Rightarrow

(II):

𝟎 \in span (ℒ︀)

, and the trivial relation represents it, so by uniqueness it is the only linear combination representing

𝟎

. (II)

\Rightarrow

(I), by contrapositive: if

\sum 𝑎_{𝑖} 𝐯_{𝑖}

and

\sum 𝑏_{𝑖} 𝐯_{𝑖}

are different representations of

𝐰

, then

\sum (𝑎_{𝑖} - 𝑏_{𝑖}) 𝐯_{𝑖} =

𝐰 -

𝐰 =

𝟎

, and

𝑎_{𝑗} \neq 𝑏_{𝑗}

for some

𝑗

, so this relation is nontrivial.

(I) $\Rightarrow$ (II). Suppose that $ℒ︀$ is linearly independent. The trivial relation represents $𝟎$ , so $𝟎 \in span (ℒ︀)$ , and by (I) no other linear combination of $ℒ︀$ represents $𝟎$ . That is, every linear relation of $ℒ︀$ is trivial.

(II) $\Rightarrow$ (I). We prove the contrapositive: if $ℒ︀$ is linearly dependent, then $ℒ︀$ has a nontrivial linear relation. Suppose that $ℒ︀$ is linearly dependent. Then some $𝐰 \in span (ℒ︀)$ is represented by two different linear combinations of $ℒ︀$ , say with coefficients $𝑎_{1}, \dots, 𝑎_{𝑘}$ and $𝑏_{1}, \dots, 𝑏_{𝑘}$ . By (A4) and Proposition 1.2.34, then Lemma 1.3.9(b) with $𝑐 = - 1$ , and Lemma 1.3.9(a),

\begin{aligned} 𝟎 = 𝐰 + (- 1) 𝐰 & = \sum_{𝑖 = 1}^{𝑘} 𝑎_{𝑖} 𝐯_{𝑖} + (- 1) \sum_{𝑖 = 1}^{𝑘} 𝑏_{𝑖} 𝐯_{𝑖} \\ = \sum_{𝑖 = 1}^{𝑘} 𝑎_{𝑖} 𝐯_{𝑖} + \sum_{𝑖 = 1}^{𝑘} (- 𝑏_{𝑖}) 𝐯_{𝑖} = \sum_{𝑖 = 1}^{𝑘} (𝑎_{𝑖} - 𝑏_{𝑖}) 𝐯_{𝑖} . \end{aligned}

The two linear combinations are different, so $𝑎_{𝑗} \neq 𝑏_{𝑗}$ for some $𝑗$ , and then $𝑎_{𝑗} - 𝑏_{𝑗} \neq 0$ . So the scalars $𝑎_{1} -$ $𝑏_{1},$ $\dots,$ $𝑎_{𝑘} -$ $𝑏_{𝑘}$ form a nontrivial linear relation of $ℒ︀$ , and (II) fails. □

In practice, to show that $ℒ︀$ is independent, suppose that $𝑎_{1} 𝐯_{1} +$ $\dots +$ $𝑎_{𝑘} 𝐯_{𝑘} =$ $𝟎$ and deduce that every $𝑎_{𝑖}$ is $0$ . To show that $ℒ︀$ is dependent, exhibit one nontrivial relation. A relation is a certificate: anyone can check it by computing a single linear combination, without knowing how it was found.

A single relation also produces many representations. If $𝑐_{1}, \dots, 𝑐_{𝑘}$ is a dependence relation and $𝑏_{1}, \dots, 𝑏_{𝑘}$ represents $𝐰$ , then for every $𝑡 \in 𝐹$ the coefficients $𝑏_{1} +$ $𝑡 𝑐_{1},$ $\dots,$ $𝑏_{𝑘} +$ $𝑡 𝑐_{𝑘}$ represent $𝐰 + 𝑡 𝟎 = 𝐰$ , by Lemma 1.3.9. Different values of $𝑡$ give different linear combinations, because $𝑐_{𝑗} \neq 0$ for some $𝑗$ . So over an infinite field, a dependent list represents each vector of its span in infinitely many ways, and over a finite field with $𝑞$ elements in at least $𝑞$ ways.

Example 1.5.6 (A list whose independence depends on the field). Consider $ℒ︀ = (1, 2), (2, 1)$ in $𝐹^{2}$ , where $2 = 1 + 1$ in $𝐹$ . Suppose that $𝑎 (1, 2) +$ $𝑏 (2, 1) =$ $𝟎$ , that is,

𝑎 + 2 𝑏 = 0 and 2 𝑎 + 𝑏 = 0 .

Subtracting twice the first equation from the second gives $𝑏 - 4 𝑏 = 0$ , that is, $- 3 𝑏 = 0$ , where $3 = 1 + 1 + 1$ .

If $3 \neq 0$ in $𝐹$ , as in $ℚ$ , $ℝ$ , $ℂ$ , $𝔽_{2}$ , and $𝔽_{5}$ , then $- 3 \neq 0$ and $𝑏 = 0$ (Proposition 1.1.17), and then $𝑎 = - 2 𝑏 = 0$ . So the only linear relation is trivial, and $ℒ︀$ is linearly independent by Theorem 1.5.5. (Over $𝔽_{2}$ the list is just $(1, 0), (0, 1)$ .)

If $3 = 0$ , as in $𝔽_{3}$ , both equations hold for $𝑎 = 𝑏 = 1$ , since $1 + 2 = 3 = 0$ . So $(1, 2) + (2, 1) = 𝟎$ in $𝔽_{3}^{2}$ is a dependence relation, and $ℒ︀$ is linearly dependent. In fact $(2, 1) = 2 (1, 2)$ in $𝔽_{3}^{2}$ , since $2 \cdot 2 = 4 = 1$ .

Example 1.5.7 (Monomials). In

𝐹 [𝑥]

, the list

1, 𝑥, 𝑥^{2}, \dots, 𝑥^{𝑛}

is linearly independent. By Notation 1.2.15, the linear combination

𝑎_{0} +

𝑎_{1} 𝑥 +

\dots +

𝑎_{𝑛} 𝑥^{𝑛}

represents the polynomial with coefficients

(𝑎_{0}, 𝑎_{1}, \dots, 𝑎_{𝑛}, 0, 0, \dots)

, and by Definition 1.2.13 this is the zero polynomial only if

𝑎_{0} = 𝑎_{1} = \dots = 𝑎_{𝑛} = 0

. So the only linear relation is trivial. This holds over every field,

𝔽_{2}

included, because polynomials are compared coefficient by coefficient (Aside (Polynomials versus polynomial functions)).

Exercise 1.5.8.routine Let

𝐯, 𝐰 \in 𝑉

be linearly independent. Show that

𝐯 + 𝐰, 𝐯 - 𝐰

is linearly independent if and only if

1 + 1 \neq 0

𝐹

Solution.

Uses. Theorem 1.5.5 (Independence is decided at zero), Lemma 1.3.9 (Arithmetic of linear combinations), Proposition 1.1.17 (No zero divisors)

Hint 1. Expand

𝑎 (𝐯 + 𝐰) +

𝑏 (𝐯 - 𝐰)

as a linear combination of

𝐯, 𝐰

, and use that

𝐯, 𝐰

has only the trivial relation.

Hint 2. You get

𝑎 + 𝑏 = 0

and

𝑎 - 𝑏 = 0

. Add them. When does

(1 + 1) 𝑎 = 0

force

𝑎 = 0

Sketch. Expanding, the combination with coefficients

𝑎, 𝑏

of the new list is the combination with coefficients

𝑎 + 𝑏

𝑎 - 𝑏

𝐯, 𝐰

. So a relation of the new list gives

𝑎 + 𝑏 = 𝑎 - 𝑏 = 0

, hence

(1 + 1) 𝑎 = 0

and

(1 + 1) 𝑏 = 0

. If

1 + 1 \neq 0

, then

𝑎 = 𝑏 = 0

. If

1 + 1 = 0

, then

(𝐯 + 𝐰) +

(𝐯 - 𝐰) =

(1 + 1) 𝐯 =

𝟎

is a dependence relation.

By Lemma 1.3.9, for $𝑎, 𝑏 \in 𝐹$ ,

𝑎 (𝐯 + 𝐰) + 𝑏 (𝐯 - 𝐰) = (𝑎 + 𝑏) 𝐯 + (𝑎 - 𝑏) 𝐰 .

Suppose that $1 + 1 \neq 0$ , and that the left side is $𝟎$ . Since $𝐯, 𝐰$ is independent, Theorem 1.5.5 gives $𝑎 + 𝑏 = 0$ and $𝑎 - 𝑏 = 0$ . Adding and subtracting these equations gives $(1 + 1) 𝑎 = 0$ and $(1 + 1) 𝑏 = 0$ , so $𝑎 = 𝑏 = 0$ by Proposition 1.1.17. Hence $𝐯 + 𝐰, 𝐯 - 𝐰$ is independent.

Suppose that $1 + 1 = 0$ . Taking $𝑎 = 𝑏 = 1$ , the right side is $(1 + 1) 𝐯 + 0 𝐰 = 𝟎$ . So $1, 1$ is a dependence relation, and the list is dependent. In fact $- 1 = 1$ , so $𝐯 - 𝐰 = 𝐯 + 𝐰$ , and the list repeats an entry.

1.5.3The linear dependence lemma

Theorem 1.5.5 detects dependence through a relation. The next result reads off from a relation which entry is redundant.

Intuition. A dependence relation $𝑎_{1} 𝐯_{1} +$ $\dots +$ $𝑎_{𝑘} 𝐯_{𝑘} =$ $𝟎$ can be solved for any entry whose coefficient is nonzero, and this writes that entry as a linear combination of the others. To control which entries appear on the other side, solve for the last entry with a nonzero coefficient. All later entries have coefficient $0$ , so only earlier entries remain.

Here is a picture. Build $span (ℒ︀)$ by adding the entries one at a time: first $span (𝐯_{1})$ , then $span (𝐯_{1}, 𝐯_{2})$ , and so on. At each step the span either grows or stays the same, and it stays the same exactly when the new entry already lies in the span of the earlier ones (Corollary 1.3.20(c)). The lemma says that for a dependent list, some step does not make the span grow.

The proof chooses an index that is as large as possible. This is the first of many proofs built on an extreme choice.

Technique 1.5.9 (Extremal choice and minimal counterexamples). When a proof needs an object with special properties, choose one that is extreme in some respect: the largest index with a nonzero coefficient, a polynomial of largest degree, a dependence relation with the fewest nonzero coefficients, a smallest counterexample. Extremality is a hypothesis you get for free. “The largest $𝑗$ with $𝑎_{𝑗} \neq 0$ ” also says that every later coefficient is $0$ . “A relation with the fewest nonzero coefficients” also says that every relation with fewer nonzero coefficients is trivial.

It combines with contradiction. To show that no object has some property, suppose that some do, take an extreme one, and use it to build another object with the property that is more extreme still. This contradicts the choice.

Reach for it when a relation or a sum has many terms and the argument would be easy if most of them vanished. The canonical example is the linear dependence lemma (Lemma 1.5.10), which solves for the largest index with a nonzero coefficient. The same choice, of a largest degree, proves Proposition 1.5.24, and the contradiction form appears in Exercise 1.5.44.

Used in 47 places and 4 practice exercises

Lemma 1.5.10, Proposition 1.5.24, Example 1.5.27, Exercise 1.5.44, Exercise 1.5.45, Theorem 1.6.10, Exercise 1.7.8, Exercise 1.7.9, Problem 1.4, Problem 1.15, Exercise 3.6.13, Problem 3.18, Lemma 4.1.2, Theorem 4.1.10, Proposition 4.1.21, Exercise 4.1.56, Exercise 4.2.51, Theorem 4.4.7, Exercise 4.6.55, Theorem 4.7.34, Exercise 5.5.39, Exercise 6.4.61, Problem 6.13, Theorem 7.1.32, Theorem 7.1.45, Theorem 7.2.21, Proposition 7.2.35, Proposition 7.2.37, Exercise 7.2.51, Exercise 7.4.53, Theorem 7.6.2, Theorem 7.6.7, Theorem 7.6.31, Exercise 7.6.49, Exercise 7.6.56, Problem 7.1, Theorem 8.2.5, Exercise 8.2.44, Exercise 8.2.46, Notation 8.3.10, Exercise A.1.30, Theorem A.2.1, Proposition A.2.4, Exercise A.2.10, Theorem A.4.4, Theorem A.4.7, Exercise A.4.8; 4 practice exercises.

Lemma 1.5.10 (Linear dependence lemma). Let $ℒ︀ = 𝐯_{1}, \dots, 𝐯_{𝑘}$ be a linearly dependent list in $𝑉$ . Then there is an index $𝑗 \in {1, \dots, 𝑘}$ with

𝐯_{𝑗} \in span (𝐯_{1}, \dots, 𝐯_{𝑗 - 1}) .

Moreover, for every such $𝑗$ , deleting $𝐯_{𝑗}$ from $ℒ︀$ does not change the span:

span (𝐯_{1}, \dots, 𝐯_{𝑗 - 1}, 𝐯_{𝑗 + 1}, \dots, 𝐯_{𝑘}) = span (ℒ︀) .

For $𝑗 = 1$ the condition reads $𝐯_{1} \in span (()) = {𝟎}$ , that is, $𝐯_{1} = 𝟎$ .

Proof.standard

Uses. Theorem 1.5.5 (Independence is decided at zero), Lemma 1.3.9 (Arithmetic of linear combinations), Proposition 1.2.32 (The scalar zero), Proposition 1.2.28 (Uniqueness of additive inverses), Proposition 1.2.34 (Negatives and the scalar $- 1$ ), Corollary 1.3.20 (Operations that preserve the span)

Techniques. Extremal choice and minimal counterexamples (Technique 1.5.9)

Hint 1. By Theorem 1.5.5,

ℒ︀

has a nontrivial relation

𝑎_{1} 𝐯_{1} +

\dots +

𝑎_{𝑘} 𝐯_{𝑘} =

𝟎

. Solve it for one entry. Which choice of entry leaves only earlier entries on the other side?

Hint 2. Let

𝑗

be the largest index with

𝑎_{𝑗} \neq 0

. The terms after

𝑗

vanish; move the others to the other side and divide by

𝑎_{𝑗}

Hint 3. For the second statement,

𝐯_{𝑗}

lies in the span of the list with

𝐯_{𝑗}

deleted. Use Corollary 1.3.20(a), (b), and (c).

Sketch. Take a nontrivial relation and the largest

𝑗

with

𝑎_{𝑗} \neq 0

. Then

𝑎_{1} 𝐯_{1} +

\dots +

𝑎_{𝑗} 𝐯_{𝑗} =

𝟎

, so

𝐯_{𝑗} =

\sum_{𝑖 < 𝑗} (- 𝑎_{𝑖} / 𝑎_{𝑗}) 𝐯_{𝑖}

. If

𝐯_{𝑗} \in

span (𝐯_{1}, \dots, 𝐯_{𝑗 - 1})

and

{ℒ︀}^{'}

ℒ︀

without

𝐯_{𝑗}

, then

𝐯_{𝑗} \in span ({ℒ︀}^{'})

, so appending

𝐯_{𝑗}

{ℒ︀}^{'}

does not change the span (Corollary 1.3.20(c)); and

{ℒ︀}^{'}, 𝐯_{𝑗}

is a reordering of

ℒ︀

Since $ℒ︀$ is dependent, (II) of Theorem 1.5.5 fails: there are scalars $𝑎_{1}, \dots, 𝑎_{𝑘}$ , not all $0$ , with $𝑎_{1} 𝐯_{1} +$ $\dots +$ $𝑎_{𝑘} 𝐯_{𝑘} =$ $𝟎$ . Let $𝑗$ be the largest index with $𝑎_{𝑗} \neq 0$ . For $𝑖 > 𝑗$ we have $𝑎_{𝑖} = 0$ , so $𝑎_{𝑖} 𝐯_{𝑖} = 𝟎$ by Proposition 1.2.32, and dropping these terms gives

(𝑎_{1} 𝐯_{1} + \dots + 𝑎_{𝑗 - 1} 𝐯_{𝑗 - 1}) + 𝑎_{𝑗} 𝐯_{𝑗} = 𝟎 .

By Proposition 1.2.28, $𝑎_{𝑗} 𝐯_{𝑗}$ is the additive inverse of the sum in parentheses. By Proposition 1.2.34 and Lemma 1.3.9(b), that inverse is $(- 1)$ times the sum, so

𝑎_{𝑗} 𝐯_{𝑗} = (- 𝑎_{1}) 𝐯_{1} + \dots + (- 𝑎_{𝑗 - 1}) 𝐯_{𝑗 - 1} .

Since $𝑎_{𝑗} \neq 0$ , we may multiply both sides by $𝑎_{𝑗}^{- 1}$ . By (A6) and (A5) on the left, and Lemma 1.3.9(b) on the right,

𝐯_{𝑗} = \sum_{𝑖 = 1}^{𝑗 - 1} (- \frac{𝑎_{𝑖}}{𝑎_{𝑗}}) 𝐯_{𝑖} \in span (𝐯_{1}, \dots, 𝐯_{𝑗 - 1}) .

(If $𝑗 = 1$ , the sum is empty and the equation says $𝐯_{1} = 𝟎$ .)

Now let $𝑗$ be any index with $𝐯_{𝑗} \in$ $span (𝐯_{1}, \dots, 𝐯_{𝑗 - 1})$ , and let ${ℒ︀}^{'}$ be the list obtained from $ℒ︀$ by deleting $𝐯_{𝑗}$ . The list $𝐯_{1}, \dots, 𝐯_{𝑗 - 1}$ is a sublist of ${ℒ︀}^{'}$ , so $𝐯_{𝑗} \in span ({ℒ︀}^{'})$ by Corollary 1.3.20(b). By Corollary 1.3.20(c), $span ({ℒ︀}^{'}, 𝐯_{𝑗}) =$ $span ({ℒ︀}^{'})$ . The list ${ℒ︀}^{'}, 𝐯_{𝑗}$ is a reordering of $ℒ︀$ , so its span is $span (ℒ︀)$ by Corollary 1.3.20(a). Hence $span ({ℒ︀}^{'}) =$ $span (ℒ︀)$ . □

The proof did not search for $𝑗$ . It read $𝑗$ off a dependence relation: any relation gives an index, the largest one with a nonzero coefficient. Different relations can give different indices, and the lemma guarantees only that some $𝑗$ works, not that a particular one does.

Example 1.5.11 (Which entries are redundant). Take ${ℒ︀}_{1} =$ $(0, 0),$ $(1, - 1),$ $(- 𝜋, 𝜋)$ in $ℝ^{2}$ again, and write $𝐯_{1}, 𝐯_{2}, 𝐯_{3}$ for its entries. The relation $1 𝐯_{1} + 0 𝐯_{2} + 0 𝐯_{3} = 𝟎$ has largest nonzero index $1$ , and indeed $𝐯_{1} = 𝟎 \in span (())$ . The relation $0 𝐯_{1} +$ $𝜋 𝐯_{2} +$ $1 𝐯_{3} =$ $𝟎$ gives $𝑗 = 3$ , and indeed $𝐯_{3} = - 𝜋 𝐯_{2}$ . No relation gives $𝑗 = 2$ , because $(1, - 1) \notin$ $span ((0, 0)) =$ ${𝟎}$ . Deleting $𝐯_{1}$ and then, in the remaining list $(1, - 1), (- 𝜋, 𝜋)$ , deleting the last entry, the lemma recovers $span ({ℒ︀}_{1}) =$ $span ((1, - 1))$ , the computation of Example 1.3.21.

The last entry of a dependent list need not be redundant. In $ℝ^{2}$ , the list $(1, 0), (2, 0), (0, 1)$ is dependent, since $2 (1, 0) +$ $(- 1) (2, 0) +$ $0 (0, 1) =$ $𝟎$ , but $(0, 1)$ does not lie in $span ((1, 0), (2, 0))$ , which is the first axis. Here $𝑗 = 2$ is the only index that works.

The list

𝐯_{1},

𝐯_{2},

𝐯_{3} =

(2, 1),

(- 1, 1),

(1, 2)

is dependent:

𝐯_{1} + 𝐯_{2} - 𝐯_{3} = 𝟎

. So

𝐯_{3} \in span (𝐯_{1}, 𝐯_{2})

, and by Lemma 1.5.10 deleting

𝐯_{3}

leaves the span unchanged. In the interactive version, the explorer reports a dependence relation and the representations of

𝐰 = (0, 3)

. Delete one vector and drag the other two onto a common line to see when two vectors are dependent (Proposition 1.5.15). With three vectors in

ℝ^{2}

, no position makes the list independent; Section 4.1 explains why.

Exercise 1.5.12.routine In $ℝ^{3}$ , let $ℒ︀$ be the list

𝐯_{1}, \dots, 𝐯_{5} = (1, 1, 0), (2, 2, 0), (0, 1, 1), (1, 2, 1), (0, 0, 1) .

Find every $𝑗$ with $𝐯_{𝑗} \in$ $span (𝐯_{1}, \dots, 𝐯_{𝑗 - 1})$ , and for each such $𝑗$ , a dependence relation whose largest index with a nonzero coefficient is $𝑗$ .

Solution.

Uses. Lemma 1.5.10 (Linear dependence lemma), Definition 1.3.10 (Span), Corollary 1.3.20 (Operations that preserve the span)

Hint 1. Go through

𝑗 = 1, \dots, 5

in order. For

𝑗 = 2

, compare

𝐯_{2}

with

𝐯_{1}

Hint 2. Once you know that

𝐯_{2}

is redundant,

span (𝐯_{1}, 𝐯_{2}, 𝐯_{3}) =

span (𝐯_{1}, 𝐯_{3})

, whose elements are

(𝑎, 𝑎 + 𝑏, 𝑏)

. Test

𝐯_{4}

and

𝐯_{5}

against this description.

Sketch.

𝑗 = 2

, since

𝐯_{2} = 2 𝐯_{1}

, and

𝑗 = 4

, since

𝐯_{4} = 𝐯_{1} + 𝐯_{3}

, with relations

2 𝐯_{1} - 𝐯_{2} = 𝟎

and

𝐯_{1} + 𝐯_{3} - 𝐯_{4} = 𝟎

. No other

𝑗

works:

𝐯_{1} \neq 𝟎

𝐯_{3}

is not a multiple of

𝐯_{1}

, and

span (𝐯_{1}, \dots, 𝐯_{4}) =

{(𝑎, 𝑎 + 𝑏, 𝑏)}

does not contain

(0, 0, 1)

$𝑗 = 1$ : $𝐯_{1} \neq 𝟎$ , so $𝐯_{1} \notin span (()) = {𝟎}$ .

$𝑗 = 2$ : $𝐯_{2} = 2 𝐯_{1}$ . The relation $2 𝐯_{1} + (- 1) 𝐯_{2} = 𝟎$ , with zero coefficients on the other entries, has largest nonzero index $2$ .

$𝑗 = 3$ : By Corollary 1.3.20(c), $span (𝐯_{1}, 𝐯_{2}) =$ $span (𝐯_{1})$ , whose elements $(𝑎, 𝑎, 0)$ have third coordinate $0$ . So $𝐯_{3} = (0, 1, 1)$ is not in it.

$𝑗 = 4$ : $𝐯_{1} +$ $𝐯_{3} =$ $(1, 2, 1) =$ $𝐯_{4}$ . The relation $𝐯_{1} +$ $𝐯_{3} +$ $(- 1) 𝐯_{4} =$ $𝟎$ has largest nonzero index $4$ .

$𝑗 = 5$ : By Corollary 1.3.20(a) and (c), deleting $𝐯_{2}$ and $𝐯_{4}$ shows $span (𝐯_{1}, \dots, 𝐯_{4}) =$ $span (𝐯_{1}, 𝐯_{3})$ , which consists of the vectors $𝑎 (1, 1, 0) +$ $𝑏 (0, 1, 1) =$ $(𝑎, 𝑎 + 𝑏, 𝑏)$ . For $(0, 0, 1)$ we would need $𝑎 = 0$ , $𝑏 = 1$ , and $𝑎 + 𝑏 = 0$ , which is impossible. So $𝐯_{5} \notin$ $span (𝐯_{1}, \dots, 𝐯_{4})$ .

Hence $𝑗 = 2$ and $𝑗 = 4$ are the indices that work.

The lemma has a converse. If some entry lies in the span of the earlier ones, solving for it backwards produces a relation in which that entry has coefficient $- 1$ . So the condition of the lemma characterizes dependence.

Corollary 1.5.13 (Independence, one entry at a time). A list $ℒ︀ = 𝐯_{1}, \dots, 𝐯_{𝑘}$ in $𝑉$ is linearly independent if and only if

𝐯_{𝑗} \notin span (𝐯_{1}, \dots, 𝐯_{𝑗 - 1}) for every 𝑗 \in {1, \dots, 𝑘} .

Proof.routine

Uses. Lemma 1.5.10 (Linear dependence lemma), Theorem 1.5.5 (Independence is decided at zero), Proposition 1.2.34 (Negatives and the scalar $- 1$ ), Proposition 1.2.32 (The scalar zero)

Techniques. Contrapositive (Technique 1.5.4)

Hint 1. One direction is the contrapositive of Lemma 1.5.10.

Hint 2. For the other, suppose

𝐯_{𝑗} =

𝑏_{1} 𝐯_{1} +

\dots +

𝑏_{𝑗 - 1} 𝐯_{𝑗 - 1}

. Write down a linear relation of

ℒ︀

in which

𝐯_{𝑗}

has coefficient

- 1

Sketch. (

\Leftarrow

) If

ℒ︀

were dependent, Lemma 1.5.10 would give a

𝑗

violating the condition. (

\Rightarrow

) If

𝐯_{𝑗} =

\sum_{𝑖 < 𝑗} 𝑏_{𝑖} 𝐯_{𝑖}

, then the coefficients

𝑏_{1},

\dots,

𝑏_{𝑗 - 1},

- 1,

0,

\dots,

0

form a nontrivial relation, so

ℒ︀

is dependent.

( $\Leftarrow$ ) This is the contrapositive of Lemma 1.5.10: if $ℒ︀$ is dependent, then $𝐯_{𝑗} \in$ $span (𝐯_{1}, \dots, 𝐯_{𝑗 - 1})$ for some $𝑗$ .

( $\Rightarrow$ ) We prove the contrapositive. Suppose that $𝐯_{𝑗} =$ $𝑏_{1} 𝐯_{1} +$ $\dots +$ $𝑏_{𝑗 - 1} 𝐯_{𝑗 - 1}$ for some $𝑗$ and some scalars $𝑏_{𝑖}$ . Consider the linear combination of $ℒ︀$ with coefficients $𝑏_{1}, \dots, 𝑏_{𝑗 - 1}$ on the first $𝑗 - 1$ entries, $- 1$ on $𝐯_{𝑗}$ , and $0$ on the entries after $𝐯_{𝑗}$ . By Proposition 1.2.34, Proposition 1.2.32, and (A4), it represents

(𝑏_{1} 𝐯_{1} + \dots + 𝑏_{𝑗 - 1} 𝐯_{𝑗 - 1}) + (- 1) 𝐯_{𝑗} = 𝐯_{𝑗} + (- 𝐯_{𝑗}) = 𝟎 .

Its coefficient on $𝐯_{𝑗}$ is $- 1 \neq 0$ , so it is a nontrivial relation, and $ℒ︀$ is dependent by Theorem 1.5.5. □

Condition (II) of Theorem 1.5.5 does not refer to the order of the entries, so a reordering of an independent list is independent (Proposition 1.5.18(a)). Applying Corollary 1.5.13 to a reordering in which a chosen entry comes last gives the symmetric form: $ℒ︀$ is linearly dependent if and only if some entry lies in the span of the other entries. In that form, the entry is the one that the intuition at the start of the section called “made up for by the others”.

The corollary also says what happens when an independent list is lengthened by one vector.

Proposition 1.5.14 (Appending a vector). Let

ℒ︀

be a linearly independent list in

𝑉

, and let

𝐰 \in 𝑉

. Then

ℒ︀, 𝐰

is linearly independent if and only if

𝐰 \notin span (ℒ︀)

Proof.routine

Uses. Corollary 1.5.13 (Independence, one entry at a time), Theorem 1.5.5 (Independence is decided at zero), Lemma 1.3.9 (Arithmetic of linear combinations)

Hint 1. For (

\Rightarrow

), the last entry of

ℒ︀, 𝐰

𝐰

. Apply Corollary 1.5.13.

Hint 2. For (

\Leftarrow

), take a relation

𝑎_{1} 𝐯_{1} +

\dots +

𝑎_{𝑘} 𝐯_{𝑘} +

𝑏 𝐰 =

𝟎

, and split into the cases

𝑏 \neq 0

and

𝑏 = 0

Sketch. If

𝐰 \in span (ℒ︀)

, the last entry of

ℒ︀, 𝐰

lies in the span of the earlier ones. Conversely, in a relation

\sum 𝑎_{𝑖} 𝐯_{𝑖} + 𝑏 𝐰 = 𝟎

, a nonzero

𝑏

would give

𝐰 =

\sum (- 𝑎_{𝑖} / 𝑏) 𝐯_{𝑖} \in

span (ℒ︀)

; so

𝑏 = 0

, and then all

𝑎_{𝑖} = 0

by independence of

ℒ︀

Write $ℒ︀ = 𝐯_{1}, \dots, 𝐯_{𝑘}$ .

( $\Rightarrow$ ) If $𝐰 \in span (ℒ︀)$ , then the last entry of $ℒ︀, 𝐰$ lies in the span of the entries before it, so $ℒ︀, 𝐰$ is dependent by Corollary 1.5.13.

( $\Leftarrow$ ) Suppose that $𝐰 \notin span (ℒ︀)$ , and let $𝑎_{1} 𝐯_{1} +$ $\dots +$ $𝑎_{𝑘} 𝐯_{𝑘} +$ $𝑏 𝐰 =$ $𝟎$ . If $𝑏 \neq 0$ , then, as in the proof of Lemma 1.5.10,

𝐰 = \sum_{𝑖 = 1}^{𝑘} (- \frac{𝑎_{𝑖}}{𝑏}) 𝐯_{𝑖} \in span (ℒ︀),

a contradiction. So $𝑏 = 0$ , and $𝑎_{1} 𝐯_{1} +$ $\dots +$ $𝑎_{𝑘} 𝐯_{𝑘} =$ $𝟎$ . Since $ℒ︀$ is independent, all $𝑎_{𝑖} = 0$ by Theorem 1.5.5. So the relation is trivial, and $ℒ︀, 𝐰$ is independent. □

So an independent list that does not span $𝑉$ can always be lengthened, keeping it independent: append any vector outside its span. Repeating this is how independent lists are extended to bases in Section 4.1 (Theorem 4.1.16). Whether the process stops is a real question. In $𝐹 [𝑥]$ it never does: $𝑥^{𝑛 + 1} \notin$ $span (1, 𝑥, \dots, 𝑥^{𝑛})$ , since every polynomial in that span has degree at most $𝑛$ (Example 1.3.11), so appending the next power of $𝑥$ never stops.

1.5.4First consequences

Proposition 1.5.15 (Short lists, zeros, and repeats). Let $𝑉$ be a vector space over $𝐹$ .

(a)The empty list $()$ is linearly independent.
(b)A list $𝐯$ of length one is linearly independent if and only if $𝐯 \neq 𝟎$ .
(c)A list containing $𝟎$ is linearly dependent. A list with a repeated entry, $𝐯_{𝑖} = 𝐯_{𝑗}$ for some $𝑖 \neq 𝑗$ , is linearly dependent.
(d)A list $𝐯, 𝐰$ of length two is linearly dependent if and only if one of $𝐯$ , $𝐰$ is a scalar multiple of the other.

Proof.routine

Uses. Theorem 1.5.5 (Independence is decided at zero), Proposition 1.2.35 (Zero products), Proposition 1.2.32 (The scalar zero), Proposition 1.2.33 (The zero vector), Proposition 1.2.34 (Negatives and the scalar $- 1$ )

Hint 1. Use (II) of Theorem 1.5.5 throughout. For dependence, write down a nontrivial relation; for independence, start from an arbitrary relation.

Hint 2. For (b) and the forward direction of (d), the key fact is that

𝑎 𝐯 = 𝟎

forces

𝑎 = 0

𝐯 = 𝟎

(Proposition 1.2.35).

Hint 3. In (d), given

𝑎 𝐯 + 𝑏 𝐰 = 𝟎

with

(𝑎, 𝑏) \neq (0, 0)

, split into the cases

𝑎 \neq 0

and

𝑎 = 0

Sketch. (a) The only relation of

()

is trivial. (b)

1 𝟎 = 𝟎

is nontrivial; if

𝐯 \neq 𝟎

, then

𝑎 𝐯 = 𝟎

forces

𝑎 = 0

. (c)

1 𝟎 = 𝟎

and

𝐯_{𝑖} - 𝐯_{𝑗} = 𝟎

, padded with zero coefficients. (d)

𝐯 = 𝑐 𝐰

gives the relation

𝐯 - 𝑐 𝐰 = 𝟎

; conversely, from

𝑎 𝐯 + 𝑏 𝐰 = 𝟎

with

𝑎 \neq 0

we get

𝐯 = (- 𝑏 / 𝑎) 𝐰

, and with

𝑎 = 0

we get

𝑏 𝐰 = 𝟎

𝑏 \neq 0

, so

𝐰 = 𝟎 = 0 𝐯

We use (II) of Theorem 1.5.5.

(a) The only linear relation of $()$ is the empty one, which is trivial.

(b) If $𝐯 = 𝟎$ , then $1 𝐯 = 𝟎$ by Proposition 1.2.33, a nontrivial relation. If $𝐯 \neq 𝟎$ and $𝑎 𝐯 = 𝟎$ , then $𝑎 = 0$ by Proposition 1.2.35, so the only relation is trivial.

(c) If $𝐯_{𝑗} = 𝟎$ , the linear combination with coefficient $1$ on $𝐯_{𝑗}$ and $0$ elsewhere represents $1 𝟎 = 𝟎$ , by Proposition 1.2.33 and Proposition 1.2.32; it is a nontrivial relation. If $𝐯_{𝑖} = 𝐯_{𝑗}$ with $𝑖 \neq 𝑗$ , the linear combination with coefficient $1$ on $𝐯_{𝑖}$ , $- 1$ on $𝐯_{𝑗}$ , and $0$ elsewhere represents $𝐯_{𝑖} + (- 𝐯_{𝑖}) = 𝟎$ , by Proposition 1.2.34; it is nontrivial as well.

(d) If $𝐯 = 𝑐 𝐰$ , then $1 𝐯 +$ $(- 𝑐) 𝐰 =$ $𝑐 𝐰 +$ $(- 𝑐 𝐰) =$ $𝟎$ is a nontrivial relation; similarly if $𝐰 = 𝑐 𝐯$ . Conversely, suppose that $𝑎 𝐯 + 𝑏 𝐰 = 𝟎$ with $𝑎$ and $𝑏$ not both $0$ . If $𝑎 \neq 0$ , then $𝐯 = (- 𝑏 / 𝑎) 𝐰$ , by the argument in the proof of Lemma 1.5.10. If $𝑎 = 0$ , then $𝑏 \neq 0$ and $𝑏 𝐰 = 𝟎$ , so $𝐰 = 𝟎 = 0 𝐯$ by Proposition 1.2.35 and Proposition 1.2.32. Either way, one vector is a multiple of the other. □

In (d), “one of them is a multiple of the other” cannot be strengthened to “each is a multiple of the other”. If $𝐯 \neq 𝟎$ , the list $𝐯, 𝟎$ is dependent, and $𝟎 = 0 𝐯$ , but $𝐯$ is not a multiple of $𝟎$ . In $ℝ^{2}$ , (d) says that two vectors are dependent exactly when they lie on a common line through the origin. Part (c) shows once more that independence belongs to lists: the list $𝐯, 𝐯$ is dependent, although its set of entries is ${𝐯}$ .

Exercise 1.5.16.routine Find the error in the following argument.

Claim. Let $𝐯_{1}, 𝐯_{2}, 𝐯_{3} \in 𝑉$ , and suppose that none of them is a scalar multiple of another. Then $𝐯_{1}, 𝐯_{2}, 𝐯_{3}$ is linearly independent.

Proof. Suppose that $𝑎_{1} 𝐯_{1} +$ $𝑎_{2} 𝐯_{2} +$ $𝑎_{3} 𝐯_{3} =$ $𝟎$ and that some $𝑎_{𝑖} \neq 0$ , say $𝑎_{1} \neq 0$ . Then $𝐯_{1} =$ $(- 𝑎_{2} / 𝑎_{1}) 𝐯_{2} +$ $(- 𝑎_{3} / 𝑎_{1}) 𝐯_{3}$ , so $𝐯_{1}$ is a scalar multiple of $𝐯_{2}$ or of $𝐯_{3}$ , a contradiction. So all $𝑎_{𝑖} = 0$ .

Solution.

Uses. Proposition 1.5.15 (Short lists, zeros, and repeats), Theorem 1.5.5 (Independence is decided at zero)

Techniques. Finding counterexamples and minimal examples (Technique 1.4.18)

Hint 1. Which step turns a linear combination of two vectors into a multiple of one of them?

Hint 2. Test the claim on

(1, 0), (0, 1), (1, 1)

ℝ^{2}

Sketch. A combination of

𝐯_{2}

and

𝐯_{3}

with both coefficients nonzero need not be a multiple of either. The list

(1, 0), (0, 1), (1, 1)

satisfies the hypothesis but has the relation

(1, 0) +

(0, 1) -

(1, 1) =

𝟎

The error is the step “so $𝐯_{1}$ is a scalar multiple of $𝐯_{2}$ or of $𝐯_{3}$ ”. It holds when $𝑎_{2} = 0$ or $𝑎_{3} = 0$ , but a linear combination of $𝐯_{2}$ and $𝐯_{3}$ with both coefficients nonzero is in general a multiple of neither.

The claim is false. In $ℝ^{2}$ , no two of $(1, 0)$ , $(0, 1)$ , $(1, 1)$ are multiples of each other: their coordinates show that $(0, 1)$ and $(1, 1)$ are not multiples of $(1, 0)$ , and so on. But $(1, 0) +$ $(0, 1) +$ $(- 1) (1, 1) =$ $𝟎$ is a dependence relation. For two vectors the claim is correct (Proposition 1.5.15(d)), and the argument above is a valid proof in that case.

Corollary 1.5.17 (Sublists). Every sublist of a linearly independent list is linearly independent. Equivalently, if some sublist of a list

ℒ︀

is linearly dependent, then

ℒ︀

is linearly dependent.

Proof.routine

Uses. Theorem 1.5.5 (Independence is decided at zero), Proposition 1.2.32 (The scalar zero), Notation 1.3.3

Techniques. Contrapositive (Technique 1.5.4)

Hint 1. Use (II) of Theorem 1.5.5. A relation of the sublist uses only some of the entries of

ℒ︀

Hint 2. Extend the coefficients of a relation of the sublist by

0

on the entries of

ℒ︀

that were deleted.

Sketch. A relation

\sum_{𝑟} 𝑐_{𝑟} 𝐯_{𝑖_{𝑟}} = 𝟎

of the sublist, padded with zero coefficients on the deleted entries, is a relation of

ℒ︀

, so all its coefficients are

0

. The second statement is the contrapositive of the first.

Let $ℒ︀ = 𝐯_{1}, \dots, 𝐯_{𝑘}$ be linearly independent, and let ${ℒ︀}^{'} =$ $𝐯_{𝑖_{1}},$ $\dots,$ $𝐯_{𝑖_{𝑚}}$ be a sublist, with $𝑖_{1} < \dots < 𝑖_{𝑚}$ . Suppose that $𝑐_{1} 𝐯_{𝑖_{1}} +$ $\dots +$ $𝑐_{𝑚} 𝐯_{𝑖_{𝑚}} =$ $𝟎$ . Define $𝑎_{𝑖} = 𝑐_{𝑟}$ if $𝑖 = 𝑖_{𝑟}$ , and $𝑎_{𝑖} = 0$ if $𝑖$ is not one of $𝑖_{1}, \dots, 𝑖_{𝑚}$ . In $\sum_{𝑖 = 1}^{𝑘} 𝑎_{𝑖} 𝐯_{𝑖}$ , the terms with $𝑖 = 𝑖_{𝑟}$ are $𝑐_{𝑟} 𝐯_{𝑖_{𝑟}}$ , in the same order as in the relation, and the other terms are $0 𝐯_{𝑖} = 𝟎$ by Proposition 1.2.32. So

\sum_{𝑖 = 1}^{𝑘} 𝑎_{𝑖} 𝐯_{𝑖} = \sum_{𝑟 = 1}^{𝑚} 𝑐_{𝑟} 𝐯_{𝑖_{𝑟}} = 𝟎 .

Since $ℒ︀$ is independent, every $𝑎_{𝑖} = 0$ by Theorem 1.5.5; in particular $𝑐_{𝑟} = 𝑎_{𝑖_{𝑟}} = 0$ for every $𝑟$ . So ${ℒ︀}^{'}$ has only the trivial relation, and it is independent.

The second statement is the contrapositive of the first. □

The corollary goes in one direction only. A dependent list can have independent sublists, such as $(1, 0), (0, 1)$ inside the dependent list $(1, 0), (0, 1), (1, 1)$ . The corollary also gives a second proof of Proposition 1.5.15(c): a list containing $𝟎$ has the dependent sublist $𝟎$ , and a list with $𝐯_{𝑖} = 𝐯_{𝑗}$ for $𝑖 < 𝑗$ has the dependent sublist $𝐯_{𝑖}, 𝐯_{𝑗}$ , by Proposition 1.5.15(b) and (d).

The span of a list is unchanged by the moves of Corollary 1.3.20(a) and (d). These moves preserve independence too, and they are the moves of row reduction (Section 3.3).

Proposition 1.5.18 (Operations that preserve independence). Let $ℒ︀ = 𝐯_{1}, \dots, 𝐯_{𝑘}$ be a list in $𝑉$ , and let ${ℒ︀}^{'}$ be obtained from $ℒ︀$ by one of the following operations:

(a)reordering the entries;
(b)replacing $𝐯_{𝑗}$ by $𝑐 𝐯_{𝑗}$ , where $𝑐 \neq 0$ ;
(c)replacing $𝐯_{𝑗}$ by $𝐯_{𝑗} + 𝑎 𝐯_{𝑖}$ , where $𝑖 \neq 𝑗$ and $𝑎 \in 𝐹$ .

Then $span ({ℒ︀}^{'}) =$ $span (ℒ︀)$ , and ${ℒ︀}^{'}$ is linearly independent if and only if $ℒ︀$ is.

Proof.routine

Uses. Corollary 1.3.20 (Operations that preserve the span), Theorem 1.5.5 (Independence is decided at zero), Proposition 1.1.17 (No zero divisors), Lemma 1.3.9 (Arithmetic of linear combinations)

Hint 1. The spans are handled by Corollary 1.3.20. For independence, it suffices to show that if

ℒ︀

is independent then so is

{ℒ︀}^{'}

: each operation can be undone by an operation of the same kind.

Hint 2. Take a relation of

{ℒ︀}^{'}

, expand the modified entry, and collect coefficients to get a relation of

ℒ︀

. Then read off what independence of

ℒ︀

says.

Sketch. Spans: Corollary 1.3.20(a) and (d). Each operation is undone by one of the same kind: reorder back, scale by

𝑐^{- 1}

, add

- 𝑎 𝐯_{𝑖}

. So it suffices to show that

ℒ︀

independent implies

{ℒ︀}^{'}

independent. A relation of

{ℒ︀}^{'}

becomes a relation of

ℒ︀

with coefficient

𝑏_{𝑗} 𝑐

𝐯_{𝑗}

in (b), and with coefficients

𝑏_{𝑖} + 𝑎 𝑏_{𝑗}

𝐯_{𝑖}

and

𝑏_{𝑗}

𝐯_{𝑗}

in (c). Independence of

ℒ︀

makes these

0

, which forces every

𝑏_{𝑙} = 0

The spans agree by Corollary 1.3.20(a) and (d). Each operation can be undone by an operation of the same kind: a reordering by the reverse reordering, the scaling by $𝑐$ by the scaling by $𝑐^{- 1}$ , and the replacement of $𝐯_{𝑗}$ by $𝐯_{𝑗} + 𝑎 𝐯_{𝑖}$ by the replacement of the new $𝑗$ -th entry by itself plus $(- 𝑎) 𝐯_{𝑖}$ , which is allowed since $𝐯_{𝑖}$ is still an entry of ${ℒ︀}^{'}$ (as $𝑖 \neq 𝑗$ ). So it suffices to show that if $ℒ︀$ is independent, then so is ${ℒ︀}^{'}$ . Suppose that $ℒ︀$ is independent, and take a linear relation of ${ℒ︀}^{'}$ . We use (II) of Theorem 1.5.5.

(a) The coefficients of the relation, attached to the entries of $ℒ︀$ in their original positions, give a linear combination of $ℒ︀$ with the same terms in a different order. By (A1) and (A2) it also represents $𝟎$ , so all its coefficients are $0$ .

(b) Let the relation be $\sum_{𝑙 \neq 𝑗} 𝑏_{𝑙} 𝐯_{𝑙} +$ $𝑏_{𝑗} (𝑐 𝐯_{𝑗}) =$ $𝟎$ . By (A6), $𝑏_{𝑗} (𝑐 𝐯_{𝑗}) =$ $(𝑏_{𝑗} 𝑐) 𝐯_{𝑗}$ , so this is the linear combination of $ℒ︀$ with coefficient $𝑏_{𝑗} 𝑐$ on $𝐯_{𝑗}$ and $𝑏_{𝑙}$ on $𝐯_{𝑙}$ for $𝑙 \neq 𝑗$ . By independence of $ℒ︀$ , $𝑏_{𝑙} = 0$ for $𝑙 \neq 𝑗$ and $𝑏_{𝑗} 𝑐 = 0$ . Since $𝑐 \neq 0$ , $𝑏_{𝑗} = 0$ by Proposition 1.1.17.

(c) Let the relation be $\sum_{𝑙 \neq 𝑗} 𝑏_{𝑙} 𝐯_{𝑙} +$ $𝑏_{𝑗} (𝐯_{𝑗} + 𝑎 𝐯_{𝑖}) =$ $𝟎$ . By (A7), (A6), and Lemma 1.3.9, the left side is the linear combination of $ℒ︀$ with coefficient $𝑏_{𝑖} + 𝑏_{𝑗} 𝑎$ on $𝐯_{𝑖}$ , $𝑏_{𝑗}$ on $𝐯_{𝑗}$ , and $𝑏_{𝑙}$ on $𝐯_{𝑙}$ for $𝑙 \neq 𝑖, 𝑗$ . By independence of $ℒ︀$ , all of these are $0$ . So $𝑏_{𝑗} = 0$ , then $𝑏_{𝑖} =$ $𝑏_{𝑖} +$ $𝑏_{𝑗} 𝑎 =$ $0$ , and $𝑏_{𝑙} = 0$ for the remaining $𝑙$ . □

Both hypotheses are needed, as they were for the span: replacing $𝐯_{𝑗}$ by $0 𝐯_{𝑗}$ , or by $𝐯_{𝑗} + (- 1) 𝐯_{𝑗}$ , puts $𝟎$ into the list.

1.5.5Changing the field

A linear relation is a statement about scalars, so whether a list is independent depends on which scalars are allowed. In Example 1.5.6 the same coordinates gave an independent list in $ℝ^{2}$ and a dependent one in $𝔽_{3}^{2}$ , but these are different vector spaces. More striking is a single set of vectors, viewed over two fields.

Example 1.5.19 (The same vectors over two fields).

(a) $ℂ$ is a vector space over $ℂ$ and, by restricting scalars, over $ℝ$ (Example 1.2.20). Over $ℂ$ , the list $1, 𝑖$ is dependent, since $𝑖 \cdot 1 + (- 1) \cdot 𝑖 = 0$ . Over $ℝ$ it is independent: if $𝑎 \cdot 1 + 𝑏 \cdot 𝑖 = 0$ with $𝑎, 𝑏 \in ℝ$ , then $𝑎 + 𝑏 𝑖 = 0$ , so $𝑎 = 𝑏 = 0$ by Definition 1.1.29.
(b)Regard $ℝ$ as a vector space over $ℚ$ . The list $1, \sqrt{2}$ is independent over $ℚ$ : if $𝑎 + 𝑏 \sqrt{2} = 0$ with $𝑎, 𝑏 \in ℚ$ and $𝑏 \neq 0$ , then $\sqrt{2} = - 𝑎 / 𝑏$ would be rational; so $𝑏 = 0$ , and then $𝑎 = 0$ . Over $ℝ$ the same list is dependent, since $\sqrt{2} \cdot 1 + (- 1) \sqrt{2} = 0$ .
(c)In $ℂ^{2}$ , the list $(1, 𝑖), (𝑖, - 1)$ is dependent over $ℂ$ , since $(𝑖, - 1) = 𝑖 (1, 𝑖)$ . Over $ℝ$ it is independent: for $𝑎, 𝑏 \in ℝ$ ,
$𝑎 (1, 𝑖) + 𝑏 (𝑖, - 1) = (𝑎 + 𝑏 𝑖, - 𝑏 + 𝑎 𝑖),$
and this is $𝟎$ only if $𝑎 + 𝑏 𝑖 = 0$ , that is, $𝑎 = 𝑏 = 0$ .

In each case the list was independent over the smaller field and dependent over the larger one. The opposite never happens.

Proposition 1.5.20 (Fewer scalars, fewer relations). Let

𝐾

be a subfield of

𝐹

, and regard

𝑉

as a vector space over

𝐾

as well (Proposition 1.2.19). If a list in

𝑉

is linearly independent over

𝐹

, then it is linearly independent over

𝐾

Proof.routine

Uses. Proposition 1.2.19 (Restriction of scalars), Theorem 1.5.5 (Independence is decided at zero)

Hint 1. Compare the linear relations over

𝐾

with those over

𝐹

Hint 2. Scalar multiplication over

𝐾

is that of

𝐹

, restricted to

𝐾

Sketch. A linear relation over

𝐾

has coefficients in

𝐾 \subseteq 𝐹

and is computed with the same operations, so it is a linear relation over

𝐹

, hence trivial.

Let

ℒ︀ = 𝐯_{1}, \dots, 𝐯_{𝑘}

be independent over

𝐹

, and let

𝑎_{1}, \dots, 𝑎_{𝑘} \in 𝐾

with

𝑎_{1} 𝐯_{1} +

\dots +

𝑎_{𝑘} 𝐯_{𝑘} =

𝟎

. The scalar multiplication of the

𝐾

-vector space

𝑉

is that of

𝐹

restricted to

𝐾

, and the addition is the same, so

𝑎_{1}, \dots, 𝑎_{𝑘}

is also a linear relation of

ℒ︀

over

𝐹

. By Theorem 1.5.5, all

𝑎_{𝑖} = 0

. So

ℒ︀

is independent over

𝐾

. □

The converse fails, as Example 1.5.19 shows. In each of those examples, though, the vectors themselves involved the larger field: $𝑖$ , $\sqrt{2}$ , and $(𝑖, - 1)$ . For vectors whose coordinates lie in the smaller field, the extra scalars bring no new relations.

Intuition. Let

ℒ︀

be a list of real vectors. Viewed in

ℂ^{𝑚}

, it has more candidate relations, with complex coefficients. But a complex relation splits into its real and imaginary parts, and because the entries of

ℒ︀

are real, each part is a real relation by itself.

Proposition 1.5.21 (Real lists in

ℂ^{𝑚}

). Let

ℒ︀ = 𝐯_{1}, \dots, 𝐯_{𝑘}

be a list in

ℝ^{𝑚}

. Then

ℒ︀

is linearly independent in the real vector space

ℝ^{𝑚}

if and only if it is linearly independent in the complex vector space

ℂ^{𝑚}

Proof.standard

Uses. Theorem 1.5.5 (Independence is decided at zero), Definition 1.1.29 (Complex numbers), Definition 1.2.4 (The space $𝐹^{𝑛}$ )

Hint 1. One direction holds because every real relation is a complex relation.

Hint 2. For the other, write each complex coefficient as

𝑐_{𝑗} = 𝑎_{𝑗} + 𝑏_{𝑗} 𝑖

with

𝑎_{𝑗}, 𝑏_{𝑗} \in ℝ

, and look at one coordinate of the relation at a time.

Hint 3. In the

𝑡

-th coordinate,

\sum_{𝑗} 𝑐_{𝑗} 𝑣_{𝑗 𝑡} =

\sum_{𝑗} 𝑎_{𝑗} 𝑣_{𝑗 𝑡} +

(\sum_{𝑗} 𝑏_{𝑗} 𝑣_{𝑗 𝑡}) 𝑖

with both sums real. When is a complex number

0

Sketch. (

\Leftarrow

) A real relation is a complex one. (

\Rightarrow

) If

\sum 𝑐_{𝑗} 𝐯_{𝑗} = 𝟎

with

𝑐_{𝑗} = 𝑎_{𝑗} + 𝑏_{𝑗} 𝑖

, then in each coordinate

𝑡

the real and imaginary parts give

\sum 𝑎_{𝑗} 𝑣_{𝑗 𝑡} = 0

and

\sum 𝑏_{𝑗} 𝑣_{𝑗 𝑡} = 0

, since the

𝑣_{𝑗 𝑡}

are real. So

\sum 𝑎_{𝑗} 𝐯_{𝑗} =

\sum 𝑏_{𝑗} 𝐯_{𝑗} =

𝟎

ℝ^{𝑚}

, and independence over

ℝ

gives

𝑎_{𝑗} = 𝑏_{𝑗} = 0

The operations of $ℂ^{𝑚}$ , applied to real vectors and real scalars, agree with those of $ℝ^{𝑚}$ , since $ℝ$ is a subfield of $ℂ$ . Write $𝑣_{𝑗 𝑡} \in ℝ$ for the $𝑡$ -th coordinate of $𝐯_{𝑗}$ .

( $\Leftarrow$ ) Suppose that $ℒ︀$ is independent in $ℂ^{𝑚}$ , and let $𝑎_{1}, \dots, 𝑎_{𝑘} \in ℝ$ with $\sum_{𝑗} 𝑎_{𝑗} 𝐯_{𝑗} = 𝟎$ in $ℝ^{𝑚}$ . This equation also holds in $ℂ^{𝑚}$ , with the real numbers $𝑎_{𝑗}$ regarded as complex scalars, so all $𝑎_{𝑗} = 0$ by Theorem 1.5.5.

( $\Rightarrow$ ) Suppose that $ℒ︀$ is independent in $ℝ^{𝑚}$ , and let $𝑐_{1}, \dots, 𝑐_{𝑘} \in ℂ$ with $\sum_{𝑗} 𝑐_{𝑗} 𝐯_{𝑗} = 𝟎$ in $ℂ^{𝑚}$ . Write $𝑐_{𝑗} = 𝑎_{𝑗} + 𝑏_{𝑗} 𝑖$ with $𝑎_{𝑗}, 𝑏_{𝑗} \in ℝ$ . Fix a coordinate $𝑡 \in {1, \dots, 𝑚}$ . Since each $𝑣_{𝑗 𝑡}$ is real, $𝑐_{𝑗} 𝑣_{𝑗 𝑡} =$ $𝑎_{𝑗} 𝑣_{𝑗 𝑡} +$ $(𝑏_{𝑗} 𝑣_{𝑗 𝑡}) 𝑖$ , and the $𝑡$ -th coordinate of the relation reads

0 = \sum_{𝑗 = 1}^{𝑘} 𝑐_{𝑗} 𝑣_{𝑗 𝑡} = (\sum_{𝑗 = 1}^{𝑘} 𝑎_{𝑗} 𝑣_{𝑗 𝑡}) + (\sum_{𝑗 = 1}^{𝑘} 𝑏_{𝑗} 𝑣_{𝑗 𝑡}) 𝑖,

where both sums in parentheses are real numbers. By Definition 1.1.29, a complex number $𝑥 + 𝑦 𝑖$ with $𝑥, 𝑦 \in ℝ$ is $0$ only if $𝑥 = 𝑦 = 0$ . So both sums vanish for every $𝑡$ , which says that

𝑎_{1} 𝐯_{1} + \dots + 𝑎_{𝑘} 𝐯_{𝑘} = 𝟎 and 𝑏_{1} 𝐯_{1} + \dots + 𝑏_{𝑘} 𝐯_{𝑘} = 𝟎 in ℝ^{𝑚} .

Since $ℒ︀$ is independent in $ℝ^{𝑚}$ , all $𝑎_{𝑗}$ and $𝑏_{𝑗}$ are $0$ , so all $𝑐_{𝑗} = 0$ . By Theorem 1.5.5, $ℒ︀$ is independent in $ℂ^{𝑚}$ . □

Exercise 1.5.22.routine Decide whether

(1, 1 + 𝑖), (1 - 𝑖, 2)

is linearly independent in

ℂ^{2}

over

ℂ

, and over

ℝ

. Does this contradict Proposition 1.5.21?

Solution.

Uses. Proposition 1.5.15 (Short lists, zeros, and repeats), Theorem 1.5.5 (Independence is decided at zero), Definition 1.1.29 (Complex numbers), Proposition 1.5.21 (Real lists in $ℂ^{𝑚}$ )

Hint 1. Over

ℂ

, is the second vector a complex multiple of the first? Compare first coordinates to find the only candidate.

Hint 2. Over

ℝ

, write

𝑎 (1, 1 + 𝑖) +

𝑏 (1 - 𝑖, 2) =

𝟎

with

𝑎, 𝑏

real, and take the real and imaginary parts of the first coordinate.

Sketch.

(1 - 𝑖) (1, 1 + 𝑖) =

(1 - 𝑖, 2)

, so the list is dependent over

ℂ

. Over

ℝ

, the first coordinate

𝑎 + 𝑏 - 𝑏 𝑖

of a relation must vanish, which forces

𝑏 = 0

and

𝑎 = 0

. No contradiction: the vectors are not real.

Over $ℂ$ :

(1 - 𝑖) (1, 1 + 𝑖) = (1 - 𝑖, (1 - 𝑖) (1 + 𝑖)) = (1 - 𝑖, 1 - 𝑖^{2}) = (1 - 𝑖, 2) .

So the second vector is a multiple of the first, and the list is dependent by Proposition 1.5.15(d).

Over $ℝ$ : let $𝑎, 𝑏 \in ℝ$ with $𝑎 (1, 1 + 𝑖) +$ $𝑏 (1 - 𝑖, 2) =$ $𝟎$ . The first coordinate is $𝑎 +$ $𝑏 (1 - 𝑖) =$ $(𝑎 + 𝑏) +$ $(- 𝑏) 𝑖$ , which is $0$ only if $𝑎 + 𝑏 = 0$ and $- 𝑏 = 0$ , by Definition 1.1.29. So $𝑎 = 𝑏 = 0$ , and the list is independent over $ℝ$ .

This does not contradict Proposition 1.5.21, which concerns lists of vectors with real coordinates. Here the coordinates $1 + 𝑖$ and $1 - 𝑖$ are not real.

Remark 1.5.23 (Rational and real scalars). The analogue of Proposition 1.5.21 holds for

ℚ \subseteq ℝ

: a list in

ℚ^{𝑚}

is independent over

ℚ

if and only if it is independent over

ℝ

. It holds for every subfield

𝐾

of a field

𝐸

(Exercise 1.5.42). The proof above does not carry over directly. It split each complex coefficient into two real ones, which works because every complex number is a real linear combination of

1

and

𝑖

. No finite list of real numbers spans

ℝ

over

ℚ

(Exercise 1.3.45), so there is no such splitting of real coefficients into rational ones. The proof in Exercise 1.5.42 uses only the finitely many real numbers that occur as coefficients in one relation.

1.5.6Polynomials and functions

In a space of functions, a linear relation is an identity that holds at every point. So to prove independence we may evaluate at any points we like, or compare other data that the functions determine, such as their behavior for large $𝑡$ . For polynomials, which are coefficient sequences rather than functions, the data to compare are the coefficients.

Intuition. Among polynomials of different degrees, the one of largest degree has a leading term that the others cannot cancel. So a nontrivial combination of them has a nonzero top coefficient. Choosing the largest degree is the extremal move of Technique 1.5.9.

Proposition 1.5.24 (Distinct degrees). Let

𝑝_{1}, \dots, 𝑝_{𝑘} \in 𝐹 [𝑥]

be nonzero polynomials with distinct degrees. Then

𝑝_{1}, \dots, 𝑝_{𝑘}

is linearly independent.

Proof.standard

Uses. Theorem 1.5.5 (Independence is decided at zero), Definition 1.2.13 (Polynomials), Definition 1.2.16 (Degree), Proposition 1.1.17 (No zero divisors)

Techniques. Extremal choice and minimal counterexamples (Technique 1.5.9)

Hint 1. Suppose that a nontrivial combination

𝑎_{1} 𝑝_{1} + \dots + 𝑎_{𝑘} 𝑝_{𝑘}

is the zero polynomial. Among the indices with

𝑎_{𝑖} \neq 0

, choose one for which

deg 𝑝_{𝑖}

is as large as possible.

Hint 2. Compute the coefficient of the combination in position

𝑑 = deg 𝑝_{𝑖}

. Which terms can contribute to it?

Sketch. Suppose

\sum 𝑎_{𝑖} 𝑝_{𝑖} = 𝟎

with some

𝑎_{𝑖} \neq 0

. Among those

𝑖

, take the one with the largest degree

𝑑

. Every other

𝑎_{𝑙} 𝑝_{𝑙}

𝟎

or has degree less than

𝑑

, so the coefficient of the sum in position

𝑑

𝑎_{𝑖}

times the leading coefficient of

𝑝_{𝑖}

, which is nonzero. Contradiction.

Suppose, to the contrary, that

𝑎_{1} 𝑝_{1} +

\dots +

𝑎_{𝑘} 𝑝_{𝑘} =

𝟎

with not all

𝑎_{𝑖} = 0

. Among the indices

𝑖

with

𝑎_{𝑖} \neq 0

, choose one for which

𝑑 = deg 𝑝_{𝑖}

is largest; since the degrees are distinct, it is unique. Let

𝑐 \neq 0

be the leading coefficient of

𝑝_{𝑖}

. The operations of

𝐹 [𝑥]

are coefficientwise (Definition 1.2.13), so the coefficient of the sum in position

𝑑

is the sum of the coefficients of the

𝑎_{𝑙} 𝑝_{𝑙}

in position

𝑑

. For

𝑙 = 𝑖

this is

𝑎_{𝑖} 𝑐

. For

𝑙 \neq 𝑖

with

𝑎_{𝑙} \neq 0

, we have

deg 𝑝_{𝑙} < 𝑑

by the choice of

𝑖

, so the coefficient of

𝑝_{𝑙}

in position

𝑑

0

, and so is that of

𝑎_{𝑙} 𝑝_{𝑙}

. For

𝑙

with

𝑎_{𝑙} = 0

𝑎_{𝑙} 𝑝_{𝑙} = 𝟎

. So the coefficient of

𝑎_{1} 𝑝_{1} + \dots + 𝑎_{𝑘} 𝑝_{𝑘}

in position

𝑑

𝑎_{𝑖} 𝑐

, which is nonzero by Proposition 1.1.17. This contradicts

𝑎_{1} 𝑝_{1} +

\dots +

𝑎_{𝑘} 𝑝_{𝑘} =

𝟎

. By Theorem 1.5.5, the list is independent. □

For example, $1, 1 + 𝑥, 1 + 𝑥 + 𝑥^{2}$ and $1, 𝑥 - 1, 𝑥^{2} - 2 𝑥 + 1$ are linearly independent in $𝐹 [𝑥]$ over every field. The hypothesis matters: $𝑥^{2} + 𝑥, 𝑥^{2} - 𝑥, 𝑥$ has two entries of degree $2$ , and it is dependent, since $(𝑥^{2} + 𝑥) -$ $(𝑥^{2} - 𝑥) +$ $(- 2) 𝑥 =$ $𝟎$ .

Example 1.5.25 (Polynomials versus polynomial functions). Over $𝔽_{2}$ , the list $𝑥, 𝑥^{2}$ is linearly independent in $𝔽_{2} [𝑥]$ , by Proposition 1.5.24. Their polynomial functions $𝔽_{2} \to 𝔽_{2}$ are $𝑐 \mapsto 𝑐$ and $𝑐 \mapsto 𝑐^{2}$ , and these are the same function, since $0^{2} = 0$ and $1^{2} = 1$ . So in the vector space $𝔽_{2}^{𝔽_{2}}$ the two functions form a list with a repeated entry, which is dependent (Proposition 1.5.15(c)). The same “polynomials” are independent in one vector space and dependent in another, as Aside (Polynomials versus polynomial functions) warned.

Over an infinite field this cannot happen. If $𝑎_{1}, \dots, 𝑎_{𝑘}$ is a linear relation among the polynomial functions of $𝑝_{1}, \dots, 𝑝_{𝑘}$ , then the polynomial $𝑞 =$ $𝑎_{1} 𝑝_{1} +$ $\dots +$ $𝑎_{𝑘} 𝑝_{𝑘}$ satisfies $𝑞 (𝑐) = 0$ for every $𝑐 \in 𝐹$ (Proposition 1.2.18(c)). A nonzero polynomial has only finitely many roots (Proposition 7.1.22), so $𝑞 = 𝟎$ , and $𝑎_{1}, \dots, 𝑎_{𝑘}$ is a linear relation among the polynomials themselves.

Example 1.5.26 (Trigonometric functions). In $ℝ^{ℝ}$ , the list $sin, cos$ is linearly independent. Suppose that $𝑎 sin + 𝑏 cos = 𝟎$ , the zero function. Then $𝑎 sin 𝑡 + 𝑏 cos 𝑡 = 0$ for every $𝑡 \in ℝ$ . At $𝑡 = 0$ this reads $𝑏 = 0$ , and at $𝑡 = 𝜋 / 2$ it reads $𝑎 = 0$ .

On the other hand, $1, {sin}^{2}, {cos}^{2}$ (where ${sin}^{2}$ is the function $𝑡 \mapsto {(sin 𝑡)}^{2}$ ) is dependent, since ${sin}^{2} 𝑡 + {cos}^{2} 𝑡 - 1 = 0$ for every $𝑡$ .

The method used for $sin, cos$ works in general. Evaluating a relation at a point $𝑡_{0}$ gives one linear equation for the coefficients, so evaluating at as many points as there are coefficients gives a system of equations. If the only solution is $0$ , the functions are independent. If the system has nonzero solutions, nothing follows: a combination that vanishes at a few points need not vanish everywhere. To prove dependence, one needs an identity valid at every point, such as ${sin}^{2} + {cos}^{2} = 1$ .

Example 1.5.27 (Exponential functions).Beyond 21-242 In

ℝ^{ℝ}

, let

𝑓_{𝑘} (𝑡) = 𝑒^{𝑘 𝑡}

for

𝑘 = 1, 2, 3

. Then

𝑓_{1}, 𝑓_{2}, 𝑓_{3}

is linearly independent. (The proofs use calculus.)

Intuition. Evaluating at three points works, but it produces equations with entries such as

𝑒^{2}

and

𝑒^{6}

that hide what is going on. Two features of exponentials give cleaner proofs. Differentiation sends each

𝑓_{𝑘}

to a multiple of itself,

𝑓_{𝑘}^{'} = 𝑘 𝑓_{𝑘}

, with a different factor for each

𝑘

; combining a relation with its derivative eliminates one term at a time. And as

𝑡 \to \infty

, the term with the largest exponent dominates all the others.

Proof (differentiate to eliminate terms).standard

Uses. Theorem 1.5.5 (Independence is decided at zero), the derivative of $𝑒^{𝑘 𝑡}$ is $𝑘 𝑒^{𝑘 𝑡}$

Techniques. Apply an operator to a relation to kill terms (Technique 4.1.25)

Hint 1. Suppose

𝑎 𝑒^{𝑡} +

𝑏 𝑒^{2 𝑡} +

𝑐 𝑒^{3 𝑡} =

0

for all

𝑡

. Differentiate this identity. Which combination of the identity and its derivative has no

𝑒^{𝑡}

term?

Hint 2. Subtract the identity from its derivative. Repeat the idea on the result to eliminate the

𝑒^{2 𝑡}

term, then evaluate at

𝑡 = 0

Sketch. From

𝑎 𝑒^{𝑡} +

𝑏 𝑒^{2 𝑡} +

𝑐 𝑒^{3 𝑡} =

0

, subtracting the identity from its derivative gives

𝑏 𝑒^{2 𝑡} +

2 𝑐 𝑒^{3 𝑡} =

0

; doing the same with factor

2

gives

2 𝑐 𝑒^{3 𝑡} = 0

. Evaluating at

𝑡 = 0

in reverse order gives

𝑐 = 0

𝑏 = 0

𝑎 = 0

Suppose that $𝑎 𝑓_{1} +$ $𝑏 𝑓_{2} +$ $𝑐 𝑓_{3} =$ $𝟎$ , that is,

𝑎 𝑒^{𝑡} + 𝑏 𝑒^{2 𝑡} + 𝑐 𝑒^{3 𝑡} = 0 for all 𝑡 \in ℝ .

Both sides are differentiable functions of $𝑡$ , and the derivative of the zero function is $0$ , so

𝑎 𝑒^{𝑡} + 2 𝑏 𝑒^{2 𝑡} + 3 𝑐 𝑒^{3 𝑡} = 0 for all 𝑡 .

Subtracting the first identity from the second eliminates the term with $𝑒^{𝑡}$ :

𝑏 𝑒^{2 𝑡} + 2 𝑐 𝑒^{3 𝑡} = 0 for all 𝑡 .

Differentiating this gives $2 𝑏 𝑒^{2 𝑡} +$ $6 𝑐 𝑒^{3 𝑡} =$ $0$ , and subtracting twice the previous identity eliminates the term with $𝑒^{2 𝑡}$ : $2 𝑐 𝑒^{3 𝑡} = 0$ for all $𝑡$ . At $𝑡 = 0$ this gives $2 𝑐 = 0$ , so $𝑐 = 0$ . Then $𝑏 𝑒^{2 𝑡} +$ $2 𝑐 𝑒^{3 𝑡} =$ $0$ at $𝑡 = 0$ gives $𝑏 = 0$ , and the first identity at $𝑡 = 0$ gives $𝑎 + 𝑏 + 𝑐 = 0$ , so $𝑎 = 0$ . By Theorem 1.5.5, $𝑓_{1}, 𝑓_{2}, 𝑓_{3}$ is independent. □

Proof (the dominant term).standard

Uses. Theorem 1.5.5 (Independence is decided at zero), $𝑒^{- 𝑠 𝑡} \to 0$ as $𝑡 \to \infty$ , for $𝑠 > 0$

Techniques. Extremal choice and minimal counterexamples (Technique 1.5.9)

Hint 1. Suppose

𝑎 𝑒^{𝑡} +

𝑏 𝑒^{2 𝑡} +

𝑐 𝑒^{3 𝑡} =

0

for all

𝑡

. Which term grows fastest as

𝑡 \to \infty

Hint 2. Divide the identity by

𝑒^{3 𝑡}

and let

𝑡 \to \infty

Sketch. Dividing by

𝑒^{3 𝑡}

gives

𝑎 𝑒^{- 2 𝑡} +

𝑏 𝑒^{- 𝑡} +

𝑐 =

0

for all

𝑡

; letting

𝑡 \to \infty

gives

𝑐 = 0

. Then divide

𝑎 𝑒^{𝑡} + 𝑏 𝑒^{2 𝑡} = 0

𝑒^{2 𝑡}

to get

𝑏 = 0

, and

𝑎 𝑒^{𝑡} = 0

gives

𝑎 = 0

Suppose that $𝑎 𝑒^{𝑡} +$ $𝑏 𝑒^{2 𝑡} +$ $𝑐 𝑒^{3 𝑡} =$ $0$ for all $𝑡 \in ℝ$ . Multiplying by $𝑒^{- 3 𝑡}$ ,

𝑎 𝑒^{- 2 𝑡} + 𝑏 𝑒^{- 𝑡} + 𝑐 = 0 for all 𝑡 .

As $𝑡 \to \infty$ , $𝑒^{- 2 𝑡} \to 0$ and $𝑒^{- 𝑡} \to 0$ , so the left side tends to $𝑐$ . It is $0$ for every $𝑡$ , so $𝑐 = 0$ . Now $𝑎 𝑒^{𝑡} + 𝑏 𝑒^{2 𝑡} = 0$ for all $𝑡$ ; multiplying by $𝑒^{- 2 𝑡}$ and letting $𝑡 \to \infty$ in the same way gives $𝑏 = 0$ . Finally $𝑎 𝑒^{𝑡} = 0$ at $𝑡 = 0$ gives $𝑎 = 0$ . □

The first proof uses only that differentiation multiplies each $𝑓_{𝑘}$ by a different factor. It adapts to sequences, with a shift in place of the derivative (Exercise 1.5.44), and Section 4.1 names the move: apply an operator to a relation to eliminate terms (Technique 4.1.25). The second proof is the analytic counterpart of Proposition 1.5.24: there the largest degree dominated, here the largest exponent. Both extend to any number of distinct exponents (Exercise 1.5.45).

Aside (Independent sets).Beyond 21-242 A subset

𝑆 \subseteq 𝑉

, possibly infinite, is called linearly independent if every list of distinct elements of

𝑆

is linearly independent. Distinctness is needed because a list with a repeated entry is never independent. For a finite set

𝑆

, this agrees with independence of any list that runs through the elements of

𝑆

once each (Proposition 1.5.18(a), Corollary 1.5.17). For example,

{1, 𝑥, 𝑥^{2}, \dots}

is linearly independent in

𝐹 [𝑥]

, since a list of distinct monomials is a reordering of a sublist of some

1, 𝑥, \dots, 𝑥^{𝑛}

(Example 1.5.7). By Exercise 1.5.45, the set of functions

𝑡 \mapsto 𝑒^{𝜆 𝑡}

𝜆 \in ℝ

, is an uncountable independent subset of

ℝ^{ℝ}

. Independent sets and spanning sets (Aside (Spans of infinite sets)) lead to bases of infinite-dimensional spaces (Section 15.1).

Exercises

Exercise 1.5.28.routine Decide whether each list in $ℝ^{3}$ is linearly independent. For each dependent list, find a dependence relation and every $𝑗$ with $𝐯_{𝑗} \in$ $span (𝐯_{1}, \dots, 𝐯_{𝑗 - 1})$ .

(a) $(1, 2, 3),$ $(4, 5, 6),$ $(7, 8, 9)$ .
(b) $(1, 1, 1),$ $(0, 1, 1),$ $(0, 0, 1)$ .
(c) $(1, - 1, 0),$ $(0, 1, - 1),$ $(- 1, 0, 1)$ .

Solution.

Uses. Theorem 1.5.5 (Independence is decided at zero), Lemma 1.5.10 (Linear dependence lemma), Proposition 1.5.15 (Short lists, zeros, and repeats)

Hint 1. Write

𝑎 𝐯_{1} +

𝑏 𝐯_{2} +

𝑐 𝐯_{3} =

𝟎

as three equations in

𝑎, 𝑏, 𝑐

, one per coordinate, and eliminate.

Hint 2. In (b), the equations can be solved from the top down. In (c), add up the three vectors.

Sketch. (a) Dependent:

𝐯_{1} - 2 𝐯_{2} + 𝐯_{3} = 𝟎

, and only

𝑗 = 3

works. (b) Independent: the relation reads

(𝑎, 𝑎 + 𝑏, 𝑎 + 𝑏 + 𝑐) =

𝟎

. (c) Dependent:

𝐯_{1} + 𝐯_{2} + 𝐯_{3} = 𝟎

, and only

𝑗 = 3

works.

(a) The relation $𝑎 (1, 2, 3) +$ $𝑏 (4, 5, 6) +$ $𝑐 (7, 8, 9) =$ $𝟎$ reads

𝑎 + 4 𝑏 + 7 𝑐 = 0, 2 𝑎 + 5 𝑏 + 8 𝑐 = 0, 3 𝑎 + 6 𝑏 + 9 𝑐 = 0 .

Subtracting twice the first equation from the second gives $- 3 𝑏 - 6 𝑐 = 0$ , so $𝑏 = - 2 𝑐$ , and then the first gives $𝑎 = - 4 𝑏 - 7 𝑐 = 𝑐$ . The third equation then holds: $3 𝑐 - 12 𝑐 + 9 𝑐 = 0$ . Taking $𝑐 = 1$ gives the dependence relation $𝐯_{1} - 2 𝐯_{2} + 𝐯_{3} = 𝟎$ , so the list is dependent. Here $𝑗 = 1$ fails as $𝐯_{1} \neq 𝟎$ , and $𝑗 = 2$ fails as $(4, 5, 6)$ is not a multiple of $(1, 2, 3)$ (the multiplier would have to be $4$ and $5 / 2$ ). The relation gives $𝑗 = 3$ : $𝐯_{3} = - 𝐯_{1} + 2 𝐯_{2}$ .

(b) A relation reads

𝑎 (1, 1, 1) + 𝑏 (0, 1, 1) + 𝑐 (0, 0, 1) = (𝑎, 𝑎 + 𝑏, 𝑎 + 𝑏 + 𝑐) = 𝟎,

which gives $𝑎 = 0$ , then $𝑏 = 0$ , then $𝑐 = 0$ . So the list is independent.

(c) The three vectors add up to $(1 + 0 - 1, - 1 + 1 + 0, 0 - 1 + 1) =$ $𝟎$ , so $1, 1, 1$ is a dependence relation. Here $𝐯_{1} \neq 𝟎$ , and $𝐯_{2} = (0, 1, - 1)$ is not a multiple of $(1, - 1, 0)$ , since a multiple $𝑡 (1, - 1, 0)$ with first coordinate $0$ has $𝑡 = 0$ . So only $𝑗 = 3$ works, with $𝐯_{3} = - 𝐯_{1} - 𝐯_{2}$ .

Exercise 1.5.29.routine For which primes

𝑝

(1, 1, 1),

(1, 2, 3),

(1, 4, 9)

linearly independent in

𝔽_{𝑝}^{3}

? Is it linearly independent in

ℚ^{3}

Solution.

Uses. Theorem 1.5.5 (Independence is decided at zero), Proposition 1.1.17 (No zero divisors), Proposition 1.5.15 (Short lists, zeros, and repeats)

Hint 1. The relation

𝑎 (1, 1, 1) +

𝑏 (1, 2, 3) +

𝑐 (1, 4, 9) =

𝟎

gives one equation per coordinate. The

𝑡

-th coordinates of the three vectors are

1

𝑡

𝑡^{2}

Hint 2. Eliminate

𝑎

, then

𝑏

. You should reach

2 𝑐 = 0

. Which primes make

2 = 0

Sketch. The equations

𝑎 + 𝑏 + 𝑐 = 0

𝑎 + 2 𝑏 + 4 𝑐 = 0

𝑎 + 3 𝑏 + 9 𝑐 = 0

reduce to

𝑏 + 3 𝑐 = 0

and

2 𝑐 = 0

, using only operations valid in every field. If

2 \neq 0

(every

𝑝 \neq 2

, and

ℚ

), the list is independent. In

𝔽_{2}^{3}

the list is

(1, 1, 1),

(1, 0, 1),

(1, 0, 1)

, which repeats an entry.

Reading the coordinates of $𝑎 (1, 1, 1) +$ $𝑏 (1, 2, 3) +$ $𝑐 (1, 4, 9) =$ $𝟎$ one at a time gives

𝑎 + 𝑏 + 𝑐 = 0, 𝑎 + 2 𝑏 + 4 𝑐 = 0, 𝑎 + 3 𝑏 + 9 𝑐 = 0 .

Subtracting the first equation from the other two gives $𝑏 + 3 𝑐 = 0$ and $2 𝑏 + 8 𝑐 = 0$ , and subtracting twice the first of these from the second gives $2 𝑐 = 0$ . These steps are valid over every field.

If $2 \neq 0$ in $𝐹$ , then $𝑐 = 0$ by Proposition 1.1.17, so $𝑏 = - 3 𝑐 = 0$ and $𝑎 = - 𝑏 - 𝑐 = 0$ , and the list is independent by Theorem 1.5.5. This is the case for $𝐹 = ℚ$ and $𝐹 = 𝔽_{𝑝}$ with $𝑝$ odd.

If $𝑝 = 2$ , then $2 = 0$ and $4 = 0$ and $3 = 9 = 1$ in $𝔽_{2}$ , so the list is $(1, 1, 1),$ $(1, 0, 1),$ $(1, 0, 1)$ . It repeats an entry, so it is dependent (Proposition 1.5.15(c)).

So the list is independent in $𝔽_{𝑝}^{3}$ exactly for $𝑝 \neq 2$ , and it is independent in $ℚ^{3}$ .

Exercise 1.5.30.routine

(a)Find the error in the following argument.
Claim. If $𝐯_{1}, \dots, 𝐯_{𝑘}$ is linearly dependent, then $𝐯_{𝑘} \in$ $span (𝐯_{1}, \dots, 𝐯_{𝑘 - 1})$ .
Proof. Take a nontrivial relation $𝑎_{1} 𝐯_{1} +$ $\dots +$ $𝑎_{𝑘} 𝐯_{𝑘} =$ $𝟎$ , and let $𝑗$ be the largest index with $𝑎_{𝑗} \neq 0$ . Since $𝑘$ is the largest index, $𝑗 = 𝑘$ . Solving for $𝐯_{𝑘}$ as in Lemma 1.5.10 gives $𝐯_{𝑘} \in$ $span (𝐯_{1}, \dots, 𝐯_{𝑘 - 1})$ .
(b)Show that the claim does hold when $𝐯_{1}, \dots, 𝐯_{𝑘 - 1}$ is linearly independent.

Solution.

Uses. Lemma 1.5.10 (Linear dependence lemma), Proposition 1.5.14 (Appending a vector), Example 1.5.11 (Which entries are redundant)

Hint 1. Is the largest index with a nonzero coefficient necessarily

𝑘

? What if

𝑎_{𝑘} = 0

Hint 2. For (b), compare with Proposition 1.5.14.

Sketch. (a)

𝑗

is the largest index with

𝑎_{𝑗} \neq 0

, which is

𝑘

only if

𝑎_{𝑘} \neq 0

. Counterexample:

(1, 0), (2, 0), (0, 1)

ℝ^{2}

. (b) This is the contrapositive of the backward direction of Proposition 1.5.14.

(a) The step “ $𝑗 = 𝑘$ ” is wrong. The index $𝑗$ is the largest one with $𝑎_{𝑗} \neq 0$ , and nothing prevents $𝑎_{𝑘} = 0$ . The claim itself is false: in $ℝ^{2}$ , the list $(1, 0), (2, 0), (0, 1)$ is dependent (Example 1.5.11), but $(0, 1) \notin$ $span ((1, 0), (2, 0))$ , since every vector of that span has second coordinate $0$ .

(b) Suppose that $𝐯_{1}, \dots, 𝐯_{𝑘 - 1}$ is independent and that $𝐯_{𝑘} \notin$ $span (𝐯_{1}, \dots, 𝐯_{𝑘 - 1})$ . Then $𝐯_{1}, \dots, 𝐯_{𝑘}$ is independent by Proposition 1.5.14. Taking the contrapositive: if $𝐯_{1}, \dots, 𝐯_{𝑘}$ is dependent, then $𝐯_{𝑘} \in$ $span (𝐯_{1}, \dots, 𝐯_{𝑘 - 1})$ . In terms of the argument in (a): if $𝑎_{𝑘} = 0$ , the relation would be a nontrivial relation of the independent list $𝐯_{1}, \dots, 𝐯_{𝑘 - 1}$ , which is impossible, so here $𝑗 = 𝑘$ is correct.

Exercise 1.5.31.routine Let $ℒ︀ = 𝐯_{1}, \dots, 𝐯_{𝑘}$ be a list in $𝑉$ , and let $𝑆_{𝑗} =$ $span (𝐯_{1}, \dots, 𝐯_{𝑗})$ for $0 \leq 𝑗 \leq 𝑘$ , so that $𝑆_{0} = {𝟎}$ . Show that $ℒ︀$ is linearly independent if and only if

𝑆_{0} ⊊ 𝑆_{1} ⊊ \dots ⊊ 𝑆_{𝑘},

that is, every entry makes the span strictly larger.

Solution.

Uses. Corollary 1.5.13 (Independence, one entry at a time), Corollary 1.3.20 (Operations that preserve the span)

Hint 1. By Corollary 1.3.20(b),

𝑆_{𝑗 - 1} \subseteq 𝑆_{𝑗}

always. When are they equal?

Hint 2. Corollary 1.3.20(c) says

𝑆_{𝑗} = 𝑆_{𝑗 - 1}

exactly when

𝐯_{𝑗} \in 𝑆_{𝑗 - 1}

. Now use Corollary 1.5.13.

Sketch.

𝑆_{𝑗 - 1} \subseteq 𝑆_{𝑗}

, with equality if and only if

𝐯_{𝑗} \in 𝑆_{𝑗 - 1}

(Corollary 1.3.20(c)). So the chain is strict exactly when

𝐯_{𝑗} \notin 𝑆_{𝑗 - 1}

for all

𝑗

, which is independence by Corollary 1.5.13.

For

1 \leq 𝑗 \leq 𝑘

, the list

𝐯_{1}, \dots, 𝐯_{𝑗 - 1}

is a sublist of

𝐯_{1}, \dots, 𝐯_{𝑗}

, so

𝑆_{𝑗 - 1} \subseteq 𝑆_{𝑗}

by Corollary 1.3.20(b). By Corollary 1.3.20(c), applied to the list

𝐯_{1}, \dots, 𝐯_{𝑗 - 1}

and the vector

𝐯_{𝑗}

, we have

𝑆_{𝑗} = 𝑆_{𝑗 - 1}

if and only if

𝐯_{𝑗} \in 𝑆_{𝑗 - 1}

. So

𝑆_{𝑗 - 1} ⊊ 𝑆_{𝑗}

if and only if

𝐯_{𝑗} \notin

span (𝐯_{1}, \dots, 𝐯_{𝑗 - 1})

. The chain is strict at every step if and only if this holds for every

𝑗

, which by Corollary 1.5.13 is exactly the independence of

ℒ︀

Exercise 1.5.32.standard Decide whether each list is linearly independent.

(a)In $ℝ^{ℝ}$ : the functions $1$ , $𝑡 \mapsto cos 2 𝑡$ , and $𝑡 \mapsto {cos}^{2} 𝑡$ .
(b)In $ℝ^{ℝ}$ : the functions $𝑡 \mapsto sin 𝑡$ , $𝑡 \mapsto sin 2 𝑡$ , and $𝑡 \mapsto sin 3 𝑡$ .
(c)The functions $𝑡 \mapsto 𝑡$ and $𝑡 \mapsto | 𝑡 |$ , first in $ℝ^{ℝ}$ and then in $ℝ^{[0, \infty)}$ .

Solution.

Uses. Theorem 1.5.5 (Independence is decided at zero), Definition 1.2.9 (Function spaces), Example 1.5.26 (Trigonometric functions)

Hint 1. For (a), recall a double-angle formula. For (b), evaluate a relation at points where the sines are simple, such as

𝜋 / 2

𝜋 / 3

, and

𝜋 / 4

Hint 2. For (c), evaluate at

𝑡 = 1

and

𝑡 = - 1

. Which of these points is available in

ℝ^{[0, \infty)}

Sketch. (a) Dependent:

1 +

cos 2 𝑡 -

2 {cos}^{2} 𝑡 =

0

. (b) Independent: evaluating

𝑎 sin 𝑡 +

𝑏 sin 2 𝑡 +

𝑐 sin 3 𝑡 =

0

𝜋 / 2

𝜋 / 3

𝜋 / 4

gives

𝑎 = 𝑐

𝑏 = - 𝑎

, and

(\sqrt{2} - 1) 𝑎 = 0

. (c) Independent in

ℝ^{ℝ}

(evaluate at

\pm 1

); dependent in

ℝ^{[0, \infty)}

, where

| 𝑡 | = 𝑡

(a) Dependent. By the double-angle formula $cos 2 𝑡 = 2 {cos}^{2} 𝑡 - 1$ , the relation with coefficients $1, 1, - 2$ holds: $1 +$ $cos 2 𝑡 -$ $2 {cos}^{2} 𝑡 =$ $0$ for every $𝑡$ .

(b) Independent. Suppose $𝑎 sin 𝑡 +$ $𝑏 sin 2 𝑡 +$ $𝑐 sin 3 𝑡 =$ $0$ for all $𝑡$ . At $𝑡 = 𝜋 / 2$ : $sin (𝜋 / 2) = 1$ , $sin 𝜋 = 0$ , and $sin (3 𝜋 / 2) = - 1$ , so $𝑎 - 𝑐 = 0$ . At $𝑡 = 𝜋 / 3$ : $sin (𝜋 / 3) =$ $sin (2 𝜋 / 3) =$ $\sqrt{3} / 2$ and $sin 𝜋 = 0$ , so $(\sqrt{3} / 2) (𝑎 + 𝑏) = 0$ and $𝑏 = - 𝑎$ . At $𝑡 = 𝜋 / 4$ : $sin (𝜋 / 4) =$ $sin (3 𝜋 / 4) =$ $\sqrt{2} / 2$ and $sin (𝜋 / 2) = 1$ , so

\frac{\sqrt{2}}{2} 𝑎 + 𝑏 + \frac{\sqrt{2}}{2} 𝑐 = 0 .

Substituting $𝑏 = - 𝑎$ and $𝑐 = 𝑎$ gives $(\sqrt{2} - 1) 𝑎 = 0$ , so $𝑎 = 0$ , and then $𝑏 = 𝑐 = 0$ .

(c) In $ℝ^{ℝ}$ , suppose $𝑎 𝑡 + 𝑏 | 𝑡 | = 0$ for all $𝑡$ . At $𝑡 = 1$ , $𝑎 + 𝑏 = 0$ ; at $𝑡 = - 1$ , $- 𝑎 + 𝑏 = 0$ . So $𝑎 = 𝑏 = 0$ , and the list is independent. In $ℝ^{[0, \infty)}$ , the two functions are equal, since $| 𝑡 | = 𝑡$ for $𝑡 \geq 0$ , so the list repeats an entry and is dependent. The relation $1 \cdot 𝑡 + (- 1) | 𝑡 | = 0$ holds on $[0, \infty)$ but not at $𝑡 = - 1$ : whether functions are independent depends on their domain.

Exercise 1.5.33.standard Let

ℒ︀ = 𝐯_{1}, \dots, 𝐯_{𝑘}

be linearly independent, let

𝐰 =

𝑎_{1} 𝐯_{1} +

\dots +

𝑎_{𝑘} 𝐯_{𝑘}

, and fix

𝑗

. Let

{ℒ︀}^{'}

ℒ︀

with

𝐯_{𝑗}

replaced by

𝐰

. Show that

{ℒ︀}^{'}

is linearly independent if and only if

𝑎_{𝑗} \neq 0

, and that in this case

span ({ℒ︀}^{'}) =

span (ℒ︀)

Solution.

Uses. Theorem 1.5.5 (Independence is decided at zero), Lemma 1.3.9 (Arithmetic of linear combinations), Exercise 1.3.34, Corollary 1.3.19 (Equal spans)

Hint 1. If

𝑎_{𝑗} = 0

, then

𝐰

is a combination of the other entries of

{ℒ︀}^{'}

. Write down a relation.

Hint 2. If

𝑎_{𝑗} \neq 0

, take a relation

\sum_{𝑖 \neq 𝑗} 𝑏_{𝑖} 𝐯_{𝑖} +

𝑏_{𝑗} 𝐰 =

𝟎

, substitute for

𝐰

, and collect the coefficients of

𝐯_{1}, \dots, 𝐯_{𝑘}

Sketch. If

𝑎_{𝑗} = 0

\sum_{𝑖 \neq 𝑗} 𝑎_{𝑖} 𝐯_{𝑖} -

𝐰 =

𝟎

is a nontrivial relation of

{ℒ︀}^{'}

. If

𝑎_{𝑗} \neq 0

: a relation of

{ℒ︀}^{'}

becomes

\sum_{𝑖 \neq 𝑗} (𝑏_{𝑖} + 𝑏_{𝑗} 𝑎_{𝑖}) 𝐯_{𝑖} +

𝑏_{𝑗} 𝑎_{𝑗} 𝐯_{𝑗} =

𝟎

, so

𝑏_{𝑗} 𝑎_{𝑗} = 0

, whence

𝑏_{𝑗} = 0

, and then all

𝑏_{𝑖} = 0

. For the spans, solve for

𝐯_{𝑗}

Suppose $𝑎_{𝑗} = 0$ . Then $𝐰 = \sum_{𝑖 \neq 𝑗} 𝑎_{𝑖} 𝐯_{𝑖}$ , and the linear combination of ${ℒ︀}^{'}$ with coefficient $𝑎_{𝑖}$ on $𝐯_{𝑖}$ for $𝑖 \neq 𝑗$ and $- 1$ on $𝐰$ represents $𝐰 - 𝐰 = 𝟎$ . It is nontrivial, so ${ℒ︀}^{'}$ is dependent.

Suppose $𝑎_{𝑗} \neq 0$ . Let $\sum_{𝑖 \neq 𝑗} 𝑏_{𝑖} 𝐯_{𝑖} +$ $𝑏_{𝑗} 𝐰 =$ $𝟎$ . Substituting $𝐰 = \sum_{𝑖} 𝑎_{𝑖} 𝐯_{𝑖}$ and collecting coefficients with Lemma 1.3.9,

\sum_{𝑖 \neq 𝑗} (𝑏_{𝑖} + 𝑏_{𝑗} 𝑎_{𝑖}) 𝐯_{𝑖} + (𝑏_{𝑗} 𝑎_{𝑗}) 𝐯_{𝑗} = 𝟎 .

Since $ℒ︀$ is independent, all these coefficients are $0$ (Theorem 1.5.5). From $𝑏_{𝑗} 𝑎_{𝑗} = 0$ and $𝑎_{𝑗} \neq 0$ we get $𝑏_{𝑗} = 0$ , and then $𝑏_{𝑖} =$ $𝑏_{𝑖} +$ $𝑏_{𝑗} 𝑎_{𝑖} =$ $0$ for $𝑖 \neq 𝑗$ . So ${ℒ︀}^{'}$ is independent.

For the spans, $𝐰 \in span (ℒ︀)$ , and since $𝑎_{𝑗} \neq 0$ ,

𝐯_{𝑗} = 𝑎_{𝑗}^{- 1} 𝐰 + \sum_{𝑖 \neq 𝑗} (- 𝑎_{𝑗}^{- 1} 𝑎_{𝑖}) 𝐯_{𝑖} \in span ({ℒ︀}^{'}) .

So each list lies in the span of the other, and $span ({ℒ︀}^{'}) =$ $span (ℒ︀)$ by Corollary 1.3.19. (Compare Exercise 1.3.34, which made the same exchange using only spans.)

Exercise 1.5.34.standard Let $𝐮, 𝐯, 𝐰 \in 𝑉$ , and let $ℒ︀$ , $ℳ︀$ be lists in $𝑉$ . Prove or disprove each statement.

(a)If $𝐮, 𝐯$ and $𝐯, 𝐰$ are linearly independent, then so is $𝐮, 𝐰$ .
(b)If $𝐮, 𝐯, 𝐰$ is linearly dependent, then $𝐰 \in span (𝐮, 𝐯)$ .
(c)If $ℒ︀$ and $ℳ︀$ are linearly independent, then so is the concatenation $ℒ︀, ℳ︀$ .
(d)If $𝐯_{1}, \dots, 𝐯_{𝑘}$ is linearly independent, then $𝐯_{1},$ $\dots,$ $𝐯_{𝑘},$ $𝐯_{1} +$ $\dots +$ $𝐯_{𝑘}$ is linearly dependent.
(e)If $𝐮, 𝐯$ is linearly independent and $𝐰 \notin$ $span (𝐮) \cup$ $span (𝐯)$ , then $𝐮, 𝐯, 𝐰$ is linearly independent.

Solution.

Uses. Proposition 1.5.15 (Short lists, zeros, and repeats), Example 1.5.11 (Which entries are redundant), Theorem 1.5.5 (Independence is decided at zero)

Techniques. Finding counterexamples and minimal examples (Technique 1.4.18)

Hint 1. Look for counterexamples in

ℝ^{2}

among

𝐞_{1}

𝐞_{2}

𝐞_{1} + 𝐞_{2}

, and repeated vectors.

Hint 2. Exactly one statement is true. For it, write down a relation in which the last entry has coefficient

- 1

Sketch. (a) False:

𝐮 = 𝐰 = 𝐞_{1}

𝐯 = 𝐞_{2}

. (b) False:

(1, 0), (2, 0), (0, 1)

. (c) False:

ℒ︀ = ℳ︀ = 𝐞_{1}

. (d) True:

𝐯_{1} +

\dots +

𝐯_{𝑘} -

(𝐯_{1} + \dots + 𝐯_{𝑘}) =

𝟎

has coefficient

- 1

on the last entry. (e) False:

𝐞_{1}, 𝐞_{2}, 𝐞_{1} + 𝐞_{2}

Write $𝐞_{1} = (1, 0)$ and $𝐞_{2} = (0, 1)$ in $ℝ^{2}$ .

(a) False. Take $𝐮 = 𝐰 = 𝐞_{1}$ and $𝐯 = 𝐞_{2}$ . Then $𝐮, 𝐯$ and $𝐯, 𝐰$ are $𝐞_{1}, 𝐞_{2}$ and $𝐞_{2}, 𝐞_{1}$ , which are independent (Example 1.5.2, and neither is a multiple of the other). But $𝐮, 𝐰 = 𝐞_{1}, 𝐞_{1}$ repeats an entry (Proposition 1.5.15(c)).

(b) False. The list $(1, 0), (2, 0), (0, 1)$ is dependent, but $(0, 1) \notin$ $span ((1, 0), (2, 0))$ (Example 1.5.11).

(c) False. Take $ℒ︀ = ℳ︀ = 𝐞_{1}$ , which is independent by Proposition 1.5.15(b). The concatenation $𝐞_{1}, 𝐞_{1}$ repeats an entry.

(d) True. The linear combination with coefficient $1$ on each $𝐯_{𝑖}$ and $- 1$ on the last entry represents $(𝐯_{1} + \dots + 𝐯_{𝑘}) -$ $(𝐯_{1} + \dots + 𝐯_{𝑘}) =$ $𝟎$ , and it is nontrivial. (Independence of $𝐯_{1}, \dots, 𝐯_{𝑘}$ was not needed. For $𝑘 = 0$ the list is the single vector $𝟎$ , the empty sum.)

(e) False. Take $𝐮 = 𝐞_{1}$ , $𝐯 = 𝐞_{2}$ , and $𝐰 = (1, 1)$ . Then $𝐰$ is on neither axis, but $𝐮 + 𝐯 - 𝐰 = 𝟎$ . Avoiding the two lines spanned by $𝐮$ and $𝐯$ is much weaker than avoiding $span (𝐮, 𝐯)$ , which is what Proposition 1.5.14 requires.

Exercise 1.5.35.standard In $𝐹 [𝑥]$ , let

𝑝_{1} = 𝑥^{2} - 3 𝑥 + 2, 𝑝_{2} = 𝑥^{2} - 2 𝑥, 𝑝_{3} = 𝑥^{2} - 𝑥,

where $3 = 1 + 1 + 1$ and $2 = 1 + 1$ in $𝐹$ . Show that $𝑝_{1}, 𝑝_{2}, 𝑝_{3}$ is linearly independent if and only if $1 + 1 \neq 0$ in $𝐹$ .

Solution.

Uses. Theorem 1.5.5 (Independence is decided at zero), Definition 1.2.17 (Evaluation), Proposition 1.2.18 (Degree and evaluation versus the operations), Proposition 1.1.17 (No zero divisors), Proposition 1.5.15 (Short lists, zeros, and repeats)

Hint 1. Evaluate each

𝑝_{𝑖}

0

1

, and

2

. Each polynomial vanishes at two of these points.

Hint 2. If

𝑎 𝑝_{1} +

𝑏 𝑝_{2} +

𝑐 𝑝_{3} =

𝟎

, evaluate at

0

1

2

using Proposition 1.2.18(c). For the case

1 + 1 = 0

, rewrite the three polynomials with

2 = 0

and

3 = 1

Sketch.

𝑝_{1} (0) = 2

𝑝_{2} (1) = - 1

𝑝_{3} (2) = 2

, and each

𝑝_{𝑖}

vanishes at the other two points. A relation evaluated at

0, 1, 2

gives

2 𝑎 = 0

- 𝑏 = 0

2 𝑐 = 0

, so if

2 \neq 0

the list is independent. If

2 = 0

, then

𝑝_{1} = 𝑥^{2} + 𝑥 = 𝑝_{3}

, a repeated entry.

By Definition 1.2.17,

\begin{aligned} 𝑝_{1} (0) = 2, & 𝑝_{1} (1) = 1 - 3 + 2 = 0, & 𝑝_{1} (2) = 4 - 6 + 2 = 0, \\ 𝑝_{2} (0) = 0, & 𝑝_{2} (1) = 1 - 2 = - 1, & 𝑝_{2} (2) = 4 - 4 = 0, \\ 𝑝_{3} (0) = 0, & 𝑝_{3} (1) = 1 - 1 = 0, & 𝑝_{3} (2) = 4 - 2 = 2 . \end{aligned}

Suppose that $1 + 1 \neq 0$ , and that $𝑎 𝑝_{1} +$ $𝑏 𝑝_{2} +$ $𝑐 𝑝_{3} =$ $𝟎$ . The zero polynomial has value $0$ everywhere, so by Proposition 1.2.18(c), evaluating at $0$ , $1$ , $2$ gives

2 𝑎 = 0, - 𝑏 = 0, 2 𝑐 = 0 .

Since $2 = 1 + 1 \neq 0$ , Proposition 1.1.17 gives $𝑎 = 𝑐 = 0$ , and $𝑏 = 0$ . So the list is independent by Theorem 1.5.5.

Suppose that $1 + 1 = 0$ . Then $2 = 0$ , $3 = 1$ , and $- 1 = 1$ in $𝐹$ , so

𝑝_{1} = 𝑥^{2} + 𝑥, 𝑝_{2} = 𝑥^{2}, 𝑝_{3} = 𝑥^{2} + 𝑥 .

The list repeats an entry, so it is dependent (Proposition 1.5.15(c)). The evaluation argument breaks down because the values $𝑝_{1} (0) = 𝑝_{3} (2) = 2$ vanish when $2 = 0$ , so the equations at $0$ and $2$ become $0 = 0$ , and only $𝑏 = 0$ remains.

Exercise 1.5.36.standard Let $𝑛 \geq 2$ , and let $𝐯_{1}, \dots, 𝐯_{𝑛}$ be linearly independent in $𝑉$ . Let

𝐰_{𝑖} = 𝐯_{𝑖} + 𝐯_{𝑖 + 1} (1 \leq 𝑖 < 𝑛), 𝐰_{𝑛} = 𝐯_{𝑛} + 𝐯_{1} .

Find all $𝑛$ and all fields $𝐹$ for which $𝐰_{1}, \dots, 𝐰_{𝑛}$ is linearly independent.

Solution.

Uses. Theorem 1.5.5 (Independence is decided at zero), Lemma 1.3.9 (Arithmetic of linear combinations), Proposition 1.1.17 (No zero divisors)

Techniques. Try small cases and small fields (Technique 1.2.38)

Hint 1. Expand

\sum_{𝑖} 𝑎_{𝑖} 𝐰_{𝑖}

in terms of the

𝐯_{𝑖}

. Each

𝐯_{𝑖}

occurs in exactly two of the

𝐰

’s.

Hint 2. Independence of the

𝐯_{𝑖}

gives

𝑎_{𝑖} + 𝑎_{𝑖 - 1} = 0

for every

𝑖

, with

𝑎_{0} = 𝑎_{𝑛}

. So the signs alternate around the cycle. What happens when you get back to the start?

Hint 3. Try

𝑛 = 2, 3, 4

first, and over

𝔽_{2}

Sketch. With

𝑎_{0} = 𝑎_{𝑛}

\sum 𝑎_{𝑖} 𝐰_{𝑖} =

\sum_{𝑖} (𝑎_{𝑖 - 1} + 𝑎_{𝑖}) 𝐯_{𝑖}

, so a relation means

𝑎_{𝑖} = - 𝑎_{𝑖 - 1}

for all

𝑖

, that is,

𝑎_{𝑖} = {(- 1)}^{𝑖 - 1} 𝑎_{1}

and

(1 + {(- 1)}^{𝑛 - 1}) 𝑎_{1} = 0

. For

𝑛

even,

𝑎_{𝑖} = {(- 1)}^{𝑖 - 1}

is a nontrivial relation. For

𝑛

odd, the condition is

(1 + 1) 𝑎_{1} = 0

. Answer: independent exactly when

𝑛

is odd and

1 + 1 \neq 0

Let $𝑎_{1}, \dots, 𝑎_{𝑛} \in 𝐹$ , and set $𝑎_{0} = 𝑎_{𝑛}$ . The vector $𝐯_{𝑖}$ occurs in $𝐰_{𝑖 - 1}$ and in $𝐰_{𝑖}$ (in $𝐰_{𝑛}$ and $𝐰_{1}$ for $𝑖 = 1$ ), each time with coefficient $1$ . So by Lemma 1.3.9,

\sum_{𝑖 = 1}^{𝑛} 𝑎_{𝑖} 𝐰_{𝑖} = \sum_{𝑖 = 1}^{𝑛} (𝑎_{𝑖 - 1} + 𝑎_{𝑖}) 𝐯_{𝑖} .

Since the $𝐯_{𝑖}$ are independent, $𝑎_{1}, \dots, 𝑎_{𝑛}$ is a linear relation of $𝐰_{1}, \dots, 𝐰_{𝑛}$ if and only if $𝑎_{𝑖} = - 𝑎_{𝑖 - 1}$ for $2 \leq 𝑖 \leq 𝑛$ and $𝑎_{1} = - 𝑎_{𝑛}$ . The first $𝑛 - 1$ conditions say that $𝑎_{𝑖} = {(- 1)}^{𝑖 - 1} 𝑎_{1}$ for all $𝑖$ , and then the last one says $𝑎_{1} = - {(- 1)}^{𝑛 - 1} 𝑎_{1}$ , that is,

(1 + {(- 1)}^{𝑛 - 1}) 𝑎_{1} = 0 .

If $𝑛$ is even, ${(- 1)}^{𝑛 - 1} = - 1$ , so the last condition always holds, and $𝑎_{𝑖} = {(- 1)}^{𝑖 - 1}$ is a nontrivial relation. The list is dependent, over every field.

If $𝑛$ is odd, the last condition is $(1 + 1) 𝑎_{1} = 0$ . If $1 + 1 \neq 0$ , it forces $𝑎_{1} = 0$ (Proposition 1.1.17), hence every $𝑎_{𝑖} = 0$ , and the list is independent by Theorem 1.5.5. If $1 + 1 = 0$ , then $𝑎_{1} = 1$ satisfies it, giving the nontrivial relation $𝑎_{𝑖} = {(- 1)}^{𝑖 - 1} = 1$ (as $- 1 = 1$ ). Indeed,

𝐰_{1} + \dots + 𝐰_{𝑛} = (1 + 1) (𝐯_{1} + \dots + 𝐯_{𝑛}) = 𝟎 .

So $𝐰_{1}, \dots, 𝐰_{𝑛}$ is independent exactly when $𝑛$ is odd and $1 + 1 \neq 0$ in $𝐹$ . For $𝑛 = 2$ the list is $𝐯_{1} + 𝐯_{2}, 𝐯_{2} + 𝐯_{1}$ , which repeats an entry, as it must.

Exercise 1.5.37.standard Let $𝑉$ be a vector space over $ℂ$ , regarded also as a vector space over $ℝ$ (Proposition 1.2.19). Show that $𝐯_{1}, \dots, 𝐯_{𝑘}$ is linearly independent over $ℂ$ if and only if

𝐯_{1}, 𝑖 𝐯_{1}, 𝐯_{2}, 𝑖 𝐯_{2}, \dots, 𝐯_{𝑘}, 𝑖 𝐯_{𝑘}

is linearly independent over $ℝ$ .

Solution.

Uses. Theorem 1.5.5 (Independence is decided at zero), Definition 1.1.29 (Complex numbers), Proposition 1.2.19 (Restriction of scalars)

Hint 1. For real

𝑎_{𝑗}, 𝑏_{𝑗}

, rewrite

𝑎_{𝑗} 𝐯_{𝑗} +

𝑏_{𝑗} (𝑖 𝐯_{𝑗})

as a single complex multiple of

𝐯_{𝑗}

Hint 2. Complex relations of

𝐯_{1}, \dots, 𝐯_{𝑘}

and real relations of the doubled list correspond to each other, via

𝑐_{𝑗} = 𝑎_{𝑗} + 𝑏_{𝑗} 𝑖

Sketch. By (A6) and (A8),

𝑎_{𝑗} 𝐯_{𝑗} +

𝑏_{𝑗} (𝑖 𝐯_{𝑗}) =

(𝑎_{𝑗} + 𝑏_{𝑗} 𝑖) 𝐯_{𝑗}

. So real coefficients

𝑎_{1},

𝑏_{1},

\dots,

𝑎_{𝑘},

𝑏_{𝑘}

form a relation of the doubled list if and only if

𝑎_{1} +

𝑏_{1} 𝑖,

\dots,

𝑎_{𝑘} +

𝑏_{𝑘} 𝑖

form a complex relation of the original list, and one is trivial exactly when the other is.

For $𝑎_{𝑗}, 𝑏_{𝑗} \in ℝ$ , (A6) gives $𝑏_{𝑗} (𝑖 𝐯_{𝑗}) =$ $(𝑏_{𝑗} 𝑖) 𝐯_{𝑗}$ , and then (A8) gives $𝑎_{𝑗} 𝐯_{𝑗} +$ $(𝑏_{𝑗} 𝑖) 𝐯_{𝑗} =$ $(𝑎_{𝑗} + 𝑏_{𝑗} 𝑖) 𝐯_{𝑗}$ . Hence

\sum_{𝑗 = 1}^{𝑘} (𝑎_{𝑗} 𝐯_{𝑗} + 𝑏_{𝑗} (𝑖 𝐯_{𝑗})) = \sum_{𝑗 = 1}^{𝑘} (𝑎_{𝑗} + 𝑏_{𝑗} 𝑖) 𝐯_{𝑗} .

(1.5.1)

( $\Rightarrow$ ) Suppose that $𝐯_{1}, \dots, 𝐯_{𝑘}$ is independent over $ℂ$ , and that real numbers $𝑎_{1},$ $𝑏_{1},$ $\dots,$ $𝑎_{𝑘},$ $𝑏_{𝑘}$ form a relation of the doubled list. By (1.5.1), the complex numbers $𝑎_{𝑗} + 𝑏_{𝑗} 𝑖$ form a relation of $𝐯_{1}, \dots, 𝐯_{𝑘}$ , so $𝑎_{𝑗} + 𝑏_{𝑗} 𝑖 = 0$ , that is, $𝑎_{𝑗} = 𝑏_{𝑗} = 0$ (Definition 1.1.29).

( $\Leftarrow$ ) Suppose that the doubled list is independent over $ℝ$ , and that $𝑐_{1}, \dots, 𝑐_{𝑘} \in ℂ$ form a relation of $𝐯_{1}, \dots, 𝐯_{𝑘}$ . Write $𝑐_{𝑗} = 𝑎_{𝑗} + 𝑏_{𝑗} 𝑖$ with $𝑎_{𝑗}, 𝑏_{𝑗} \in ℝ$ . By (1.5.1), the real numbers $𝑎_{1},$ $𝑏_{1},$ $\dots,$ $𝑎_{𝑘},$ $𝑏_{𝑘}$ form a relation of the doubled list, so they are all $0$ , and every $𝑐_{𝑗} = 0$ .

In the language of Section 4.1: if $𝐯_{1}, \dots, 𝐯_{𝑛}$ is a basis of $𝑉$ over $ℂ$ , the doubled list is a basis over $ℝ$ , so the real dimension of $𝑉$ is twice its complex dimension.

Exercise 1.5.38.standard Let

ℒ︀ = 𝐯_{1}, \dots, 𝐯_{𝑘}

be a list in

ℝ^{𝑚}

. Show that

ℒ︀

spans the real vector space

ℝ^{𝑚}

if and only if it spans the complex vector space

ℂ^{𝑚}

Solution.

Uses. Definition 1.3.10 (Span), Definition 1.1.29 (Complex numbers), Definition 1.2.4 (The space $𝐹^{𝑛}$ ), Proposition 1.5.21 (Real lists in $ℂ^{𝑚}$ )

Hint 1. Every

𝐳 \in ℂ^{𝑚}

can be written as

𝐱 + 𝑖 𝐲

with

𝐱, 𝐲 \in ℝ^{𝑚}

, by taking real and imaginary parts coordinatewise.

Hint 2. For (

\Leftarrow

), write a real vector as a complex combination of

ℒ︀

and take real parts coordinate by coordinate, as in the proof of Proposition 1.5.21.

Sketch. (

\Rightarrow

) Write

𝐳 = 𝐱 + 𝑖 𝐲

, expand

𝐱 = \sum 𝑎_{𝑗} 𝐯_{𝑗}

and

𝐲 = \sum 𝑏_{𝑗} 𝐯_{𝑗}

over

ℝ

; then

𝐳 =

\sum (𝑎_{𝑗} + 𝑏_{𝑗} 𝑖) 𝐯_{𝑗}

. (

\Leftarrow

) If

𝐱 \in ℝ^{𝑚}

equals

\sum 𝑐_{𝑗} 𝐯_{𝑗}

with

𝑐_{𝑗} = 𝑎_{𝑗} + 𝑏_{𝑗} 𝑖

, then comparing real parts in each coordinate gives

𝐱 = \sum 𝑎_{𝑗} 𝐯_{𝑗}

Write $𝑣_{𝑗 𝑡}$ for the $𝑡$ -th coordinate of $𝐯_{𝑗}$ , a real number.

( $\Rightarrow$ ) Suppose $ℒ︀$ spans $ℝ^{𝑚}$ , and let $𝐳 \in ℂ^{𝑚}$ have coordinates $𝑧_{𝑡} = 𝑥_{𝑡} + 𝑦_{𝑡} 𝑖$ with $𝑥_{𝑡}, 𝑦_{𝑡} \in ℝ$ . Let $𝐱 = (𝑥_{1}, \dots, 𝑥_{𝑚})$ and $𝐲 = (𝑦_{1}, \dots, 𝑦_{𝑚})$ in $ℝ^{𝑚}$ , and write $𝐱 = \sum_{𝑗} 𝑎_{𝑗} 𝐯_{𝑗}$ and $𝐲 = \sum_{𝑗} 𝑏_{𝑗} 𝐯_{𝑗}$ with $𝑎_{𝑗}, 𝑏_{𝑗} \in ℝ$ . Then for each $𝑡$ ,

\sum_{𝑗 = 1}^{𝑘} (𝑎_{𝑗} + 𝑏_{𝑗} 𝑖) 𝑣_{𝑗 𝑡} = \sum_{𝑗 = 1}^{𝑘} 𝑎_{𝑗} 𝑣_{𝑗 𝑡} + (\sum_{𝑗 = 1}^{𝑘} 𝑏_{𝑗} 𝑣_{𝑗 𝑡}) 𝑖 = 𝑥_{𝑡} + 𝑦_{𝑡} 𝑖 = 𝑧_{𝑡},

so $𝐳 =$ $\sum_{𝑗} (𝑎_{𝑗} + 𝑏_{𝑗} 𝑖) 𝐯_{𝑗} \in$ ${span}_{ℂ} (ℒ︀)$ .

( $\Leftarrow$ ) Suppose $ℒ︀$ spans $ℂ^{𝑚}$ , and let $𝐱 \in ℝ^{𝑚}$ . Then $𝐱 = \sum_{𝑗} 𝑐_{𝑗} 𝐯_{𝑗}$ for some $𝑐_{𝑗} = 𝑎_{𝑗} + 𝑏_{𝑗} 𝑖$ in $ℂ$ . In coordinate $𝑡$ ,

𝑥_{𝑡} = \sum_{𝑗 = 1}^{𝑘} 𝑎_{𝑗} 𝑣_{𝑗 𝑡} + (\sum_{𝑗 = 1}^{𝑘} 𝑏_{𝑗} 𝑣_{𝑗 𝑡}) 𝑖 .

Both sums are real, and $𝑥_{𝑡}$ is real, so comparing real parts (Definition 1.1.29) gives $𝑥_{𝑡} =$ $\sum_{𝑗} 𝑎_{𝑗} 𝑣_{𝑗 𝑡}$ . Hence $𝐱 = \sum_{𝑗} 𝑎_{𝑗} 𝐯_{𝑗}$ with real coefficients, and $𝐱 \in {span}_{ℝ} (ℒ︀)$ .

Together with Proposition 1.5.21, this shows that $ℒ︀$ is a basis of $ℝ^{𝑚}$ if and only if it is a basis of $ℂ^{𝑚}$ (Section 1.6).

Exercise 1.5.39.standard Regard

ℝ

as a vector space over

ℚ

. Show that

ln 2, ln 3, ln 5

is linearly independent. (Use unique factorization of positive integers into primes.)

Solution.

Uses. Theorem 1.5.5 (Independence is decided at zero), Example 1.2.20 (Real and rational scalars)

Hint 1. Suppose

𝑎 ln 2 +

𝑏 ln 3 +

𝑐 ln 5 =

0

with

𝑎, 𝑏, 𝑐 \in ℚ

. Clear denominators to make the coefficients integers.

Hint 2. Exponentiate:

2^{𝐴} 3^{𝐵} 5^{𝐶} = 1

with integers

𝐴, 𝐵, 𝐶

. Move the factors with negative exponents to the other side.

Sketch. Multiply a relation by a common denominator to get

𝐴 ln 2 +

𝐵 ln 3 +

𝐶 ln 5 =

0

with

𝐴, 𝐵, 𝐶 \in ℤ

, so

2^{𝐴} 3^{𝐵} 5^{𝐶} = 1

. Collecting negative exponents on the right gives two factorizations of one positive integer into primes, and uniqueness forces

𝐴 = 𝐵 = 𝐶 = 0

Suppose $𝑎 ln 2 +$ $𝑏 ln 3 +$ $𝑐 ln 5 =$ $0$ with $𝑎, 𝑏, 𝑐 \in ℚ$ . Let $𝑁 \geq 1$ be a common denominator, so that $𝐴 = 𝑁 𝑎$ , $𝐵 = 𝑁 𝑏$ , $𝐶 = 𝑁 𝑐$ are integers, and $𝐴 ln 2 +$ $𝐵 ln 3 +$ $𝐶 ln 5 =$ $0$ . Exponentiating, $2^{𝐴} 3^{𝐵} 5^{𝐶} = 𝑒^{0} = 1$ . For an integer $𝑛$ , write $𝑛^{+} = max (𝑛, 0)$ and $𝑛^{-} = max (- 𝑛, 0)$ , so that $𝑛 = 𝑛^{+} - 𝑛^{-}$ and at most one of $𝑛^{+}, 𝑛^{-}$ is nonzero. Multiplying by $2^{𝐴^{-}} 3^{𝐵^{-}} 5^{𝐶^{-}}$ ,

2^{𝐴^{+}} 3^{𝐵^{+}} 5^{𝐶^{+}} = 2^{𝐴^{-}} 3^{𝐵^{-}} 5^{𝐶^{-}} .

Both sides are positive integers. By unique factorization, the exponent of $2$ on the two sides agrees, so $𝐴^{+} = 𝐴^{-}$ ; since one of them is $0$ , both are, and $𝐴 = 0$ . Likewise $𝐵 = 𝐶 = 0$ . Hence $𝑎 = 𝑏 = 𝑐 = 0$ , and the list is independent by Theorem 1.5.5.

The same argument shows that $ln 𝑝_{1}, \dots, ln 𝑝_{𝑘}$ is independent over $ℚ$ for any distinct primes $𝑝_{1}, \dots, 𝑝_{𝑘}$ . Since there are infinitely many primes, $ℝ$ over $ℚ$ contains independent lists of every length, which is another way to see that no finite list spans it (Exercise 1.3.45, Section 4.1).

Exercise 1.5.40.hard Regard

ℝ

as a vector space over

ℚ

. Show that

1, \sqrt{2}, \sqrt{3}, \sqrt{6}

is linearly independent. You may use Exercise 1.3.44:

\sqrt{3} \notin span (1, \sqrt{2})

over

ℚ

Solution.

Uses. Exercise 1.3.44, Example 1.5.19 (The same vectors over two fields), Theorem 1.5.5 (Independence is decided at zero)

Hint 1. Group a relation

𝑎 + 𝑏 \sqrt{2} + 𝑐 \sqrt{3} + 𝑑 \sqrt{6} = 0

𝛼 + 𝛽 \sqrt{3} = 0

with

𝛼 = 𝑎 + 𝑏 \sqrt{2}

and

𝛽 = 𝑐 + 𝑑 \sqrt{2}

Hint 2. If

𝛽 \neq 0

, then

\sqrt{3} = - 𝛼 / 𝛽

. Rationalize the denominator: multiply numerator and denominator by

𝑐 - 𝑑 \sqrt{2}

Hint 3. Check that

𝑐^{2} - 2 𝑑^{2} \neq 0

when

(𝑐, 𝑑) \neq (0, 0)

, so that

- 𝛼 / 𝛽

lies in

span (1, \sqrt{2})

Sketch. Write the relation as

(𝑎 + 𝑏 \sqrt{2}) +

(𝑐 + 𝑑 \sqrt{2}) \sqrt{3} =

0

. If

𝑐 + 𝑑 \sqrt{2} \neq 0

, then

𝑐^{2} - 2 𝑑^{2} \neq 0

, and

\sqrt{3} =

- (𝑎 + 𝑏 \sqrt{2}) (𝑐 - 𝑑 \sqrt{2}) / (𝑐^{2} - 2 𝑑^{2})

is of the form

𝑟 + 𝑠 \sqrt{2}

with

𝑟, 𝑠 \in ℚ

, contradicting Exercise 1.3.44. So

𝑐 + 𝑑 \sqrt{2} = 0

, hence

𝑐 = 𝑑 = 0

, and then

𝑎 = 𝑏 = 0

Suppose $𝑎 + 𝑏 \sqrt{2} + 𝑐 \sqrt{3} + 𝑑 \sqrt{6} = 0$ with $𝑎, 𝑏, 𝑐, 𝑑 \in ℚ$ . Since $\sqrt{6} = \sqrt{2} \sqrt{3}$ , this reads

(𝑎 + 𝑏 \sqrt{2}) + (𝑐 + 𝑑 \sqrt{2}) \sqrt{3} = 0 .

Suppose $𝑐 + 𝑑 \sqrt{2} \neq 0$ . Then $(𝑐, 𝑑) \neq (0, 0)$ , and $𝑐^{2} - 2 𝑑^{2} \neq 0$ : otherwise $𝑑 \neq 0$ (as $𝑐^{2} = 2 𝑑^{2}$ with $𝑑 = 0$ forces $𝑐 = 0$ ) and ${(𝑐 / 𝑑)}^{2} = 2$ , making $\sqrt{2}$ or $- \sqrt{2}$ rational. So $𝑐 - 𝑑 \sqrt{2} \neq 0$ as well, since $(𝑐 + 𝑑 \sqrt{2}) (𝑐 - 𝑑 \sqrt{2}) =$ $𝑐^{2} -$ $2 𝑑^{2}$ . Hence

\sqrt{3} = - \frac{𝑎 + 𝑏 \sqrt{2}}{𝑐 + 𝑑 \sqrt{2}} = - \frac{(𝑎 + 𝑏 \sqrt{2}) (𝑐 - 𝑑 \sqrt{2})}{𝑐^{2} - 2 𝑑^{2}} = - \frac{𝑎 𝑐 - 2 𝑏 𝑑}{𝑐^{2} - 2 𝑑^{2}} - \frac{𝑏 𝑐 - 𝑎 𝑑}{𝑐^{2} - 2 𝑑^{2}} \sqrt{2},

using

(𝑎 + 𝑏 \sqrt{2}) (𝑐 - 𝑑 \sqrt{2}) = (𝑎 𝑐 - 2 𝑏 𝑑) + (𝑏 𝑐 - 𝑎 𝑑) \sqrt{2} .

Both coefficients on the right are rational, so $\sqrt{3} \in span (1, \sqrt{2})$ over $ℚ$ , contradicting Exercise 1.3.44.

So $𝑐 + 𝑑 \sqrt{2} = 0$ . Since $1, \sqrt{2}$ is independent over $ℚ$ (Example 1.5.19(b)), $𝑐 = 𝑑 = 0$ . The relation becomes $𝑎 + 𝑏 \sqrt{2} = 0$ , and for the same reason $𝑎 = 𝑏 = 0$ . By Theorem 1.5.5, the list is independent.

Exercise 1.5.41.hard Let $𝐯_{1}, \dots, 𝐯_{𝑘} \in ℚ^{𝑚}$ have integer coordinates, let $𝑝$ be a prime, and let $𝐯_{𝑗} \in 𝔽_{𝑝}^{𝑚}$ be the vector whose coordinates are those of $𝐯_{𝑗}$ reduced modulo $𝑝$ .

(a)Show that if $𝐯_{1}, \dots, 𝐯_{𝑘}$ is linearly independent in $𝔽_{𝑝}^{𝑚}$ , then $𝐯_{1}, \dots, 𝐯_{𝑘}$ is linearly independent in $ℚ^{𝑚}$ .
(b)Show that the converse of (a) is false.

Solution.

Uses. Theorem 1.5.5 (Independence is decided at zero), Definition 1.1.19 (Integers modulo $𝑛$ ), Lemma 1.1.21 (Arithmetic in $ℤ / 𝑛 ℤ$ )

Techniques. Contrapositive (Technique 1.5.4)

Hint 1. Prove the contrapositive of (a). Starting from a nontrivial rational relation, clear denominators to get integer coefficients.

Hint 2. Divide the integer coefficients by their greatest common divisor. Then not all of them are divisible by

𝑝

, so reducing the relation modulo

𝑝

gives a nontrivial relation over

𝔽_{𝑝}

Sketch. (a) A nontrivial relation over

ℚ

can be scaled to have integer coefficients

𝑛_{1}, \dots, 𝑛_{𝑘}

with greatest common divisor

1

. Reducing each coordinate equation

\sum_{𝑗} 𝑛_{𝑗} 𝑣_{𝑗 𝑡} = 0

modulo

𝑝

gives a relation over

𝔽_{𝑝}

, which is nontrivial because

𝑝

does not divide every

𝑛_{𝑗}

. (b) The list

(2)

ℚ^{1}

is independent, but its reduction modulo

2

(0)

(a) We prove the contrapositive. Suppose that $𝑐_{1} 𝐯_{1} +$ $\dots +$ $𝑐_{𝑘} 𝐯_{𝑘} =$ $𝟎$ with $𝑐_{𝑗} \in ℚ$ not all $0$ . Multiplying by a common denominator of the $𝑐_{𝑗}$ gives a relation with integer coefficients, not all $0$ ; dividing these by their greatest common divisor gives a relation with integer coefficients $𝑛_{1}, \dots, 𝑛_{𝑘}$ whose greatest common divisor is $1$ . In particular, $𝑝$ does not divide some $𝑛_{𝑗}$ .

Write $𝑣_{𝑗 𝑡}$ for the $𝑡$ -th coordinate of $𝐯_{𝑗}$ . For each $𝑡$ , $\sum_{𝑗} 𝑛_{𝑗} 𝑣_{𝑗 𝑡} = 0$ is an equation between integers. Reducing modulo $𝑝$ is compatible with sums and products (Definition 1.1.19, Lemma 1.1.21), so $\sum_{𝑗} 𝑛_{𝑗} 𝑣_{𝑗 𝑡} = 0$ in $𝔽_{𝑝}$ , where bars denote remainders modulo $𝑝$ . That is, $𝑛_{1}, \dots, 𝑛_{𝑘}$ is a linear relation of $𝐯_{1}, \dots, 𝐯_{𝑘}$ in $𝔽_{𝑝}^{𝑚}$ . It is nontrivial, since $𝑛_{𝑗} \neq 0$ for the $𝑗$ with $𝑝 ∤ 𝑛_{𝑗}$ . So the reduced list is dependent.

(b) The list $(2)$ of length one in $ℚ^{1}$ is independent, since $(2) \neq 𝟎$ (Proposition 1.5.15(b)). Its reduction modulo $2$ is $(0)$ , which is dependent. For a list of length two: $(1, 1), (1, - 1)$ is independent in $ℚ^{2}$ (neither vector is a multiple of the other), but modulo $2$ both vectors reduce to $(1, 1)$ .

Part (a) gives a quick test: to show that an integer list is independent over $ℚ$ , it suffices to check independence over a small field such as $𝔽_{2}$ , where there are only finitely many relations to try.

Exercise 1.5.42.hard Let

𝐾

be a subfield of a field

𝐸

, for instance

ℚ \subseteq ℝ

, and let

ℒ︀ = 𝐯_{1}, \dots, 𝐯_{𝑘}

be a list in

𝐾^{𝑚}

. Show that

ℒ︀

is linearly independent in the

𝐾

-vector space

𝐾^{𝑚}

if and only if it is linearly independent in the

𝐸

-vector space

𝐸^{𝑚}

. This exercise uses Theorem 1.6.10 from Section 1.6.

Solution.

Uses. Theorem 1.5.5 (Independence is decided at zero), Proposition 1.2.19 (Restriction of scalars), Example 1.2.6 (Small fields), Theorem 1.6.10 (Every spanning list contains a basis), Proposition 1.4.14 (The span is the smallest subspace containing a list)

Hint 1. One direction holds because a relation over

𝐾

is a relation over

𝐸

. For the other, take a relation

\sum_{𝑗} 𝑐_{𝑗} 𝐯_{𝑗} = 𝟎

with

𝑐_{𝑗} \in 𝐸

Hint 2. The coefficients

𝑐_{1}, \dots, 𝑐_{𝑘}

are vectors of the

𝐾

-vector space

𝐸

. By Theorem 1.6.10, some sublist

𝑟_{1}, \dots, 𝑟_{𝑠}

𝑐_{1}, \dots, 𝑐_{𝑘}

𝐾

-independent and has the same

𝐾

-span.

Hint 3. Write

𝑐_{𝑗} =

\sum_{𝑙} 𝑞_{𝑗 𝑙} 𝑟_{𝑙}

with

𝑞_{𝑗 𝑙} \in 𝐾

, substitute into each coordinate of the relation, and use

𝐾

-independence of the

𝑟_{𝑙}

, then of

ℒ︀

Sketch. (Independence over

𝐸

implies independence over

𝐾

.) A

𝐾

-relation is an

𝐸

-relation. (Independence over

𝐾

implies independence over

𝐸

.) Given an

𝐸

-relation

\sum 𝑐_{𝑗} 𝐯_{𝑗} = 𝟎

, choose a

𝐾

-independent sublist

𝑟_{1}, \dots, 𝑟_{𝑠}

𝑐_{1}, \dots, 𝑐_{𝑘}

with the same

𝐾

-span, and write

𝑐_{𝑗} =

\sum_{𝑙} 𝑞_{𝑗 𝑙} 𝑟_{𝑙}

with

𝑞_{𝑗 𝑙} \in 𝐾

. In coordinate

𝑡

0 =

\sum_{𝑙} (\sum_{𝑗} 𝑞_{𝑗 𝑙} 𝑣_{𝑗 𝑡}) 𝑟_{𝑙}

with coefficients in

𝐾

, so

\sum_{𝑗} 𝑞_{𝑗 𝑙} 𝑣_{𝑗 𝑡} = 0

for all

𝑙, 𝑡

: each

𝑞_{1 𝑙}, \dots, 𝑞_{𝑘 𝑙}

is a

𝐾

-relation of

ℒ︀

, hence trivial. So every

𝑐_{𝑗} = 0

The operations of $𝐾^{𝑚}$ are those of $𝐸^{𝑚}$ restricted to vectors and scalars from $𝐾$ . Write $𝑣_{𝑗 𝑡} \in 𝐾$ for the $𝑡$ -th coordinate of $𝐯_{𝑗}$ .

Independence over $𝐸$ implies independence over $𝐾$ . A relation $𝑎_{1}, \dots, 𝑎_{𝑘} \in 𝐾$ of $ℒ︀$ in $𝐾^{𝑚}$ is also a relation in $𝐸^{𝑚}$ , so it is trivial.

Independence over $𝐾$ implies independence over $𝐸$ . Suppose $ℒ︀$ is independent over $𝐾$ , and let $𝑐_{1}, \dots, 𝑐_{𝑘} \in 𝐸$ with $\sum_{𝑗} 𝑐_{𝑗} 𝐯_{𝑗} = 𝟎$ in $𝐸^{𝑚}$ . The field $𝐸$ is a vector space over itself (Example 1.2.6), hence over $𝐾$ (Proposition 1.2.19), with scalar multiplication the product in $𝐸$ . Let $𝑊$ be the $𝐾$ -span of $𝑐_{1}, \dots, 𝑐_{𝑘}$ in $𝐸$ . It is a $𝐾$ -vector space (Proposition 1.4.14), and $𝑐_{1}, \dots, 𝑐_{𝑘}$ spans it, so by Theorem 1.6.10 some sublist $𝑟_{1}, \dots, 𝑟_{𝑠}$ of $𝑐_{1}, \dots, 𝑐_{𝑘}$ is a basis of $𝑊$ over $𝐾$ . In particular, $𝑟_{1}, \dots, 𝑟_{𝑠}$ is $𝐾$ -independent, and each $𝑐_{𝑗}$ lies in its $𝐾$ -span: $𝑐_{𝑗} =$ $\sum_{𝑙 = 1}^{𝑠} 𝑞_{𝑗 𝑙} 𝑟_{𝑙}$ with $𝑞_{𝑗 𝑙} \in 𝐾$ .

Fix a coordinate $𝑡$ . The $𝑡$ -th coordinate of the relation is, after expanding and regrouping in the field $𝐸$ ,

0 = \sum_{𝑗 = 1}^{𝑘} 𝑐_{𝑗} 𝑣_{𝑗 𝑡} = \sum_{𝑗 = 1}^{𝑘} \sum_{𝑙 = 1}^{𝑠} 𝑞_{𝑗 𝑙} 𝑟_{𝑙} 𝑣_{𝑗 𝑡} = \sum_{𝑙 = 1}^{𝑠} (\sum_{𝑗 = 1}^{𝑘} 𝑞_{𝑗 𝑙} 𝑣_{𝑗 𝑡}) 𝑟_{𝑙} .

Each coefficient $\sum_{𝑗} 𝑞_{𝑗 𝑙} 𝑣_{𝑗 𝑡}$ lies in $𝐾$ . Since $𝑟_{1}, \dots, 𝑟_{𝑠}$ is $𝐾$ -independent, all these coefficients are $0$ . As this holds for every $𝑡$ , we get $\sum_{𝑗} 𝑞_{𝑗 𝑙} 𝐯_{𝑗} = 𝟎$ in $𝐾^{𝑚}$ for each $𝑙$ . Since $ℒ︀$ is $𝐾$ -independent, $𝑞_{𝑗 𝑙} = 0$ for all $𝑗$ and $𝑙$ . Therefore $𝑐_{𝑗} =$ $\sum_{𝑙} 𝑞_{𝑗 𝑙} 𝑟_{𝑙} =$ $0$ for every $𝑗$ , and $ℒ︀$ is independent over $𝐸$ by Theorem 1.5.5.

For $𝐾 = ℝ$ and $𝐸 = ℂ$ , this is Proposition 1.5.21. There the list $1, 𝑖$ played the role of $𝑟_{1}, \dots, 𝑟_{𝑠}$ , chosen once and for all; here the list depends on the relation, which is what makes the argument work when $𝐸$ has no finite spanning list over $𝐾$ (Remark 1.5.23).

Exercise 1.5.43.hard Let $𝐹$ be a finite field with $𝑞$ elements.

(a)Show that a list $ℒ︀$ of length $𝑘$ in $𝑉$ is linearly independent if and only if $span (ℒ︀)$ has exactly $𝑞^{𝑘}$ elements.
(b)Show that the number of linearly independent lists of length $𝑘$ in $𝐹^{𝑛}$ is
$(𝑞^{𝑛} - 1) (𝑞^{𝑛} - 𝑞) (𝑞^{𝑛} - 𝑞^{2}) \dots (𝑞^{𝑛} - 𝑞^{𝑘 - 1}) .$
(c)How many lists of length $3$ in $𝔽_{2}^{3}$ are linearly independent? How many of length $4$ ?

Solution.

Uses. Definition 1.5.1 (Linear independence), Definition 1.3.10 (Span), Exercise 1.3.39, Proposition 1.5.14 (Appending a vector), Corollary 1.5.17 (Sublists), induction on $𝑘$

Hint 1. In (a), consider the map sending a list of coefficients

𝑎_{1}, \dots, 𝑎_{𝑘}

to the vector it represents. It maps

𝐹^{𝑘}

onto

span (ℒ︀)

. What does independence say about it?

Hint 2. For (b), build an independent list one entry at a time with Proposition 1.5.14. Given an independent list of length

𝑗

, how many vectors lie outside its span?

Sketch. (a) The map

𝐹^{𝑘} \to span (ℒ︀)

, coefficients

\mapsto

represented vector, is onto by definition, and injective exactly when

ℒ︀

is independent; a map from a set with

𝑞^{𝑘}

elements onto a set is injective iff the target has

𝑞^{𝑘}

elements. (b) By Proposition 1.5.14, an independent list of length

𝑗 + 1

is an independent list of length

𝑗

followed by a vector outside its span, which has

𝑞^{𝑗}

elements by (a):

𝑞^{𝑛} - 𝑞^{𝑗}

choices. (c)

7 \cdot 6 \cdot 4 = 168

and

0

(a) Let $ℒ︀ = 𝐯_{1}, \dots, 𝐯_{𝑘}$ , and let $𝜑 : 𝐹^{𝑘} \to span (ℒ︀)$ send $(𝑎_{1}, \dots, 𝑎_{𝑘})$ to $𝑎_{1} 𝐯_{1} + \dots + 𝑎_{𝑘} 𝐯_{𝑘}$ . By Definition 1.3.10, $𝜑$ is surjective, and by Definition 1.5.1, $ℒ︀$ is independent exactly when every vector of $span (ℒ︀)$ has one preimage, that is, when $𝜑$ is injective. The set $𝐹^{𝑘}$ has $𝑞^{𝑘}$ elements. A surjection from a set with $𝑞^{𝑘}$ elements onto a finite set is injective if and only if the target also has $𝑞^{𝑘}$ elements. So $ℒ︀$ is independent if and only if $| span (ℒ︀) | = 𝑞^{𝑘}$ .

(b) Let $𝑁_{𝑘}$ be the number of independent lists of length $𝑘$ in $𝐹^{𝑛}$ ; we show $𝑁_{𝑘} =$ $\prod_{𝑖 = 0}^{𝑘 - 1} (𝑞^{𝑛} - 𝑞^{𝑖})$ by induction on $𝑘$ . For $𝑘 = 0$ , the empty list is independent, so $𝑁_{0} = 1$ , the empty product. Let $𝑘 \geq 0$ . By Corollary 1.5.17 and Proposition 1.5.14, an independent list of length $𝑘 + 1$ is the same thing as an independent list $ℒ︀$ of length $𝑘$ followed by a vector $𝐰 \notin span (ℒ︀)$ . For each of the $𝑁_{𝑘}$ choices of $ℒ︀$ , the span has $𝑞^{𝑘}$ elements by (a), so there are $𝑞^{𝑛} - 𝑞^{𝑘}$ choices of $𝐰$ . Hence $𝑁_{𝑘 + 1} =$ $𝑁_{𝑘} (𝑞^{𝑛} - 𝑞^{𝑘})$ , which completes the induction. As soon as $𝑘 > 𝑛$ , the product contains the factor $𝑞^{𝑛} - 𝑞^{𝑛} = 0$ .

(c) For $𝑞 = 2$ , $𝑛 = 3$ , $𝑘 = 3$ : $(8 - 1) (8 - 2) (8 - 4) =$ $7 \cdot$ $6 \cdot$ $4 =$ $168$ . For $𝑘 = 4$ the product contains the factor $8 - 2^{3} = 0$ , so there are none: no list of length $4$ in $𝔽_{2}^{3}$ is independent. Over a finite field this counting argument already proves that an independent list in $𝐹^{𝑛}$ has length at most $𝑛$ , a fact that Section 4.1 proves over every field (Theorem 4.1.10).

Exercise 1.5.44.hard Let

𝑋 = {0, 1, 2, \dots}

, so that

𝐹^{𝑋}

is the space of sequences

(𝑥_{0}, 𝑥_{1}, 𝑥_{2}, \dots)

𝐹

(Remark 1.2.11). For

𝜆 \in 𝐹

, let

𝐬_{𝜆} =

(1, 𝜆, 𝜆^{2}, 𝜆^{3}, \dots)

. Show that if

𝜆_{1}, \dots, 𝜆_{𝑘} \in 𝐹

are distinct, then

𝐬_{𝜆_{1}}, \dots, 𝐬_{𝜆_{𝑘}}

is linearly independent.

Solution.

Uses. Theorem 1.5.5 (Independence is decided at zero), Definition 1.2.9 (Function spaces), Proposition 1.1.17 (No zero divisors)

Techniques. Extremal choice and minimal counterexamples (Technique 1.5.9)

Hint 1. Suppose the list is dependent, and choose a dependence relation

𝑐_{1}, \dots, 𝑐_{𝑘}

with as few nonzero coefficients as possible. A relation says

\sum_{𝑖} 𝑐_{𝑖} 𝜆_{𝑖}^{𝑚} = 0

for every

𝑚 \geq 0

Hint 2. Shift: the same identity holds with

𝑚 + 1

in place of

𝑚

. Subtract

𝜆_{𝑖_{0}}

times the original identity, where

𝑐_{𝑖_{0}} \neq 0

Hint 3. The new relation has coefficients

𝑐_{𝑖} (𝜆_{𝑖} - 𝜆_{𝑖_{0}})

. It has fewer nonzero coefficients, so it is trivial. What does that say about

𝑐_{𝑖}

for

𝑖 \neq 𝑖_{0}

Sketch. Take a dependence relation

\sum 𝑐_{𝑖} 𝜆_{𝑖}^{𝑚} = 0

(all

𝑚

) with the fewest nonzero coefficients, and

𝑖_{0}

with

𝑐_{𝑖_{0}} \neq 0

. Then

\sum_{𝑖} 𝑐_{𝑖} (𝜆_{𝑖} - 𝜆_{𝑖_{0}}) 𝜆_{𝑖}^{𝑚} =

0

for all

𝑚

, a relation with fewer nonzero coefficients (the

𝑖_{0}

one vanishes), hence trivial. Since

𝜆_{𝑖} \neq 𝜆_{𝑖_{0}}

𝑐_{𝑖} = 0

for

𝑖 \neq 𝑖_{0}

, and then the

𝑚 = 0

term gives

𝑐_{𝑖_{0}} = 0

, a contradiction.

The $𝑚$ -th term of $𝐬_{𝜆}$ is $𝜆^{𝑚}$ (with $𝜆^{0} = 1$ ). So scalars $𝑐_{1}, \dots, 𝑐_{𝑘}$ form a linear relation of the list exactly when

\sum_{𝑖 = 1}^{𝑘} 𝑐_{𝑖} 𝜆_{𝑖}^{𝑚} = 0 for every 𝑚 \geq 0 .

Suppose the list is dependent. Among its dependence relations, choose one, $𝑐_{1}, \dots, 𝑐_{𝑘}$ , with the fewest nonzero coefficients, and fix $𝑖_{0}$ with $𝑐_{𝑖_{0}} \neq 0$ . Applying the identity with $𝑚 + 1$ in place of $𝑚$ , and subtracting $𝜆_{𝑖_{0}}$ times the identity for $𝑚$ ,

\sum_{𝑖 = 1}^{𝑘} 𝑐_{𝑖} (𝜆_{𝑖} - 𝜆_{𝑖_{0}}) 𝜆_{𝑖}^{𝑚} = \sum_{𝑖 = 1}^{𝑘} 𝑐_{𝑖} 𝜆_{𝑖}^{𝑚 + 1} - 𝜆_{𝑖_{0}} \sum_{𝑖 = 1}^{𝑘} 𝑐_{𝑖} 𝜆_{𝑖}^{𝑚} = 0 for every 𝑚 \geq 0 .

So $𝑑_{𝑖} =$ $𝑐_{𝑖} (𝜆_{𝑖} - 𝜆_{𝑖_{0}})$ is a linear relation. Every $𝑖$ with $𝑑_{𝑖} \neq 0$ has $𝑐_{𝑖} \neq 0$ , and $𝑑_{𝑖_{0}} = 0$ while $𝑐_{𝑖_{0}} \neq 0$ . So $𝑑$ has fewer nonzero coefficients than $𝑐$ , and by the choice of $𝑐$ it is not a dependence relation: it is trivial. For $𝑖 \neq 𝑖_{0}$ , $𝜆_{𝑖} - 𝜆_{𝑖_{0}} \neq 0$ , so $𝑑_{𝑖} = 0$ forces $𝑐_{𝑖} = 0$ (Proposition 1.1.17). The relation $𝑐$ thus reads $𝑐_{𝑖_{0}} 𝜆_{𝑖_{0}}^{𝑚} = 0$ for all $𝑚$ , and at $𝑚 = 0$ this gives $𝑐_{𝑖_{0}} = 0$ , a contradiction. So the list is independent.

Shifting a sequence multiplies $𝐬_{𝜆}$ by $𝜆$ , just as differentiation multiplies $𝑡 \mapsto 𝑒^{𝜆 𝑡}$ by $𝜆$ ; the argument is the first proof of Example 1.5.27, done once for all $𝑘$ . A variant of the argument, by induction on $𝑘$ instead of a minimal relation, shows that the truncated vectors $(1, 𝜆_{𝑖}, 𝜆_{𝑖}^{2}, \dots, 𝜆_{𝑖}^{𝑘 - 1}) \in$ $𝐹^{𝑘}$ , $1 \leq 𝑖 \leq 𝑘$ , are independent. This is the Vandermonde determinant in disguise (Theorem 5.5.21).

Exercise 1.5.45.hardBeyond 21-242 Let

𝜆_{1}, \dots, 𝜆_{𝑘} \in ℝ

be distinct. Show that the functions

𝑡 \mapsto

𝑒^{𝜆_{1} 𝑡},

\dots,

𝑡 \mapsto

𝑒^{𝜆_{𝑘} 𝑡}

are linearly independent in

ℝ^{ℝ}

Solution.

Uses. Theorem 1.5.5 (Independence is decided at zero), $𝑒^{- 𝑠 𝑡} \to 0$ as $𝑡 \to \infty$ , for $𝑠 > 0$

Techniques. Extremal choice and minimal counterexamples (Technique 1.5.9)

Hint 1. Follow the second proof of Example 1.5.27. In a dependence relation, which term dominates as

𝑡 \to \infty

Hint 2. Among the

𝑖

with

𝑐_{𝑖} \neq 0

, take the one with the largest

𝜆_{𝑖}

, divide by

𝑒^{𝜆_{𝑖} 𝑡}

, and let

𝑡 \to \infty

Sketch. Suppose

\sum 𝑐_{𝑖} 𝑒^{𝜆_{𝑖} 𝑡} = 0

for all

𝑡

with some

𝑐_{𝑖} \neq 0

, and let

𝜇 = 𝜆_{𝑖_{0}}

be the largest

𝜆_{𝑖}

with

𝑐_{𝑖} \neq 0

. Dividing by

𝑒^{𝜇 𝑡}

gives

𝑐_{𝑖_{0}} +

\sum 𝑐_{𝑖} 𝑒^{(𝜆_{𝑖} - 𝜇) 𝑡} =

0

, the sum over the other

𝑖

with

𝑐_{𝑖} \neq 0

, all of which have

𝜆_{𝑖} - 𝜇 < 0

. Letting

𝑡 \to \infty

gives

𝑐_{𝑖_{0}} = 0

, a contradiction.

Suppose, to the contrary, that $\sum_{𝑖 = 1}^{𝑘} 𝑐_{𝑖} 𝑒^{𝜆_{𝑖} 𝑡} =$ $0$ for all $𝑡 \in ℝ$ , with not all $𝑐_{𝑖} = 0$ . Let $𝐼 = {𝑖 | 𝑐_{𝑖} \neq 0}$ , and choose $𝑖_{0} \in 𝐼$ with $𝜇 = 𝜆_{𝑖_{0}}$ as large as possible; since the $𝜆_{𝑖}$ are distinct, $𝜆_{𝑖} < 𝜇$ for all $𝑖 \in 𝐼$ other than $𝑖_{0}$ . Dropping the terms with $𝑐_{𝑖} = 0$ and multiplying by $𝑒^{- 𝜇 𝑡}$ ,

𝑐_{𝑖_{0}} + \sum_{𝑖 \in 𝐼, 𝑖 \neq 𝑖_{0}} 𝑐_{𝑖} 𝑒^{(𝜆_{𝑖} - 𝜇) 𝑡} = 0 for all 𝑡 .

Each exponent $𝜆_{𝑖} - 𝜇$ in the sum is negative, so each term tends to $0$ as $𝑡 \to \infty$ , and the left side tends to $𝑐_{𝑖_{0}}$ . Since it is $0$ for every $𝑡$ , $𝑐_{𝑖_{0}} = 0$ , contradicting $𝑖_{0} \in 𝐼$ . So the functions are independent.

In the language of Aside (Independent sets), the set of all functions $𝑡 \mapsto 𝑒^{𝜆 𝑡}$ with $𝜆 \in ℝ$ is linearly independent, and it is uncountable. The first proof of Example 1.5.27, organized as in Exercise 1.5.44 with $𝑑 / 𝑑 𝑡$ in place of the shift, also works.

Exercise 1.5.46.hard A town has

𝑛

residents, numbered

1, \dots, 𝑛

, and

𝑘

clubs

𝐶_{1},

\dots,

𝐶_{𝑘} \subseteq

{1, \dots, 𝑛}

. Every club has an odd number of members, and for

𝑖 \neq 𝑗

the clubs

𝐶_{𝑖}

and

𝐶_{𝑗}

have an even number of members in common. (In particular, no club is listed twice.) For a club

𝐶

, let

𝐱_{𝐶} \in 𝔽_{2}^{𝑛}

have

𝑡

-th coordinate

1

𝑡 \in 𝐶

and

0

otherwise. Show that

𝐱_{𝐶_{1}}, \dots, 𝐱_{𝐶_{𝑘}}

is linearly independent in

𝔽_{2}^{𝑛}

Solution.

Uses. Theorem 1.5.5 (Independence is decided at zero), Definition 1.2.4 (The space $𝐹^{𝑛}$ ), Example 1.1.4 (The field with two elements)

Hint 1. For

𝐱, 𝐲 \in 𝔽_{2}^{𝑛}

, let

𝐱 \cdot

𝐲 =

𝑥_{1} 𝑦_{1} +

\dots +

𝑥_{𝑛} 𝑦_{𝑛} \in

𝔽_{2}

. What is

𝐱_{𝐶} \cdot 𝐱_{𝐷}

in terms of the clubs

𝐶

and

𝐷

Hint 2. Take a relation

\sum_{𝑗} 𝑎_{𝑗} 𝐱_{𝐶_{𝑗}} = 𝟎

and take the dot product of both sides with

𝐱_{𝐶_{𝑖}}

. Which terms survive?

Sketch.

𝐱_{𝐶} \cdot 𝐱_{𝐷}

is the parity of

| 𝐶 \cap 𝐷 |

, so

𝐱_{𝐶_{𝑖}} \cdot 𝐱_{𝐶_{𝑗}}

1

𝑖 = 𝑗

and

0

otherwise. The dot product satisfies

(\sum_{𝑗} 𝑎_{𝑗} 𝐱_{𝑗}) \cdot

𝐲 =

\sum_{𝑗} 𝑎_{𝑗} (𝐱_{𝑗} \cdot 𝐲)

. Dotting a relation with

𝐱_{𝐶_{𝑖}}

leaves

𝑎_{𝑖} = 0

For $𝐱, 𝐲 \in 𝔽_{2}^{𝑛}$ , define $𝐱 \cdot$ $𝐲 =$ $𝑥_{1} 𝑦_{1} +$ $\dots +$ $𝑥_{𝑛} 𝑦_{𝑛} \in$ $𝔽_{2}$ . By the coordinatewise operations and distributivity in $𝔽_{2}$ , $(𝐱 + 𝐱^{'}) \cdot$ $𝐲 =$ $𝐱 \cdot$ $𝐲 +$ $𝐱^{'} \cdot$ $𝐲$ and $(𝑎 𝐱) \cdot$ $𝐲 =$ $𝑎 (𝐱 \cdot 𝐲)$ , so by induction on the number of terms,

(\sum_{𝑗 = 1}^{𝑘} 𝑎_{𝑗} 𝐱_{𝑗}) \cdot 𝐲 = \sum_{𝑗 = 1}^{𝑘} 𝑎_{𝑗} (𝐱_{𝑗} \cdot 𝐲),

and $𝟎 \cdot 𝐲 = 0$ . For clubs $𝐶$ and $𝐷$ , the product ${(𝐱_{𝐶})}_{𝑡} {(𝐱_{𝐷})}_{𝑡}$ is $1$ if $𝑡 \in 𝐶 \cap 𝐷$ and $0$ otherwise, so $𝐱_{𝐶} \cdot 𝐱_{𝐷}$ is the sum of $| 𝐶 \cap 𝐷 |$ ones in $𝔽_{2}$ , which is $1$ if $| 𝐶 \cap 𝐷 |$ is odd and $0$ if it is even (Example 1.1.4). By hypothesis, writing $𝐱_{𝑗} = 𝐱_{𝐶_{𝑗}}$ ,

𝐱_{𝑖} \cdot 𝐱_{𝑖} = 1, 𝐱_{𝑗} \cdot 𝐱_{𝑖} = 0 (𝑗 \neq 𝑖) .

Now suppose $\sum_{𝑗} 𝑎_{𝑗} 𝐱_{𝑗} = 𝟎$ , and fix $𝑖$ . Taking the dot product of both sides with $𝐱_{𝑖}$ ,

0 = 𝟎 \cdot 𝐱_{𝑖} = \sum_{𝑗 = 1}^{𝑘} 𝑎_{𝑗} (𝐱_{𝑗} \cdot 𝐱_{𝑖}) = 𝑎_{𝑖} .

So every $𝑎_{𝑖} = 0$ , and the list is independent by Theorem 1.5.5.

Taking a dot product with $𝐱_{𝑖}$ eliminated every term of the relation but one, the idea of Technique 4.1.25. Once we know that an independent list in $𝔽_{2}^{𝑛}$ has length at most $𝑛$ (Exercise 1.5.43, Theorem 4.1.10), it follows that the town has at most $𝑛$ clubs.

Exercise 1.5.47.hard Let

𝑎_{1} <

𝑎_{2} <

\dots <

𝑎_{𝑛}

be real numbers, and let

𝑓_{𝑖} (𝑡) =

| 𝑡 -

𝑎_{𝑖} |

. Show that the functions

1

𝑡 \mapsto 𝑡

𝑓_{1}, \dots, 𝑓_{𝑛}

are linearly independent in

ℝ^{ℝ}

. (No calculus is needed.)

Solution.

Uses. Theorem 1.5.5 (Independence is decided at zero), Definition 1.2.9 (Function spaces)

Techniques. Apply an operator to a relation to kill terms (Technique 4.1.25)

Hint 1. For a function

𝑔

, a point

𝑠

, and

ℎ > 0

, consider

Δ_{ℎ} 𝑔 (𝑠) =

𝑔 (𝑠 + ℎ) -

2 𝑔 (𝑠) +

𝑔 (𝑠 - ℎ)

. What is it for

𝑔 (𝑡) = 𝑐 + 𝑑 𝑡

Hint 2. If

ℎ

is smaller than the distance from

𝑎_{𝑖}

to every other

𝑎_{𝑙}

, compute

Δ_{ℎ} 𝑓_{𝑙} (𝑎_{𝑖})

for

𝑙 \neq 𝑖

and for

𝑙 = 𝑖

Sketch. The operation

Δ_{ℎ} 𝑔 (𝑠) =

𝑔 (𝑠 + ℎ) -

2 𝑔 (𝑠) +

𝑔 (𝑠 - ℎ)

respects linear combinations, kills affine functions, and kills

| 𝑡 - 𝑎_{𝑙} |

𝑠 = 𝑎_{𝑖}

when

𝑙 \neq 𝑖

and

ℎ

is small (the function is affine near

𝑎_{𝑖}

). But

Δ_{ℎ} 𝑓_{𝑖} (𝑎_{𝑖}) = 2 ℎ

. Applying it to a relation at

𝑠 = 𝑎_{𝑖}

gives

2 ℎ 𝑏_{𝑖} = 0

. Once all

𝑏_{𝑖} = 0

, evaluating

𝑐 + 𝑑 𝑡 = 0

𝑡 = 0, 1

gives

𝑐 = 𝑑 = 0

For a function $𝑔 : ℝ \to ℝ$ , a point $𝑠$ , and $ℎ > 0$ , let $Δ_{ℎ} 𝑔 (𝑠) =$ $𝑔 (𝑠 + ℎ) -$ $2 𝑔 (𝑠) +$ $𝑔 (𝑠 - ℎ)$ . If $𝑔 = \sum_{𝑟} 𝑐_{𝑟} 𝑔_{𝑟}$ , then $Δ_{ℎ} 𝑔 (𝑠) =$ $\sum_{𝑟} 𝑐_{𝑟} Δ_{ℎ} 𝑔_{𝑟} (𝑠)$ , since the pointwise operations let us expand and regroup.

Affine functions. For $𝑔 (𝑡) = 𝑐 + 𝑑 𝑡$ ,

Δ_{ℎ} 𝑔 (𝑠) = (𝑐 + 𝑑 𝑠 + 𝑑 ℎ) - 2 (𝑐 + 𝑑 𝑠) + (𝑐 + 𝑑 𝑠 - 𝑑 ℎ) = 0 .

The functions $𝑓_{𝑙}$ near $𝑎_{𝑖}$ . Fix $𝑖$ , and let $ℎ > 0$ be smaller than $| 𝑎_{𝑙} - 𝑎_{𝑖} |$ for every $𝑙 \neq 𝑖$ . For $𝑙 \neq 𝑖$ , the interval $[𝑎_{𝑖} - ℎ, 𝑎_{𝑖} + ℎ]$ lies entirely on one side of $𝑎_{𝑙}$ , so on it $𝑓_{𝑙} (𝑡) =$ $𝜀 (𝑡 - 𝑎_{𝑙})$ for a fixed sign $𝜀 \in {1, - 1}$ . This is an affine function of $𝑡$ , so $Δ_{ℎ} 𝑓_{𝑙} (𝑎_{𝑖}) = 0$ by the previous computation. For $𝑙 = 𝑖$ , $Δ_{ℎ} 𝑓_{𝑖} (𝑎_{𝑖}) =$ $| ℎ | -$ $2 \cdot$ $0 +$ $| -$ $ℎ | =$ $2 ℎ$ .

Now suppose that $𝑐 +$ $𝑑 𝑡 +$ $\sum_{𝑙 = 1}^{𝑛} 𝑏_{𝑙} 𝑓_{𝑙} (𝑡) =$ $0$ for all $𝑡$ . Applying $Δ_{ℎ}$ at $𝑠 = 𝑎_{𝑖}$ , with $ℎ$ as above, every term but one vanishes, and we get $2 ℎ 𝑏_{𝑖} = 0$ , so $𝑏_{𝑖} = 0$ . This holds for every $𝑖$ , so $𝑐 + 𝑑 𝑡 = 0$ for all $𝑡$ . At $𝑡 = 0$ this gives $𝑐 = 0$ , and at $𝑡 = 1$ it gives $𝑑 = 0$ . By Theorem 1.5.5, the list is independent.

The operation $Δ_{ℎ}$ at $𝑎_{𝑖}$ measures the kink of a function at $𝑎_{𝑖}$ ; only $𝑓_{𝑖}$ has a kink there. This is the move of Technique 4.1.25 with a “second difference” as the operator.

Exercise 1.5.48.challenge Let

𝜆 \geq 1

and

𝑚 \geq 2

be integers, and let

𝐴_{1}, \dots, 𝐴_{𝑚}

be distinct subsets of

{1, \dots, 𝑛}

such that

| 𝐴_{𝑖} \cap 𝐴_{𝑗} | = 𝜆

for all

𝑖 \neq 𝑗

. For a subset

𝐴

, let

𝐱_{𝐴} \in ℝ^{𝑛}

have

𝑡

-th coordinate

1

𝑡 \in 𝐴

and

0

otherwise. Show that

𝐱_{𝐴_{1}}, \dots, 𝐱_{𝐴_{𝑚}}

is linearly independent in

ℝ^{𝑛}

Solution.

Uses. Theorem 1.5.5 (Independence is decided at zero), Definition 1.2.4 (The space $𝐹^{𝑛}$ ), a sum of nonnegative real numbers is $0$ only if every term is $0$

Techniques. A sum of nonnegative terms (Technique 6.1.9)

Hint 1. For

𝐱, 𝐲 \in ℝ^{𝑛}

, let

𝐱 \cdot

𝐲 =

𝑥_{1} 𝑦_{1} +

\dots +

𝑥_{𝑛} 𝑦_{𝑛}

. What is

𝐱_{𝐴} \cdot 𝐱_{𝐵}

? Given a relation

\sum_{𝑖} 𝑐_{𝑖} 𝐱_{𝐴_{𝑖}} = 𝟎

, take the dot product of the left side with itself.

Hint 2. You should get

0 =

\sum_{𝑖} 𝑐_{𝑖}^{2} | 𝐴_{𝑖} | +

𝜆 \sum_{𝑖 \neq 𝑗} 𝑐_{𝑖} 𝑐_{𝑗}

. Rewrite

\sum_{𝑖 \neq 𝑗} 𝑐_{𝑖} 𝑐_{𝑗}

using

{(\sum_{𝑖} 𝑐_{𝑖})}^{2}

, and check that every resulting term is nonnegative.

Hint 3. Each

| 𝐴_{𝑖} | \geq 𝜆

. Can two of the sets have exactly

𝜆

elements?

Sketch. With

𝐱_{𝑖} = 𝐱_{𝐴_{𝑖}}

𝐱_{𝑖} \cdot

𝐱_{𝑗} =

| 𝐴_{𝑖} \cap

𝐴_{𝑗} |

. Dotting a relation

𝐮 = \sum 𝑐_{𝑖} 𝐱_{𝑖} = 𝟎

with itself gives

0 =

\sum_{𝑖} 𝑐_{𝑖}^{2} (| 𝐴_{𝑖} | - 𝜆) +

𝜆 {(\sum_{𝑖} 𝑐_{𝑖})}^{2}

, a sum of nonnegative terms, so each vanishes:

\sum_{𝑖} 𝑐_{𝑖} = 0

, and

𝑐_{𝑖} = 0

unless

| 𝐴_{𝑖} | = 𝜆

. Two sets with

𝜆

elements would both equal their intersection, so at most one

𝑐_{𝑖}

survives, and

\sum_{𝑖} 𝑐_{𝑖} = 0

kills it.

For $𝐱, 𝐲 \in ℝ^{𝑛}$ , let $𝐱 \cdot$ $𝐲 =$ $𝑥_{1} 𝑦_{1} +$ $\dots +$ $𝑥_{𝑛} 𝑦_{𝑛}$ . By the coordinatewise operations and the arithmetic of $ℝ$ , $𝐱 \cdot 𝐲 = 𝐲 \cdot 𝐱$ , and the dot product respects linear combinations in each argument: expanding and regrouping finite sums,

(\sum_{𝑖} 𝑐_{𝑖} 𝐱_{𝑖}) \cdot (\sum_{𝑗} 𝑐_{𝑗} 𝐱_{𝑗}) = \sum_{𝑖} \sum_{𝑗} 𝑐_{𝑖} 𝑐_{𝑗} (𝐱_{𝑖} \cdot 𝐱_{𝑗}) .

Write $𝐱_{𝑖} = 𝐱_{𝐴_{𝑖}}$ . The product of the $𝑡$ -th coordinates of $𝐱_{𝑖}$ and $𝐱_{𝑗}$ is $1$ if $𝑡 \in 𝐴_{𝑖} \cap 𝐴_{𝑗}$ and $0$ otherwise, so $𝐱_{𝑖} \cdot$ $𝐱_{𝑗} =$ $| 𝐴_{𝑖} \cap$ $𝐴_{𝑗} |$ . This is $𝜆$ for $𝑖 \neq 𝑗$ , and $| 𝐴_{𝑖} |$ for $𝑖 = 𝑗$ .

Suppose $𝐮 = \sum_{𝑖} 𝑐_{𝑖} 𝐱_{𝑖} = 𝟎$ with $𝑐_{𝑖} \in ℝ$ . Then $𝐮 \cdot 𝐮 = 0$ , and by the display,

0 = \sum_{𝑖} 𝑐_{𝑖}^{2} | 𝐴_{𝑖} | + 𝜆 \sum_{𝑖 \neq 𝑗} 𝑐_{𝑖} 𝑐_{𝑗} = \sum_{𝑖} 𝑐_{𝑖}^{2} (| 𝐴_{𝑖} | - 𝜆) + 𝜆 {(\sum_{𝑖} 𝑐_{𝑖})}^{2},

using ${(\sum_{𝑖} 𝑐_{𝑖})}^{2} =$ $\sum_{𝑖} 𝑐_{𝑖}^{2} +$ $\sum_{𝑖 \neq 𝑗} 𝑐_{𝑖} 𝑐_{𝑗}$ . Since $𝑚 \geq 2$ , each $𝐴_{𝑖}$ meets some other $𝐴_{𝑗}$ in $𝜆$ elements, so $| 𝐴_{𝑖} | \geq 𝜆$ . So every term on the right is a nonnegative real number, and since they add up to $0$ , each of them is $0$ . As $𝜆 \geq 1$ , this gives $\sum_{𝑖} 𝑐_{𝑖} = 0$ , and $𝑐_{𝑖} = 0$ for every $𝑖$ with $| 𝐴_{𝑖} | > 𝜆$ .

At most one $𝑖$ has $| 𝐴_{𝑖} | = 𝜆$ . Indeed, if $| 𝐴_{𝑖} | = | 𝐴_{𝑗} | = 𝜆$ with $𝑖 \neq 𝑗$ , then $𝐴_{𝑖} \cap 𝐴_{𝑗}$ is a subset of $𝐴_{𝑖}$ with as many elements as $𝐴_{𝑖}$ , so $𝐴_{𝑖} \cap 𝐴_{𝑗} = 𝐴_{𝑖}$ ; likewise $𝐴_{𝑖} \cap 𝐴_{𝑗} = 𝐴_{𝑗}$ . Then $𝐴_{𝑖} = 𝐴_{𝑗}$ , contradicting distinctness. So all $𝑐_{𝑖}$ vanish except possibly one, and that one equals $\sum_{𝑖} 𝑐_{𝑖} = 0$ . Hence the list is independent by Theorem 1.5.5.

The hypotheses are needed: with $𝜆 = 0$ , the sets $\emptyset, {1}$ give the dependent list $𝟎, 𝐞_{1}$ . Once we know that an independent list in $ℝ^{𝑛}$ has at most $𝑛$ entries (Theorem 4.1.10), it follows that $𝑚 \leq 𝑛$ . This is Fisher’s inequality from combinatorics, and the dot product trick is the one of Exercise 1.5.46, with positivity over $ℝ$ in place of parity over $𝔽_{2}$ .

More practice

The practice bank has 61 exercises on this section’s topics.