1.3 Linear Combinations and Span

We now have vector spaces and, inside them, subspaces. So far every subspace has been handed to us by a condition, such as “ $x + 2y = 0$ ” or “ $\mathbf{A}^{\top} = \mathbf{A}$ ”. This section goes the other way. We start from a few vectors, build everything that can be built from them, and show that the result is always a subspace: the smallest one containing the vectors we started with. Along the way we meet the first way of measuring a space, by asking whether finitely many vectors are enough to build all of it.

1.3.1. Linear combinations

Take two vectors in $\mathbb{R}^3$ , say $\mathbf{v}_1 = (1, 0, 1)$ and $\mathbf{v}_2 = (0, 1, 1)$ . Which vectors can we build from them, using only the two operations a vector space gives us? Scaling gives $a\mathbf{v}_1$ and $b\mathbf{v}_2$ , and adding gives $a\mathbf{v}_1 + b\mathbf{v}_2 = (a, b, a + b).$ Adding or scaling again produces nothing new: for instance $2(a\mathbf{v}_1 + b\mathbf{v}_2) + (c\mathbf{v}_1 + d\mathbf{v}_2) = (2a + c)\mathbf{v}_1 + (2b + d)\mathbf{v}_2$ has the same shape. So the vectors we can reach are exactly those of the form $(a, b, a + b)$ : the plane $z = x + y$ through the origin. The expression $a\mathbf{v}_1 + b\mathbf{v}_2$ will appear in almost every argument from now on, so it deserves a name.

The vectors we combine come as a list $(\mathbf{v}_1, \dots, \mathbf{v}_k)$ : a finite sequence of vectors, in order, in which repeats are allowed. A list of length $k = 0$ is the empty list $()$ . Why lists rather than sets becomes important in the next section; for now it costs nothing.

Definition 1.3.1 (Linear Combination)

Let $V$ be a vector space over $F$ , and let $(\mathbf{v}_1, \dots, \mathbf{v}_k)$ be a list of vectors in $V$ , where $k \ge 0$ . A linear combination of $(\mathbf{v}_1, \dots, \mathbf{v}_k)$ is a vector of the form $a_1\mathbf{v}_1 + a_2\mathbf{v}_2 + \dots + a_k\mathbf{v}_k, \qquad \text{where } a_1, \dots, a_k \in F.$ The scalars $a_i$ are the coefficients of the combination. A linear combination of the empty list is, by convention, the empty sum $\mathbf{0}$ .

In words: scale each vector of the list by a scalar from $F$ , then add up the results. Two small points hide in the notation. First, a sum of $k$ vectors needs no brackets, because addition in $V$ is associative (VS2); so the expression names a single vector. Second, the coefficients must lie in the field $F$ we are working over. Changing the field can change what counts as a combination, as Exercise (C2: The Span Depends on the Field) shows.

The empty sum convention is the additive twin of $0! = 1$ and $x^0 = 1$ , where a product with no factors is the neutral element $1$ for multiplication: a sum with no terms is the neutral element $\mathbf{0}$ for addition. It will make several statements true without exceptions.

Example (Linear Combinations in Four Families)

Show that each vector is a linear combination of the given list.

(a) $(3, -2, 1) \in \mathbb{R}^3$ , of the list $((1, 0, 1), (0, 1, 1))$ .
(b) $x^2 - 1 \in \mathbb{R}[x]$ , of the list $((x + 1)^2, x + 1)$ .
(c) The function $\sin^2$ in $\mathbb{R}^\mathbb{R}$ , of the list $(1, \cos 2x)$ , where $1$ is the constant function.
(d) The zero vector of any vector space $V$ , of any list $(\mathbf{v}_1, \dots, \mathbf{v}_k)$ in $V$ .

Solution.

(a) We need $a(1, 0, 1) + b(0, 1, 1) = (a, b, a + b)$ to equal $(3, -2, 1)$ . The first two entries force $a = 3$ and $b = -2$ , and then the third entry is $a + b = 1$ , as required. Hence $(3, -2, 1) = 3(1, 0, 1) - 2(0, 1, 1)$ .
(b) Expanding, $(x + 1)^2 - 2(x + 1) = x^2 + 2x + 1 - 2x - 2 = x^2 - 1$ . So the coefficients are $1$ and $-2$ .
(c) The double-angle formula $\cos 2x = 1 - 2\sin^2 x$ holds for every real $x$ . Hence $\sin^2 x = \tfrac12 \cdot 1 + \bigl(-\tfrac12\bigr) \cos 2x$ for every $x$ , which is an equality of functions by Definition 0.4.1. The coefficients $\tfrac12$ and $-\tfrac12$ are real, as they must be.
(d) Take every coefficient to be $0$ . By Theorem 1.1.5, $0\mathbf{v}_i = \mathbf{0}$ for each $i$ , so $0\mathbf{v}_1 + \dots + 0\mathbf{v}_k = \mathbf{0}$ . For the empty list, $\mathbf{0}$ is the empty sum. This degenerate case matters: it says the zero vector can always be built, from anything, even from nothing.

Notice that the question in (a) was a small system of equations in the unknown coefficients. That is typical: deciding whether a vector is a combination of a list means deciding whether a system of linear equations has a solution. Here we solve such systems by hand; Chapter 3 gives a systematic method.

1.3.2. The span

The span of some vectors is everything you can build from them by scaling and adding.

