64 CHAPTER 2. LINEAR TRANSFORMATIONS

Definition 2.6.8 A finite set of vectors, {x1, · · · ,xr} is a basis for a subspace V of Fn ifspan (x1, · · · ,xr) = V and {x1, · · · ,xr} is linearly independent.

Corollary 2.6.9 Let {x1, · · · ,xr} and {y1, · · · ,ys} be two bases for V . Then r = s.

Proof: From the exchange theorem, r ≤ s and s ≤ r. ■

Definition 2.6.10 Let V be a subspace of Fn. Then dim (V ) read as the dimension of Vis the number of vectors in a basis.

Of course you should wonder right now whether an arbitrary subspace even has a basis.In fact it does and this is in the next theorem. First, here is an interesting lemma.

Lemma 2.6.11 Suppose v /∈ span (u1, · · · ,uk) and {u1, · · · ,uk} is linearly independent.Then {u1, · · · ,uk,v} is also linearly independent.

Proof: Suppose∑k

i=1 ciui + dv = 0. It is required to verify that each ci = 0 andthat d = 0. But if d ̸= 0, then you can solve for v as a linear combination of the vectors,{u1, · · · ,uk},

v = −k∑

i=1

(cid

)ui

contrary to assumption. Therefore, d = 0. But then∑k

i=1 ciui = 0 and the linear indepen-dence of {u1, · · · ,uk} implies each ci = 0 also. ■

Theorem 2.6.12 Let V be a nonzero subspace of Fn. Then V has a basis.

Proof: Let v1 ∈ V where v1 ̸= 0. If span {v1} = V, stop. {v1} is a basis for V .Otherwise, there exists v2 ∈ V which is not in span {v1} . By Lemma 2.6.11 {v1,v2} is alinearly independent set of vectors. If span {v1,v2} = V stop, {v1,v2} is a basis for V. Ifspan {v1,v2} ≠ V, then there exists v3 /∈ span {v1,v2} and {v1,v2,v3} is a larger linearlyindependent set of vectors. Continuing this way, the process must stop before n + 1 stepsbecause if not, it would be possible to obtain n+1 linearly independent vectors contrary tothe exchange theorem. ■

In words the following corollary states that any linearly independent set of vectors canbe enlarged to form a basis.

Corollary 2.6.13 Let V be a subspace of Fn and let {v1, · · · ,vr} be a linearly independentset of vectors in V . Then either it is a basis for V or there exist vectors, vr+1, · · · ,vs suchthat {v1, · · · ,vr,vr+1, · · · ,vs} is a basis for V.

Proof: This follows immediately from the proof of Theorem 2.6.12. You do exactly thesame argument except you start with {v1, · · · ,vr} rather than {v1}. ■

It is also true that any spanning set of vectors can be restricted to obtain a basis.

Theorem 2.6.14 Let V be a subspace of Fn and suppose span (u1 · · · ,up) = V wherethe ui are nonzero vectors. Then there exist vectors {v1 · · · ,vr} such that {v1 · · · ,vr} ⊆{u1 · · · ,up} and {v1 · · · ,vr} is a basis for V .

Proof: Let r be the smallest positive integer with the property that for some set{v1 · · · ,vr} ⊆ {u1 · · · ,up} ,

span (v1 · · · ,vr) = V.

Then r ≤ p and it must be the case that {v1 · · · ,vr} is linearly independent because if itwere not so, one of the vectors, say vk would be a linear combination of the others. Butthen you could delete this vector from {v1 · · · ,vr} and the resulting list of r − 1 vectorswould still span V contrary to the definition of r. ■