1.3 Lists, linear combinations, and span

A vector space has two operations, and each of them combines at most two vectors. Applying them over and over to finitely many vectors $𝐯_{1}, \dots, 𝐯_{𝑘}$ produces sums $𝑎_{1} 𝐯_{1} + \dots + 𝑎_{𝑘} 𝐯_{𝑘}$ , and every expression built from the $𝐯_{𝑖}$ with the two operations can be brought into this form (Lemma 1.3.9). Two questions about these sums run through the rest of the book: which vectors they produce, and in how many ways. This section answers the first question with the span; the second leads to linear independence in Section 1.5. We begin by making “finitely many vectors $𝐯_{1}, \dots, 𝐯_{𝑘}$ ” precise, in a form where the order is fixed and repetitions are allowed.

1.3.1Lists

Definition 1.3.1 (List). Let $𝑉$ be a set and let $𝑘 \geq 0$ be an integer. A list of length $𝑘$ in $𝑉$ is a function ${1, \dots, 𝑘} \to 𝑉$ . Writing $𝐯_{𝑖}$ for its value at $𝑖$ , we write the list as

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

without parentheses, and call $𝐯_{𝑖}$ its $𝑖$ -th entry. Two lists are equal when they have the same length and the same $𝑖$ -th entry for every $𝑖$ . Lists are named by calligraphic letters, as in $ℒ︀ = 𝐯_{1}, \dots, 𝐯_{𝑘}$ , and $| ℒ︀ | = 𝑘$ is the length of $ℒ︀$ . For $𝑘 = 0$ the domain is empty, and there is exactly one function from the empty set to $𝑉$ . It is the empty list, written $()$ .

So a list is a finite sequence. Defining it as a function settles what equality of lists means, and it makes the empty list an ordinary list rather than an exception. A list of length one is written $𝐯$ , and a list of length two $𝐯, 𝐰$ . Columns in $𝐹^{𝑛}$ keep their parentheses, so $(1, 0), (0, 1)$ is a list of length two in $ℝ^{2}$ , and $(1, 0)$ alone is a list of length one.

Example 1.3.2 (Lists versus sets). In

ℝ^{2}

, the lists

(1, 0), (0, 1)

and

(0, 1), (1, 0)

are different, since their first entries differ, while the sets

{(1, 0), (0, 1)}

and

{(0, 1), (1, 0)}

are equal. In any vector space,

𝟎, 𝟎, 𝟎

is a list of length

3

. It is different from the list

𝟎

of length

1

and from the empty list

()

, although

{𝟎, 𝟎, 𝟎} = {𝟎}

as sets.

We work with lists because a linear combination gives each entry its own coefficient. In the list $𝐯, 𝐯$ , the vector $𝐯$ receives two coefficients, and $1 𝐯 + (- 1) 𝐯$ produces $𝟎$ in a way that the set ${𝐯}$ cannot record. This kind of redundancy is what linear independence detects (Section 1.5), and the order of a list will fix the order of coordinates (Section 1.6).

Notation 1.3.3. Let $ℒ︀ = 𝐯_{1}, \dots, 𝐯_{𝑘}$ be a list in $𝑉$ .

We write $𝐯 \in ℒ︀$ if $𝐯 = 𝐯_{𝑖}$ for some $𝑖$ . For a subset $𝑆 \subseteq 𝑉$ , we write $ℒ︀ \subseteq 𝑆$ if every entry of $ℒ︀$ lies in $𝑆$ .
For a list $ℳ︀ = 𝐰_{1}, \dots, 𝐰_{𝑚}$ , the concatenation $ℒ︀, ℳ︀$ is the list $𝐯_{1},$ $\dots,$ $𝐯_{𝑘},$ $𝐰_{1},$ $\dots,$ $𝐰_{𝑚}$ of length $𝑘 + 𝑚$ . In particular, $ℒ︀, 𝐰$ is $ℒ︀$ with $𝐰$ appended.
A sublist of $ℒ︀$ is a list $𝐯_{𝑖_{1}}, \dots, 𝐯_{𝑖_{𝑚}}$ with $1 \leq$ $𝑖_{1} <$ $\dots <$ $𝑖_{𝑚} \leq$ $𝑘$ . It is obtained by deleting some entries and keeping the rest in order. A reordering of $ℒ︀$ is a list $𝐯_{𝜎 (1)},$ $\dots,$ $𝐯_{𝜎 (𝑘)}$ , where $𝜎$ is a bijection from ${1, \dots, 𝑘}$ to itself.

1.3.2Linear combinations

From now on, $𝑉$ is a vector space over a field $𝐹$ .

Definition 1.3.4 (Linear combination). Let $ℒ︀ = 𝐯_{1}, \dots, 𝐯_{𝑘}$ be a list in $𝑉$ . A linear combination of $ℒ︀$ is an expression

𝑎_{1} 𝐯_{1} + 𝑎_{2} 𝐯_{2} + \dots + 𝑎_{𝑘} 𝐯_{𝑘}, also written \sum_{𝑖 = 1}^{𝑘} 𝑎_{𝑖} 𝐯_{𝑖},

where $𝑎_{1}, \dots, 𝑎_{𝑘} \in 𝐹$ are its coefficients. Two linear combinations of $ℒ︀$ are the same exactly when their coefficients are the same. Carrying out the operations of $𝑉$ in the expression produces a vector of $𝑉$ , and we say that the linear combination represents that vector. The empty list has exactly one linear combination, the empty sum, and it represents $𝟎$ .

To carry out the operations, compute each term $𝑎_{𝑖} 𝐯_{𝑖}$ and add the terms from left to right:

\sum_{𝑖 = 1}^{0} 𝑎_{𝑖} 𝐯_{𝑖} = 𝟎, \sum_{𝑖 = 1}^{𝑘} 𝑎_{𝑖} 𝐯_{𝑖} = (\sum_{𝑖 = 1}^{𝑘 - 1} 𝑎_{𝑖} 𝐯_{𝑖}) + 𝑎_{𝑘} 𝐯_{𝑘} (𝑘 \geq 1) .

(1.3.1)

By (A1) and (A2), neither the order nor the grouping of the terms affects the result; the argument is the one for sums in a field (Section 1.1.2). The empty sum must be $𝟎$ if the recursion is to give $\sum_{𝑖 = 1}^{1} 𝑎_{𝑖} 𝐯_{𝑖} =$ $𝑎_{1} 𝐯_{1}$ .

The definition separates two things that everyday usage runs together: the expression, which is determined by its coefficients once $ℒ︀$ is fixed, and the vector it represents. Formally, a linear combination of $ℒ︀$ is just its list of coefficients $𝑎_{1}, \dots, 𝑎_{𝑘}$ . When we write $𝐰 =$ $𝑎_{1} 𝐯_{1} +$ $\dots +$ $𝑎_{𝑘} 𝐯_{𝑘}$ , the equation says that the linear combination on the right represents $𝐰$ . We also say “ $𝐰$ is a linear combination of $ℒ︀$ ” to mean that some linear combination of $ℒ︀$ represents $𝐰$ . This phrase is standard and harmless, as long as we keep track of which object is meant. The next example shows why the distinction matters.

Example 1.3.5 (One vector, many representations). In $ℝ^{2}$ , let ${ℒ︀}_{1} =$ $(0, 0),$ $(1, - 1),$ $(- 𝜋, 𝜋)$ . The linear combinations

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

are different, because their coefficients differ, but both represent $(1, - 1)$ . So “the linear combination equal to $(1, - 1)$ ” does not name a single linear combination of ${ℒ︀}_{1}$ . By contrast, in $𝐹^{2}$ the vector $(𝑥, 𝑦)$ is represented by exactly one linear combination of $(1, 0), (0, 1)$ : the combination $𝑎 (1, 0) + 𝑏 (0, 1)$ represents $(𝑎, 𝑏)$ , which is $(𝑥, 𝑦)$ only if $𝑎 = 𝑥$ and $𝑏 = 𝑦$ . Lists with this uniqueness property are the linearly independent ones (Section 1.5).

Exercise 1.3.6.routine For the list

{ℒ︀}_{1}

of Example 1.3.5, find all linear combinations of

{ℒ︀}_{1}

that represent

(1, - 1)

, and all that represent

𝟎

. How are the two families related?

Solution.

Uses. Definition 1.3.4 (Linear combination), Definition 1.2.4 (The space $𝐹^{𝑛}$ )

Hint 1. Compute the vector represented by an arbitrary linear combination

𝑎_{1} (0, 0) +

𝑎_{2} (1, - 1) +

𝑎_{3} (- 𝜋, 𝜋)

, one coordinate at a time.

Hint 2. The second coordinate is always the negative of the first, so a single equation constrains

𝑎_{1}, 𝑎_{2}, 𝑎_{3}

. Which coefficient does not appear in it?

Sketch. The combination represents

(𝑎_{2} - 𝜋 𝑎_{3}, - (𝑎_{2} - 𝜋 𝑎_{3}))

. It represents

(1, - 1)

exactly when

𝑎_{2} = 1 + 𝜋 𝑎_{3}

, and

𝟎

exactly when

𝑎_{2} = 𝜋 𝑎_{3}

, with

𝑎_{1}

and

𝑎_{3}

free in both cases. Adding the coefficients of each representation of

𝟎

to those of one representation of

(1, - 1)

gives all representations of

(1, - 1)

By the coordinatewise operations, the linear combination with coefficients $𝑎_{1}, 𝑎_{2}, 𝑎_{3}$ represents

𝑎_{1} (0, 0) + 𝑎_{2} (1, - 1) + 𝑎_{3} (- 𝜋, 𝜋) = (𝑎_{2} - 𝜋 𝑎_{3}, - 𝑎_{2} + 𝜋 𝑎_{3}) .

The second coordinate is the negative of the first. So the combination represents $(1, - 1)$ exactly when $𝑎_{2} - 𝜋 𝑎_{3} = 1$ , and it represents $𝟎$ exactly when $𝑎_{2} - 𝜋 𝑎_{3} = 0$ ; the coefficient $𝑎_{1}$ plays no role. Hence the linear combinations representing $(1, - 1)$ are those with coefficients

𝑎_{1}, 1 + 𝜋 𝑡, 𝑡 (𝑎_{1}, 𝑡 \in ℝ),

and those representing $𝟎$ are those with coefficients $𝑎_{1}, 𝜋 𝑡, 𝑡$ for $𝑎_{1}, 𝑡 \in ℝ$ . The first family is obtained from the single representation with coefficients $0, 1, 0$ by adding the coefficients of each member of the second: $(0 + 𝑎_{1}, 1 + 𝜋 𝑡, 0 + 𝑡)$ . Exercise 1.3.40 shows that this is a general phenomenon.

Example 1.3.7 (Standard lists). For $1 \leq 𝑖 \leq 𝑛$ , let $𝐞_{𝑖} \in 𝐹^{𝑛}$ be the column with $1$ in position $𝑖$ and $0$ elsewhere. For every $𝐱 =$ $(𝑥_{1}, \dots, 𝑥_{𝑛}) \in$ $𝐹^{𝑛}$ ,

𝐱 = 𝑥_{1} 𝐞_{1} + 𝑥_{2} 𝐞_{2} + \dots + 𝑥_{𝑛} 𝐞_{𝑛},

because by the coordinatewise operations, the $𝑖$ -th coordinate of the right side is $𝑥_{1} \cdot$ $0 +$ $\dots +$ $𝑥_{𝑖} \cdot$ $1 +$ $\dots +$ $𝑥_{𝑛} \cdot$ $0 =$ $𝑥_{𝑖}$ . So every vector of $𝐹^{𝑛}$ is a linear combination of $𝐞_{1}, \dots, 𝐞_{𝑛}$ , the standard basis of $𝐹^{𝑛}$ (Definition 1.6.8).

In $𝐹 [𝑥]$ , Notation 1.2.15 says that the polynomial with coefficients $(𝑎_{0}, \dots, 𝑎_{𝑑}, 0, 0, \dots)$ is represented by the linear combination $𝑎_{0} \cdot$ $1 +$ $𝑎_{1} 𝑥 +$ $\dots +$ $𝑎_{𝑑} 𝑥^{𝑑}$ of the list $1, 𝑥, \dots, 𝑥^{𝑑}$ . The coefficients of the polynomial and those of the linear combination coincide.

Example 1.3.8 (Is a vector a linear combination?). Is $(1, 2, 3) \in ℝ^{3}$ a linear combination of $(1, 1, 0), (0, 1, 1)$ ? An arbitrary linear combination represents

𝑎 (1, 1, 0) + 𝑏 (0, 1, 1) = (𝑎, 𝑎 + 𝑏, 𝑏) .

For this to be $(1, 2, 3)$ , we need $𝑎 = 1$ , $𝑏 = 3$ , and $𝑎 + 𝑏 = 2$ . The first two equations force $𝑎 + 𝑏 = 4$ , so no linear combination works, and the answer is no. In contrast, $(1, 4, 3) =$ $1 (1, 1, 0) +$ $3 (0, 1, 1)$ .

The answer depends on the field. Read in $𝔽_{2}^{3}$ , the same coordinates give the vector $(1, 0, 1)$ , and the equations become $𝑎 = 1$ , $𝑏 = 1$ , and $𝑎 + 𝑏 = 0$ . These hold, since $1 + 1 = 0$ in $𝔽_{2}$ . Indeed, $(1, 1, 0) +$ $(0, 1, 1) =$ $(1, 2, 1) =$ $(1, 0, 1)$ in $𝔽_{2}^{3}$ .

In general, deciding whether $𝐰$ is a linear combination of $𝐯_{1}, \dots, 𝐯_{𝑘}$ means deciding whether the equation $𝑎_{1} 𝐯_{1} +$ $\dots +$ $𝑎_{𝑘} 𝐯_{𝑘} =$ $𝐰$ can be solved for the coefficients. In $𝐹^{𝑛}$ this is a system of linear equations, and Section 3.1 develops the general method (Technique 3.1.9).

Computing with linear combinations relies on the following rules.

Lemma 1.3.9 (Arithmetic of linear combinations). Let $ℒ︀ = 𝐯_{1}, \dots, 𝐯_{𝑘}$ be a list in $𝑉$ , and let $𝑎_{1},$ $\dots,$ $𝑎_{𝑘},$ $𝑏_{1},$ $\dots,$ $𝑏_{𝑘},$ $𝑐 \in$ $𝐹$ . Then

(a) $\sum_{𝑖 = 1}^{𝑘} 𝑎_{𝑖} 𝐯_{𝑖} +$ $\sum_{𝑖 = 1}^{𝑘} 𝑏_{𝑖} 𝐯_{𝑖} =$ $\sum_{𝑖 = 1}^{𝑘} (𝑎_{𝑖} + 𝑏_{𝑖}) 𝐯_{𝑖}$ ;
(b) $𝑐 \sum_{𝑖 = 1}^{𝑘} 𝑎_{𝑖} 𝐯_{𝑖} =$ $\sum_{𝑖 = 1}^{𝑘} (𝑐 𝑎_{𝑖}) 𝐯_{𝑖}$ ;
(c) $\sum_{𝑖 = 1}^{𝑘} 0 𝐯_{𝑖} = 𝟎$ .

Here each sum denotes the vector that the linear combination represents.

Proof.routine

Uses. (1.3.1), Definition 1.2.1 (Vector space), Proposition 1.2.32 (The scalar zero), Proposition 1.2.33 (The zero vector), induction on $𝑘$

Hint 1. Use induction on

𝑘

, splitting off the last term of each sum as in (1.3.1).

Hint 2. In the inductive step of (a), regroup

(𝐱 + 𝑎 𝐯) +

(𝐲 + 𝑏 𝐯)

(𝐱 + 𝐲) +

(𝑎 𝐯 + 𝑏 𝐯)

and apply (A8) to the second part. For (b), apply (A7) and then (A6).

Sketch. Induction on

𝑘

. For

𝑘 = 0

every sum is

𝟎

, and

𝟎 + 𝟎 = 𝟎

𝑐 𝟎 = 𝟎

. In the inductive step, write each sum as the sum of its first

𝑘

terms plus its last term. Then (a) follows by regrouping with (A1) and (A2) and applying (A8) to the last terms, (b) follows from (A7) and (A6), and (c) from

0 𝐯_{𝑘 + 1} = 𝟎

For a list of scalars $𝑎 = 𝑎_{1}, 𝑎_{2}, \dots$ , write $𝑆_{𝑘} (𝑎) =$ $\sum_{𝑖 = 1}^{𝑘} 𝑎_{𝑖} 𝐯_{𝑖}$ , and write $𝑎 + 𝑏$ and $𝑐 𝑎$ for the lists with entries $𝑎_{𝑖} + 𝑏_{𝑖}$ and $𝑐 𝑎_{𝑖}$ . By (1.3.1), $𝑆_{0} (𝑎) = 𝟎$ and $𝑆_{𝑘 + 1} (𝑎) =$ $𝑆_{𝑘} (𝑎) +$ $𝑎_{𝑘 + 1} 𝐯_{𝑘 + 1}$ . We use induction on $𝑘$ .

For $𝑘 = 0$ all the sums are empty. Then (a) reads $𝟎 + 𝟎 = 𝟎$ , which is (A3); (b) reads $𝑐 𝟎 = 𝟎$ , which is Proposition 1.2.33; and (c) reads $𝟎 = 𝟎$ .

Now suppose that (a)–(c) hold for lists of length $𝑘$ , and consider a list of length $𝑘 + 1$ . For (a),

\begin{aligned} 𝑆_{𝑘 + 1} (𝑎) + 𝑆_{𝑘 + 1} (𝑏) & = (𝑆_{𝑘} (𝑎) + 𝑎_{𝑘 + 1} 𝐯_{𝑘 + 1}) + (𝑆_{𝑘} (𝑏) + 𝑏_{𝑘 + 1} 𝐯_{𝑘 + 1}) \\ = (𝑆_{𝑘} (𝑎) + 𝑆_{𝑘} (𝑏)) + (𝑎_{𝑘 + 1} 𝐯_{𝑘 + 1} + 𝑏_{𝑘 + 1} 𝐯_{𝑘 + 1}) & (A1, A2) \\ = 𝑆_{𝑘} (𝑎 + 𝑏) + (𝑎_{𝑘 + 1} + 𝑏_{𝑘 + 1}) 𝐯_{𝑘 + 1} & (induction, A8) \\ = 𝑆_{𝑘 + 1} (𝑎 + 𝑏) . \end{aligned}

