6.3 Linear combinations and span

Given a list of vectors, which vectors can be obtained by adding scalar multiples of its members? Linear combinations describe individual outputs, and span collects all such outputs.

Linear combinations are the basic building blocks

Definition 6.3.1

(Linear combination)

Let $u_1, u_2, \ldots, u_n$ be vectors in a vector space $V$, and let $\alpha_1, \alpha_2, \ldots, \alpha_n \in R$. Then

$$\alpha_1 u_1 + \alpha_2 u_2 + \cdots + \alpha_n u_n$$

is called a linear combination of $u_1, u_2, \ldots, u_n$.

Throughout this section, $V$ is a real vector space and the generating list is finite, with $n\geq 1$. A coefficient belongs to $\mathbb R$, whereas a generator belongs to $V$: these are different kinds of objects. The generators remain fixed while the coefficients vary. For example, finding coefficients for one target does not require the same coefficients to work for every other target.

“Finite” means that every expression uses only finitely many additions and scalar multiplications. No infinite series or limiting operation is part of this definition. Repetitions and zero vectors are allowed in a generating list; whether they contribute anything new is a separate question.

The coefficients may be any real numbers: positive, negative, fractional, irrational, or zero.

Span collects all possible outputs

Definition 6.3.2

(Span)

Let $u_1, u_2, \ldots, u_n$ be vectors in a vector space $V$. The span of these vectors is the set of all linear combinations of them:

$$\operatorname{Span}\{u_1, u_2, \ldots, u_n\} = \{\alpha_1u_1 + \alpha_2u_2 + \cdots + \alpha_nu_n \mid \alpha_i \in R\}.$$

So the span is not one vector. It is the whole collection of vectors that can be built from the given list.

This is why span is often read as "the subspace generated by" or "the set spanned by" the given vectors.

Worked example 6.3.3

(Examples of linear combinations)

For a list $u_1,\ldots,u_n$ with $n\geq2$, the following are linear combinations:

$$23u_1 - \sqrt{2}\,u_2 + \pi u_n,$$$$0 = 0u_1 + 0u_2 + \cdots + 0u_n,$$

and

$$u_1 = 1u_1 + 0u_2 + \cdots + 0u_n.$$

There is also a closure fact: if $v$ and $w$ are themselves linear combinations of $u_1, \ldots, u_n$, then any expression $cv + dw$ is again a linear combination of $u_1, \ldots, u_n$.

So linear combinations are stable under the very operations that created them in the first place.

More generally, suppose $v_j=\sum\limits_{i=1}^n a_{ij}u_i$ for $j=1,\ldots,r$. Substituting these finite sums gives

$$\sum_{j=1}^r b_jv_j =\sum_{i=1}^n\left(\sum_{j=1}^r b_ja_{ij}\right)u_i.$$

Each bracket is a real coefficient. Thus repeatedly forming linear combinations cannot escape the collection of combinations of the original generators. The two indices distinguish the original generators from the intermediate vectors; the number of intermediate vectors need not equal the number of generators.

Membership in a span is a solvability question

In practice, the question "Is $b$ a linear combination of $u_1, \ldots, u_n$?" is not answered by inspection. It is answered by solving a linear system.

Theorem 6.3.4

(Linear combinations and linear systems)

Let $u_1, u_2, \ldots, u_n$ and $b$ be vectors in $R^m$, and let

$$A = \begin{bmatrix} u_1 & u_2 & \cdots & u_n \end{bmatrix}.$$

Then $b$ can be expressed as a linear combination of $u_1, \ldots, u_n$ if and only if the linear system

$$Ax = b$$

has a solution.

A generation question is therefore equivalent to a consistency question for a matrix equation.

Worked example 6.3.5

(Testing whether a vector is a linear combination)

Let

$$u_1 = \begin{bmatrix} 1 \\ -2 \\ -1 \end{bmatrix}, \qquad u_2 = \begin{bmatrix} 3 \\ -5 \\ 4 \end{bmatrix}.$$

Consider the vector

$$w = \begin{bmatrix} 2 \\ -6 \\ -16 \end{bmatrix}.$$

To ask whether $w$ is a linear combination of $u_1$ and $u_2$ is to ask whether there exist scalars $c_1, c_2$ such that

$$c_1u_1 + c_2u_2 = w.$$

Equivalently,

$$\begin{bmatrix} 1 & 3 \\ -2 & -5 \\ -1 & 4 \end{bmatrix} \begin{bmatrix} c_1 \\ c_2 \end{bmatrix} = \begin{bmatrix} 2 \\ -6 \\ -16 \end{bmatrix}.$$

