62 CHAPTER 5. SOME IMPORTANT LINEAR ALGEBRA

Say ck ̸= 0. Then you can solve for xk as

xk = ∑j ̸=k

(−c j)/ckx j

contrary to assumption. This proves the lemma.The following is called the exchange theorem.

Theorem 5.1.3 (Exchange Theorem) Let {x1, · · · ,xr} be a linearly independent set of vec-tors such that each xi is in span(y1, · · · ,ys) . Then r ≤ s.

Proof: Define span{y1, · · · ,ys} ≡V, it follows there exist scalars, c1, · · · ,cs such that

x1 =s

∑i=1

ciyi. (5.1.1)

Not all of these scalars can equal zero because if this were the case, it would follow thatx1 = 0 and so {x1, · · · ,xr} would not be linearly independent. Indeed, if x1 = 0, 1x1 +

∑ri=2 0xi = x1 = 0 and so there would exist a nontrivial linear combination of the vectors{x1, · · · ,xr} which equals zero.

Say ck ̸= 0. Then solve (5.1.1) for yk and obtain

yk ∈ span

x1,

s-1 vectors here︷ ︸︸ ︷y1, · · · ,yk−1,yk+1, · · · ,ys

 .

Define {z1, · · · ,zs−1} by

{z1, · · · ,zs−1} ≡ {y1, · · · ,yk−1,yk+1, · · · ,ys}

Therefore, span{x1,z1, · · · ,zs−1}=V because if v∈V, there exist constants c1, · · · ,cs suchthat

v =s−1

∑i=1

cizi + csyk.

Now replace the yk in the above with a linear combination of the vectors,

{x1,z1, · · · ,zs−1}

to obtainv ∈ span{x1,z1, · · · ,zs−1} .

The vector yk, in the list {y1, · · · ,ys} , has now been replaced with the vector x1 and the re-sulting modified list of vectors has the same span as the original list of vectors, {y1, · · · ,ys} .

Now suppose that r > s and that

span(x1, · · · ,xl ,z1, · · · ,zp) =V