Kenneth Kuttler

7.2. SUBSPACES AND BASES 191

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 . (7.6)

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, (7.6) 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.

Proof 2: Let

xk =

s∑j=1

ajkyj

If r > s, then the matrix A = (ajk) has more columns than rows. By Corollary 4.3.9one of these columns is a linear combination of the others. This implies there exist scalarsc1, · · · , cr, not all zero such that

r∑k=1

ajkck = 0, j = 1, · · · , r

Thenr∑

k=1

ckxk =

r∑k=1

s∑j=1

ajkyj =

s∑j=1

(r∑

k=1

ckajk

)yj = 0

which contradicts the assumption that {x1, · · · ,xr} is linearly independent. Hence r ≤ s.

7.2. SUBSPACES AND BASES 191Define {z1,--- ,Z;—1} by{Z1,°°° ,Zs—1} = {Y1.0°° >Vk-1,Yk4+1,°°° Lys}Therefore, span {x1,Z1,-:- ,Zs-1} = V because if v € V, there exist constants c),--- ,Cssuch thats—lv= S- CiZi + CsYk-i=lNow replace the y, in the above with a linear combination of the vectors, {x1,Z1,-+--+ ,Zs—1}to obtain v € span {x1,Z1,+-- ,Zs—1}. The vector yx, in the list {y1,--- ,y;}, 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, {x1,--- ,x,} and since span {x1,--- ,X),Z1,:-: ,Zp} = V thereexist scalars c; and d; such thatU PX41 = S- Cixi + S- d5jZ;. (7.6)i=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, (7.6) can be solved for one of the z;, say z,, in terms of x,4, andthe other z; and just as in the above argument, replace that z; with xj;;, to obtainp-1 vectors hereSpan | X1,°°*X],X141,21,°°*Zk-1, Zk+1,°°* » Zp =V.Continue this way, eventually obtainingspan (X1,°-* ,Xs) = V.But then x, € span {x,,--- ,x,} contrary to the assumption that {x1,--- ,x,} is linearlyindependent. Therefore, r < s as claimed.Proof 2: Let :Xk = S- A;KY jj=lIf r > s, then the matrix A = (a;,) has more columns than rows. By Corollary 4.3.9one of these columns is a linear combination of the others. This implies there exist scalarsC1,°°: ,€,r, not all zero such thatrS AjrCk = 0, j=l,--: +7k=1ThenTr sTr s TrSo chxe = Sock So agKy; = S- (>: as] yj =9k=1 k=1k=1 j=l j=lwhich contradicts the assumption that {x,,--- ,x,} is linearly independent. Hence r < s.