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.

62 CHAPTER 2. LINEAR TRANSFORMATIONScontradicting the assumption that {x,,--- ,x,} is linearly independent.Proof 2: Define span{y,,---,ys} = V, it follows there exist scalars c,,--- ,c, suchthatxX, = S- Ciyi- (2.25)i=1Not all of these scalars can equal zero because if this were the case, it would follow thatx, = O and so {x,,--- ,x,} would not be linearly independent. Indeed, if x1 = 0, 1x; +ye. Ox; = X; = O and so there would exist a nontrivial linear combination of the vectors{x1,--- ,x,} which equals zero.Say cy 4 0. Then solve 2.25 for y, and obtains-1 vectors hereYe € span | X1,Y1,°°* ,Yk-1,Yk+15°°' 5 YsDefine {z1,--- ,Zs—1} by{Z1,°°* ,Zs—1} = {¥1s°++ -Yk—-1,Ye+15°** YsTherefore, span {x1,Z1,-:- ,Zs-1} = V because if v € V, there exist constants c),--- ,Cssuch thats—lv= S- CiZi + CsYk-i=1Now replace the y, in the above with a linear combination of the vectors, {x1,Z1,--- ,Zs—1}to obtain v € span {x1,Z1,-+- ,Z;—1}. The vector yx, in the list {y1,--- , ys}, has now beenreplaced with the vector x; 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,--- ,X1,Z1,--: ,Z)} = V where the vectors,Z1,°** Zp are each taken from the set, {y1,--- ,ys} and 1+p =. This has now been donefor 1 = 1 above. Then since r > s, it follows that 1 << s <randsol+1<vr. Therefore, xj+1is a vector not in the list, {x,,--- ,x,} and since span {x1,--- ,X7,Z1,°-- ,Zp} = V, thereexist scalars c; and d; such thatl PX41 = S> CyXy + S- djZ;. (2.26)j=l j=lNow not all the d; can equal zero because if this were so, it would follow that {x1,--- ,x,}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 z;, say z,, in terms of xj41 andthe other z; and just as in the above argument, replace that z; with xj41 to obtainp-l vectors herespan ¢ X1,°°*X1,X141,2Z1,°°* Zk—1,Zk+15°°* »Zp p = V.Continue this way, eventually obtainingspan {x1,--- , Xs} =V.But then x, € span {x;,--- ,x;} contrary to the assumption that {x,,--- ,x,} is linearlyindependent. Therefore, r < s as claimed.