We have two kinds of input to cover. Usually we start from a list, as above. But sometimes the natural input is a set, possibly infinite, such as all the powers $1, x, x^2, \dots$ in $F[x]$ . A linear combination only ever uses finitely many vectors, so for a set we allow every finite list drawn from it.

Definition 1.3.2 (Span)

Let $V$ be a vector space over $F$ .

The span of a list $(\mathbf{v}_1, \dots, \mathbf{v}_k)$ of vectors in $V$ is the set of all its linear combinations: $\operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_k) = \{ a_1\mathbf{v}_1 + \dots + a_k\mathbf{v}_k : a_1, \dots, a_k \in F \}.$
The span of a subset $S \subseteq V$ , possibly infinite, is the set of all vectors that are linear combinations of some finite list of vectors in $S$ : $\operatorname{span}(S) = \{ a_1\mathbf{s}_1 + \dots + a_k\mathbf{s}_k : k \ge 0,\ \mathbf{s}_1, \dots, \mathbf{s}_k \in S,\ a_1, \dots, a_k \in F \}.$

In particular $\operatorname{span}() = \operatorname{span}(\varnothing) = \{ \mathbf{0} \}$ . When the field matters we write $\operatorname{span}_F$ .

In words: for a list, the span collects every choice of coefficients. For a set, we may first pick any finite number of vectors from $S$ (the same vector more than once is allowed), and then any coefficients. The value $k = 0$ is allowed, and it contributes the empty sum $\mathbf{0}$ . So $\mathbf{0} \in \operatorname{span}(S)$ for every $S$ , including $S = \varnothing$ .

One thing to check. A list $(\mathbf{v}_1, \dots, \mathbf{v}_k)$ now has two spans: the span of the list, and the span of the set $\{ \mathbf{v}_1, \dots, \mathbf{v}_k \}$ of its entries. They agree. A combination of the list is a combination of a finite list from the set, so the first is contained in the second. Conversely, take a combination $b_1\mathbf{w}_1 + \dots + b_m\mathbf{w}_m$ where each $\mathbf{w}_r$ is one of the $\mathbf{v}_i$ ; for each $r$ , choose one index $i(r)$ with $\mathbf{w}_r = \mathbf{v}_{i(r)}$ . Group the terms with the same index together, using (VS1), (VS2) and $b\mathbf{v} + b'\mathbf{v} = (b + b')\mathbf{v}$ (VS6). The result is $a_1\mathbf{v}_1 + \dots + a_k\mathbf{v}_k$ , where $a_i$ is the sum of the $b_r$ with $i(r) = i$ (and $a_i = 0$ if there are none, by Theorem 1.1.5). So the second is contained in the first. In particular the span of a list does not change if we reorder the list or repeat an entry.

Why $\operatorname{span}(\varnothing) = \{ \mathbf{0} \}$ ? The definition forces it through the empty sum, but it is also the only sensible choice. We will prove that the span of $S$ is the smallest subspace containing $S$ . The smallest subspace containing nothing in particular is $\{ \mathbf{0} \}$ , since every subspace contains $\mathbf{0}$ . Any other convention would make that theorem false for $S = \varnothing$ , and the empty list will turn out to be a basis of the zero space.

Example (Computing Spans)

Describe each span.

(a) $\operatorname{span}((1, 0, 1), (0, 1, 1))$ in $\mathbb{R}^3$ . Is $(1, 2, 3)$ in it? Is $(1, 2, 4)$ ?
(b) $\operatorname{span}(\mathbf{v})$ for a single vector $\mathbf{v}$ in a vector space $V$ .
(c) $\operatorname{span}(1, x^2)$ in $\mathbb{R}[x]$ .
(d) $\operatorname{span}(\{ 1, x, x^2, x^3, \dots \})$ in $F[x]$ .

Solution.

(a) As computed at the start of the section, the combinations are $a(1, 0, 1) + b(0, 1, 1) = (a, b, a + b)$ . So the span is $\{ (x, y, z) \in \mathbb{R}^3 : z = x + y \}$ , a plane through the origin. For membership, a vector $(x, y, z)$ is in the span exactly when the entries fit: the first two entries force $a = x$ and $b = y$ , and then we need $z = x + y$ . Since $3 = 1 + 2$ , the vector $(1, 2, 3) = 1(1, 0, 1) + 2(0, 1, 1)$ is in the span. Since $4 \neq 1 + 2$ , the vector $(1, 2, 4)$ is not.
(b) $\operatorname{span}(\mathbf{v}) = \{ a\mathbf{v} : a \in F \}$ . If $\mathbf{v} \neq \mathbf{0}$ and $V = \mathbb{R}^2$ or $\mathbb{R}^3$ , this is the line through the origin in the direction of $\mathbf{v}$ . If $\mathbf{v} = \mathbf{0}$ , then $a\mathbf{0} = \mathbf{0}$ for every $a$ (Theorem 1.1.6), so $\operatorname{span}(\mathbf{0}) = \{ \mathbf{0} \}$ . This degenerate case shows that a span can be as small as the zero space even when the list is not empty.
(c) The combinations are $a + bx^2$ with $a, b \in \mathbb{R}$ : the polynomials of degree at most $2$ with no $x$ term. For example $x^2 + x$ is not in the span, because its coefficient of $x$ is $1 \neq 0$ and polynomials are equal only when all coefficients agree (Definition 0.8.1).
(d) Every polynomial $a_0 + a_1x + \dots + a_Nx^N$ is a combination of the finite list $(1, x, \dots, x^N)$ of vectors in the set. Conversely every combination of finitely many powers of $x$ is a polynomial. So the span is all of $F[x]$ . No single polynomial here is a combination of infinitely many powers: each one uses only the powers up to its degree.

