Spanning and Linear Independence

References are to Anton–Rorres, 7th edition

Coordinates Let V be a given vector space. We wish to equip V with a coordinate system, much as we did geometrically for the plane and space. We have the origin 0. However, because V is only a vector space, the concepts of length and orthogonality do not apply.

Take any set S = {v_{1}, v_{2}, …, v_{r}} of vectors in V. There is an associated linear transformation L: R^{r} → V (well hidden in Anton–Rorres), given by

L(k_{1}, k_{2}, … k_{r}) = k_{1}v_{1} + k_{2}v_{2} + … k_{r}v_{r}  (1)

So L(e_{i}) = v_{i} for each i. It is easy to check that L is linear. The idea is to choose S to make L an isomorphism of vector spaces, which will allow us to transfer everything from the general vector space V to the familiar vector space R^{r}.

Definition 2 The set S = {v_{1}, v_{2}, …, v_{r}} of vectors in V is a basis [plural: bases] of V if the above linear transformation (1) satisfies the two conditions:

(i) The range R(L) of L is the whole of V; (ii) The kernel Ker(L) of L is {0}.

Then by Theorem 8.3.1, L is 1–1 and we can restate the definition explicitly.

Theorem 3 (=Thm. 5.4.1) If S = {v_{1}, v_{2}, …, v_{r}} is a basis of V, then any vector v ∈ V can be uniquely expressed as a linear combination

v = k_{1}v_{1} + k_{2}v_{2} + … k_{r}v_{r} = L(k_{1}, k_{2}, …, k_{r})  (4)

We then have the inverse linear transformation L^{−1}: V → R^{r} and L^{−1}(v_{i}) = e_{i}.

Definition 5 If S is a basis of V, we define the coordinate vector relative to S of any vector v ∈ V to be L^{−1}(v), and write it (v)_{S}. This is a vector in R^{r}.

Explicitly, if v is the linear combination (4), then (v)_{S} = (k_{1}, k_{2}, …, k_{r}).

Example We have the standard basis S = {e_{1}, e_{2}, …, e_{r}} of R^{r}. In this case, L is the identity linear transformation and (v)_{S} = v.

We break up Definition 2 and discuss the two conditions separately.

Spanning In any case, the range R(L) of L is always a subspace of V.

Definition 6 For any set S in V, we define the span of S to be the range R(L) of the linear transformation L in equation (1), and write span(S) = R(L).

Explicitly, span(S) is the set of all linear combinations (4). Many different sets of vectors S can span the same subspace. Clearly, we can omit the zero vector 0 if it is present in S. More generally, as a direct application of Theorem 5.2.4, we have the following reduction, known as the Minus Theorem.

Lemma 7 (=Thm. 5.4.4(b)) Suppose v_{i} ∈ S is a linear combination of the other vectors in S. Let S′ denote the set S with v_{i} removed. Then span(S′) = span(S).

Linear independence

Definition 8 The set S = {v_{1}, v_{2}, …, v_{r}} is linearly independent if the kernel Ker(L) of the linear transformation L in equation (1) is {0}, i. e. L is 1–1 (see Thm. 8.3.1). Otherwise, S is linearly dependent. [As linear independence is clearly the desirable condition, we shall eschew the term “linearly dependent”.]

Explicitly, S is linearly independent if there is no linear relation

k_{1}v_{1} + k_{2}v_{2} + … + k_{r}v_{r} = 0  (9)

between the v’s, other than the obvious trivial relation

0v_{1} + 0v_{2} + … + 0v_{r} = 0

The following property is clear enough, but note the direction of the implication.

Lemma 10 Let T: V → W be a linear transformation and S = {v_{1}, v_{2}, …, v_{r}} a set of vectors in V. If the image set T (S) = {T (v_{1}), T (v_{2}), …, T (v_{r})} is linearly independent in W, then S is linearly independent in V.

Proof Suppose the vectors in S satisfy the linear relation