For (b),

\begin{aligned} 𝑐 𝑆_{𝑘 + 1} (𝑎) & = 𝑐 𝑆_{𝑘} (𝑎) + 𝑐 (𝑎_{𝑘 + 1} 𝐯_{𝑘 + 1}) & (A7) \\ = 𝑆_{𝑘} (𝑐 𝑎) + (𝑐 𝑎_{𝑘 + 1}) 𝐯_{𝑘 + 1} = 𝑆_{𝑘 + 1} (𝑐 𝑎) & (induction, A6) . \end{aligned}

For (c), $𝑆_{𝑘 + 1} (0) =$ $𝑆_{𝑘} (0) +$ $0 𝐯_{𝑘 + 1} =$ $𝟎 +$ $𝟎 =$ $𝟎$ , by the inductive hypothesis, Proposition 1.2.32, and (A3). □

Together with $- 𝐯 = (- 1) 𝐯$ (Proposition 1.2.34), the lemma rewrites any expression built from $𝐯_{1}, \dots, 𝐯_{𝑘}$ with addition, subtraction, and scalar multiplication as a single linear combination of $𝐯_{1}, \dots, 𝐯_{𝑘}$ . For example, reading $𝐯_{1} + 3 𝐯_{2}$ and $𝐯_{1}$ as the linear combinations of $𝐯_{1}, 𝐯_{2}$ with coefficients $1, 3$ and $1, 0$ ,

2 (𝐯_{1} + 3 𝐯_{2}) - 𝐯_{1} = (2 𝐯_{1} + 6 𝐯_{2}) + ((- 1) 𝐯_{1} + 0 𝐯_{2}) = 𝐯_{1} + 6 𝐯_{2} .

1.3.3Span

Definition 1.3.10 (Span). The span of a list $ℒ︀ = 𝐯_{1}, \dots, 𝐯_{𝑘}$ in $𝑉$ is the set of vectors represented by linear combinations of $ℒ︀$ :

span (ℒ︀) = {𝑎_{1} 𝐯_{1} + \dots + 𝑎_{𝑘} 𝐯_{𝑘} | 𝑎_{1}, \dots, 𝑎_{𝑘} \in 𝐹} \subseteq 𝑉 .

We also write $span (𝐯_{1}, \dots, 𝐯_{𝑘})$ for $span (ℒ︀)$ . In particular, $span (()) = {𝟎}$ , since the only linear combination of the empty list represents $𝟎$ .

So $𝐰 \in span (ℒ︀)$ means that there are scalars $𝑎_{1}, \dots, 𝑎_{𝑘}$ with $𝐰 =$ $𝑎_{1} 𝐯_{1} +$ $\dots +$ $𝑎_{𝑘} 𝐯_{𝑘}$ . To show that $𝐰$ is in the span, exhibit the scalars. To show that it is not, show that no choice of scalars works. Usually this means finding a property that every vector of the span has and $𝐰$ lacks. In Example 1.3.8, every vector $(𝑎, 𝑎 + 𝑏, 𝑏)$ of the span has middle coordinate equal to the sum of the outer two, and $(1, 2, 3)$ does not.

Example 1.3.11 (Small spans). One vector. $span (𝐯) =$ ${𝑎 𝐯 | 𝑎 \in 𝐹}$ is the set of multiples of $𝐯$ . In $ℝ^{2}$ with $𝐯 \neq 𝟎$ , it is the line through $𝟎$ and $𝐯$ . In $𝔽_{2}^{𝑛}$ it is ${𝟎, 𝐯}$ , since the only scalars are $0$ and $1$ .

Zero. $span (𝟎) =$ ${𝑎 𝟎 | 𝑎 \in 𝐹} =$ ${𝟎}$ by Proposition 1.2.33. So the lists $()$ , $𝟎$ , and $𝟎, 𝟎$ are different, but they have the same span.

Standard lists. By Example 1.3.7, $span (𝐞_{1}, \dots, 𝐞_{𝑛}) =$ $𝐹^{𝑛}$ . Similarly $span (1, 𝑥, \dots, 𝑥^{𝑑}) =$ ${𝐹 [𝑥]}_{\leq 𝑑}$ : a linear combination $𝑎_{0} +$ $𝑎_{1} 𝑥 +$ $\dots +$ $𝑎_{𝑑} 𝑥^{𝑑}$ has no nonzero coefficients beyond position $𝑑$ , so it has degree at most $𝑑$ , and conversely Definition 1.2.16 describes ${𝐹 [𝑥]}_{\leq 𝑑}$ as the set of such combinations.

Functions. In $ℝ^{ℝ}$ , the identity $sin (𝑡 + 𝑐) =$ $cos 𝑐 sin 𝑡 +$ $sin 𝑐 cos 𝑡$ shows that every shift $𝑡 \mapsto sin (𝑡 + 𝑐)$ of the sine function lies in $span (sin, cos)$ . The constant function $1$ does not: if $1 = 𝑎 sin + 𝑏 cos$ as functions, then evaluating at $𝑡 = 0$ and at $𝑡 = 𝜋$ gives $1 = 𝑏$ and $1 = - 𝑏$ , a contradiction.

Figure 1.3.1. The faint lines are the combinations

𝑎 𝐮 + 𝑏 𝐯

𝐮 = (2, 1)

and

𝐯 = (- 1, 1)

in which

𝑎

𝑏

is an integer. Every vector of

ℝ^{2}

appears to be a combination of

𝐮

and

𝐯

; for instance,

𝐰 =

(1, 3) =

\frac{4}{3} 𝐮 +

\frac{5}{3} 𝐯

Figure 1.3.1 suggests that two vectors pointing in different directions span the whole plane; Exercise 1.3.37 makes this precise.

Definition 1.3.12 (Spanning list). A list

ℒ︀

𝑉

spans

𝑉

, and is a spanning list of

𝑉

, if

span (ℒ︀) = 𝑉

By Example 1.3.11, $𝐞_{1}, \dots, 𝐞_{𝑛}$ spans $𝐹^{𝑛}$ , the list $1, 𝑥, \dots, 𝑥^{𝑑}$ spans ${𝐹 [𝑥]}_{\leq 𝑑}$ , and the empty list spans the zero space ${𝟎}$ . A spanning list may contain entries that are not needed: $(1, 0), (0, 1), (1, 1)$ also spans $ℝ^{2}$ . Spanning lists without such entries are the bases of Section 1.6.

Double containment

Describing a span explicitly means proving that two sets are equal: the span, whose elements are the vectors that some linear combination represents, and a set described in another way, typically by equations. Such proofs follow a fixed pattern, built from two moves.

Technique 1.3.13 (Fix an arbitrary element and chase it). To prove $𝐴 \subseteq 𝐵$ , let $𝑥$ be an arbitrary element of $𝐴$ . Unpack the definition of $𝐴$ until $𝑥$ is described concretely, manipulate that description until it matches the definition of $𝐵$ , and conclude that $𝑥 \in 𝐵$ . Since $𝑥$ was arbitrary, $𝐴 \subseteq 𝐵$ .

Reach for it for every containment between sets defined by properties. Once both definitions are written out, the proof has a fixed shape: the first line is “let $𝑥 \in 𝐴$ ”, the next uses the definition of $𝐴$ , and the last uses the definition of $𝐵$ . For spans, unpacking produces scalars (“let $𝐰 \in span (ℒ︀)$ , say $𝐰 =$ $𝑎_{1} 𝐯_{1} +$ $\dots +$ $𝑎_{𝑘} 𝐯_{𝑘}$ ”), and repacking means exhibiting scalars. The canonical example is each half of Example 1.3.15.

Used in 31 places and 1 practice exercise

Example 1.3.15, Exercise 1.3.16, Proposition 1.3.18, Proposition 1.4.14, Proposition 1.4.16, Proposition 1.4.22, Proposition 1.4.24, Exercise 1.7.5, Proposition 2.5.4, Proposition 2.5.5, Exercise 2.5.33, Proposition 2.6.8, Theorem 2.6.11, Proposition 2.6.15, Exercise 2.6.36, Exercise 2.6.39, Exercise 2.6.51, Exercise 2.6.52, Proposition 2.7.7, Problem 2.1, Proposition 4.2.3, Proposition 4.5.5, Theorem 4.5.17, Theorem 4.6.5, Proposition 4.7.3, Proposition 4.7.10, Proposition 6.3.9, Proposition 7.2.30, Proposition A.1.5, Theorem A.1.12, Exercise A.1.26; 1 practice exercise.

Technique 1.3.14 (Double containment). To prove that two sets $𝐴$ and $𝐵$ are equal, prove $𝐴 \subseteq 𝐵$ and $𝐵 \subseteq 𝐴$ separately, each by Technique 1.3.13.

Reach for it whenever a claim says that two sets are equal. The two containments usually need different ideas, and one is often much easier than the other. For a span, “ $span (ℒ︀) \subseteq 𝐵$ ” is a computation with an arbitrary linear combination, while “ $𝐵 \subseteq span (ℒ︀)$ ” requires constructing coefficients for each element of $𝐵$ . A common mistake is to prove one containment carefully and forget the other (Exercise 1.3.30). The canonical example is Example 1.3.15.

Used in 43 places and 7 practice exercises

Example 1.3.15, Exercise 1.3.16, Corollary 1.3.19, Exercise 1.3.26, Exercise 1.3.30, Exercise 1.3.32, Exercise 1.3.33, Exercise 1.3.36, Corollary 1.4.17, Exercise 1.4.35, Exercise 1.4.36, Exercise 1.4.37, Exercise 1.4.44, Exercise 1.7.5, Exercise 1.7.15, Proposition 2.1.16, Corollary 2.6.31, Exercise 2.6.39, Exercise 2.6.51, Proposition 3.1.19, Exercise 3.1.41, Exercise 3.1.45, Proposition 3.2.30, Exercise 3.2.46, Problem 3.1, Proposition 4.4.2, Proposition 4.6.11, Lemma 4.6.14, Exercise 4.6.40, Proposition 4.7.3, Exercise 6.2.42, Proposition 6.3.9, Exercise 6.3.11, Theorem 6.4.15, Corollary 6.4.25, Theorem 6.4.26, Exercise 6.4.47, Proposition 6.5.9, Proposition 6.6.23, Proposition A.1.5, Exercise A.2.10, Lemma A.3.5, Exercise A.3.20; 7 practice exercises.

Example 1.3.15 (A span that is a line). In $ℝ^{2}$ , let ${ℒ︀}_{1} =$ $(0, 0),$ $(1, - 1),$ $(- 𝜋, 𝜋)$ as in Example 1.3.5, and let

𝑊 = {(𝑐_{1}, 𝑐_{2}) \in ℝ^{2} | 𝑐_{2} = - 𝑐_{1}} .

Then $span ({ℒ︀}_{1}) = 𝑊$ . In particular, $(2, 0) \notin span ({ℒ︀}_{1})$ , since $0 \neq - 2$ .

Proof.routine

Uses. Definition 1.3.10 (Span), Definition 1.3.4 (Linear combination), Definition 1.2.4 (The space $𝐹^{𝑛}$ )

Techniques. Double containment (Technique 1.3.14), Fix an arbitrary element and chase it (Technique 1.3.13)

Hint 1. Write out both definitions. What does an element of

span ({ℒ︀}_{1})

look like, and what condition defines

𝑊

Hint 2. For

span ({ℒ︀}_{1}) \subseteq 𝑊

, compute an arbitrary linear combination coordinatewise. For

𝑊 \subseteq span ({ℒ︀}_{1})

, you need coefficients for

(𝑐_{1}, - 𝑐_{1})

, and one entry of

{ℒ︀}_{1}

suffices.

Sketch. Every linear combination of

{ℒ︀}_{1}

represents

(𝑎_{2} - 𝜋 𝑎_{3}, - (𝑎_{2} - 𝜋 𝑎_{3}))

, which lies in

𝑊

. Conversely,

(𝑐_{1}, - 𝑐_{1}) =

0 (0, 0) +

𝑐_{1} (1, - 1) +

0 (- 𝜋, 𝜋)

We proceed by double containment.

$span ({ℒ︀}_{1}) \subseteq 𝑊$ . Let $𝐰 \in span ({ℒ︀}_{1})$ . Then some linear combination of ${ℒ︀}_{1}$ represents $𝐰$ , so for some $𝑎_{1}, 𝑎_{2}, 𝑎_{3} \in ℝ$ ,

𝐰 = 𝑎_{1} (0, 0) + 𝑎_{2} (1, - 1) + 𝑎_{3} (- 𝜋, 𝜋) = (𝑎_{2} - 𝜋 𝑎_{3}, - 𝑎_{2} + 𝜋 𝑎_{3}) .

The second coordinate of $𝐰$ is $- 𝑎_{2} +$ $𝜋 𝑎_{3} =$ $- (𝑎_{2} - 𝜋 𝑎_{3})$ , the negative of the first, so $𝐰 \in 𝑊$ .

$𝑊 \subseteq span ({ℒ︀}_{1})$ . Let $(𝑐_{1}, 𝑐_{2}) \in 𝑊$ . By the definition of $𝑊$ , $𝑐_{2} = - 𝑐_{1}$ , so

(𝑐_{1}, 𝑐_{2}) = (𝑐_{1}, - 𝑐_{1}) = 0 (0, 0) + 𝑐_{1} (1, - 1) + 0 (- 𝜋, 𝜋) .

This linear combination of ${ℒ︀}_{1}$ represents $(𝑐_{1}, 𝑐_{2})$ , so $(𝑐_{1}, 𝑐_{2}) \in$ $span ({ℒ︀}_{1})$ , as desired. □

The two containments needed different kinds of argument. The first was a computation that applies to every linear combination at once. The second needed one well-chosen linear combination for each element of $𝑊$ , and it used only the entry $(1, - 1)$ . The other two entries of ${ℒ︀}_{1}$ contribute nothing to the span, and Example 1.3.21 explains why without computing anything.

The span of

{ℒ︀}_{1}

is the line

𝑐_{2} = - 𝑐_{1}

, and

(2, 0)

is not on it. In the interactive version,

(- 𝜋, 𝜋)

is replaced by

(- 3, 3)

, which has the same span. Drag an entry off the line: the span becomes all of

ℝ^{2}

, and the explorer shows coefficients that represent

𝐰 = (2, 0)

Exercise 1.3.16.routine Show that

span ((1, 0, - 1), (0, 1, - 1)) = {(𝑥, 𝑦, 𝑧) \in ℝ^{3} | 𝑥 + 𝑦 + 𝑧 = 0} .

Solution.

Uses. Definition 1.3.10 (Span), Definition 1.2.4 (The space $𝐹^{𝑛}$ )

Techniques. Double containment (Technique 1.3.14), Fix an arbitrary element and chase it (Technique 1.3.13)

Hint 1. Compute the vector represented by

𝑎 (1, 0, - 1) +

𝑏 (0, 1, - 1)

and add up its coordinates.

Hint 2. For the other containment, a vector

(𝑥, 𝑦, 𝑧)

with

𝑥 + 𝑦 + 𝑧 = 0

has

𝑧 = - 𝑥 - 𝑦

. Which coefficients reproduce its first two coordinates?

Sketch.

𝑎 (1, 0, - 1) +

𝑏 (0, 1, - 1) =

(𝑎, 𝑏, - 𝑎 - 𝑏)

has coordinate sum

0

. Conversely, if

𝑥 + 𝑦 + 𝑧 = 0

then

(𝑥, 𝑦, 𝑧) =

(𝑥, 𝑦, - 𝑥 - 𝑦) =

𝑥 (1, 0, - 1) +

𝑦 (0, 1, - 1)

Let $𝑃 =$ ${(𝑥, 𝑦, 𝑧) \in ℝ^{3} | 𝑥 + 𝑦 + 𝑧 = 0}$ . We proceed by double containment.

$span \subseteq 𝑃$ . Every element of the span is represented by some linear combination $𝑎 (1, 0, - 1) +$ $𝑏 (0, 1, - 1) =$ $(𝑎, 𝑏, - 𝑎 - 𝑏)$ , whose coordinates add up to $𝑎 + 𝑏 - 𝑎 - 𝑏 = 0$ . So it lies in $𝑃$ .

$𝑃 \subseteq span$ . Let $(𝑥, 𝑦, 𝑧) \in 𝑃$ . Then $𝑧 = - 𝑥 - 𝑦$ , and

𝑥 (1, 0, - 1) + 𝑦 (0, 1, - 1) = (𝑥, 𝑦, - 𝑥 - 𝑦) = (𝑥, 𝑦, 𝑧) .

So $(𝑥, 𝑦, 𝑧)$ is in the span, as desired.

1.3.4Comparing spans

A span is usually an infinite set, so comparing two spans element by element means checking infinitely many vectors. The results of this subsection reduce such a comparison to finitely many checks.

Proposition 1.3.17 (A list lies in its span). Let

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

be a list in

𝑉

. Then

𝟎 \in span (ℒ︀)

, and

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

for each

𝑗

. That is,

ℒ︀ \subseteq span (ℒ︀)

Proof.routine

Uses. Definition 1.3.10 (Span), Lemma 1.3.9 (Arithmetic of linear combinations), Proposition 1.2.32 (The scalar zero)

Hint 1. Membership in a span is shown by exhibiting coefficients.

Hint 2. Use the coefficients

0, \dots, 0

for

𝟎

. For

𝐯_{𝑗}

, use the coefficient

1

𝐯_{𝑗}

and

0

on every other entry.

Sketch.

𝟎 = 0 𝐯_{1} + \dots + 0 𝐯_{𝑘}

, and

𝐯_{𝑗}

is represented by the combination with coefficient

1

in position

𝑗

and

0

elsewhere, since

0 𝐯_{𝑖} = 𝟎

and

1 𝐯_{𝑗} = 𝐯_{𝑗}