Quick check. Is $\operatorname{span}((1, 2))$ a subset of $\operatorname{span}((2, 4))$ in $\mathbb{R}^2$ ? Are they equal?

Solution. Yes to both. Since $(2, 4) = 2(1, 2)$ , every $a(2, 4) = (2a)(1, 2)$ lies in $\operatorname{span}((1, 2))$ . Since $(1, 2) = \tfrac12 (2, 4)$ , every $a(1, 2) = \tfrac{a}{2}(2, 4)$ lies in $\operatorname{span}((2, 4))$ . Both spans are the line $y = 2x$ . Different lists can have the same span.

1.3.3. The span is the smallest subspace

The plane in Example (Computing Spans) (a) was a subspace. That was no accident. Adding two combinations gives a combination, and so does scaling one. And any subspace that contains the vectors must contain all their combinations, because a subspace is closed under exactly the operations that build them. So the span is both a subspace and the smallest one available:

Theorem 1.3.1 (Span Is the Smallest Subspace)

Let $V$ be a vector space over $F$ and let $S \subseteq V$ . Then:

(1) $\operatorname{span}(S)$ is a subspace of $V$ ;
(2) $S \subseteq \operatorname{span}(S)$ ;
(3) if $U$ is a subspace of $V$ with $S \subseteq U$ , then $\operatorname{span}(S) \subseteq U$ .

The same holds for the span of a list, which equals the span of the set of its entries.

Idea. Part (1) is the three-check subspace test. Part (2) is the combination $1\mathbf{s}$ . Part (3) is “a subspace is closed under the operations that build combinations”; since a combination has $k$ terms for an arbitrary $k$ , we add one term at a time, by induction on $k$ .

Proof.

We apply Theorem 1.2.1.
- Zero. The empty list is a finite list of vectors in $S$ , and its only combination is $\mathbf{0}$ . Hence $\mathbf{0} \in \operatorname{span}(S)$ .
- Addition. Let $\mathbf{x}, \mathbf{y} \in \operatorname{span}(S)$ . Then $\mathbf{x} = a_1\mathbf{s}_1 + \dots + a_k\mathbf{s}_k$ and $\mathbf{y} = b_1\mathbf{t}_1 + \dots + b_m\mathbf{t}_m$ for some $\mathbf{s}_i, \mathbf{t}_j \in S$ and scalars $a_i, b_j \in F$ . Therefore $\mathbf{x} + \mathbf{y} = a_1\mathbf{s}_1 + \dots + a_k\mathbf{s}_k + b_1\mathbf{t}_1 + \dots + b_m\mathbf{t}_m ,$ which is a combination of the list $(\mathbf{s}_1, \dots, \mathbf{s}_k, \mathbf{t}_1, \dots, \mathbf{t}_m)$ of vectors in $S$ . (If some $\mathbf{t}_j$ equals some $\mathbf{s}_i$ , the list has a repeat, which lists allow.) Hence $\mathbf{x} + \mathbf{y} \in \operatorname{span}(S)$ . This shows $\operatorname{span}(S)$ is closed under addition.
- Scaling. Let $\mathbf{x} = a_1\mathbf{s}_1 + \dots + a_k\mathbf{s}_k \in \operatorname{span}(S)$ and $c \in F$ . By (VS5), applied $k - 1$ times, and by (VS7) for each term, $c\mathbf{x} = (ca_1)\mathbf{s}_1 + \dots + (ca_k)\mathbf{s}_k ,$ which is a combination of the same list. Hence $c\mathbf{x} \in \operatorname{span}(S)$ . This shows $\operatorname{span}(S)$ is closed under scalar multiplication.
Therefore $\operatorname{span}(S)$ is a subspace of $V$ .
Let $\mathbf{s} \in S$ . By (VS8), $\mathbf{s} = 1\mathbf{s}$ , which is a combination of the list $(\mathbf{s})$ . Hence $\mathbf{s} \in \operatorname{span}(S)$ .
Let $U$ be a subspace with $S \subseteq U$ . By Theorem 1.2.1, $U$ contains $\mathbf{0}$ and is closed under addition and scalar multiplication. We prove by induction on $k \ge 0$ (Theorem 0.2.7) that every combination $a_1\mathbf{s}_1 + \dots + a_k\mathbf{s}_k$ with $\mathbf{s}_i \in S$ lies in $U$ . For $k = 0$ the combination is $\mathbf{0} \in U$ . Suppose the claim holds for $k$ , and consider $a_1\mathbf{s}_1 + \dots + a_{k+1}\mathbf{s}_{k+1}$ . By the induction hypothesis $\mathbf{x} = a_1\mathbf{s}_1 + \dots + a_k\mathbf{s}_k \in U$ . Since $\mathbf{s}_{k+1} \in S \subseteq U$ and $U$ is closed under scaling, $a_{k+1}\mathbf{s}_{k+1} \in U$ . Since $U$ is closed under addition, $\mathbf{x} + a_{k+1}\mathbf{s}_{k+1} \in U$ . This completes the induction, and shows $\operatorname{span}(S) \subseteq U$ .

In one phrase: $\operatorname{span}(S)$ is a subspace containing $S$ , and it sits inside every other one. So “the smallest subspace containing $S$ ” makes sense, and it is $\operatorname{span}(S)$ . This gives a second, top-down description of the span, which does not mention combinations at all.

Corollary 1.3.2 (Span as an Intersection)