k_{1}v_{1} + k_{2}v_{2} + … + k_{r}v_{r} = 0

We apply T to this to see that T (S) satisfies the corresponding linear relation

k_{1}T (v_{1}) + k_{2}T (v_{2}) + … + k_{r}T (v_{r}) = 0

We need to recast the definition of linear independence in a more useful form. Roughly stated, S is linearly independent if each vector in S is new in the sense that it cannot be expressed in terms of the previous members of S.

Lemma 11 (=Thm. 5.3.1(b), but sharper) The set S = {v_{1}, v_{2}, …, v_{r}} of vectors is linearly independent if and only if v_{1} ≠ 0 and no vector v_{i} ∈ S is a linear combination of the preceding vectors in S, i. e. for 2 ≤ i ≤ r, v_{i} ∉ span{v_{1}, v_{2}, …, v_{i−1}}.

Proof Assume there is a nontrivial linear relation (9), with k_{m} as the last nonzero coefficient. Then we can divide by k_{m} and rearrange equation (9) as

v_{m} = l_{1}v_{1} + l_{2}v_{2} + … + l_{m−1}v_{m−1}  (12)

where each l_{i} = −k_{i}/k_{m}. This expresses v_{m} as a linear combination of the preceding vectors. (If m = 1, equation (12) degenerates to v_{1} = 0.) Conversely, if equation (12) holds for some m, we can rearrange it as the linear relation

l_{1}v_{1} + l_{2}v_{2} + … + l_{m−1}v_{m−1} − v_{m} = 0

Corollary 13 (=Thm. 5.4.4(a), the Plus Theorem) Suppose the set S = {v_{1}, v_{2}, …, v_{r}} of vectors in V is linearly independent but does not span V. Take any vector v_{r+1} ∉ span(S). Then the enlarged set {v_{1}, v_{2}, …, v_{r}, v_{r+1}} remains linearly independent.

Proof The condition of Lemma 11 holds for v_{i} if i ≤ r because S is linearly independent. It holds for v_{r+1} by hypothesis.

Occasionally, a variant of Lemma 11 is useful.

Corollary 14 The set S = {v_{1}, v_{2}, …, v_{r}} of vectors in V is linearly independent if and only if v_{r} ≠ 0 and for 1 ≤ i < r, v_{i} is not a linear combination of the later vectors in S.

Proof We simply write the set S in reverse order and apply Lemma 11.

Vectors in R^{n} All the main results depend ultimately on the following fact, which is intuitively obvious but not trivial to prove. However, the real work has already been done. Roughly, the consequence is that in a given vector space, a spanning set of vectors cannot be too small, and a linearly independent set cannot be too large.

Lemma 15 (=Thm. 5.3.3) A linearly independent set S of vectors in R^{n} has at most n members.

Proof Suppose S has r members, and consider the linear transformation L: R^{r} → R^{n} in equation (1). We are given Ker(L) = {0}. Let A be the matrix of L, so that L(x) = Ax. We know Ax = 0 has no nontrivial solutions. Since A is an n×r matrix, Theorem 1.2.1 shows that we must have r ≤ n.

From this we deduce the result we really want.

Theorem 16 Suppose the vector space V is spanned by a set containing n vectors. Then any linearly independent set of vectors in V contains at most n members.

Proof From the given spanning set, we construct as in equation (1) a linear transformation L: R^{n} → V such that R(L) = V. Let S = {v_{1}, v_{2}, …, v_{r}} be any linearly independent set of vectors in V. Since R(L) = V, we can choose for each i a vector u_{i} ∈ R^{n} such that L(u_{i}) = v_{i}. Then by Lemma 10, the set {u_{1}, u_{2}, …, u_{r}} is linearly independent in R^{n}. Lemma 15 now shows that r ≤ n.

Corollary 17 (=Thm. 5.4.3) Any two bases of V contain the same number of vectors.

