9.1. SUBSPACES 163

Which contradicts the assertion that the set of vectors {u1, · · · ,ur} is linearly independent.Indeed, there is a nonzero vector x for which

(u1 · · · ur

)x= 0. Thus we cannot

have s < r and so the only other possibility is that s≥ r. ■

Definition 9.1.7 Let V be a subspace of Fn. Then {u1, · · · ,ur} is called a basis for V ifeach ui ∈V and span(u1, · · · ,ur) =V and {u1, · · · ,ur} is linearly independent. In words,{u1, · · · ,ur} spans and is independent.

Theorem 9.1.8 Let {u1, · · · ,ur} and {v1, · · · ,vs} be bases for V . Then s = r.

Proof: From Theorem 9.1.6, r ≤ s because each ui is in the span of {v1, · · · ,vs} and{u1, · · · ,ur} is independent. Then also r ≥ s by the same reasoning. ■

Definition 9.1.9 Let V be a subspace of Fn. Then the dimension of V is the number ofvectors in a basis. This is well defined by Theorem 9.1.8.

Observation 9.1.10 The dimension of Fn is n. This is obvious because if x ∈ Fn, where

x =(

x1 · · · xn

)T, then x= ∑

ni=1 xiei which shows that {e1, · · · ,en} is a spanning

set. However, these vectors are clearly independent because if ∑i xiei = 0, then

0 =(

x1 · · · xn

)T

and so each xi = 0. Thus {e1, · · · ,en} is also linearly independent.

The next lemma says that if you have a vector not in the span of a linearly independentset, then you can add it in and the resulting longer list of vectors will still be linearlyindependent.

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

Proof: Suppose ∑ki=1 ciui+dv= 0. It is required to verify that each ci = 0 and that 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

(ci

d

)ui

contrary to assumption. Therefore, d = 0. But then ∑ki=1 ciui = 0 and the linear indepen-

dence of {u1, · · · ,uk} implies each ci = 0 also. ■It turns out that every subspace equals the span of some vectors. This is the content of

the next theorem.

Theorem 9.1.12 V is a nonzero subspace of Fn if and only if it has a basis.

Proof: Pick a nonzero vector of V,u1. If V = span{u1} , then stop. You have foundyour basis. If V ̸= span(u1) , then there exists u2 a vector of V which is not a vector inspan(u1) . Consider span(u1,u2) . By Lemma 9.1.11, {u1,u2} is linearly independent.If V = span(u1,u2) , stop. You have found a basis. Otherwise, pick u3 /∈ span(u1,u2) .Continue this way until you obtain a basis. The process must stop after fewer than n+ 1iterations because if it didn’t, then there would be a linearly independent set of more thann vectors which is impossible because there is a spanning set of n vectors from the aboveobservation. ■

The following is a fundamental result.