Let $V$ be a vector space and $S \subseteq V$ . Let $\mathcal{U}$ be the set of all subspaces $U$ of $V$ with $S \subseteq U$ . Then $\operatorname{span}(S) = \bigcap_{U \in \mathcal{U}} U .$

Proof. The index set $\mathcal{U}$ is non-empty, because $V$ is a subspace of itself containing $S$ ; so the intersection is defined (Definition 0.3.9).

$(\subseteq)$ By Theorem 1.3.1 (3), $\operatorname{span}(S) \subseteq U$ for every $U \in \mathcal{U}$ . Hence $\operatorname{span}(S)$ is contained in the intersection.

$(\supseteq)$ By Theorem 1.3.1 (1) and (2), $\operatorname{span}(S)$ is itself a member of $\mathcal{U}$ . An intersection is contained in each of its members, so the intersection is contained in $\operatorname{span}(S)$ .

By Theorem 0.3.1, the two sets are equal.

By Theorem 1.2.2, an intersection of subspaces is a subspace, so the right-hand side is a subspace for a reason that never mentions combinations. The two descriptions complement each other. The bottom-up one (combinations) tells us what the elements look like. The top-down one (intersection) is convenient for proving that the span lies inside something.

Warning. The span of $S$ is not $S$ , and it is a subspace even when $S$ is not. For example $S = \{ (1, 0), (0, 1) \}$ is a two-element set, and not a subspace of $\mathbb{R}^2$ (it does not contain $(0, 0)$ ). Its span is the whole plane $\mathbb{R}^2$ , since $(x, y) = x(1, 0) + y(0, 1)$ . By Theorem 1.3.1, $\operatorname{span}(S) = S$ holds exactly when $S$ is already a subspace. Also keep the two uses of the word apart: “the span of $S$ ” is a noun, a subspace; “ $S$ spans $V$ ” is a verb, defined next.

1.3.4. Spanning lists and finite-dimensional spaces

The most important case is when the span is everything. Then the list is a complete toolkit for the space: every vector can be built from it.

Definition 1.3.3 (Spanning List, Spanning Set)

Let $V$ be a vector space over $F$ . A list $(\mathbf{v}_1, \dots, \mathbf{v}_k)$ in $V$ spans $V$ , or is a spanning list of $V$ , if $\operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_k) = V$ . A subset $S \subseteq V$ spans $V$ , or is a spanning set of $V$ , if $\operatorname{span}(S) = V$ .

Since every span is contained in $V$ , to show that a list spans $V$ we must show one thing: every $\mathbf{v} \in V$ can be written as $a_1\mathbf{v}_1 + \dots + a_k\mathbf{v}_k$ for some scalars. The scalars may depend on $\mathbf{v}$ , and they need not be unique.

Example (Spanning Lists)

Show that each list spans the given space.

(a) $(\mathbf{e}_1, \dots, \mathbf{e}_n)$ in $F^n$ , where $\mathbf{e}_i$ has $1$ in position $i$ and $0$ elsewhere.
(b) $(1, x, x^2)$ in $F[x]_{\le 2}$ .
(c) $((1, 1), (1, -1))$ in $\mathbb{R}^2$ .
(d) $(\mathbf{E}_{11}, \mathbf{E}_{12}, \mathbf{E}_{21}, \mathbf{E}_{22})$ in $M_2(F)$ , where $\mathbf{E}_{ij}$ has $1$ in entry $(i, j)$ and $0$ elsewhere.
(e) The empty list, in the zero space $\{ \mathbf{0} \}$ .

Solution.

(a) Let $(x_1, \dots, x_n) \in F^n$ . Adding entry by entry, $x_1\mathbf{e}_1 + \dots + x_n\mathbf{e}_n = (x_1, \dots, x_n)$ . So every vector is a combination, with its own entries as coefficients.
(b) Every $p \in F[x]_{\le 2}$ has the form $a_0 + a_1x + a_2x^2$ (Definition 0.8.4), which is the combination $a_0 \cdot 1 + a_1 \cdot x + a_2 \cdot x^2$ .
(c) Let $(p, q) \in \mathbb{R}^2$ . We look for $a, b$ with $a(1, 1) + b(1, -1) = (p, q)$ , that is, $a + b = p, \qquad a - b = q.$ Adding the equations gives $2a = p + q$ , and subtracting gives $2b = p - q$ . So $a = \tfrac{p + q}{2}$ and $b = \tfrac{p - q}{2}$ . Check: $\tfrac{p + q}{2} + \tfrac{p - q}{2} = p$ and $\tfrac{p + q}{2} - \tfrac{p - q}{2} = q$ . Hence $(p, q) = \tfrac{p + q}{2}(1, 1) + \tfrac{p - q}{2}(1, -1)$ , and the list spans $\mathbb{R}^2$ . For instance $(3, 5) = 4(1, 1) - (1, -1)$ .
(d) For any matrix, $\begin{pmatrix} a & b \\ c & d \end{pmatrix} = a\mathbf{E}_{11} + b\mathbf{E}_{12} + c\mathbf{E}_{21} + d\mathbf{E}_{22}$ , by adding entry by entry.
(e) $\operatorname{span}() = \{ \mathbf{0} \}$ by Definition 1.3.2. So the empty list spans the zero space. (So does the list $(\mathbf{0})$ .)

