62 CHAPTER 2. LINEAR TRANSFORMATIONS
contradicting the assumption that {x1, · · · ,xr} is linearly independent.Proof 2: Define span{y1, · · · ,ys} ≡ V, it follows there exist scalars c1, · · · , cs such
that
x1 =
s∑i=1
ciyi. (2.25)
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 +∑r
i=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 2.25 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, · · · , cssuch that
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 obtain v ∈ span {x1, z1, · · · , zs−1} . The vector yk, in the list {y1, · · · ,ys} , has now beenreplaced with the vector x1 and the resulting modified list of vectors has the same span asthe original list of vectors, {y1, · · · ,ys} .
Now suppose that r > s and that span {x1, · · · ,xl, z1, · · · , zp} = V where the vectors,z1, · · · , zp are each taken from the set, {y1, · · · ,ys} and l+ p = s. This has now been donefor l = 1 above. Then since r > s, it follows that l ≤ s < r and so l+1 ≤ r. Therefore, xl+1
is a vector not in the list, {x1, · · · ,xl} and since span {x1, · · · ,xl, z1, · · · , zp} = V, thereexist scalars ci and dj such that
xl+1 =l∑
i=1
cixi +
p∑j=1
djzj . (2.26)
Now not all the dj 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 combinationof the others. Therefore, 2.26 can be solved for one of the zi, say zk, in terms of xl+1 andthe 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 linearlyindependent. Therefore, r ≤ s as claimed.