By Lemma 1.3.9(c), the linear combination with all coefficients

0

represents

𝟎

, so

𝟎 \in span (ℒ︀)

. Now fix

𝑗

, and consider the linear combination with

𝑎_{𝑗} = 1

and

𝑎_{𝑖} = 0

for

𝑖 \neq 𝑗

. Its terms are

1 𝐯_{𝑗} = 𝐯_{𝑗}

, by (A5), and

0 𝐯_{𝑖} = 𝟎

for

𝑖 \neq 𝑗

, by Proposition 1.2.32. Adding copies of

𝟎

changes nothing, by (A3), so this linear combination represents

𝐯_{𝑗}

, and

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

. □

Intuition (Recipes of recipes). Think of a linear combination of $ℒ︀$ as a recipe that says how much of each $𝐯_{𝑖}$ to use. Suppose that every entry of $ℳ︀ = 𝐰_{1}, \dots, 𝐰_{𝑚}$ has a recipe in terms of $ℒ︀$ . A linear combination of $ℳ︀$ is then a recipe whose ingredients are themselves recipes, and expanding it gives a recipe in terms of $ℒ︀$ . For instance, if $𝐰_{1} = 𝐯_{1} + 𝐯_{2}$ and $𝐰_{2} = 𝐯_{1} - 𝐯_{2}$ , then

3 𝐰_{1} + 2 𝐰_{2} = (3 𝐯_{1} + 3 𝐯_{2}) + (2 𝐯_{1} - 2 𝐯_{2}) = 5 𝐯_{1} + 𝐯_{2} .

So as soon as the finitely many entries of $ℳ︀$ lie in $span (ℒ︀)$ , every vector of $span (ℳ︀)$ does.

Proposition 1.3.18 (Comparing spans). Let

ℒ︀

and

ℳ︀

be lists in

𝑉

. Then

span (ℳ︀) \subseteq span (ℒ︀)

if and only if

ℳ︀ \subseteq span (ℒ︀)

Proof.standard

Uses. Proposition 1.3.17 (A list lies in its span), Lemma 1.3.9 (Arithmetic of linear combinations), Definition 1.3.10 (Span), induction on $𝑚$

Techniques. Fix an arbitrary element and chase it (Technique 1.3.13)

Hint 1. One direction follows at once from Proposition 1.3.17. For the other, let

𝐮 \in span (ℳ︀)

and write

𝐮 = \sum_{𝑗} 𝑐_{𝑗} 𝐰_{𝑗}

Hint 2. Replace each

𝐰_{𝑗}

by a linear combination of

ℒ︀

that represents it, say

𝐰_{𝑗} =

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

. Then use Lemma 1.3.9 to collect the coefficient of each

𝐯_{𝑖}

Sketch. (

\Rightarrow

)

ℳ︀ \subseteq

span (ℳ︀) \subseteq

span (ℒ︀)

. (

\Leftarrow

) If

𝐰_{𝑗} =

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

, then by Lemma 1.3.9,

\sum_{𝑗} 𝑐_{𝑗} 𝐰_{𝑗} =

\sum_{𝑗} \sum_{𝑖} (𝑐_{𝑗} 𝑏_{𝑖 𝑗}) 𝐯_{𝑖} =

\sum_{𝑖} (\sum_{𝑗} 𝑐_{𝑗} 𝑏_{𝑖 𝑗}) 𝐯_{𝑖}

, which is a linear combination of

ℒ︀

Write $ℒ︀ = 𝐯_{1}, \dots, 𝐯_{𝑘}$ and $ℳ︀ = 𝐰_{1}, \dots, 𝐰_{𝑚}$ .

( $\Rightarrow$ ) By Proposition 1.3.17, $ℳ︀ \subseteq span (ℳ︀)$ , and $span (ℳ︀) \subseteq span (ℒ︀)$ by assumption.

( $\Leftarrow$ ) Suppose that $ℳ︀ \subseteq span (ℒ︀)$ . For each $𝑗$ , choose scalars $𝑏_{1 𝑗}, \dots, 𝑏_{𝑘 𝑗}$ with

𝐰_{𝑗} = \sum_{𝑖 = 1}^{𝑘} 𝑏_{𝑖 𝑗} 𝐯_{𝑖} .

Let $𝐮 \in span (ℳ︀)$ , say $𝐮 =$ $\sum_{𝑗 = 1}^{𝑚} 𝑐_{𝑗} 𝐰_{𝑗}$ with $𝑐_{1}, \dots, 𝑐_{𝑚} \in 𝐹$ . By Lemma 1.3.9(b), $𝑐_{𝑗} 𝐰_{𝑗} =$ $\sum_{𝑖 = 1}^{𝑘} (𝑐_{𝑗} 𝑏_{𝑖 𝑗}) 𝐯_{𝑖}$ for each $𝑗$ . Adding these $𝑚$ vectors one at a time with Lemma 1.3.9(a), that is, by induction on $𝑚$ , gives

𝐮 = \sum_{𝑗 = 1}^{𝑚} \sum_{𝑖 = 1}^{𝑘} (𝑐_{𝑗} 𝑏_{𝑖 𝑗}) 𝐯_{𝑖} = \sum_{𝑖 = 1}^{𝑘} (\sum_{𝑗 = 1}^{𝑚} 𝑐_{𝑗} 𝑏_{𝑖 𝑗}) 𝐯_{𝑖} .

(For $𝑚 = 0$ both sides are $𝟎$ , by Lemma 1.3.9(c).) So $𝐮$ is represented by the linear combination of $ℒ︀$ with coefficients $𝑑_{𝑖} =$ $\sum_{𝑗} 𝑐_{𝑗} 𝑏_{𝑖 𝑗}$ , and $𝐮 \in span (ℒ︀)$ . Since $𝐮$ was arbitrary, $span (ℳ︀) \subseteq span (ℒ︀)$ , as desired. □

The forward direction is Proposition 1.3.17. The backward direction is the useful one: to show that one span contains another, it suffices to check the finitely many entries of one list. Section 1.4 gives a second proof. There we show that $span (ℒ︀)$ is the smallest subspace of $𝑉$ containing the entries of $ℒ︀$ (Proposition 1.4.14), and the backward direction follows at once.

Corollary 1.3.19 (Equal spans). Let

ℒ︀

and

ℳ︀

be lists in

𝑉

. Then

span (ℒ︀) = span (ℳ︀)

if and only if

ℒ︀ \subseteq span (ℳ︀)

and

ℳ︀ \subseteq span (ℒ︀)

Proof.routine

Uses. Proposition 1.3.18 (Comparing spans)

Techniques. Double containment (Technique 1.3.14)

Hint 1. Split the equality of sets into two containments.

Hint 2. Apply Proposition 1.3.18 to each containment.

Sketch.

span (ℒ︀) \subseteq span (ℳ︀)

if and only if

ℒ︀ \subseteq span (ℳ︀)

, and

span (ℳ︀) \subseteq span (ℒ︀)

if and only if

ℳ︀ \subseteq span (ℒ︀)

The sets

span (ℒ︀)

and

span (ℳ︀)

are equal exactly when each contains the other. By Proposition 1.3.18,

span (ℒ︀) \subseteq span (ℳ︀)

holds exactly when

ℒ︀ \subseteq span (ℳ︀)

, and

span (ℳ︀) \subseteq span (ℒ︀)

holds exactly when

ℳ︀ \subseteq span (ℒ︀)

. □

Corollary 1.3.20 (Operations that preserve the span). Let $ℒ︀ = 𝐯_{1}, \dots, 𝐯_{𝑘}$ be a list in $𝑉$ .

(a)Every reordering of $ℒ︀$ has the same span as $ℒ︀$ .
(b)If ${ℒ︀}^{'}$ is a sublist of $ℒ︀$ , then $span ({ℒ︀}^{'}) \subseteq$ $span (ℒ︀)$ .
(c)For $𝐰 \in 𝑉$ , $span (ℒ︀, 𝐰) =$ $span (ℒ︀)$ if and only if $𝐰 \in span (ℒ︀)$ . In particular, appending $𝟎$ or a second copy of an entry of $ℒ︀$ does not change the span.
(d)Let $𝑖 \neq 𝑗$ , and let $𝑎, 𝑐 \in 𝐹$ with $𝑐 \neq 0$ . Replacing $𝐯_{𝑗}$ by $𝑐 𝐯_{𝑗}$ , or by $𝐯_{𝑗} + 𝑎 𝐯_{𝑖}$ , does not change the span.

Proof.routine

Uses. Corollary 1.3.19 (Equal spans), Proposition 1.3.18 (Comparing spans), Proposition 1.3.17 (A list lies in its span), Notation 1.3.3

Hint 1. Each part compares the spans of two lists. By Corollary 1.3.19, it suffices to check that the entries of each list lie in the span of the other, and Proposition 1.3.17 handles the entries the two lists share.

Hint 2. For (d), write

𝐯_{𝑗}

in terms of the new entries:

𝐯_{𝑗} = 𝑐^{- 1} (𝑐 𝐯_{𝑗})

, and

𝐯_{𝑗} =

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

(- 𝑎) 𝐯_{𝑖}

Sketch. (a) The two lists have the same entries. (b)