Apply $R_2\leftarrow R_2+2R_1$ and $R_3\leftarrow R_3+R_1$, then $R_3\leftarrow R_3-7R_2$:

$$\left[\begin{array}{cc|c}1&3&2\\-2&-5&-6\\-1&4&-16\end{array}\right] \longrightarrow \left[\begin{array}{cc|c}1&3&2\\0&1&-2\\0&7&-14\end{array}\right] \longrightarrow \left[\begin{array}{cc|c}1&3&2\\0&1&-2\\0&0&0\end{array}\right].$$

The last row imposes no extra restriction. Back substitution gives

$$c_1 = 8, \qquad c_2 = -2.$$

Hence

$$w = 8u_1 - 2u_2.$$

So $w$ belongs to the span of $u_1$ and $u_2$.

For comparison, replace only the target by $v=(2,-6,3)^T$. The same operations now give the last augmented row $[\,0\ \ 0\mid19\,]$, which asserts $0=19$. The first two equations still force $(c_1,c_2)=(8,-2)$, but that candidate fails the third equation. Matching some coordinates is insufficient: one coefficient vector must satisfy every coordinate equation simultaneously.

The same method can also prove non-membership: if the system is inconsistent, then the target vector is not in the span.

A systematic membership algorithm

The theorem above gives a practical routine. Given vectors $u_1,\ldots,u_q$ and a target vector $v$, do the following.

1. Form the matrix

$$U = \begin{bmatrix} u_1 & u_2 & \cdots & u_q \end{bmatrix}.$$

2. Row-reduce the augmented matrix $[U|v]$.

3. If the reduced system has a contradiction, then $v$ is not in $\operatorname{Span}\{u_1,\ldots,u_q\}$.

4. If the system is consistent, read off one solution $c=(c_1,\ldots,c_q)^T$ and write

$$v = c_1u_1 + c_2u_2 + \cdots + c_qu_q.$$

The matrix-vector product

$$Uc$$

is exactly

$$c_1u_1+c_2u_2+\cdots+c_qu_q.$$

Therefore $Uc=v$ is solvable exactly when $v$ is a linear combination of the columns of $U$. Row reduction decides whether such a coefficient vector $c$ exists.

Here $U$ has size $m\times q$, $c\in\mathbb R^q$, and $v\in\mathbb R^m$. A column of $U$ represents one available generator, while a row represents one coordinate equation. Consequently, a free variable is a choice of coefficient, not a new coordinate of the target. Consistency must be checked before assigning values to free variables. If the system is consistent, setting all free variables to zero gives one representation; retaining parameters describes all representations.

Worked example 6.3.6

(Using inconsistency to prove non-membership)

Let

$$u_1=\begin{bmatrix}1\\2\\1\end{bmatrix}, \qquad u_2=\begin{bmatrix}3\\6\\3\end{bmatrix}, \qquad v=\begin{bmatrix}1\\0\\1\end{bmatrix}.$$

The augmented matrix for $Uc=v$ is

$$\left[ \begin{array}{cc|c} 1 & 3 & 1\\ 2 & 6 & 0\\ 1 & 3 & 1 \end{array} \right].$$

Since the second row is twice the first on the coefficient side but not on the augmented side, row reduction produces a contradiction. Hence $Uc=v$ is inconsistent, and

$$v\notin \operatorname{Span}\{u_1,u_2\}.$$

The operation $R_2\leftarrow R_2-2R_1$ gives $[\,0\ \ 0\mid-2\,]$, so the second equation becomes $0=-2$.

One generator or two: geometric cases

The following sequence compares the sets generated by one nonzero vector and by two independent vectors. Membership means that at least one choice of coefficients reaches the target. A zero generator gives only $\{0\}$, because every scalar multiple of zero is zero.

Standard geometric examples

Worked example 6.3.7

(What span looks like in $R^3$)

Let

$$e_1 = \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}, \qquad e_2 = \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix}, \qquad e_3 = \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix}.$$

Then every vector in $\operatorname{Span}\{e_1, e_2\}$ has the form

$$\alpha e_1 + \beta e_2 = \begin{bmatrix} \alpha \\ \beta \\ 0 \end{bmatrix}.$$

So

$$\operatorname{Span}\{e_1, e_2\}$$

is exactly the $x_1x_2$-plane in $R^3$.

If we include $e_3$ as well, then every vector in $R^3$ can be written as

$$\alpha_1 e_1 + \alpha_2 e_2 + \alpha_3 e_3,$$