The solution of (3) divided by $2$ , which is fine in $\mathbb{R}$ . Over $\mathbb{F}_2$ , where $2 = 0$ , the same list fails: there $1 = -1$ , so both vectors equal $(1, 1)$ , and their span is $\{ (0, 0), (1, 1) \} \neq \mathbb{F}_2^2$ . Whether a list spans depends on the field.

Now the non-example, by a minimal change of (3). Replace the list by $((1, 2), (2, 4))$ . It still has two vectors, and neither is zero. But every combination is $a(1, 2) + b(2, 4) = (a + 2b)(1, 2),$ a vector whose second entry is twice its first. So $(0, 1)$ is not reached, and the list does not span $\mathbb{R}^2$ . The clause that fails is “every $\mathbf{v} \in V$ is a combination”. The two vectors point along the same line, so their span is only the line $y = 2x$ .

Some spaces are spanned by a short list; others need infinitely many vectors. That distinction is the first coarse measurement of size in this book.

Definition 1.3.4 (Finite-Dimensional)

A vector space $V$ over $F$ is finite-dimensional if some finite list of vectors in $V$ spans $V$ . Otherwise $V$ is infinite-dimensional.

By Example (Spanning Lists), $F^n$ , $F[x]_{\le 2}$ , $M_2(F)$ and $\{ \mathbf{0} \}$ are finite-dimensional. The same argument as in (2) and (4) shows that $F[x]_{\le n}$ and $M_{m \times n}(F)$ are finite-dimensional too. The word “dimension” is used before we have defined a number called dimension; that number, and the fact that it is well defined, are the subject of section 6 of this chapter.

For the whole polynomial space no finite list is enough. The reason is degree: finitely many polynomials have a largest degree, and combining them never climbs above it.

Theorem 1.3.3 (

F\lbrack x\rbrack

Is Infinite-Dimensional)

For every field $F$ , the vector space $F[x]$ is infinite-dimensional.

Proof. Let $(p_1, \dots, p_k)$ be any finite list in $F[x]$ . We show it does not span $F[x]$ . Each $\deg p_i$ is either a natural number or $-\infty$ , and there are finitely many, so we can choose $N \in \mathbb{N}$ with $\deg p_i \le N$ for every $i$ .

Let $a_1, \dots, a_k \in F$ . The coefficients of $a_ip_i$ are $a_i$ times those of $p_i$ (Example (The Standard Vector Spaces) (c)). Every coefficient of $x^m$ with $m > N$ in $p_i$ is $0$ , by Definition 0.8.3, and $a_i \cdot 0 = 0$ by (F6) and Theorem 0.7.1 (d); hence $\deg(a_ip_i) \le N$ . By Theorem 0.8.2, $\deg(p + q) \le \max(\deg p, \deg q)$ , so a sum of two polynomials of degree at most $N$ has degree at most $N$ . Applying this $k - 1$ times, $\deg(a_1p_1 + \dots + a_kp_k) \le N$ . (For $k = 0$ the combination is $0$ , of degree $-\infty \le N$ .)

Hence every element of $\operatorname{span}(p_1, \dots, p_k)$ has degree at most $N$ . But $x^{N+1} \in F[x]$ has degree $N + 1 > N$ , so $x^{N+1} \notin \operatorname{span}(p_1, \dots, p_k)$ . Since the list was arbitrary, no finite list spans $F[x]$ . This shows $F[x]$ is infinite-dimensional.

(In the proof we wrote polynomials in plain italic, $p$ , as in Chapter 0; they are vectors of $F[x]$ all the same.) The proof is the move “find a quantity that combinations cannot increase”. The space $\mathbb{R}^\mathbb{R}$ of all functions is infinite-dimensional too, and so are the sequence spaces; we return to such spaces in section 8 of this chapter.

Remark. For an arbitrary subset $S \subseteq V$ , finite or infinite, “ $S$ spans $V$ ” means that every vector of $V$ is a combination of some finite list of vectors in $S$ . Different vectors may use different finite lists, as in Example (Computing Spans) (d). We never form infinite sums: a vector space only lets us add two vectors at a time, so only finite sums have a meaning. The same “every finite list” reading will be used for independence of an arbitrary set in the next section.

1.3.5. Working with spans

Three facts make spans easy to manipulate. Each follows from Theorem 1.3.1 without writing a single combination.

Proposition 1.3.4 (Basic Properties of Span)

Let $V$ be a vector space and $S, T \subseteq V$ .

(1) If $T \subseteq \operatorname{span}(S)$ , then $\operatorname{span}(T) \subseteq \operatorname{span}(S)$ .
(2) (Monotonicity) If $T \subseteq S$ , then $\operatorname{span}(T) \subseteq \operatorname{span}(S)$ .
(3) $\operatorname{span}(\operatorname{span}(S)) = \operatorname{span}(S)$ .

Proof.

By Theorem 1.3.1 (1), $\operatorname{span}(S)$ is a subspace, and by hypothesis it contains $T$ . By Theorem 1.3.1 (3) applied to $T$ , $\operatorname{span}(T) \subseteq \operatorname{span}(S)$ .
By Theorem 1.3.1 (2), $T \subseteq S \subseteq \operatorname{span}(S)$ . Now apply (1).
Taking $T = \operatorname{span}(S)$ in (1) gives $\operatorname{span}(\operatorname{span}(S)) \subseteq \operatorname{span}(S)$ . The reverse inclusion is Theorem 1.3.1 (2) applied to the set $\operatorname{span}(S)$ .

Part (1) is the workhorse. To show $\operatorname{span}(T) \subseteq \operatorname{span}(S)$ , it is enough to check that each vector of $T$ is a combination of vectors of $S$ ; we do not have to handle every combination of $T$ .