{ℒ︀}^{'} \subseteq ℒ︀ \subseteq span (ℒ︀)

. (c) If

𝐰 \in span (ℒ︀)

, then every entry of

ℒ︀, 𝐰

lies in

span (ℒ︀)

, and

ℒ︀

is a sublist of

ℒ︀, 𝐰

; conversely

𝐰 \in span (ℒ︀, 𝐰)

. (d) The new entry is a linear combination of

ℒ︀

, and

𝐯_{𝑗}

is a linear combination of the new list because

𝑐 \neq 0

and

𝑖 \neq 𝑗

(a) A reordering ${ℒ︀}^{'}$ of $ℒ︀$ has the same entries as $ℒ︀$ . By Proposition 1.3.17, ${ℒ︀}^{'} \subseteq span (ℒ︀)$ and $ℒ︀ \subseteq span ({ℒ︀}^{'})$ , so the spans are equal by Corollary 1.3.19.

(b) Every entry of ${ℒ︀}^{'}$ is an entry of $ℒ︀$ , so ${ℒ︀}^{'} \subseteq span (ℒ︀)$ by Proposition 1.3.17, and $span ({ℒ︀}^{'}) \subseteq$ $span (ℒ︀)$ by Proposition 1.3.18.

(c) Suppose that $𝐰 \in span (ℒ︀)$ . The entries of $ℒ︀, 𝐰$ are the $𝐯_{𝑖}$ , which lie in $span (ℒ︀)$ by Proposition 1.3.17, and $𝐰$ , which lies there by assumption. So $span (ℒ︀, 𝐰) \subseteq$ $span (ℒ︀)$ by Proposition 1.3.18. Conversely, $ℒ︀$ is a sublist of $ℒ︀, 𝐰$ , so $span (ℒ︀) \subseteq$ $span (ℒ︀, 𝐰)$ by (b). Now suppose instead that $span (ℒ︀, 𝐰) =$ $span (ℒ︀)$ . Then $𝐰 \in$ $span (ℒ︀, 𝐰) =$ $span (ℒ︀)$ by Proposition 1.3.17. The last statement of (c) follows, since $𝟎$ and the entries of $ℒ︀$ lie in $span (ℒ︀)$ by Proposition 1.3.17.

(d) Let ${ℒ︀}^{'}$ be $ℒ︀$ with $𝐯_{𝑗}$ replaced by $𝐯_{𝑗}^{'}$ , where $𝐯_{𝑗}^{'} = 𝑐 𝐯_{𝑗}$ or $𝐯_{𝑗}^{'} = 𝐯_{𝑗} + 𝑎 𝐯_{𝑖}$ . The entries of ${ℒ︀}^{'}$ other than $𝐯_{𝑗}^{'}$ are entries of $ℒ︀$ , and $𝐯_{𝑗}^{'}$ is a linear combination of $ℒ︀$ : the one with coefficient $𝑐$ on $𝐯_{𝑗}$ and $0$ elsewhere, or the one with coefficient $1$ on $𝐯_{𝑗}$ , $𝑎$ on $𝐯_{𝑖}$ , and $0$ elsewhere (this uses $𝑖 \neq 𝑗$ ). So ${ℒ︀}^{'} \subseteq span (ℒ︀)$ . In the other direction, the entries of $ℒ︀$ other than $𝐯_{𝑗}$ are entries of ${ℒ︀}^{'}$ , and

𝐯_{𝑗} = 𝑐^{- 1} (𝑐 𝐯_{𝑗}) or 𝐯_{𝑗} = (𝐯_{𝑗} + 𝑎 𝐯_{𝑖}) + (- 𝑎) 𝐯_{𝑖},

by (A6) and (A5), or by (A2), (A8), Proposition 1.2.32, and (A3). Since $𝑐 \neq 0$ , and since $𝐯_{𝑖}$ is still an entry of ${ℒ︀}^{'}$ (as $𝑖 \neq 𝑗$ ), these are linear combinations of ${ℒ︀}^{'}$ . So $ℒ︀ \subseteq span ({ℒ︀}^{'})$ , and Corollary 1.3.19 finishes the proof. □

Combining (a) and (c): the entry $𝐯_{𝑗}$ can be deleted from $ℒ︀$ without changing the span exactly when $𝐯_{𝑗}$ lies in the span of the remaining entries. (Reorder so that $𝐯_{𝑗}$ comes last, and apply (c).) Parts (a) and (d) are the three moves of row reduction, applied to the entries of a list: swap two entries, scale an entry by a nonzero scalar, and add a multiple of one entry to another. Section 3.3 performs them on the rows of a matrix. Both hypotheses in (d) are needed: scaling by $𝑐 = 0$ , or replacing $𝐯_{𝑗}$ by $𝐯_{𝑗} + (- 1) 𝐯_{𝑗}$ , turns $𝐯_{𝑗}$ into $𝟎$ , and in $ℝ^{2}$ this shrinks $span (𝐞_{1}, 𝐞_{2}) = ℝ^{2}$ to the line $span (𝐞_{1})$ .

Example 1.3.21 (A span that is a line, again). In ${ℒ︀}_{1} =$ $(0, 0),$ $(1, - 1),$ $(- 𝜋, 𝜋)$ , the third entry is $- 𝜋 (1, - 1)$ and the first is $𝟎$ . By Corollary 1.3.20(c), together with (a) to move entries to the end, we may delete $(- 𝜋, 𝜋)$ , since it lies in $span ((0, 0), (1, - 1))$ , and then delete $(0, 0)$ . Hence

span ({ℒ︀}_{1}) = span ((1, - 1)) = {𝑐 (1, - 1) | 𝑐 \in ℝ} = {(𝑐, - 𝑐) | 𝑐 \in ℝ},

which is the set $𝑊$ of Example 1.3.15. Two observations about entries have replaced the double containment.

Example 1.3.22 (Equal spans, and a small field). Let $ℒ︀ =$ $(1, 1, 0),$ $(0, 1, 1)$ and $ℳ︀ =$ $(1, 2, 1),$ $(1, 0, - 1)$ in $𝐹^{3}$ . We transform $ℒ︀$ into $ℳ︀$ with the moves of Corollary 1.3.20(d):

(1, 1, 0), (0, 1, 1) ⇝ (1, 2, 1), (0, 1, 1) ⇝ (1, 2, 1), (0, - 2, - 2) ⇝ (1, 2, 1), (1, 0, - 1) .

The first move adds the second entry to the first, the second scales the second entry by $- 2$ , and the third adds the first entry to the second. Each move preserves the span, provided that $- 2 \neq 0$ in $𝐹$ , which holds exactly when $1 + 1 \neq 0$ . So over $ℚ$ , $ℝ$ , $ℂ$ , or $𝔽_{3}$ , $span (ℒ︀) = span (ℳ︀)$ .

Over $𝔽_{2}$ the conclusion is false. There $(1, 2, 1) =$ $(1, 0, - 1) =$ $(1, 0, 1)$ , so $ℳ︀$ is the list $(1, 0, 1), (1, 0, 1)$ , and $span (ℳ︀) =$ $span ((1, 0, 1)) =$ ${𝟎, (1, 0, 1)}$ by Corollary 1.3.20(c) and Example 1.3.11. This set does not contain the vector $(1, 1, 0)$ of $span (ℒ︀)$ . The move that fails is the scaling by $- 2 = 0$ . Testing the claim over $𝔽_{2}$ (Technique 1.2.38) is how one notices that the hypothesis $𝑐 \neq 0$ in (d) is doing real work.

Remark 1.3.23 (What the span forgets). By Corollary 1.3.20, the span of a list depends neither on the order of the entries, nor on repetitions, nor on entries that lie in the span of the others. In particular, it depends only on the set of entries (Exercise 1.3.24), and lists of different lengths can have the same span. The span also does not record how many linear combinations represent each of its vectors. Section 1.5 shows that some entry of a list lies in the span of the other entries exactly when some vector of its span has more than one representation.

Exercise 1.3.24.routine Let

ℒ︀

and

ℳ︀

be lists in

𝑉

with the same set of entries; that is,

𝐯 \in ℒ︀

if and only if

𝐯 \in ℳ︀

. Show that

span (ℒ︀) = span (ℳ︀)

Solution.

Uses. Corollary 1.3.19 (Equal spans), Proposition 1.3.17 (A list lies in its span)

Hint 1. By Corollary 1.3.19, it suffices to show

ℒ︀ \subseteq span (ℳ︀)

and

ℳ︀ \subseteq span (ℒ︀)

Hint 2. Each entry of

ℒ︀

is an entry of

ℳ︀

. Where do the entries of

ℳ︀

lie?

Sketch. Every entry of

ℒ︀

is an entry of

ℳ︀

, hence lies in

span (ℳ︀)

by Proposition 1.3.17, and symmetrically. Apply Corollary 1.3.19.

Let

𝐯 \in ℒ︀

. By assumption

𝐯 \in ℳ︀

, so

𝐯 \in span (ℳ︀)

by Proposition 1.3.17. Hence

ℒ︀ \subseteq span (ℳ︀)

, and by the same argument with the roles exchanged,

ℳ︀ \subseteq span (ℒ︀)

. By Corollary 1.3.19,

span (ℒ︀) = span (ℳ︀)

Exercise 1.3.25.routine Let

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

, and let

𝐰_{𝑗} = 𝐯_{1} + \dots + 𝐯_{𝑗}

for

1 \leq 𝑗 \leq 𝑘

. Show that

span (𝐰_{1}, \dots, 𝐰_{𝑘}) =

span (𝐯_{1}, \dots, 𝐯_{𝑘})

Solution.

Uses. Corollary 1.3.19 (Equal spans)

Hint 1. Use Corollary 1.3.19. Each

𝐰_{𝑗}

is visibly a linear combination of the

𝐯_{𝑖}

Hint 2. Recover

𝐯_{𝑗}

from two consecutive partial sums.

Sketch.

𝐰_{𝑗}

is the combination of the

𝐯_{𝑖}

with coefficients

1

in positions

1, \dots, 𝑗

and

0

after. Conversely

𝐯_{1} = 𝐰_{1}

and

𝐯_{𝑗} = 𝐰_{𝑗} - 𝐰_{𝑗 - 1}

for

𝑗 \geq 2

Write $𝒱︀ = 𝐯_{1}, \dots, 𝐯_{𝑘}$ and $𝒲︀ = 𝐰_{1}, \dots, 𝐰_{𝑘}$ . Each $𝐰_{𝑗}$ is represented by the linear combination of $𝒱︀$ with coefficient $1$ on $𝐯_{1}, \dots, 𝐯_{𝑗}$ and $0$ on the remaining entries, so $𝒲︀ \subseteq span (𝒱︀)$ . Conversely, $𝐯_{1} = 𝐰_{1}$ , and for $𝑗 \geq 2$ ,

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

by Proposition 1.2.30(a). So each $𝐯_{𝑗}$ is a linear combination of $𝒲︀$ , with coefficient $1$ on $𝐰_{𝑗}$ , $- 1$ on $𝐰_{𝑗 - 1}$ , and $0$ elsewhere, and $𝒱︀ \subseteq span (𝒲︀)$ . By Corollary 1.3.19, the spans are equal.

Aside (Spans of infinite sets).Beyond 21-242 Every linear combination has finitely many terms. A vector space only adds two vectors at a time, and an infinite sum would need a notion of convergence, which a general vector space does not have. For an arbitrary subset

𝑆 \subseteq 𝑉

, possibly infinite, one defines

span (𝑆)

as the set of vectors represented by linear combinations of finite lists in

𝑆

; the empty list is allowed, so

span (\emptyset) = {𝟎}

. For a finite set

𝑆

, this is the span of any list whose set of entries is

𝑆

(Exercise 1.3.24). For example,

span ({1, 𝑥, 𝑥^{2}, \dots}) =

𝐹 [𝑥]

, since each polynomial is a linear combination of

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

for some

𝑑

, while no finite list spans

𝐹 [𝑥]

(Section 1.6). Spanning sets of this kind are the subject of Section 15.1.

Exercises

Exercise 1.3.26.routine Let $ℒ︀ =$ $(1, 2, 0),$ $(0, 1, 1)$ in $ℝ^{3}$ .

(a)Show that $span (ℒ︀) =$ ${(𝑥, 𝑦, 𝑧) \in ℝ^{3} | 𝑦 = 2 𝑥 + 𝑧}$ .
(b)Decide whether $(1, 1, 1)$ and $(2, 5, 1)$ lie in $span (ℒ︀)$ . For each one that does, find a linear combination of $ℒ︀$ that represents it.

Solution.

Uses. Definition 1.3.10 (Span), Definition 1.2.4 (The space $𝐹^{𝑛}$ )

Techniques. Double containment (Technique 1.3.14)

Hint 1. For (a), compute the vector represented by

𝑎 (1, 2, 0) +

𝑏 (0, 1, 1)

and compare its middle coordinate with the outer ones.

Hint 2. For the other containment in (a), the coefficients can be read off from the first and third coordinates. Then (b) is a matter of checking the equation

𝑦 = 2 𝑥 + 𝑧

Sketch. (a)

𝑎 (1, 2, 0) +

𝑏 (0, 1, 1) =

(𝑎, 2 𝑎 + 𝑏, 𝑏)

satisfies

𝑦 = 2 𝑥 + 𝑧

; conversely, if

𝑦 = 2 𝑥 + 𝑧

, then

(𝑥, 𝑦, 𝑧) =

𝑥 (1, 2, 0) +

𝑧 (0, 1, 1)

. (b)

(1, 1, 1)

fails the equation since

2 + 1 \neq 1

;

(2, 5, 1)

satisfies it, and

(2, 5, 1) =

2 (1, 2, 0) +

(0, 1, 1)

(a) Let $𝑃 =$ ${(𝑥, 𝑦, 𝑧) \in ℝ^{3} | 𝑦 = 2 𝑥 + 𝑧}$ . We proceed by double containment. An element of $span (ℒ︀)$ is represented by some linear combination

𝑎 (1, 2, 0) + 𝑏 (0, 1, 1) = (𝑎, 2 𝑎 + 𝑏, 𝑏),

and its middle coordinate $2 𝑎 + 𝑏$ is twice the first plus the third. So $span (ℒ︀) \subseteq 𝑃$ . Conversely, let $(𝑥, 𝑦, 𝑧) \in 𝑃$ . Then

𝑥 (1, 2, 0) + 𝑧 (0, 1, 1) = (𝑥, 2 𝑥 + 𝑧, 𝑧) = (𝑥, 𝑦, 𝑧),

so $(𝑥, 𝑦, 𝑧) \in$ $span (ℒ︀)$ . Hence $𝑃 \subseteq span (ℒ︀)$ .

(b) For $(1, 1, 1)$ we have $2 \cdot 1 + 1 = 3 \neq 1$ , so $(1, 1, 1) \notin span (ℒ︀)$ by (a). For $(2, 5, 1)$ we have $2 \cdot 2 + 1 = 5$ , so $(2, 5, 1) \in span (ℒ︀)$ , and the proof of (a) gives the representation $(2, 5, 1) =$ $2 (1, 2, 0) +$ $1 (0, 1, 1)$ .

Exercise 1.3.27.routine Let $ℒ︀ =$ $(1, 1, 0),$ $(0, 1, 2)$ in $𝔽_{3}^{3}$ .

(a)List the elements of $span (ℒ︀)$ , and decide whether $(1, 0, 1)$ and $(1, 1, 1)$ belong to it.
(b)Let $ℳ︀ =$ $(1, 1, 0),$ $(0, 1, 2),$ $(1, 2, 2)$ . Show that $span (ℳ︀) = span (ℒ︀)$ . How many linear combinations of $ℳ︀$ are there, and how many of them represent $(1, 0, 1)$ ?

Solution.

Uses. Definition 1.3.10 (Span), Corollary 1.3.20 (Operations that preserve the span), Definition 1.3.4 (Linear combination)

Hint 1. The combination

𝑎 (1, 1, 0) +

𝑏 (0, 1, 2)

represents

(𝑎, 𝑎 + 𝑏, 2 𝑏)

. Run through the nine choices of

𝑎, 𝑏 \in 𝔽_{3}

, reducing modulo

3

Hint 2. For (b),

(1, 2, 2)

is the sum of the other two entries. Rewrite an arbitrary combination of

ℳ︀

as a combination of

ℒ︀

and use that the nine vectors in (a) are distinct.

Sketch. (a) The span consists of the vectors

(𝑎, 𝑎 + 𝑏, 2 𝑏)

(0, 0, 0),

(0, 1, 2),

(0, 2, 1),

(1, 1, 0),

(1, 2, 2),

(1, 0, 1),

(2, 2, 0),

(2, 0, 2),

(2, 1, 1)

. It contains

(1, 0, 1)

(

𝑎 = 1

𝑏 = 2

) but not

(1, 1, 1)

. (b)

(1, 2, 2) \in span (ℒ︀)

. There are

27

combinations;

𝑎, 𝑏, 𝑐

represents

(𝑎 + 𝑐) (1, 1, 0) +

(𝑏 + 𝑐) (0, 1, 2)

, which is

(1, 0, 1)

exactly when

𝑎 + 𝑐 = 1

and

𝑏 + 𝑐 = 2

, giving

3

combinations, one for each

𝑐

(a) The combination with coefficients $𝑎, 𝑏$ represents $𝑎 (1, 1, 0) +$ $𝑏 (0, 1, 2) =$ $(𝑎, 𝑎 + 𝑏, 2 𝑏)$ . Running through $𝑎, 𝑏 \in 𝔽_{3}$ and reducing modulo $3$ :

\begin{aligned} 𝑎 = 0 : & (0, 0, 0), (0, 1, 2), (0, 2, 1), \\ 𝑎 = 1 : & (1, 1, 0), (1, 2, 2), (1, 0, 1), \\ 𝑎 = 2 : & (2, 2, 0), (2, 0, 2), (2, 1, 1), \end{aligned}

with $𝑏 = 0, 1, 2$ in each row. These nine vectors are distinct, because the first coordinate determines $𝑎$ and the third determines $𝑏$ (as $2 𝑏 = 2 𝑏^{'}$ forces $𝑏 = 𝑏^{'}$ ). The vector $(1, 0, 1)$ appears, with $𝑎 = 1$ and $𝑏 = 2$ . The vector $(1, 1, 1)$ does not: $𝑎 = 1$ and $2 𝑏 = 1$ force $𝑏 = 2$ , and then $𝑎 + 𝑏 = 0 \neq 1$ .

(b) In $𝔽_{3}^{3}$ , $(1, 1, 0) +$ $(0, 1, 2) =$ $(1, 2, 2)$ , so the third entry of $ℳ︀$ lies in $span (ℒ︀)$ , and $span (ℳ︀) = span (ℒ︀)$ by Corollary 1.3.20(c). A linear combination of $ℳ︀$ is determined by its three coefficients, so there are $3^{3} = 27$ of them. By Lemma 1.3.9, the one with coefficients $𝑎, 𝑏, 𝑐$ represents

𝑎 (1, 1, 0) + 𝑏 (0, 1, 2) + 𝑐 ((1, 1, 0) + (0, 1, 2)) = (𝑎 + 𝑐) (1, 1, 0) + (𝑏 + 𝑐) (0, 1, 2) .

By (a), the combinations of $ℒ︀$ represent distinct vectors for distinct coefficients, and $(1, 0, 1)$ is represented by the coefficients $1, 2$ . So $𝑎, 𝑏, 𝑐$ represents $(1, 0, 1)$ exactly when $𝑎 + 𝑐 = 1$ and $𝑏 + 𝑐 = 2$ . For each $𝑐 \in 𝔽_{3}$ there is exactly one such $𝑎$ and $𝑏$ , so exactly $3$ linear combinations of $ℳ︀$ represent $(1, 0, 1)$ : those with coefficients $1, 2, 0$ , then $0, 1, 1$ , and $2, 0, 2$ . The same count holds for each of the nine vectors of the span, and $9 \cdot 3 = 27$ .

Exercise 1.3.28.routine

(a)Find all lists $ℒ︀$ in $𝑉$ with $span (ℒ︀) = {𝟎}$ . Which lists span the zero space?
(b)Let $𝐯, 𝐰 \in 𝑉$ . Show that $span (𝐯) = span (𝐰)$ if and only if $𝐰 = 𝑐 𝐯$ for some nonzero $𝑐 \in 𝐹$ .

Solution.

Uses. Proposition 1.3.17 (A list lies in its span), Proposition 1.3.18 (Comparing spans), Corollary 1.3.19 (Equal spans), Definition 1.3.10 (Span), Proposition 1.2.33 (The zero vector)

Hint 1. For (a), if some entry is nonzero, what does Proposition 1.3.17 say? If all entries are

𝟎

, compare with the empty list.

Hint 2. For (b), the forward direction gives

𝐰 = 𝑐 𝐯

for some

𝑐

. Rule out

𝑐 = 0

separately in the cases

𝐯 = 𝟎

and

𝐯 \neq 𝟎

Sketch. (a)

span (ℒ︀) = {𝟎}

exactly when every entry is

𝟎

, the empty list included; these are also exactly the lists that span

{𝟎}

. (b) If

𝐰 = 𝑐 𝐯

with

𝑐 \neq 0

, then

𝐯 = 𝑐^{- 1} 𝐰

, so the spans agree. Conversely

𝐰 \in span (𝐯)

gives

𝐰 = 𝑐 𝐯

; if

𝑐 = 0

then

𝐰 = 𝟎

, so

𝐯 \in span (𝟎) = {𝟎}

and

𝐰 = 1 𝐯

anyway.

(a) If some entry $𝐯_{𝑗}$ of $ℒ︀$ is nonzero, then $𝐯_{𝑗} \in span (ℒ︀)$ by Proposition 1.3.17, so $span (ℒ︀) \neq {𝟎}$ . If every entry of $ℒ︀$ is $𝟎$ (this includes the empty list), then $ℒ︀ \subseteq {𝟎} = span (())$ , so $span (ℒ︀) \subseteq {𝟎}$ by Proposition 1.3.18, and $𝟎 \in span (ℒ︀)$ by Proposition 1.3.17. So $span (ℒ︀) = {𝟎}$ exactly when all entries of $ℒ︀$ are $𝟎$ . A list in the zero space has all its entries equal to $𝟎$ , so by what we just showed, every list in ${𝟎}$ spans it: $()$ , $𝟎$ , $𝟎, 𝟎$ , and so on.

(b) Suppose $𝐰 = 𝑐 𝐯$ with $𝑐 \neq 0$ . Then $𝐰 \in span (𝐯)$ , and $𝐯 =$ $𝑐^{- 1} (𝑐 𝐯) =$ $𝑐^{- 1} 𝐰 \in$ $span (𝐰)$ by (A6) and (A5). So the spans are equal by Corollary 1.3.19.

Conversely, suppose $span (𝐯) = span (𝐰)$ . Then $𝐰 \in span (𝐯)$ by Proposition 1.3.17, so $𝐰 = 𝑐 𝐯$ for some $𝑐 \in 𝐹$ . If $𝑐 \neq 0$ we are done. If $𝑐 = 0$ , then $𝐰 = 𝟎$ , so $span (𝐯) =$ $span (𝟎) =$ ${𝟎}$ , and therefore $𝐯 = 𝟎$ by (a). Then $𝐰 = 𝟎 = 1 𝐯$ , with $1 \neq 0$ .

Exercise 1.3.29.routine

(a)Find the error in the following argument.
Claim. Let $𝐯_{1}, 𝐯_{2} \in 𝑉$ and $𝑎_{1},$ $𝑎_{2},$ $𝑏_{1},$ $𝑏_{2} \in$ $𝐹$ . If $𝑎_{1} 𝐯_{1} +$ $𝑎_{2} 𝐯_{2} =$ $𝑏_{1} 𝐯_{1} +$ $𝑏_{2} 𝐯_{2}$ , then $𝑎_{1} = 𝑏_{1}$ and $𝑎_{2} = 𝑏_{2}$ .
Proof. Two linear combinations of $𝐯_{1}, 𝐯_{2}$ are the same exactly when they have the same coefficients (Definition 1.3.4). The two sides of the hypothesis are equal, so their coefficients are equal.
(b)Show that the claim is false in general, and that it is true for $𝐯_{1} = (1, 0)$ and $𝐯_{2} = (0, 1)$ in $𝐹^{2}$ .

Solution.

Uses. Definition 1.3.4 (Linear combination), Example 1.3.5 (One vector, many representations)

Hint 1. What does the equation

𝑎_{1} 𝐯_{1} +

𝑎_{2} 𝐯_{2} =

𝑏_{1} 𝐯_{1} +

𝑏_{2} 𝐯_{2}

assert: that two expressions are the same, or that two vectors are equal?

Hint 2. For a counterexample, take

𝐯_{1} = 𝐯_{2}

Sketch. The equation says that the two linear combinations represent the same vector, not that they are the same linear combination. With

𝐯_{1} = 𝐯_{2} = 𝐯 \neq 𝟎

1 𝐯_{1} +

0 𝐯_{2} =

0 𝐯_{1} +

1 𝐯_{2}

. For

(1, 0), (0, 1)

, the two sides are

(𝑎_{1}, 𝑎_{2})

and

(𝑏_{1}, 𝑏_{2})

(a) The hypothesis is an equation between vectors: it says that the two linear combinations represent the same vector. The argument reads it as saying that the two linear combinations are the same, which is what the claim asserts. So the argument assumes its conclusion.

(b) Let $𝐯 \neq 𝟎$ (for instance $𝐯 = (1, 0)$ in $ℝ^{2}$ ), and take $𝐯_{1} = 𝐯_{2} = 𝐯$ . Then $1 𝐯_{1} +$ $0 𝐯_{2} =$ $𝐯 =$ $0 𝐯_{1} +$ $1 𝐯_{2}$ , but $1 \neq 0$ . For $𝐯_{1} = (1, 0)$ and $𝐯_{2} = (0, 1)$ , the two sides represent $(𝑎_{1}, 𝑎_{2})$ and $(𝑏_{1}, 𝑏_{2})$ , and these columns are equal only if $𝑎_{1} = 𝑏_{1}$ and $𝑎_{2} = 𝑏_{2}$ . The lists for which the claim holds are the linearly independent ones (Section 1.5).

Exercise 1.3.30.standard

(a)Find the gap in the following argument.
Claim. $span ((1, 1), (1, - 1)) =$ $ℝ^{2}$ .
Proof. Let $𝐰 \in$ $span ((1, 1), (1, - 1))$ , say $𝐰 =$ $𝑎 (1, 1) +$ $𝑏 (1, - 1) =$ $(𝑎 + 𝑏, 𝑎 - 𝑏)$ . Both coordinates are real numbers, so $𝐰 \in ℝ^{2}$ . Hence $span ((1, 1), (1, - 1)) =$ $ℝ^{2}$ .
(b)Prove the claim.
(c)Is $span ((1, 1), (1, - 1)) =$ $𝔽_{2}^{2}$ in $𝔽_{2}^{2}$ ? Is $span ((1, 1), (1, - 1)) =$ $𝔽_{3}^{2}$ in $𝔽_{3}^{2}$ ?

Solution.

Uses. Definition 1.3.10 (Span), Example 1.3.11 (Small spans)

Techniques. Double containment (Technique 1.3.14), Try small cases and small fields (Technique 1.2.38)

Hint 1. The argument proves a containment. Which one, and is it the one with content?

Hint 2. For (b), solve

𝑎 + 𝑏 = 𝑥

and

𝑎 - 𝑏 = 𝑦

for

𝑎

and

𝑏

. Which field element do you divide by?

Sketch. (a) It shows only

span \subseteq ℝ^{2}

, which holds for any list in

ℝ^{2}

; the containment

ℝ^{2} \subseteq span

is missing. (b)

(𝑥, 𝑦) =

\frac{𝑥 + 𝑦}{2} (1, 1) +

\frac{𝑥 - 𝑦}{2} (1, - 1)

. (c) Over

𝔽_{2}

(1, - 1) = (1, 1)

and the span is

{𝟎, (1, 1)} \neq 𝔽_{2}^{2}

. Over

𝔽_{3}

2^{- 1} = 2

, so the formula of (b) works and the span is

𝔽_{3}^{2}

(a) The argument proves $span ((1, 1), (1, - 1)) \subseteq$ $ℝ^{2}$ , which holds for every list in $ℝ^{2}$ because the operations of $ℝ^{2}$ produce elements of $ℝ^{2}$ . The containment $ℝ^{2} \subseteq$ $span ((1, 1), (1, - 1))$ is never addressed, and it is the one with content.

(b) It remains to show $ℝ^{2} \subseteq$ $span ((1, 1), (1, - 1))$ . Let $(𝑥, 𝑦) \in ℝ^{2}$ , and set $𝑎 = (𝑥 + 𝑦) / 2$ and $𝑏 = (𝑥 - 𝑦) / 2$ . Then

𝑎 (1, 1) + 𝑏 (1, - 1) = (𝑎 + 𝑏, 𝑎 - 𝑏) = (𝑥, 𝑦),

so $(𝑥, 𝑦)$ lies in the span.

(c) In $𝔽_{2}^{2}$ , $- 1 = 1$ , so the list is $(1, 1), (1, 1)$ , and its span is $span ((1, 1)) =$ ${𝟎, (1, 1)}$ by Corollary 1.3.20(c) and Example 1.3.11. This is not $𝔽_{2}^{2}$ ; for instance, $(1, 0)$ is missing. The proof of (b) breaks down because it divides by $2 = 0$ . In $𝔽_{3}$ , $2 \neq 0$ and $2^{- 1} = 2$ , so with $𝑎 = 2 (𝑥 + 𝑦)$ and $𝑏 = 2 (𝑥 - 𝑦)$ ,

𝑎 (1, 1) + 𝑏 (1, - 1) = (4 𝑥, 4 𝑦) = (𝑥, 𝑦),

since $4 = 1$ in $𝔽_{3}$ . So the list spans $𝔽_{3}^{2}$ .

Exercise 1.3.31.standard Work in the real vector space $ℝ^{ℝ}$ of functions $ℝ \to ℝ$ .

(a)Show that the function $𝑡 \mapsto {cos}^{2} 𝑡$ lies in $span (1, 𝑐_{2})$ , where $𝑐_{2} (𝑡) = cos 2 𝑡$ .
(b)Show that $sin \notin span (1, cos)$ .
(c)Does the function $𝑡 \mapsto {sin}^{2} 𝑡$ lie in $span (1, cos)$ ?

Solution.

Uses. Definition 1.3.10 (Span), Definition 1.2.9 (Function spaces)

Hint 1. For (a), use a double-angle formula. For (b), compare

𝑓 (𝑡)

with

𝑓 (- 𝑡)

for

𝑓 = 𝑎 + 𝑏 cos

Hint 2. For (c), write

{sin}^{2} = 1 - {cos}^{2}

. If

{sin}^{2} = 𝑎 + 𝑏 cos

, evaluate at three values of

𝑡

where

cos 𝑡

0

1

, and

- 1

Sketch. (a)

{cos}^{2} 𝑡 =

\frac{1}{2} +

\frac{1}{2} cos 2 𝑡

. (b) Every

𝑎 + 𝑏 cos

is even, while

sin (𝜋 / 2) =

1 \neq

- 1 =

sin (- 𝜋 / 2)

. (c) No:

{sin}^{2} = 𝑎 + 𝑏 cos

𝑡 = 𝜋 / 2, 0, 𝜋

gives

1 = 𝑎

0 = 𝑎 + 𝑏

0 = 𝑎 - 𝑏

, which is inconsistent.

(a) By the double-angle formula $cos 2 𝑡 = 2 {cos}^{2} 𝑡 - 1$ , we have ${cos}^{2} 𝑡 =$ $\frac{1}{2} \cdot$ $1 +$ $\frac{1}{2} cos 2 𝑡$ for all $𝑡$ . So $𝑡 \mapsto {cos}^{2} 𝑡$ is represented by the linear combination $\frac{1}{2} \cdot 1 + \frac{1}{2} 𝑐_{2}$ .

(b) Every element of $span (1, cos)$ has the form $𝑓 = 𝑎 + 𝑏 cos$ with $𝑎, 𝑏 \in ℝ$ , and $𝑓 (- 𝑡) =$ $𝑎 +$ $𝑏 cos (- 𝑡) =$ $𝑎 +$ $𝑏 cos 𝑡 =$ $𝑓 (𝑡)$ for all $𝑡$ . But $sin (𝜋 / 2) = 1$ and $sin (- 𝜋 / 2) = - 1$ , so $sin$ is not of this form.

(c) No. Suppose ${sin}^{2} 𝑡 = 𝑎 + 𝑏 cos 𝑡$ for all $𝑡 \in ℝ$ . At $𝑡 = 𝜋 / 2$ this gives $1 = 𝑎$ . At $𝑡 = 0$ it gives $0 = 𝑎 + 𝑏$ , and at $𝑡 = 𝜋$ it gives $0 = 𝑎 - 𝑏$ . Adding the last two equations gives $𝑎 = 0$ , contradicting $𝑎 = 1$ .

Exercise 1.3.32.standard Let

𝑊 =

{𝑝 \in {ℝ [𝑥]}_{\leq 3} | 𝑝 (1) = 0}

. Find a list of length

3

that spans

𝑊

, and prove that it does.

Solution.

Uses. Definition 1.2.17 (Evaluation), Definition 1.2.16 (Degree), Definition 1.3.10 (Span), Notation 1.2.15

Techniques. Double containment (Technique 1.3.14)

Hint 1. Write

𝑝 =

𝑎_{0} +

𝑎_{1} 𝑥 +

𝑎_{2} 𝑥^{2} +

𝑎_{3} 𝑥^{3}

. The condition

𝑝 (1) = 0

expresses

𝑎_{0}

in terms of

𝑎_{1}, 𝑎_{2}, 𝑎_{3}

Hint 2. Substitute

𝑎_{0} = - 𝑎_{1} - 𝑎_{2} - 𝑎_{3}

and group the terms by

𝑎_{1}

𝑎_{2}

, and

𝑎_{3}

Sketch. The list

𝑥 - 1, 𝑥^{2} - 1, 𝑥^{3} - 1

. A combination

𝑎_{1} (𝑥 - 1) +

𝑎_{2} (𝑥^{2} - 1) +

𝑎_{3} (𝑥^{3} - 1)

has degree at most

3

and vanishes at

1

. Conversely, if

𝑝 (1) =

𝑎_{0} +

𝑎_{1} +

𝑎_{2} +

𝑎_{3} =

0

, then

𝑝 =

𝑎_{1} (𝑥 - 1) +

𝑎_{2} (𝑥^{2} - 1) +

𝑎_{3} (𝑥^{3} - 1)

We show that $span (𝑥 - 1, 𝑥^{2} - 1, 𝑥^{3} - 1) =$ $𝑊$ , by double containment.

$span \subseteq 𝑊$ . A linear combination of the list represents

𝑎_{1} (𝑥 - 1) + 𝑎_{2} (𝑥^{2} - 1) + 𝑎_{3} (𝑥^{3} - 1) = - (𝑎_{1} + 𝑎_{2} + 𝑎_{3}) + 𝑎_{1} 𝑥 + 𝑎_{2} 𝑥^{2} + 𝑎_{3} 𝑥^{3},

which has no nonzero coefficients beyond position $3$ , so it lies in ${ℝ [𝑥]}_{\leq 3}$ . Its value at $1$ is $- (𝑎_{1} + 𝑎_{2} + 𝑎_{3}) +$ $𝑎_{1} +$ $𝑎_{2} +$ $𝑎_{3} =$ $0$ (Definition 1.2.17). So it lies in $𝑊$ .

$𝑊 \subseteq span$ . Let $𝑝 =$ $𝑎_{0} +$ $𝑎_{1} 𝑥 +$ $𝑎_{2} 𝑥^{2} +$ $𝑎_{3} 𝑥^{3} \in$ $𝑊$ . Then $𝑝 (1) =$ $𝑎_{0} +$ $𝑎_{1} +$ $𝑎_{2} +$ $𝑎_{3} =$ $0$ , so $𝑎_{0} =$ $- (𝑎_{1} + 𝑎_{2} + 𝑎_{3})$ , and by the computation above,

𝑝 = - (𝑎_{1} + 𝑎_{2} + 𝑎_{3}) + 𝑎_{1} 𝑥 + 𝑎_{2} 𝑥^{2} + 𝑎_{3} 𝑥^{3} = 𝑎_{1} (𝑥 - 1) + 𝑎_{2} (𝑥^{2} - 1) + 𝑎_{3} (𝑥^{3} - 1) .

So $𝑝$ lies in the span.

Exercise 1.3.33.standard

(a)Let $𝑝_{0},$ $𝑝_{1},$ $\dots,$ $𝑝_{𝑛} \in$ $𝐹 [𝑥]$ with $deg 𝑝_{𝑘} = 𝑘$ for each $𝑘$ . Show that $span (𝑝_{0}, \dots, 𝑝_{𝑛}) =$ ${𝐹 [𝑥]}_{\leq 𝑛}$ .
(b)Write $𝑥^{2}$ as a linear combination of $1, 𝑥 - 1, 𝑥^{2} - 2 𝑥 + 1$ in $ℝ [𝑥]$ .

Solution.

Uses. Proposition 1.3.18 (Comparing spans), Example 1.3.11 (Small spans), Definition 1.2.16 (Degree), induction on $𝑛$

Techniques. Double containment (Technique 1.3.14)

Hint 1. One containment is a degree count, via Proposition 1.3.18 and

{𝐹 [𝑥]}_{\leq 𝑛} =

span (1, 𝑥, \dots, 𝑥^{𝑛})

. For the other, it suffices to show that each

𝑥^{𝑘}

with

𝑘 \leq 𝑛

lies in

span (𝑝_{0}, \dots, 𝑝_{𝑛})

Hint 2. Induct on

𝑛

. If

𝑝_{𝑛}

has leading coefficient

𝑐 \neq 0

, then

𝑝_{𝑛} - 𝑐 𝑥^{𝑛}

has degree less than

𝑛

, and

𝑥^{𝑛} =

𝑐^{- 1} (𝑝_{𝑛} - (𝑝_{𝑛} - 𝑐 𝑥^{𝑛}))

Sketch. (a) Each

𝑝_{𝑘}

lies in

{𝐹 [𝑥]}_{\leq 𝑛} =

span (1, \dots, 𝑥^{𝑛})

, giving

\subseteq

. For

\supseteq

, induct on

𝑛

𝑝_{0}

is a nonzero constant, so

1 \in span (𝑝_{0})

. If

span (𝑝_{0}, \dots, 𝑝_{𝑛 - 1}) =

{𝐹 [𝑥]}_{\leq 𝑛 - 1}

and

𝑝_{𝑛} = 𝑐 𝑥^{𝑛} + 𝑟

with

𝑐 \neq 0

and

deg 𝑟 < 𝑛

, then

𝑟 \in

span (𝑝_{0}, \dots, 𝑝_{𝑛 - 1})

, so

𝑥^{𝑛} =

𝑐^{- 1} (𝑝_{𝑛} - 𝑟) \in

span (𝑝_{0}, \dots, 𝑝_{𝑛})

, and the lower powers are there by induction. (b)

𝑥^{2} =

(𝑥^{2} - 2 𝑥 + 1) +

2 (𝑥 - 1) +

1

(a) Write ${𝒫︀}_{𝑛} = 𝑝_{0}, \dots, 𝑝_{𝑛}$ . We prove $span ({𝒫︀}_{𝑛}) =$ ${𝐹 [𝑥]}_{\leq 𝑛}$ by induction on $𝑛$ , and in each case by double containment.

$span ({𝒫︀}_{𝑛}) \subseteq$ ${𝐹 [𝑥]}_{\leq 𝑛}$ . Each $𝑝_{𝑘}$ has degree $𝑘 \leq 𝑛$ , so ${𝒫︀}_{𝑛} \subseteq$ ${𝐹 [𝑥]}_{\leq 𝑛} =$ $span (1, 𝑥, \dots, 𝑥^{𝑛})$ (Example 1.3.11). By Proposition 1.3.18, $span ({𝒫︀}_{𝑛}) \subseteq$ $span (1, 𝑥, \dots, 𝑥^{𝑛}) =$ ${𝐹 [𝑥]}_{\leq 𝑛}$ .

${𝐹 [𝑥]}_{\leq 𝑛} \subseteq$ $span ({𝒫︀}_{𝑛})$ . By Proposition 1.3.18, it suffices to show $𝑥^{𝑘} \in span ({𝒫︀}_{𝑛})$ for $0 \leq 𝑘 \leq 𝑛$ . For $𝑛 = 0$ , $𝑝_{0}$ has degree $0$ , so $𝑝_{0} = 𝑐$ is a nonzero constant and $1 =$ $𝑐^{- 1} 𝑝_{0} \in$ $span (𝑝_{0})$ . Now let $𝑛 \geq 1$ , and assume $span ({𝒫︀}_{𝑛 - 1}) =$ ${𝐹 [𝑥]}_{\leq 𝑛 - 1}$ . Let $𝑐 \neq 0$ be the leading coefficient of $𝑝_{𝑛}$ , and let $𝑟 = 𝑝_{𝑛} - 𝑐 𝑥^{𝑛}$ . The coefficients of $𝑟$ in positions $𝑘 > 𝑛$ are $0$ , and so is its coefficient in position $𝑛$ , so $𝑟 \in$ ${𝐹 [𝑥]}_{\leq 𝑛 - 1} =$ $span ({𝒫︀}_{𝑛 - 1})$ , say $𝑟 =$ $\sum_{𝑘 = 0}^{𝑛 - 1} 𝑑_{𝑘} 𝑝_{𝑘}$ . Then

𝑥^{𝑛} = 𝑐^{- 1} (𝑝_{𝑛} - 𝑟) = 𝑐^{- 1} 𝑝_{𝑛} - \sum_{𝑘 = 0}^{𝑛 - 1} (𝑐^{- 1} 𝑑_{𝑘}) 𝑝_{𝑘} \in span ({𝒫︀}_{𝑛}),

using Lemma 1.3.9. For $𝑘 < 𝑛$ , $𝑥^{𝑘} \in$ ${𝐹 [𝑥]}_{\leq 𝑛 - 1} =$ $span ({𝒫︀}_{𝑛 - 1}) \subseteq$ $span ({𝒫︀}_{𝑛})$ , by the inductive hypothesis and Corollary 1.3.20(b). This completes the induction.

(b) Following the proof of (a) from the top degree down, $𝑥^{2} =$ $(𝑥^{2} - 2 𝑥 + 1) +$ $(2 𝑥 - 1)$ and $2 𝑥 - 1 = 2 (𝑥 - 1) + 1$ . So

𝑥^{2} = 1 \cdot 1 + 2 (𝑥 - 1) + 1 \cdot (𝑥^{2} - 2 𝑥 + 1) .

Check: $1 +$ $2 𝑥 -$ $2 +$ $𝑥^{2} -$ $2 𝑥 +$ $1 =$ $𝑥^{2}$ .

Exercise 1.3.34.standard Let $ℒ︀ = 𝐯_{1}, \dots, 𝐯_{𝑘}$ be a list in $𝑉$ , and let $𝐰 \in span (ℒ︀)$ with $𝐰 \notin$ $span (𝐯_{1}, \dots, 𝐯_{𝑘 - 1})$ . Show that

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

In other words, $𝐰$ can be exchanged for $𝐯_{𝑘}$ without changing the span.

Solution.

Uses. Corollary 1.3.19 (Equal spans), Proposition 1.3.17 (A list lies in its span), Lemma 1.3.9 (Arithmetic of linear combinations)

Hint 1. Write

𝐰 =

𝑎_{1} 𝐯_{1} +

\dots +

𝑎_{𝑘} 𝐯_{𝑘}

. What does the hypothesis

𝐰 \notin

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

say about

𝑎_{𝑘}

Hint 2. Since

𝑎_{𝑘} \neq 0

, solve for

𝐯_{𝑘}

. Then use Corollary 1.3.19.

Sketch. Write

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

. If

𝑎_{𝑘} = 0

, then

𝐰 \in

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

, so

𝑎_{𝑘} \neq 0

and

𝐯_{𝑘} =

𝑎_{𝑘}^{- 1} 𝐰 -

\sum_{𝑖 < 𝑘} 𝑎_{𝑘}^{- 1} 𝑎_{𝑖} 𝐯_{𝑖}

. So each list lies in the span of the other.

Since $𝐰 \in span (ℒ︀)$ , we can write $𝐰 =$ $𝑎_{1} 𝐯_{1} +$ $\dots +$ $𝑎_{𝑘} 𝐯_{𝑘}$ . If $𝑎_{𝑘} = 0$ , then $𝐰 =$ $𝑎_{1} 𝐯_{1} +$ $\dots +$ $𝑎_{𝑘 - 1} 𝐯_{𝑘 - 1}$ (the term $0 𝐯_{𝑘} = 𝟎$ contributes nothing), contradicting $𝐰 \notin$ $span (𝐯_{1}, \dots, 𝐯_{𝑘 - 1})$ . So $𝑎_{𝑘} \neq 0$ . (In particular $𝑘 \geq 1$ .) By Lemma 1.3.9 and Proposition 1.2.34,

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

Let ${ℒ︀}^{'} =$ $𝐯_{1},$ $\dots,$ $𝐯_{𝑘 - 1},$ $𝐰$ . The entries of ${ℒ︀}^{'}$ lie in $span (ℒ︀)$ : the $𝐯_{𝑖}$ by Proposition 1.3.17, and $𝐰$ by assumption. The entries of $ℒ︀$ lie in $span ({ℒ︀}^{'})$ : the $𝐯_{𝑖}$ with $𝑖 < 𝑘$ by Proposition 1.3.17, and $𝐯_{𝑘}$ by the display. By Corollary 1.3.19, $span ({ℒ︀}^{'}) =$ $span (ℒ︀)$ .

This exchange is the step that drives the proof of Lemma 4.1.2.

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

(a) $span (ℒ︀) \cup$ $span (ℳ︀) =$ $span (ℒ︀, ℳ︀)$ .
(b) $span (ℒ︀) \cap$ $span (ℳ︀) =$ $span (𝒩︀)$ , where $𝒩︀$ is a list of the vectors that are entries of both $ℒ︀$ and $ℳ︀$ .
(c)If $span (ℒ︀) = span (ℳ︀)$ , then $| ℒ︀ | = | ℳ︀ |$ .
(d)If $𝐮 \in span (𝐯, 𝐰)$ and $𝐯 \in span (𝐮, 𝐰)$ , then $𝐰 \in span (𝐮, 𝐯)$ .
(e)If $𝐮 \in span (𝐯, 𝐰)$ and $𝐮 \notin span (𝐰)$ , then $𝐯 \in span (𝐮, 𝐰)$ .

Solution.

Uses. Definition 1.3.10 (Span), Example 1.3.11 (Small spans), Exercise 1.3.34

Hint 1. Test (a)–(d) in

ℝ^{2}

with the vectors

𝐞_{1} = (1, 0)

𝐞_{2} = (0, 1)

, and

𝐞_{1} + 𝐞_{2}

Hint 2. (e) is true. Write

𝐮 = 𝑎 𝐯 + 𝑏 𝐰

and decide what

𝐮 \notin span (𝐰)

says about

𝑎

Sketch. (a) False:

𝐞_{1} +

𝐞_{2} \in

span (𝐞_{1}, 𝐞_{2})

lies on neither axis. (b) False:

span (𝐞_{1}, 𝐞_{2}) \cap

span (𝐞_{1} + 𝐞_{2})

contains

𝐞_{1} + 𝐞_{2}

, but the lists share no entry, so

𝒩︀ = ()

. (c) False:

()

and

𝟎

. (d) False:

𝐮 = 𝐯 = 𝐞_{1}

𝐰 = 𝐞_{2}

. (e) True:

𝐮 = 𝑎 𝐯 + 𝑏 𝐰

with

𝑎 \neq 0

, so

𝐯 =

𝑎^{- 1} 𝐮 -

𝑎^{- 1} 𝑏 𝐰

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

(a) False. Let $ℒ︀ = 𝐞_{1}$ and $ℳ︀ = 𝐞_{2}$ . Then $(1, 1) =$ $𝐞_{1} +$ $𝐞_{2} \in$ $span (𝐞_{1}, 𝐞_{2})$ , but $span (𝐞_{1}) =$ ${(𝑎, 0) | 𝑎 \in ℝ}$ and $span (𝐞_{2}) =$ ${(0, 𝑏) | 𝑏 \in ℝ}$ , and $(1, 1)$ lies in neither.

(b) False. Let $ℒ︀ = 𝐞_{1}, 𝐞_{2}$ and $ℳ︀ = (1, 1)$ . No vector is an entry of both lists, so $𝒩︀ = ()$ and $span (𝒩︀) = {𝟎}$ . But $(1, 1) \in span (ℳ︀)$ and $(1, 1) \in span (ℒ︀) = ℝ^{2}$ , so the intersection contains $(1, 1) \neq 𝟎$ .

(c) False. $span (()) =$ ${𝟎} =$ $span (𝟎)$ by Example 1.3.11, but the lists have lengths $0$ and $1$ .

(d) False. Let $𝐮 = 𝐯 = 𝐞_{1}$ and $𝐰 = 𝐞_{2}$ . Then $𝐮 = 1 𝐯 + 0 𝐰$ and $𝐯 = 1 𝐮 + 0 𝐰$ , but $span (𝐮, 𝐯) =$ $span (𝐞_{1})$ does not contain $𝐞_{2}$ .

(e) True. Write $𝐮 = 𝑎 𝐯 + 𝑏 𝐰$ . If $𝑎 = 0$ , then $𝐮 = 𝑏 𝐰 \in span (𝐰)$ , contrary to assumption. So $𝑎 \neq 0$ , and

𝐯 = 𝑎^{- 1} (𝐮 - 𝑏 𝐰) = 𝑎^{- 1} 𝐮 + (- 𝑎^{- 1} 𝑏) 𝐰 \in span (𝐮, 𝐰) .

This is the case $𝑘 = 2$ of Exercise 1.3.34, applied to the list $𝐰, 𝐯$ .

Exercise 1.3.36.standard Let $ℒ︀$ and $ℳ︀$ be lists in $𝑉$ . Show that

span (ℒ︀, ℳ︀) = {𝐮 + 𝐰 | 𝐮 \in span (ℒ︀), 𝐰 \in span (ℳ︀)} .

Solution.

Uses. Definition 1.3.10 (Span), (1.3.1), Notation 1.3.3

Techniques. Double containment (Technique 1.3.14)

Hint 1. A linear combination of the concatenation

ℒ︀, ℳ︀

has one coefficient for each entry of

ℒ︀

and one for each entry of

ℳ︀

Hint 2. By (A2), the sum over the concatenation can be grouped as (the terms from

ℒ︀

) plus (the terms from

ℳ︀

Sketch. The combination of

ℒ︀, ℳ︀

with coefficients

𝑎_{1},

\dots,

𝑎_{𝑘},

𝑏_{1},

\dots,

𝑏_{𝑚}

represents

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

\sum 𝑏_{𝑗} 𝐰_{𝑗}

, by grouping the terms. So the vectors it represents are exactly the sums

𝐮 + 𝐰

, both containments included.

Let $ℒ︀ = 𝐯_{1}, \dots, 𝐯_{𝑘}$ and $ℳ︀ = 𝐰_{1}, \dots, 𝐰_{𝑚}$ , and let $𝑆$ be the set on the right. A linear combination of $ℒ︀, ℳ︀$ has coefficients $𝑎_{1},$ $\dots,$ $𝑎_{𝑘},$ $𝑏_{1},$ $\dots,$ $𝑏_{𝑚}$ , and by (1.3.1) and (A2) the vector it represents is

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

(If $𝑘 = 0$ or $𝑚 = 0$ , the corresponding sum is $𝟎$ , and the identity holds by (A1) and (A3).) We use this identity for both containments.

$span (ℒ︀, ℳ︀) \subseteq 𝑆$ . An element of the left side is represented by some such combination, and the identity writes it as $𝐮 + 𝐰$ with $𝐮 =$ $\sum 𝑎_{𝑖} 𝐯_{𝑖} \in$ $span (ℒ︀)$ and $𝐰 =$ $\sum 𝑏_{𝑗} 𝐰_{𝑗} \in$ $span (ℳ︀)$ .

$𝑆 \subseteq span (ℒ︀, ℳ︀)$ . Let $𝐮 \in span (ℒ︀)$ and $𝐰 \in span (ℳ︀)$ , say $𝐮 = \sum 𝑎_{𝑖} 𝐯_{𝑖}$ and $𝐰 = \sum 𝑏_{𝑗} 𝐰_{𝑗}$ . By the identity, the combination of $ℒ︀, ℳ︀$ with coefficients $𝑎_{1},$ $\dots,$ $𝑎_{𝑘},$ $𝑏_{1},$ $\dots,$ $𝑏_{𝑚}$ represents $𝐮 + 𝐰$ , so $𝐮 + 𝐰 \in span (ℒ︀, ℳ︀)$ .

In the language of Section 4.4, the span of a concatenation is the sum of the spans (Definition 4.4.1).

Exercise 1.3.37.standard Let $𝐮 = (𝑎, 𝑏)$ and $𝐯 = (𝑐, 𝑑)$ be vectors in $𝐹^{2}$ .

(a)Show that $𝐮, 𝐯$ spans $𝐹^{2}$ if and only if $𝑎 𝑑 - 𝑏 𝑐 \neq 0$ .
(b)Suppose $𝐮 \neq 𝟎$ . Show that $𝐮, 𝐯$ spans $𝐹^{2}$ if and only if $𝐯 \notin span (𝐮)$ .

Solution.

Uses. Proposition 1.3.18 (Comparing spans), Example 1.3.11 (Small spans), Corollary 1.3.20 (Operations that preserve the span)

Hint 1. If

𝛿 = 𝑎 𝑑 - 𝑏 𝑐 \neq 0

, compute

𝑑 𝐮 - 𝑏 𝐯

and

𝑎 𝐯 - 𝑐 𝐮

Hint 2. If

𝛿 = 0

, show that every vector

(𝑝, 𝑞)

in the span satisfies

𝑏 𝑝 - 𝑎 𝑞 = 0

and

𝑑 𝑝 - 𝑐 𝑞 = 0

. Then find a vector of

𝐹^{2}

that violates one of these equations.

Hint 3. For (b), compute

𝛿

when

𝐯 = 𝑡 𝐮

. Conversely, if

𝛿 = 0

and

𝑎 \neq 0

, try

𝑡 = 𝑐 / 𝑎

Sketch. (a)

𝑑 𝐮 - 𝑏 𝐯 = (𝛿, 0)

and

𝑎 𝐯 - 𝑐 𝐮 = (0, 𝛿)

, so if

𝛿 \neq 0

then

𝐞_{1}, 𝐞_{2}

lie in the span. If

𝛿 = 0

, every

𝑥 𝐮 + 𝑦 𝐯

satisfies

𝑏 𝑝 - 𝑎 𝑞 = 0

and

𝑑 𝑝 - 𝑐 𝑞 = 0

; if

𝐮 = 𝐯 = 𝟎

the span is

{𝟎}

, and otherwise one of

𝐞_{1}

𝐞_{2}

violates an equation with a nonzero coefficient. (b)

𝐯 = 𝑡 𝐮

gives

𝛿 = 0

; conversely,

𝛿 = 0

with

𝑎 \neq 0

gives

𝐯 = (𝑐 / 𝑎) 𝐮

, and with

𝑎 = 0

𝑏 \neq 0

it gives

𝑐 = 0

and

𝐯 = (𝑑 / 𝑏) 𝐮

Let $𝛿 = 𝑎 𝑑 - 𝑏 𝑐$ .

(a) Suppose $𝛿 \neq 0$ . Then

𝑑 𝐮 - 𝑏 𝐯 = (𝑑 𝑎 - 𝑏 𝑐, 𝑑 𝑏 - 𝑏 𝑑) = (𝛿, 0), 𝑎 𝐯 - 𝑐 𝐮 = (𝑎 𝑐 - 𝑐 𝑎, 𝑎 𝑑 - 𝑐 𝑏) = (0, 𝛿) .

So $𝐞_{1} =$ $𝛿^{- 1} (𝑑 𝐮 - 𝑏 𝐯)$ and $𝐞_{2} =$ $𝛿^{- 1} (𝑎 𝐯 - 𝑐 𝐮)$ lie in $span (𝐮, 𝐯)$ , and by Proposition 1.3.18, $𝐹^{2} =$ $span (𝐞_{1}, 𝐞_{2}) \subseteq$ $span (𝐮, 𝐯)$ .

Now suppose $𝛿 = 0$ . A vector $(𝑝, 𝑞) =$ $𝑥 𝐮 +$ $𝑦 𝐯 =$ $(𝑥 𝑎 + 𝑦 𝑐, 𝑥 𝑏 + 𝑦 𝑑)$ of the span satisfies

𝑏 𝑝 - 𝑎 𝑞 = 𝑦 (𝑏 𝑐 - 𝑎 𝑑) = 0 and 𝑑 𝑝 - 𝑐 𝑞 = 𝑥 (𝑎 𝑑 - 𝑏 𝑐) = 0 .

If $𝑎 = 𝑏 = 𝑐 = 𝑑 = 0$ , then $span (𝐮, 𝐯) =$ ${𝟎} \neq$ $𝐹^{2}$ . Otherwise one of these two equations has a nonzero coefficient. If $𝑎 \neq 0$ or $𝑐 \neq 0$ , the vector $𝐞_{2} = (0, 1)$ gives $𝑏 \cdot 0 - 𝑎 \cdot 1 = - 𝑎$ and $𝑑 \cdot 0 - 𝑐 \cdot 1 = - 𝑐$ , one of which is nonzero, so $𝐞_{2}$ is not in the span. If $𝑏 \neq 0$ or $𝑑 \neq 0$ , then similarly $𝐞_{1} = (1, 0)$ gives $𝑏$ and $𝑑$ , and $𝐞_{1}$ is not in the span. Either way, $𝐮, 𝐯$ does not span $𝐹^{2}$ .

(b) If $𝐯 \in span (𝐮)$ , say $𝐯 =$ $𝑡 𝐮 =$ $(𝑡 𝑎, 𝑡 𝑏)$ , then $𝛿 =$ $𝑎 𝑡 𝑏 -$ $𝑏 𝑡 𝑎 =$ $0$ , so the list does not span by (a). Conversely, suppose the list does not span, so $𝛿 = 0$ by (a). If $𝑎 \neq 0$ , then $𝑏 𝑐 = 𝑎 𝑑$ gives

\frac{𝑐}{𝑎} 𝐮 = (𝑐, \frac{𝑏 𝑐}{𝑎}) = (𝑐, 𝑑) = 𝐯 .

If $𝑎 = 0$ , then $𝑏 \neq 0$ because $𝐮 \neq 𝟎$ , and $𝛿 = - 𝑏 𝑐 = 0$ forces $𝑐 = 0$ ; then $𝐯 =$ $(0, 𝑑) =$ $(𝑑 / 𝑏) (0, 𝑏) =$ $(𝑑 / 𝑏) 𝐮$ . Either way $𝐯 \in span (𝐮)$ .

The quantity $𝑎 𝑑 - 𝑏 𝑐$ is the determinant of the $2 \times 2$ matrix with columns $𝐮$ and $𝐯$ (Theorem 5.1.13).

Exercise 1.3.38.standard Let $𝐹$ be a finite field with $𝑞$ elements.

(a)Show that no list of length $1$ spans $𝐹^{2}$ .
(b)Show that exactly $(𝑞^{2} - 1) (𝑞^{2} - 𝑞)$ lists of length $2$ span $𝐹^{2}$ .
(c)For $𝑞 = 2$ , how many lists of length $3$ span $𝔽_{2}^{2}$ ?

Solution.

Uses. Exercise 1.3.37, Corollary 1.2.36 (Cancelling scalars and vectors), Example 1.3.11 (Small spans), Corollary 1.3.20 (Operations that preserve the span)

Hint 1. For (a), how many elements does

span (𝐯)

have?

Hint 2. For (b), use Exercise 1.3.37(b). First show that a spanning list

𝐮, 𝐯

has

𝐮 \neq 𝟎

. Then count the choices of

𝐯

outside

span (𝐮)

, which has exactly

𝑞

elements.

Hint 3. For (c), a list in

𝔽_{2}^{2}

spans exactly when it has two different nonzero entries. Count the complement.

Sketch. (a)

span (𝐯) = {𝑎 𝐯}

has at most

𝑞 < 𝑞^{2}

elements. (b) If

𝐮 = 𝟎

, then

span (𝟎, 𝐯) =

span (𝐯) \neq

𝐹^{2}

. For each of the

𝑞^{2} - 1

nonzero

𝐮

, the multiples of

𝐮

are

𝑞

distinct vectors, and

𝐯

must avoid them:

𝑞^{2} - 𝑞

choices. (c) A list of length

3

fails to span exactly when its nonzero entries are all equal:

1 + 3 (2^{3} - 1) = 22

lists. So

64 - 22 = 42

span.

(a) For $𝐯 \in 𝐹^{2}$ , $span (𝐯) =$ ${𝑎 𝐯 | 𝑎 \in 𝐹}$ has at most $𝑞$ elements, and $𝐹^{2}$ has $𝑞^{2} > 𝑞$ elements.

(b) If $𝐮 = 𝟎$ , then $span (𝟎, 𝐯) =$ $span (𝐯)$ by Corollary 1.3.20(a) and (c), which is not $𝐹^{2}$ by (a). So a spanning list $𝐮, 𝐯$ has $𝐮 \neq 𝟎$ , and there are $𝑞^{2} - 1$ such $𝐮$ . For each of them, Exercise 1.3.37(b) says that $𝐮, 𝐯$ spans $𝐹^{2}$ exactly when $𝐯 \notin span (𝐮)$ . The vectors $𝑎 𝐮$ , $𝑎 \in 𝐹$ , are distinct by Corollary 1.2.36(b), so $span (𝐮)$ has exactly $𝑞$ elements, and there are $𝑞^{2} - 𝑞$ choices for $𝐯$ . In total, $(𝑞^{2} - 1) (𝑞^{2} - 𝑞)$ lists of length $2$ span $𝐹^{2}$ . For $𝑞 = 2$ this is $3 \cdot 2 = 6$ .

(c) Let $ℒ︀$ be a list of length $3$ in $𝔽_{2}^{2}$ . If $ℒ︀$ has two different nonzero entries $𝐮, 𝐯$ , then $𝐯 \notin$ ${𝟎, 𝐮} =$ $span (𝐮)$ , so $𝐮, 𝐯$ spans $𝔽_{2}^{2}$ by Exercise 1.3.37(b), and so does $ℒ︀$ , by Corollary 1.3.20(a) and (b). Otherwise all nonzero entries of $ℒ︀$ equal a single vector $𝐰$ (or there are none), and $span (ℒ︀) \subseteq$ $span (𝐰) =$ ${𝟎, 𝐰}$ , which is not $𝔽_{2}^{2}$ . The lists of the second kind are the zero list $𝟎, 𝟎, 𝟎$ , and, for each of the $3$ nonzero vectors $𝐰$ , the $2^{3} - 1 = 7$ lists with entries in ${𝟎, 𝐰}$ other than the zero list. That makes $1 + 3 \cdot 7 = 22$ lists. Since there are $4^{3} = 64$ lists of length $3$ , exactly $64 - 22 = 42$ of them span $𝔽_{2}^{2}$ .

Exercise 1.3.39.standard Let $𝐹$ be a finite field with $𝑞$ elements, and let $ℒ︀$ be a list of length $𝑘$ in $𝑉$ .

(a)Show that $span (ℒ︀)$ has at most $𝑞^{𝑘}$ elements.
(b)Deduce that no list of length less than $𝑛$ spans $𝐹^{𝑛}$ .

Solution.

Uses. Definition 1.3.10 (Span), Definition 1.3.4 (Linear combination)

Hint 1. How many linear combinations does

ℒ︀

have? Each element of the span is represented by at least one of them.

Hint 2. For (b), compare

𝑞^{𝑘}

with the number of elements of

𝐹^{𝑛}

Sketch. (a) A linear combination of

ℒ︀

is determined by its

𝑘

coefficients, so there are

𝑞^{𝑘}

of them, and

span (ℒ︀)

is the set of vectors they represent. (b)

𝐹^{𝑛}

has

𝑞^{𝑛} > 𝑞^{𝑘}

elements when

𝑘 < 𝑛

(a) A linear combination of $ℒ︀$ is determined by its list of coefficients $𝑎_{1}, \dots, 𝑎_{𝑘}$ , so $ℒ︀$ has exactly $𝑞^{𝑘}$ linear combinations (for $𝑘 = 0$ , exactly one). The span is the set of vectors represented by them, and each linear combination represents exactly one vector. So $span (ℒ︀)$ has at most $𝑞^{𝑘}$ elements.

(b) $𝐹^{𝑛}$ has $𝑞^{𝑛}$ elements. If $ℒ︀$ has length $𝑘 < 𝑛$ , then $span (ℒ︀)$ has at most $𝑞^{𝑘} < 𝑞^{𝑛}$ elements by (a), so $span (ℒ︀) \neq 𝐹^{𝑛}$ .

The statement of (b) holds over every field, but over an infinite field counting is useless, and the proof needs the theory of dimension (Section 4.1).

Exercise 1.3.40.hard Let $𝐹$ be a finite field with $𝑞$ elements, and let $ℒ︀ = 𝐯_{1}, \dots, 𝐯_{𝑘}$ be a list in $𝑉$ . For $𝐰 \in 𝑉$ , let $𝑁 (𝐰)$ be the number of linear combinations of $ℒ︀$ that represent $𝐰$ .

(a)Show that $𝑁 (𝐰) = 𝑁 (𝟎)$ for every $𝐰 \in span (ℒ︀)$ .
(b)Deduce that $𝑞^{𝑘} =$ $| span (ℒ︀) | \cdot$ $𝑁 (𝟎)$ . In particular, $| span (ℒ︀) |$ divides $𝑞^{𝑘}$ .
(c)If $𝐹 = 𝔽_{𝑝}$ with $𝑝$ prime, show that $span (ℒ︀)$ has $𝑝^{𝑟}$ elements for some integer $0 \leq 𝑟 \leq 𝑘$ .

Solution.

Uses. Lemma 1.3.9 (Arithmetic of linear combinations), Exercise 1.3.39, Proposition 1.2.30 (Additive arithmetic)

Hint 1. Fix one representation

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

𝐰

. If

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

represents

𝟎

, what does

𝑎_{1} +

𝑏_{1},

\dots,

𝑎_{𝑘} +

𝑏_{𝑘}

represent?

Hint 2. Show that

𝑎 \mapsto 𝑎 + 𝑏

is a bijection from the representations of

𝟎

to the representations of

𝐰

. For (b), sort the

𝑞^{𝑘}

linear combinations by the vector they represent.

Sketch. (a) If

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

, then

𝑎 \mapsto 𝑎 + 𝑏

sends representations of

𝟎

to representations of

𝐰

, with inverse

𝑎^{'} \mapsto 𝑎^{'} - 𝑏

, by Lemma 1.3.9. (b) Each of the

𝑞^{𝑘}

linear combinations represents exactly one vector of the span, and each vector of the span is represented

𝑁 (𝟎)

times. (c) A divisor of

𝑝^{𝑘}

is a power of

𝑝

(a) Let $𝐰 \in span (ℒ︀)$ , and fix coefficients $𝑏_{1}, \dots, 𝑏_{𝑘}$ with $\sum 𝑏_{𝑖} 𝐯_{𝑖} = 𝐰$ . If $𝑎_{1}, \dots, 𝑎_{𝑘}$ represents $𝟎$ , then by Lemma 1.3.9(a),

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

Conversely, if $𝑎_{1}^{'}, \dots, 𝑎_{𝑘}^{'}$ represents $𝐰$ , then by Lemma 1.3.9(a) and (b) with $𝑐 = - 1$ , and Proposition 1.2.34,

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

So $𝑎 \mapsto 𝑎 + 𝑏$ maps the representations of $𝟎$ to the representations of $𝐰$ , and $𝑎^{'} \mapsto 𝑎^{'} - 𝑏$ maps back. These maps are inverse to each other, so both sets have the same number of elements: $𝑁 (𝐰) = 𝑁 (𝟎)$ .

(b) As in Exercise 1.3.39, $ℒ︀$ has exactly $𝑞^{𝑘}$ linear combinations, and each represents exactly one vector, which lies in $span (ℒ︀)$ . Grouping them by the vector they represent and using (a),

𝑞^{𝑘} = \sum_{𝐰 \in span (ℒ︀)} 𝑁 (𝐰) = | span (ℒ︀) | \cdot 𝑁 (𝟎) .

(c) By (b), $| span (ℒ︀) |$ divides $𝑝^{𝑘}$ . By unique factorization, the positive divisors of $𝑝^{𝑘}$ are $𝑝^{𝑟}$ with $0 \leq 𝑟 \leq 𝑘$ .

The bijection in (a) is the same idea as Proposition 3.1.19: all representations of $𝐰$ are one of them plus a representation of $𝟎$ .

Exercise 1.3.41.standard Let $𝐮, 𝐯, 𝐰 \in 𝑉$ , and let $𝐷 =$ $span (𝐮 - 𝐯, 𝐯 - 𝐰)$ .

(a)Show that $𝐷 =$ $span (𝐮 - 𝐯, 𝐯 - 𝐰, 𝐰 - 𝐮)$ and $𝐷 \subseteq span (𝐮, 𝐯, 𝐰)$ .
(b)Prove or disprove: $𝐷 = span (𝐮, 𝐯, 𝐰)$ .
(c)Show that $𝐷 = span (𝐮, 𝐯, 𝐰)$ if and only if $𝐮 \in 𝐷$ .

Solution.

Uses. Corollary 1.3.20 (Operations that preserve the span), Proposition 1.3.18 (Comparing spans), Proposition 1.3.17 (A list lies in its span)

Hint 1. For (a), express

𝐰 - 𝐮

in terms of the other two differences.

Hint 2. For (b), try the standard vectors

𝐞_{1}, 𝐞_{2}, 𝐞_{3}

ℝ^{3}

and add up coordinates.

Hint 3. For (c), if

𝐮 \in 𝐷

, recover

𝐯

and

𝐰

from

𝐮

and the differences.

Sketch. (a)

𝐰 -

𝐮 =

- (𝐮 - 𝐯) -

(𝐯 - 𝐰)

, and each difference lies in

span (𝐮, 𝐯, 𝐰)

. (b) False: for

𝐞_{1}, 𝐞_{2}, 𝐞_{3}

ℝ^{3}

, every difference has coordinate sum

0

, hence so does every combination, but

𝐞_{1}

does not. (c) If equality holds,

𝐮 \in 𝐷

. If

𝐮 \in 𝐷

, then

𝐯 = 𝐮 - (𝐮 - 𝐯) \in 𝐷

and

𝐰 = 𝐯 - (𝐯 - 𝐰) \in 𝐷

, so

span (𝐮, 𝐯, 𝐰) \subseteq 𝐷

(a) Since $𝐰 -$ $𝐮 =$ $- (𝐮 - 𝐯) -$ $(𝐯 - 𝐰) \in$ $𝐷$ , Corollary 1.3.20(c) gives $span (𝐮 - 𝐯, 𝐯 - 𝐰, 𝐰 - 𝐮) =$ $𝐷$ . Each difference is a linear combination of $𝐮, 𝐯, 𝐰$ (for instance $𝐮 -$ $𝐯 =$ $1 𝐮 +$ $(- 1) 𝐯 +$ $0 𝐰$ ), so $𝐷 \subseteq span (𝐮, 𝐯, 𝐰)$ by Proposition 1.3.18.

(b) False. In $ℝ^{3}$ , take $𝐮 = 𝐞_{1}$ , $𝐯 = 𝐞_{2}$ , $𝐰 = 𝐞_{3}$ . Then $span (𝐮, 𝐯, 𝐰) = ℝ^{3}$ . The differences $(1, - 1, 0)$ and $(0, 1, - 1)$ have coordinate sum $0$ , so every vector $𝑎 (1, - 1, 0) +$ $𝑏 (0, 1, - 1) =$ $(𝑎, 𝑏 - 𝑎, - 𝑏)$ of $𝐷$ has coordinate sum $0$ . Since $𝐞_{1}$ has coordinate sum $1$ , $𝐞_{1} \notin 𝐷$ .

(c) If $𝐷 = span (𝐮, 𝐯, 𝐰)$ , then $𝐮 \in 𝐷$ by Proposition 1.3.17. Conversely, suppose $𝐮 \in 𝐷$ . Then $𝐯 = 𝐮 - (𝐮 - 𝐯)$ and $𝐰 = 𝐯 - (𝐯 - 𝐰)$ lie in $span (𝐮, 𝐮 - 𝐯, 𝐯 - 𝐰)$ , which equals $𝐷$ by Corollary 1.3.20(a) and (c), since $𝐮 \in 𝐷$ . So $span (𝐮, 𝐯, 𝐰) \subseteq 𝐷$ by Proposition 1.3.18, and equality follows from (a).

Exercise 1.3.42.hard Let

𝑛 \geq 2

, let

𝐬 = (1, 1, \dots, 1) \in 𝐹^{𝑛}

, and let

𝐮_{𝑖} = 𝐬 - 𝐞_{𝑖}

be the vector with

0

in position

𝑖

and

1

elsewhere. For a positive integer

𝑚

, write

𝑚 * 1 = 1 + \dots + 1

(

𝑚

terms) in

𝐹

, as in Exercise 1.2.45. Show that

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

spans

𝐹^{𝑛}

if and only if

(𝑛 - 1) * 1 \neq 0

𝐹

Solution.

Uses. Proposition 1.3.18 (Comparing spans), Example 1.3.11 (Small spans), Exercise 1.2.45

Hint 1. Add up all the

𝐮_{𝑖}

. Each coordinate of the sum is a sum of

𝑛 - 1

ones.

Hint 2. If

(𝑛 - 1) * 1 \neq 0

, get

𝐬

and then each

𝐞_{𝑖} = 𝐬 - 𝐮_{𝑖}

. If

(𝑛 - 1) * 1 = 0

, compute the sum of the coordinates of an arbitrary combination

\sum 𝑎_{𝑖} 𝐮_{𝑖}

Sketch.

\sum_{𝑖} 𝐮_{𝑖} =

((𝑛 - 1) * 1) 𝐬

. If

𝑚 = (𝑛 - 1) * 1 \neq 0

, then

𝐬 = 𝑚^{- 1} \sum 𝐮_{𝑖}

and

𝐞_{𝑖} = 𝐬 - 𝐮_{𝑖}

lie in the span. If

𝑚 = 0

, the vector

\sum 𝑎_{𝑖} 𝐮_{𝑖}

has coordinates

𝑆 - 𝑎_{𝑗}

with

𝑆 = \sum 𝑎_{𝑖}

, whose sum is

𝑛 * 𝑆 - 𝑆 = 𝑚 𝑆 = 0

, while

𝐞_{1}

has coordinate sum

1

Let $𝑚 = (𝑛 - 1) * 1 \in 𝐹$ . Each coordinate of $𝐮_{1} + \dots + 𝐮_{𝑛}$ is a sum of $𝑛 - 1$ ones and one zero, so $𝐮_{1} + \dots + 𝐮_{𝑛} = 𝑚 𝐬$ .

Suppose $𝑚 \neq 0$ . Then $𝐬 =$ $𝑚^{- 1} (𝐮_{1} + \dots + 𝐮_{𝑛}) \in$ $span (𝐮_{1}, \dots, 𝐮_{𝑛})$ , and so $𝐞_{𝑖} = 𝐬 - 𝐮_{𝑖}$ lies in the span for each $𝑖$ . By Proposition 1.3.18, $𝐹^{𝑛} =$ $span (𝐞_{1}, \dots, 𝐞_{𝑛}) \subseteq$ $span (𝐮_{1}, \dots, 𝐮_{𝑛})$ .

Suppose $𝑚 = 0$ . An element of the span is $𝐱 = \sum_{𝑖} 𝑎_{𝑖} 𝐮_{𝑖}$ for some $𝑎_{1}, \dots, 𝑎_{𝑛} \in 𝐹$ ; let $𝑆 = 𝑎_{1} + \dots + 𝑎_{𝑛}$ . The $𝑗$ -th coordinate of $𝐱$ is the sum of the $𝑎_{𝑖}$ with $𝑖 \neq 𝑗$ , which is $𝑆 - 𝑎_{𝑗}$ . So the sum of the coordinates of $𝐱$ is

\sum_{𝑗 = 1}^{𝑛} (𝑆 - 𝑎_{𝑗}) = (𝑛 * 1) 𝑆 - 𝑆 = ((𝑛 - 1) * 1) 𝑆 = 𝑚 𝑆 = 0 .

The coordinates of $𝐞_{1}$ sum to $1 \neq 0$ , so $𝐞_{1}$ is not in the span, and the list does not span $𝐹^{𝑛}$ .

For example, over $ℝ$ the list always spans, while over $𝔽_{2}$ it spans exactly when $𝑛$ is even, and over $𝔽_{3}$ exactly when $𝑛 - 1$ is not a multiple of $3$ .

Exercise 1.3.43.hard Let $𝑛 \geq 3$ . Let ${𝒲︀}_{2}$ be a list of all vectors in $𝐹^{𝑛}$ with exactly two coordinates equal to $1$ and all others $0$ , and define ${𝒲︀}_{3}$ similarly with three coordinates equal to $1$ .

(a)Show that if $1 + 1 \neq 0$ in $𝐹$ , then ${𝒲︀}_{2}$ spans $𝐹^{𝑛}$ .
(b)Over $𝔽_{2}$ , show that $span ({𝒲︀}_{2}) =$ ${𝐱 \in 𝔽_{2}^{𝑛} | 𝑥_{1} + \dots + 𝑥_{𝑛} = 0}$ .
(c)Over $𝔽_{2}$ , show that ${𝒲︀}_{3}$ spans $𝔽_{2}^{𝑛}$ when $𝑛 \geq 4$ . What is $span ({𝒲︀}_{3})$ when $𝑛 = 3$ ?

Solution.

Uses. Proposition 1.3.18 (Comparing spans), Example 1.3.11 (Small spans), Corollary 1.3.20 (Operations that preserve the span)

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

Hint 1. For (a), combine

𝐞_{𝑖} + 𝐞_{𝑗}

𝐞_{𝑖} + 𝐞_{𝑘}

, and

𝐞_{𝑗} + 𝐞_{𝑘}

to isolate a multiple of

𝐞_{𝑖}

Hint 2. For (b), the sum of the coordinates of a sum of vectors is the sum of their coordinate sums. For the other containment, pair up the coordinates equal to

1

Hint 3. For (c), the sum of two vectors of

{𝒲︀}_{3}

that share two positions lies in

{𝒲︀}_{2}

. Then handle vectors with an odd number of ones by adding

(1, 1, 1, 0, \dots, 0)

Sketch. (a)

(𝐞_{𝑖} + 𝐞_{𝑗}) +

(𝐞_{𝑖} + 𝐞_{𝑘}) -

(𝐞_{𝑗} + 𝐞_{𝑘}) =

(1 + 1) 𝐞_{𝑖}

. (b) Each entry of

{𝒲︀}_{2}

has coordinate sum

0

, so every combination does; a vector with

2 𝑟

ones is a sum of

𝑟

entries of

{𝒲︀}_{2}

. (c) For

𝑛 \geq 4

(𝐞_{𝑖} + 𝐞_{𝑘} + 𝐞_{𝑙}) +

(𝐞_{𝑗} + 𝐞_{𝑘} + 𝐞_{𝑙}) =

𝐞_{𝑖} +

𝐞_{𝑗}

, so the span contains

span ({𝒲︀}_{2})

; a vector with coordinate sum

1

(𝐱 + 𝐭) + 𝐭

with

𝐭 = 𝐞_{1} + 𝐞_{2} + 𝐞_{3}

. For

𝑛 = 3

{𝒲︀}_{3} = (1, 1, 1)

and the span is

{𝟎, (1, 1, 1)}

The entries of ${𝒲︀}_{2}$ are the vectors $𝐞_{𝑖} + 𝐞_{𝑗}$ with $𝑖 < 𝑗$ , and those of ${𝒲︀}_{3}$ are $𝐞_{𝑖} + 𝐞_{𝑗} + 𝐞_{𝑘}$ with $𝑖 < 𝑗 < 𝑘$ . By Corollary 1.3.20(a), the order in which they are listed does not affect the spans.

(a) Fix $𝑖$ , and choose $𝑗$ and $𝑘$ so that $𝑖, 𝑗, 𝑘$ are distinct, which is possible since $𝑛 \geq 3$ . Then

(𝐞_{𝑖} + 𝐞_{𝑗}) + (𝐞_{𝑖} + 𝐞_{𝑘}) - (𝐞_{𝑗} + 𝐞_{𝑘}) = (1 + 1) 𝐞_{𝑖} .

Since $1 + 1 \neq 0$ , $𝐞_{𝑖} =$ ${(1 + 1)}^{- 1} (1 + 1) 𝐞_{𝑖} \in$ $span ({𝒲︀}_{2})$ . By Proposition 1.3.18, $𝐹^{𝑛} =$ $span (𝐞_{1}, \dots, 𝐞_{𝑛}) \subseteq$ $span ({𝒲︀}_{2})$ .

(b) For $𝐱 \in 𝔽_{2}^{𝑛}$ , write $𝜎 (𝐱) =$ $𝑥_{1} +$ $\dots +$ $𝑥_{𝑛} \in$ $𝔽_{2}$ . Then $𝜎 (𝐱 + 𝐲) =$ $𝜎 (𝐱) +$ $𝜎 (𝐲)$ and $𝜎 (𝑎 𝐱) = 𝑎 𝜎 (𝐱)$ , by the coordinatewise operations and the field axioms. Let $𝐸 = {𝐱 | 𝜎 (𝐱) = 0}$ . We proceed by double containment.

Each entry $𝐞_{𝑖} + 𝐞_{𝑗}$ of ${𝒲︀}_{2}$ has $𝜎 = 1 + 1 = 0$ . So for a linear combination $𝐱 =$ $\sum 𝑐_{𝑖 𝑗} (𝐞_{𝑖} + 𝐞_{𝑗})$ , applying the two rules for $𝜎$ term by term (by induction on the number of terms) gives $𝜎 (𝐱) =$ $\sum 𝑐_{𝑖 𝑗} \cdot$ $0 =$ $0$ . Hence $span ({𝒲︀}_{2}) \subseteq 𝐸$ .

Conversely, let $𝐱 \in 𝐸$ , and let $𝑖_{1} <$ $𝑖_{2} <$ $\dots <$ $𝑖_{𝑡}$ be the positions where $𝑥_{𝑖} = 1$ . Then $𝜎 (𝐱)$ is the sum of $𝑡$ ones, which is $0$ in $𝔽_{2}$ exactly when $𝑡$ is even, say $𝑡 = 2 𝑟$ . Then

𝐱 = (𝐞_{𝑖_{1}} + 𝐞_{𝑖_{2}}) + (𝐞_{𝑖_{3}} + 𝐞_{𝑖_{4}}) + \dots + (𝐞_{𝑖_{2 𝑟 - 1}} + 𝐞_{𝑖_{2 𝑟}})

is a sum of entries of ${𝒲︀}_{2}$ (and $𝐱 = 𝟎$ if $𝑟 = 0$ ), so $𝐱 \in span ({𝒲︀}_{2})$ .

(c) Let $𝑛 \geq 4$ . For $𝑖 \neq 𝑗$ , choose $𝑘$ and $𝑙$ so that $𝑖, 𝑗, 𝑘, 𝑙$ are distinct. In $𝔽_{2}^{𝑛}$ , $𝐞_{𝑘} + 𝐞_{𝑘} = 𝟎$ , so

(𝐞_{𝑖} + 𝐞_{𝑘} + 𝐞_{𝑙}) + (𝐞_{𝑗} + 𝐞_{𝑘} + 𝐞_{𝑙}) = 𝐞_{𝑖} + 𝐞_{𝑗} .

So ${𝒲︀}_{2} \subseteq span ({𝒲︀}_{3})$ , and by Proposition 1.3.18 and (b), every $𝐱$ with $𝜎 (𝐱) = 0$ lies in $span ({𝒲︀}_{3})$ . Now let $𝜎 (𝐱) = 1$ , and let $𝐭 = 𝐞_{1} + 𝐞_{2} + 𝐞_{3}$ , an entry of ${𝒲︀}_{3}$ . Then $𝜎 (𝐱 + 𝐭) = 1 + 1 = 0$ , so $𝐱 + 𝐭 \in span ({𝒲︀}_{3})$ , and $𝐱 = (𝐱 + 𝐭) + 𝐭$ is a sum of two elements of $span ({𝒲︀}_{3})$ , written as combinations of ${𝒲︀}_{3}$ . By Lemma 1.3.9(a), $𝐱 \in span ({𝒲︀}_{3})$ . So ${𝒲︀}_{3}$ spans $𝔽_{2}^{𝑛}$ .

For $𝑛 = 3$ , the only vector with three coordinates equal to $1$ is $(1, 1, 1)$ , so $span ({𝒲︀}_{3}) =$ $span ((1, 1, 1)) =$ ${𝟎, (1, 1, 1)}$ by Example 1.3.11. The pairing trick needs a fourth position.

Exercise 1.3.44.standard Regard

ℝ

as a vector space over

ℚ

(Example 1.2.20). Show that

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

. You may use that

\sqrt{2}

\sqrt{3}

, and

\sqrt{6}

are irrational.

Solution.

Uses. Definition 1.3.10 (Span), Example 1.2.20 (Real and rational scalars)

Hint 1. Suppose

\sqrt{3} = 𝑎 + 𝑏 \sqrt{2}

with

𝑎, 𝑏 \in ℚ

, and square both sides.

Hint 2. The squared equation is

3 = 𝑎^{2} + 2 𝑏^{2} + 2 𝑎 𝑏 \sqrt{2}

. If

𝑎 𝑏 \neq 0

, solve for

\sqrt{2}

. Otherwise treat

𝑎 = 0

and

𝑏 = 0

separately.

Sketch. If

\sqrt{3} = 𝑎 + 𝑏 \sqrt{2}

with

𝑎, 𝑏

rational, then

3 = 𝑎^{2} + 2 𝑏^{2} + 2 𝑎 𝑏 \sqrt{2}

. If

𝑎 𝑏 \neq 0

\sqrt{2}

is rational. If

𝑏 = 0

\sqrt{3} = 𝑎

is rational. If

𝑎 = 0

, then

\sqrt{6} = \sqrt{2} \sqrt{3} = 2 𝑏

is rational. Each case is impossible.

Over $ℚ$ , $span (1, \sqrt{2}) =$ ${𝑎 + 𝑏 \sqrt{2} | 𝑎, 𝑏 \in ℚ}$ . Suppose that $\sqrt{3} = 𝑎 + 𝑏 \sqrt{2}$ with $𝑎, 𝑏 \in ℚ$ . Squaring gives

3 = 𝑎^{2} + 2 𝑏^{2} + 2 𝑎 𝑏 \sqrt{2} .

If $𝑎 𝑏 \neq 0$ , then $\sqrt{2} =$ $(3 - 𝑎^{2} - 2 𝑏^{2}) / (2 𝑎 𝑏)$ is rational, a contradiction. So $𝑎 = 0$ or $𝑏 = 0$ . If $𝑏 = 0$ , then $\sqrt{3} = 𝑎$ is rational, a contradiction. If $𝑎 = 0$ , then $\sqrt{3} = 𝑏 \sqrt{2}$ , and multiplying by $\sqrt{2}$ gives $\sqrt{6} = 2 𝑏$ , which is rational, a contradiction. Hence $\sqrt{3} \notin span (1, \sqrt{2})$ .

Over $ℝ$ instead of $ℚ$ , $span (1) = ℝ$ contains every real number. The span depends on the field of scalars, a theme of Section 1.5.

Exercise 1.3.45.hardBeyond 21-242 Show that no finite list spans

ℝ

as a vector space over

ℚ

. (Use countability.)

Solution.

Uses. Definition 1.3.10 (Span), Example 1.2.20 (Real and rational scalars), $ℚ^{𝑘}$ is countable, and $ℝ$ is uncountable

Hint 1. How many linear combinations with rational coefficients does a list of length

𝑘

have?

Hint 2. The span is the image of the countable set

ℚ^{𝑘}

under the map that sends coefficients to the vector they represent.

Sketch. The span of

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

over

ℚ

is the image of

ℚ^{𝑘}

under

(𝑎_{1}, \dots, 𝑎_{𝑘}) \mapsto

\sum 𝑎_{𝑖} 𝑣_{𝑖}

. A finite product of countable sets is countable, and so is the image of a countable set, while

ℝ

is uncountable.

Let $𝑣_{1}, \dots, 𝑣_{𝑘} \in ℝ$ . (Vectors here are real numbers, so we do not write them in bold.) The map $ℚ^{𝑘} \to ℝ$ sending $(𝑎_{1}, \dots, 𝑎_{𝑘})$ to $𝑎_{1} 𝑣_{1} + \dots + 𝑎_{𝑘} 𝑣_{𝑘}$ has image $span (𝑣_{1}, \dots, 𝑣_{𝑘})$ , by Definition 1.3.10. The set $ℚ^{𝑘}$ is countable, being a finite product of countable sets (for $𝑘 = 0$ it has one element), and the image of a countable set under any map is countable. So $span (𝑣_{1}, \dots, 𝑣_{𝑘})$ is countable. Since $ℝ$ is uncountable, $span (𝑣_{1}, \dots, 𝑣_{𝑘}) \neq$ $ℝ$ .

The same argument shows that $span$ over $ℚ$ of any countable set is countable, so every spanning set of $ℝ$ over $ℚ$ is uncountable (Aside (Spans of infinite sets)).

Exercise 1.3.46.challenge A row of $𝑛 \geq 1$ lamps, each on or off, is recorded as a vector $𝐱 \in 𝔽_{2}^{𝑛}$ , with $𝑥_{𝑖} = 1$ when lamp $𝑖$ is on. Pressing lamp $𝑖$ switches lamp $𝑖$ and its neighbors $𝑖 - 1$ and $𝑖 + 1$ (those that exist). That is, it adds $𝐭_{𝑖} =$ $𝐞_{𝑖 - 1} +$ $𝐞_{𝑖} +$ $𝐞_{𝑖 + 1}$ to $𝐱$ , where $𝐞_{0} = 𝐞_{𝑛 + 1} = 𝟎$ .

(a)Show that every configuration can be switched entirely off by pressing lamps if and only if $𝐭_{1}, \dots, 𝐭_{𝑛}$ spans $𝔽_{2}^{𝑛}$ .
(b)Show that this happens if and only if $𝑛$ is not of the form $3 𝑚 + 2$ .

Solution.

Uses. Definition 1.3.10 (Span), Proposition 1.3.18 (Comparing spans), Example 1.3.11 (Small spans)

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

Hint 1. For (a), pressing lamps in any order adds a sum of

𝐭_{𝑖}

’s, and pressing a lamp twice does nothing. Over

𝔽_{2}

, what are the linear combinations of

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

Hint 2. Work out

𝑛 = 1, 2, 3, 4, 5

by hand. For

𝑛 = 2

and

𝑛 = 5

, look for a set

𝑆

of positions such that every

𝐭_{𝑖}

has an even number of ones in

𝑆

Hint 3. For

𝑛 = 3 𝑚 + 2

, take

𝑆 = {𝑖 | 3 ∤ 𝑖}

. For the other

𝑛

, show

𝐭_{3 𝑗 + 1} +

𝐭_{3 𝑗 + 2} =

𝐞_{3 𝑗} +

𝐞_{3 𝑗 + 3}

, walk along the row from the left end to get

𝐞_{3}, 𝐞_{6}, \dots

, then come back.

Sketch. (a) The reachable configurations from

𝐱

are

𝐱 + \sum_{𝑖 \in 𝑆} 𝐭_{𝑖}

, and over

𝔽_{2}

these sums are exactly the linear combinations of the

𝐭_{𝑖}

;

𝐱 + 𝐲 = 𝟎

means

𝐱 = 𝐲

. (b) If

𝑛 = 3 𝑚 + 2

, the parity of the lamps in positions not divisible by

3

is unchanged by every press, since each

𝐭_{𝑖}

meets those positions in

0

2

places, while

𝐞_{1}

has parity

1

. If

𝑛 = 3 𝑚

3 𝑚 + 1

, then

𝐞_{3}, 𝐞_{6}, \dots, 𝐞_{3 𝑚}

are in the span,

𝐭_{𝑛}

supplies whichever of

𝐞_{𝑛 - 1}, 𝐞_{𝑛}

is missing, and going back with

𝐞_{𝑖 - 1} =

𝐭_{𝑖} +

𝐞_{𝑖} +

𝐞_{𝑖 + 1}

gives all

𝐞_{𝑖}

(a) Pressing lamps one after another adds the corresponding $𝐭_{𝑖}$ ’s, and since addition in $𝔽_{2}^{𝑛}$ is commutative and $𝐭_{𝑖} + 𝐭_{𝑖} = 𝟎$ , the result of any sequence of presses from $𝐱$ is $𝐱 + \sum_{𝑖 \in 𝑆} 𝐭_{𝑖}$ , where $𝑆$ is the set of lamps pressed an odd number of times. Every subset $𝑆$ arises. Since the only scalars in $𝔽_{2}$ are $0$ and $1$ , the linear combinations of $𝐭_{1}, \dots, 𝐭_{𝑛}$ represent exactly the sums $\sum_{𝑖 \in 𝑆} 𝐭_{𝑖}$ . Finally, $𝐱 + 𝐲 = 𝟎$ in $𝔽_{2}^{𝑛}$ if and only if $𝐱 = - 𝐲 = 𝐲$ . So $𝐱$ can be switched off if and only if $𝐱 \in$ $span (𝐭_{1}, \dots, 𝐭_{𝑛})$ , and every configuration can be switched off if and only if the list spans $𝔽_{2}^{𝑛}$ .

(b) For $𝑛 = 1$ , $𝐭_{1} = 𝐞_{1}$ spans $𝔽_{2}^{1}$ . From now on let $𝑛 \geq 2$ , so $𝐭_{1} = 𝐞_{1} + 𝐞_{2}$ and $𝐭_{𝑛} = 𝐞_{𝑛 - 1} + 𝐞_{𝑛}$ .

Case $𝑛 = 3 𝑚 + 2$ . For $𝐱 \in 𝔽_{2}^{𝑛}$ , let $𝑓 (𝐱) = \sum_{𝑖 \in 𝑆} 𝑥_{𝑖}$ , where $𝑆$ is the set of $𝑖 \in {1, \dots, 𝑛}$ not divisible by $3$ . Then $𝑓 (𝐱 + 𝐲) =$ $𝑓 (𝐱) +$ $𝑓 (𝐲)$ . We claim $𝑓 (𝐭_{𝑖}) = 0$ for every $𝑖$ . For $2 \leq 𝑖 \leq 𝑛 - 1$ , the positions $𝑖 - 1, 𝑖, 𝑖 + 1$ are three consecutive integers, exactly one of which is divisible by $3$ , so $𝑓 (𝐭_{𝑖}) = 1 + 1 = 0$ . For $𝑖 = 1$ , positions $1$ and $2$ both lie in $𝑆$ . For $𝑖 = 𝑛 = 3 𝑚 + 2$ , positions $3 𝑚 + 1$ and $3 𝑚 + 2$ both lie in $𝑆$ . So $𝑓$ vanishes on each $𝐭_{𝑖}$ , hence on every sum of them, hence on the span. Since $𝑓 (𝐞_{1}) = 1$ , $𝐞_{1}$ is not in the span.

Case $𝑛 = 3 𝑚$ or $𝑛 = 3 𝑚 + 1$ , with $𝑚 \geq 1$ . First, $𝐭_{1} +$ $𝐭_{2} =$ $(𝐞_{1} + 𝐞_{2}) +$ $(𝐞_{1} + 𝐞_{2} + 𝐞_{3}) =$ $𝐞_{3}$ . Next, if $3 𝑗 + 3 \leq 𝑛$ , then $3 𝑗 + 2 \leq 𝑛 - 1$ , so lamp $3 𝑗 + 2$ has a right neighbor, and

𝐭_{3 𝑗 + 1} + 𝐭_{3 𝑗 + 2} = (𝐞_{3 𝑗} + 𝐞_{3 𝑗 + 1} + 𝐞_{3 𝑗 + 2}) + (𝐞_{3 𝑗 + 1} + 𝐞_{3 𝑗 + 2} + 𝐞_{3 𝑗 + 3}) = 𝐞_{3 𝑗} + 𝐞_{3 𝑗 + 3} .

So $𝐞_{3 𝑗 + 3} =$ $𝐭_{3 𝑗 + 1} +$ $𝐭_{3 𝑗 + 2} +$ $𝐞_{3 𝑗}$ , and by induction on $𝑗$ , the vectors $𝐞_{3}, 𝐞_{6}, \dots, 𝐞_{3 𝑚}$ lie in the span. If $𝑛 = 3 𝑚$ , this gives $𝐞_{𝑛}$ , and then $𝐞_{𝑛 - 1} = 𝐭_{𝑛} + 𝐞_{𝑛}$ . If $𝑛 = 3 𝑚 + 1$ , it gives $𝐞_{𝑛 - 1}$ , and then $𝐞_{𝑛} = 𝐭_{𝑛} + 𝐞_{𝑛 - 1}$ . In both cases $𝐞_{𝑛 - 1}$ and $𝐞_{𝑛}$ lie in the span, and for $𝑖 = 𝑛 - 1, 𝑛 - 2, \dots, 2$ in turn, $𝐞_{𝑖 - 1} =$ $𝐭_{𝑖} +$ $𝐞_{𝑖} +$ $𝐞_{𝑖 + 1}$ does too. So every $𝐞_{𝑖}$ lies in the span, and the list spans $𝔽_{2}^{𝑛}$ by Proposition 1.3.18.

Since every $𝑛 \geq 1$ has exactly one of the forms $3 𝑚$ , $3 𝑚 + 1$ , $3 𝑚 + 2$ , this proves (b). Small cases are how one finds $𝑆$ : for $𝑛 = 2$ the two presses are equal, $𝐭_{1} = 𝐭_{2} = (1, 1)$ , and the invariant is $𝑥_{1} + 𝑥_{2}$ ; for $𝑛 = 5$ it is $𝑥_{1} + 𝑥_{2} + 𝑥_{4} + 𝑥_{5}$ .

More practice

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