so

$$\operatorname{Span}\{e_1, e_2, e_3\} = R^3.$$

Why the span is always a subspace

The span of a set of vectors is not just some arbitrary subset. It is the smallest natural vector-space object generated by those vectors.

Theorem 6.3.8

(The span of any set of vectors is a subspace)

If $u_1, \ldots, u_n$ are vectors in a vector space $V$, then

$$\operatorname{Span}\{u_1, \ldots, u_n\}$$

is a subspace of $V$.

Moreover, this span is the smallest subspace of $V$ containing every generator: if $W\subseteq V$ is a subspace and $u_i\in W$ for every $i$, then $\operatorname{Span}\{u_1,\ldots,u_n\}\subseteq W$.

Proof

(Why the span is a subspace)

The span is nonempty because it contains the zero vector:

$$0 = 0u_1 + \cdots + 0u_n.$$

Now take two vectors $v$ and $w$ in the span. Then there exist scalars $\alpha_i$ and $\beta_i$ such that

$$v = \alpha_1u_1 + \cdots + \alpha_nu_n, \qquad w = \beta_1u_1 + \cdots + \beta_nu_n.$$

Then

$$v + w = (\alpha_1 + \beta_1)u_1 + \cdots + (\alpha_n + \beta_n)u_n,$$

which is again a linear combination of the same vectors. So the span is closed under addition.

If $c \in R$, then

$$cv = (c\alpha_1)u_1 + \cdots + (c\alpha_n)u_n,$$

which is also a linear combination of the same vectors. So the span is closed under scalar multiplication.

Therefore the span is a subspace of $V$.

For the minimality assertion, each $u_i$ belongs to the span by choosing its coefficient to be one and all others zero. Now let $W$ be any subspace containing the generators. Scalar closure puts every $\alpha_i u_i$ in $W$, and repeated addition puts their finite sum in $W$. Every vector in the span therefore lies in $W$, proving the required inclusion. This argument uses finiteness: no closure under infinite sums has been assumed.

“Smallest” refers to inclusion of sets, not to the number of vectors written in the generating list. Any subspace containing the generators must contain all the outputs that their linear combinations force. For example, the $x_1x_2$-plane is the smallest subspace containing $e_1,e_2$, even though the larger space $\mathbb R^3$ also contains them. This is also a useful proof method: to show that a span lies in a known subspace, check its generators rather than an unspecified vector with many coefficients.

Different coefficients can represent the same vector

Worked example 6.3.9

(A redundant generator and a free coefficient)

Consider a new list and target:

$$u_1=\begin{bmatrix}1\\2\\1\end{bmatrix},\quad u_2=\begin{bmatrix}-4\\-1\\2\end{bmatrix},\quad u_3=\begin{bmatrix}-3\\1\\3\end{bmatrix},\quad v=\begin{bmatrix}-7\\7\\11\end{bmatrix}.$$

For $U=[\,u_1\ u_2\ u_3\,]$, first use $R_2\leftarrow R_2-2R_1$ and $R_3\leftarrow R_3-R_1$. Then divide the second row by seven, subtract six times that row from the third, and add four times it to the first:

$$\left[\begin{array}{ccc|c}1&-4&-3&-7\\2&-1&1&7\\1&2&3&11\end{array}\right] \longrightarrow \left[\begin{array}{ccc|c}1&-4&-3&-7\\0&7&7&21\\0&6&6&18\end{array}\right] \longrightarrow \left[\begin{array}{ccc|c}1&0&1&5\\0&1&1&3\\0&0&0&0\end{array}\right].$$

The system is consistent. Its equations are $c_1+c_3=5$ and $c_2+c_3=3$, so all coefficient vectors are described by

$$c_1=5-t,\qquad c_2=3-t,\qquad c_3=t,\qquad t\in\mathbb R.$$

In particular, $t=0$ and $t=2$ give

$$v=5u_1+3u_2=3u_1+u_2+2u_3.$$

Both expressions evaluate to $(-7,7,11)^T$. We have not found two target vectors: we have found two ways to obtain the one prescribed target. Every real value of $t$ works, because it satisfies the complete reduced system.

Concept lensAlgebraic

Coefficient vectors and output vectors

The expression $Uc$ has an input $c\in\mathbb R^q$ and an output in $\mathbb R^m$. Span asks which outputs occur at least once. It does not ask whether each output has a unique input. In the example, $u_3=u_1+u_2$, so increasing $c_3$ by $t$ while decreasing $c_1,c_2$ by $t$ leaves the output unchanged.

