5.1. SUBSPACES SPANS AND BASES 63

where the vectors, z1, · · · ,zp are each taken from the set, {y1, · · · ,ys} and l + p = s. Thishas now been done for l = 1 above. Then since r > s, it follows that l ≤ s < r and sol +1≤ r. Therefore, xl+1 is a vector not in the list, {x1, · · · ,xl} and since

span{

x1, · · · ,xl ,z1, · · · ,zp}=V,

there exist scalars, ci and d j such that

xl+1 =l

∑i=1

cixi +p

∑j=1

d jz j. (5.1.2)

Now not all the d j can equal zero because if this were so, it would follow that {x1, · · · ,xr}would be a linearly dependent set because one of the vectors would equal a linear combi-nation of the others. Therefore, (5.1.2) can be solved for one of the zi, say zk, in terms ofxl+1 and the other zi and just as in the above argument, replace that zi with xl+1 to obtain

span

x1, · · ·xl ,xl+1,

p-1 vectors here︷ ︸︸ ︷z1, · · ·zk−1,zk+1, · · · ,zp

=V.

Continue this way, eventually obtaining

span(x1, · · · ,xs) =V.

But then xr ∈ span(x1, · · · ,xs) contrary to the assumption that {x1, · · · ,xr} is linearly in-dependent. Therefore, r ≤ s as claimed.

Definition 5.1.4 A finite set of vectors, {x1, · · · ,xr} is a basis for Fn if

span(x1, · · · ,xr) = Fn

and {x1, · · · ,xr} is linearly independent.

Corollary 5.1.5 Let {x1, · · · ,xr} and {y1, · · · ,ys} be two bases1 of Fn. Then r = s = n.

Proof: From the exchange theorem, r ≤ s and s≤ r. Now note the vectors,

ei =

1 is in the ith slot︷ ︸︸ ︷(0, · · · ,0,1,0 · · · ,0)

for i = 1,2, · · · ,n are a basis for Fn. This proves the corollary.

Lemma 5.1.6 Let {v1, · · · ,vr} be a set of vectors. Then V ≡ span(v1, · · · ,vr) is a sub-space.

1This is the plural form of basis. We could say basiss but it would involve an inordinate amount of hissing asin “The sixth shiek’s sixth sheep is sick”. This is the reason that bases is used instead of basiss.