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