Definition 18 A vector space V is finite-dimensional if it has a basis that contains n vectors for some finite n. The number n is the dimension of V and is written dim(V). (By Corollary 17, it is well defined. For completeness, the zero vector space is considered to have dimension 0, and the empty set (not {0}) as a basis; this works.)

We say that V is infinite-dimensional if it does not have a finite basis.

We are primarily interested in finite-dimensional vector spaces.

Theorem 19 Every finite-dimensional vector space is isomorphic to the standard vector space R^{n} for a unique integer n.

We collect in one place all the information about subsets of V.

Theorem 20 (=Thms. 5.4.2 and 5.4.5) Let S = {v_{1}, v_{2}, …, v_{r}} be any set of r vectors in the n-dimensional vector space V. Then:

(a) If r < n, S does not span V. (It may or may not be linearly independent.)

(b) If r = n, S spans V if and only if it is linearly independent. Thus S is a basis of V if either of these conditions holds.

(c) If r > n, S is not linearly independent. (S may or may not span V.)

Proof Parts (a) and (c) both follow immediately from Theorem 16.

For (b), suppose first that S spans V. If S is not linearly independent, Lemma 11 shows that some v_{i} ∈ S is a linear combination of the other members. We remove v_{i} from S to get a set S′ of n−1 vectors. By Lemma 7, S′ still spans V; but this contradicts (a).

Conversely, suppose that S is linearly independent. If S does not span V, we could use Corollary 13 to add another vector to S to form a linearly independent set of n+1 vectors in V, which would contradict (c).

It is not immediately obvious that any subspace of a finite-dimensional vector space is finite-dimensional.

Theorem 21 (=Thm. 5.4.7) If W is a subspace of the finite-dimensional vector space V, then W is again finite-dimensional and dim(W) ≤ dim(V), with equality only if W = V.

Proof Choose a linearly independent set S = {v_{1}, v_{2}, …, v_{r}} of vectors in W with r as large as possible; such a set exists because these vectors also lie in V, so that by Theorem 20(c), r ≤ n where n = dim(V). Then span(S) = W, otherwise Corollary 13 (applied in W) would allow us to extend S by one more vector and increase r by 1. So S must be a basis of W and dim(W) = r.

If W ≠ V, choose any vector v_{r+1} ∈ V that is not in W; by Corollary 13, {v_{1}, v_{2}, …, v_{r}, v_{r+1}} is still linearly independent. By Theorem 20(c), r+1 ≤ n.

Constructing bases Obviously, if a subset S of V spans V, so does any subset S′ of V that contains S. Any subset of a linearly independent set S remains linearly independent. Beyond these restrictions, we can construct bases of V as follows.

Theorem 22 (=Thm. 5.4.6(a)) Suppose the set S = {v_{1}, v_{2}, …, v_{r}} spans the vector space V. Then we can thin out S to find a subset S′ ⊂ S that is a basis of V. In particular, V is finite-dimensional. (Explicitly, one possibility is to take S′ as the set of all the nonzero v_{i} ∈ S that are not linear combinations of the preceding members of S, but there are other choices.)

Proof If v_{i} ∈ S is a linear combination of the other members of S, we can delete v_{i} from S without affecting span(S), by Lemma 7. We repeat this, deleting elements of S one at a time, until we can go no further. By Lemma 11, the end result S′ is linearly independent and therefore a basis of V. (We leave the suggested candidate for S′ as an exercise.)

Theorem 23 (=Thm. 5.4.6(b)) Suppose given any linearly independent set S = {v_{1}, v_{2}, …, v_{r}} of vectors in a finite-dimensional vector space V that does not span V. Then we can extend S to a basis S′ = {v_{1}, v_{2}, …, v_{r}, …, v_{n}} of V.

Proof By Corollary 13, we extend S by one more vector to get a larger subset that is still linearly independent. We repeat as long as possible, until we find a linearly independent set S′ that does span V and is therefore a basis. The process must terminate, because by Theorem 20(c), the set S′ can never have more than n members, where n = dim(V). (In fact, it has exactly n, by Corollary 17.)