More precisely, if $Uc_0=v$, then another coefficient vector $c$ gives the same target exactly when $U(c-c_0)=0$. Conversely, every $d$ satisfying $Ud=0$ produces another representation $U(c_0+d)=v$. This follows by distributivity and explains the free parameter without confusing the fixed target with its variable representations. Here $d=(-t,-t,t)^T$ records a cancellation among the generators.

The extra generator is redundant for every target, not just the one calculated above. Indeed,

$$a_1u_1+a_2u_2+a_3u_3=(a_1+a_3)u_1+(a_2+a_3)u_2.$$

Thus every combination of the three generators is a combination of the first two. Conversely, a combination of the first two is a combination of all three with third coefficient zero. Removing $u_3$ preserves the span. This is a local application of the generator-comparison method in 4.2 Set language and solution sets.

Appending a generator already in the span therefore changes the available representations without enlarging the set of outputs. If the appended vector lies outside the old span, the span strictly enlarges: the old combinations remain available by assigning the new coefficient zero, and the new vector itself is an additional output. Neither conclusion follows merely from counting the listed vectors.

Predict what the coefficients can reach

Before changing the controls, predict whether two generators will sweep out a line or a plane. Then vary one coefficient at a time. If the generators are dependent, identify two coefficient pairs that reach the same target; if they are independent, explain why that cannot happen.

Common mistakes

Common mistake

(Span is not the set of positive multiples only)

The coefficients in a linear combination may be any real numbers. Negative and zero coefficients are just as legitimate as positive ones.

Common mistake

(To prove membership in a span, prove that suitable coefficients exist)

It is not enough to say that a target vector "looks similar." You must prove that suitable coefficients exist, either by producing them explicitly or by showing that the associated linear system is consistent.

Quick checks

Quick check

(Is the zero vector always in the span of any finite list of vectors?)

Use the definition of linear combination directly.

Solution · Answer

Yes. Set every coefficient equal to $0$. The resulting linear combination is the zero vector, so the span always contains $0$.

Quick check

(Why does $\operatorname{Span}\{e_1, e_2\}$ in $R^3$ contain $(2, -1, 0)$?)

Write the vector as a combination of $e_1$ and $e_2$.

Solution · Answer

Because

$$\begin{bmatrix} 2 \\ -1 \\ 0 \end{bmatrix} = 2e_1 - e_2.$$

So the vector is a linear combination of $e_1$ and $e_2$.

Exercises

Quick check

(Explain why every vector $u_i$ in a generating list automatically lies in $\operatorname{Span}\{u_1, \ldots, u_n\}$.)

Use coefficients.

Solution · Guided solution

To isolate $u_i$, choose coefficient $1$ for $u_i$ and coefficient $0$ for every other vector. Then

$$u_i = 0u_1 + \cdots + 0u_{i-1} + 1u_i + 0u_{i+1} + \cdots + 0u_n,$$

so $u_i$ is a linear combination of the full list and therefore belongs to its span.

Quick check

(Why does the theorem $b \in \operatorname{Span}\{u_1, \ldots, u_n\}$ if and only if $Ax = b$ is solvable matter so much in practice?)

Answer in terms of what it lets you do computationally.

Solution · Guided solution

It turns a generation question into a linear-system question. Instead of guessing coefficients by inspection, you form the matrix with columns $u_1, \ldots, u_n$ and row-reduce the augmented system $Ax = b$. Consistency then tells you exactly whether $b$ lies in the span.

Quick check

(In the redundant-generator example, find a representation of the target using only the second and third generators.)

Choose the parameter so that the first coefficient vanishes.

Solution · Guided solution

Since $c_1=5-t$, choose $t=5$. Then $(c_1,c_2,c_3)=(0,-2,5)$ and $v=-2u_2+5u_3=(-7,7,11)^T$. The first generator may be omitted for this target; the preceding identity $u_1=u_3-u_2$ also shows that this pair generates the entire same span.

Quick check

(A subspace contains two vectors. Must it contain every linear combination of them? Must it equal their span?)

Distinguish containment from equality.

Solution · Guided solution

It must contain their span by scalar and additive closure. Equality need not hold: $\mathbb R^3$ contains $e_1,e_2$ and all their combinations, but also contains $e_3$, which is outside their span because its third coordinate is one. Equality needs the additional inclusion of the subspace in the span.

Related notes

Read 6.2 Subspaces for the subspace tests used here, and then continue to 6.4 Linear dependence and independence, where span is paired with the question of redundancy in a generating list.