The next fact is the one later sections lean on most. If a vector can already be built from $S$ , then adding it to $S$ builds nothing new.

Theorem 1.3.5 (Absorbing a Vector into a Span)

Let $V$ be a vector space, $S \subseteq V$ and $\mathbf{v} \in V$ . If $\mathbf{v} \in \operatorname{span}(S)$ , then $\operatorname{span}(S \cup \{ \mathbf{v} \}) = \operatorname{span}(S).$ In particular, for a list: if $\mathbf{v} \in \operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_k)$ , then $\operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_k, \mathbf{v}) = \operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_k)$ , and the same holds with $\mathbf{v}$ inserted at any position of the list.

Proof. $(\supseteq)$ Since $S \subseteq S \cup \{ \mathbf{v} \}$ , monotonicity (Proposition 1.3.4 (2)) gives $\operatorname{span}(S) \subseteq \operatorname{span}(S \cup \{ \mathbf{v} \})$ .

$(\subseteq)$ By Theorem 1.3.1 (2), $S \subseteq \operatorname{span}(S)$ , and $\mathbf{v} \in \operatorname{span}(S)$ by hypothesis. Hence $S \cup \{ \mathbf{v} \} \subseteq \operatorname{span}(S)$ , and Proposition 1.3.4 (1) gives $\operatorname{span}(S \cup \{ \mathbf{v} \}) \subseteq \operatorname{span}(S)$ .

For the list version, the span of a list equals the span of the set of its entries, whatever the order. The entries of $(\mathbf{v}_1, \dots, \mathbf{v}_k, \mathbf{v})$ form the set $\{ \mathbf{v}_1, \dots, \mathbf{v}_k \} \cup \{ \mathbf{v} \}$ , so the first part applies.

Concretely, the proof substitutes. If $\mathbf{v} = c_1\mathbf{v}_1 + \dots + c_k\mathbf{v}_k$ , then any combination $a_1\mathbf{v}_1 + \dots + a_k\mathbf{v}_k + b\mathbf{v}$ equals $(a_1 + bc_1)\mathbf{v}_1 + \dots + (a_k + bc_k)\mathbf{v}_k$ , which no longer uses $\mathbf{v}$ . Read backwards, the lemma says that a vector lying in the span of the others can be deleted from a list without shrinking its span. The next section turns this into the idea of a redundant vector, and section 6 of this chapter uses it at every step of the Exchange Theorem.

Example (Two Lists with the Same Span)

Show that $\operatorname{span}(1 + x, 1 - x) = \operatorname{span}(1, x)$ in $\mathbb{R}[x]$ .

Solution. $(\subseteq)$ Both $1 + x = 1 \cdot 1 + 1 \cdot x$ and $1 - x = 1 \cdot 1 + (-1) \cdot x$ lie in $\operatorname{span}(1, x)$ . By Proposition 1.3.4 (1), $\operatorname{span}(1 + x, 1 - x) \subseteq \operatorname{span}(1, x)$ .

$(\supseteq)$ Conversely, $1 = \tfrac12 (1 + x) + \tfrac12 (1 - x), \qquad x = \tfrac12 (1 + x) - \tfrac12 (1 - x),$ so both $1$ and $x$ lie in $\operatorname{span}(1 + x, 1 - x)$ . By Proposition 1.3.4 (1) again, $\operatorname{span}(1, x) \subseteq \operatorname{span}(1 + x, 1 - x)$ .

Hence the spans are equal; both are $\mathbb{R}[x]_{\le 1}$ . Notice that we only checked four vectors, not all combinations. We also used $\tfrac12$ , so the argument needs $2 \neq 0$ in the field.

Quick check. Is $x^2 + 1 \in \operatorname{span}(x^2 + x, x + 1)$ in $\mathbb{R}[x]$ ?

Solution. No. Suppose $a(x^2 + x) + b(x + 1) = x^2 + 1$ . The left side is $ax^2 + (a + b)x + b$ . Comparing coefficients (Definition 0.8.1): $a = 1$ from $x^2$ , $b = 1$ from the constant term, and $a + b = 0$ from $x$ . But then $a + b = 2 \neq 0$ , a contradiction. So no such $a, b$ exist.

1.3.6. Exercises

A. Check your understanding

Exercise (A1)

(a) Define the span of a subset $S$ of a vector space $V$ . What is $\operatorname{span}(\varnothing)$ , and why?
(b) Determine whether the following statement is true: “for a subset $S \subseteq V$ , $\operatorname{span}(S) = S$ if and only if $S$ is a subspace of $V$ .” Justify your answer.
(c) Determine whether the following statement is true: “if $\operatorname{span}(S) = \operatorname{span}(T)$ , then $S = T$ .” Justify your answer.
(d) Is the zero vector in the span of every list? Is it in the span of the empty list?
(e) State what it means for $V$ to be finite-dimensional, and name the quantity used to show that $F[x]$ is not.

Solution.

(a) $\operatorname{span}(S)$ is the set of all linear combinations $a_1\mathbf{s}_1 + \dots + a_k\mathbf{s}_k$ with $k \ge 0$ , $\mathbf{s}_i \in S$ and $a_i \in F$ . $\operatorname{span}(\varnothing) = \{ \mathbf{0} \}$ : the only combination with no vectors is the empty sum $\mathbf{0}$ . This is also the smallest subspace containing $\varnothing$ , as Theorem 1.3.1 requires.
(b) True. If $\operatorname{span}(S) = S$ , then $S$ is a subspace by Theorem 1.3.1 (1). Conversely, if $S$ is a subspace, then $\operatorname{span}(S) \subseteq S$ by Theorem 1.3.1 (3) with $U = S$ , and $S \subseteq \operatorname{span}(S)$ by (2).
(c) False. In $\mathbb{R}^2$ , take $S = \{ (1, 0), (0, 1) \}$ and $T = \{ (1, 1), (1, -1) \}$ . Both span $\mathbb{R}^2$ (Example (Spanning Lists)), but $S \neq T$ .
(d) Yes to both: take all coefficients $0$ , or, for the empty list, the empty sum. See Example (Linear Combinations in Four Families) (d).
(e) $V$ is finite-dimensional if some finite list of vectors in $V$ spans $V$ . For $F[x]$ the quantity is the degree: combinations of a finite list have degree at most the largest degree in the list (Theorem 1.3.3).

B. Practice

Exercise (B1: Membership in a Span)

Determine whether each vector lies in the given span. If it does, write it as a linear combination. Justify your answer.

(a) $(2, -1, 5)$ and $(3, 4, 1)$ , in $\operatorname{span}((1, 1, 0), (0, 1, 1)) \subseteq \mathbb{R}^3$ .
(b) $2x^2 - 3x + 1$ and $x^2 + x + 1$ , in $\operatorname{span}(x^2 - x, x - 1) \subseteq \mathbb{R}[x]$ .

Solution.

(a) A combination is $a(1, 1, 0) + b(0, 1, 1) = (a, a + b, b)$ . For $(2, -1, 5)$ , the first and third entries force $a = 2$ and $b = 5$ ; then the middle entry would be $7 \neq -1$ . Hence $(2, -1, 5)$ is not in the span. For $(3, 4, 1)$ , we get $a = 3$ , $b = 1$ , and the middle entry is $4$ , as required. Hence $(3, 4, 1) = 3(1, 1, 0) + (0, 1, 1)$ is in the span.
(b) A combination is $a(x^2 - x) + b(x - 1) = ax^2 + (b - a)x - b$ . Compare coefficients (Definition 0.8.1). For $2x^2 - 3x + 1$ : $a = 2$ , $-b = 1$ so $b = -1$ , and then $b - a = -3$ , as required. Hence $2x^2 - 3x + 1 = 2(x^2 - x) - (x - 1)$ is in the span. For $x^2 + x + 1$ : $a = 1$ , $b = -1$ , and then $b - a = -2 \neq 1$ . Hence $x^2 + x + 1$ is not in the span. (Every element $p$ of this span has $p(1) = a - a + b - b = 0$ , and indeed $x^2 + x + 1$ has value $3$ at $1$ .)

Exercise (B2: Two Lists with the Same Span)

Prove that $\operatorname{span}((1, 1, 0), (0, 1, 1)) = \operatorname{span}((1, 2, 1), (1, 0, -1))$ in $\mathbb{R}^3$ .

Solution. Write $\mathbf{u} = (1, 1, 0)$ , $\mathbf{w} = (0, 1, 1)$ .

$(\subseteq)$ We have $\mathbf{u} = \tfrac12 (1, 2, 1) + \tfrac12 (1, 0, -1)$ and $\mathbf{w} = \tfrac12 (1, 2, 1) - \tfrac12 (1, 0, -1)$ : indeed $\tfrac12(2, 2, 0) = (1, 1, 0)$ and $\tfrac12 (0, 2, 2) = (0, 1, 1)$ . So $\mathbf{u}, \mathbf{w} \in \operatorname{span}((1, 2, 1), (1, 0, -1))$ , and Proposition 1.3.4 (1) gives the inclusion.

$(\supseteq)$ We have $(1, 2, 1) = \mathbf{u} + \mathbf{w}$ and $(1, 0, -1) = \mathbf{u} - \mathbf{w}$ . So both lie in $\operatorname{span}(\mathbf{u}, \mathbf{w})$ , and Proposition 1.3.4 (1) gives the reverse inclusion.

Hence the two spans are equal.

Exercise (B3: Spans in

\mathbb{R}^3

, Geometrically)

Describe each span as the origin, a line through the origin, a plane through the origin (give an equation), or all of $\mathbb{R}^3$ . Justify your answer.

(a) $\operatorname{span}((1, 2, 3))$ .
(b) $\operatorname{span}((1, 0, 0), (0, 1, 0), (1, 1, 0))$ .
(c) $\operatorname{span}((1, -1, 0), (0, 1, -1))$ .
(d) $\operatorname{span}((0, 0, 0))$ .

Solution.

(a) The span is $\{ (t, 2t, 3t) : t \in \mathbb{R} \}$ : the line through the origin and $(1, 2, 3)$ .
(b) Since $(1, 1, 0) = (1, 0, 0) + (0, 1, 0)$ , Theorem 1.3.5 gives $\operatorname{span}((1, 0, 0), (0, 1, 0), (1, 1, 0)) = \operatorname{span}((1, 0, 0), (0, 1, 0)) = \{ (a, b, 0) : a, b \in \mathbb{R} \}$ : the plane $z = 0$ .
(c) A combination is $a(1, -1, 0) + b(0, 1, -1) = (a, b - a, -b)$ , whose entries sum to $0$ . Conversely, if $x + y + z = 0$ , take $a = x$ and $b = -z$ ; then $b - a = -z - x = y$ , so $(x, y, z) = x(1, -1, 0) - z(0, 1, -1)$ . Hence the span is the plane $x + y + z = 0$ .
(d) $\operatorname{span}((0, 0, 0)) = \{ \mathbf{0} \}$ , by Example (Computing Spans) (b): the origin alone.

C. Going deeper

Exercise (C1: Spans of Intersections and Unions)

Let $S, T$ be subsets of a vector space $V$ .

(a) Prove that $\operatorname{span}(S \cap T) \subseteq \operatorname{span}(S) \cap \operatorname{span}(T)$ .
(b) Give an example in $\mathbb{R}^2$ where the inclusion in (a) is strict.
(c) Prove that $\operatorname{span}(S \cup T) = \{ \mathbf{s} + \mathbf{t} : \mathbf{s} \in \operatorname{span}(S),\ \mathbf{t} \in \operatorname{span}(T) \}$ .

Hint for (c): in a combination of vectors of $S \cup T$ , sort the terms into two groups.

Solution.

(a) Since $S \cap T \subseteq S$ , monotonicity (Proposition 1.3.4 (2)) gives $\operatorname{span}(S \cap T) \subseteq \operatorname{span}(S)$ . By symmetry, $\operatorname{span}(S \cap T) \subseteq \operatorname{span}(T)$ . Hence $\operatorname{span}(S \cap T) \subseteq \operatorname{span}(S) \cap \operatorname{span}(T)$ .
(b) Take $S = \{ (1, 0), (0, 1) \}$ and $T = \{ (1, 1) \}$ . Then $S \cap T = \varnothing$ , so $\operatorname{span}(S \cap T) = \{ \mathbf{0} \}$ . But $\operatorname{span}(S) = \mathbb{R}^2$ (Example (Spanning Lists)), so $\operatorname{span}(S) \cap \operatorname{span}(T) = \operatorname{span}(T)$ , the line $y = x$ , which contains $(1, 1) \neq \mathbf{0}$ . The inclusion is strict.
(c) Write $W = \{ \mathbf{s} + \mathbf{t} : \mathbf{s} \in \operatorname{span}(S),\ \mathbf{t} \in \operatorname{span}(T) \}$ .

$(\subseteq)$ Let $\mathbf{v} \in \operatorname{span}(S \cup T)$ , say $\mathbf{v} = a_1\mathbf{u}_1 + \dots + a_k\mathbf{u}_k$ with each $\mathbf{u}_i \in S \cup T$ . Let $\mathbf{s}$ be the sum of the terms $a_i\mathbf{u}_i$ with $\mathbf{u}_i \in S$ , and $\mathbf{t}$ the sum of the remaining terms, whose vectors lie in $T$ . Since addition is commutative and associative, $\mathbf{v} = \mathbf{s} + \mathbf{t}$ . Now $\mathbf{s} \in \operatorname{span}(S)$ and $\mathbf{t} \in \operatorname{span}(T)$ ; if a group is empty, its sum is $\mathbf{0}$ , which lies in every span. Hence $\mathbf{v} \in W$ .

$(\supseteq)$ Let $\mathbf{s} \in \operatorname{span}(S)$ and $\mathbf{t} \in \operatorname{span}(T)$ . By monotonicity, both lie in $\operatorname{span}(S \cup T)$ , which is closed under addition by Theorem 1.3.1 (1). Hence $\mathbf{s} + \mathbf{t} \in \operatorname{span}(S \cup T)$ .

By Theorem 0.3.1, $\operatorname{span}(S \cup T) = W$ . (So $W$ is the set $\operatorname{span}(S) + \operatorname{span}(T)$ of Exercise (C2: The Sum of Two Subspaces), the sum of the two subspaces, studied in section 7 of this chapter.)

Exercise (C2: The Span Depends on the Field)

The set $\mathbb{C}^2$ is a vector space over $\mathbb{C}$ . With the same addition, and scalar multiplication restricted to real scalars, it is also a vector space over $\mathbb{R}$ , by Exercise (C3: Shrinking the Field): every axiom holds for all complex scalars, so in particular for real ones.

(a) Show that $((1, 0), (0, 1))$ spans $\mathbb{C}^2$ over $\mathbb{C}$ .
(b) Explain why $((1, 0), (0, 1))$ does not span $\mathbb{C}^2$ over $\mathbb{R}$ .
(c) Find a finite list that spans $\mathbb{C}^2$ over $\mathbb{R}$ . Hence $\mathbb{C}^2$ is finite-dimensional over $\mathbb{R}$ as well.

Solution.

(a) For $(z, w) \in \mathbb{C}^2$ , $(z, w) = z(1, 0) + w(0, 1)$ with $z, w \in \mathbb{C}$ .
(b) Over $\mathbb{R}$ the coefficients must be real, and $a(1, 0) + b(0, 1) = (a, b)$ with $a, b \in \mathbb{R}$ has real entries. So $(i, 0)$ is not in $\operatorname{span}_\mathbb{R}((1, 0), (0, 1))$ .
(c) Take $((1, 0), (i, 0), (0, 1), (0, i))$ . Write $z = a + bi$ and $w = c + di$ with $a, b, c, d \in \mathbb{R}$ (Definition 0.6.1). Then $(z, w) = a(1, 0) + b(i, 0) + c(0, 1) + d(0, i),$ a combination with real coefficients. So this list spans $\mathbb{C}^2$ over $\mathbb{R}$ , and $\mathbb{C}^2$ is finite-dimensional over $\mathbb{R}$ by Definition 1.3.4.