Linear Algebra: Linear Systems and Matrices - …

1 LinearAlgebra:LinearSystemsandMatrices-Q uadraticFormsandDe niteness-EigenvaluesandMarkovChainsJoshu aWilde,revisedbyIsab elTecu,TakeshiSuzukiandMar aJos Bo ccardiAugust13, +a12x2+ +a1nxnb2=a21x1+a22x2+ + +am2x2+ +amnxnLinearequationsareimp ortantsincenon- Linear ,di erentiablefunctionscanb eapproximatedbylinearones(aswehaveseen). Forexample,theb ehaviorofadi erentiablefunctionf:R2 Raroundap ointx canb eapproximatedbythetangentplaneatx . , ethoughtofasapproximationsformorecomplic atedunderlyingrelationshipsb ewritteninmatrixform: m 1= amn m n n 1,Inshort,wecanwritethissystemasb=Axwher eAisanm nmatrix,bisanm 1vectorandxisann ,alsoreferredtoaslinearmap,canthereforeb eidenti edwithamatrix,andanymatrixcanb eidenti edwith("turnedinto") ,westudymatricesandtheirprop erationsandProp ertiesConsidertwon mmatrices:A= anm , B= bnm 12 LinearAlgebraThenthebasicmatrixop +B= a11+ a1m+ + anm+bnm 2.

2 A= anm ,where RNoticethattheelementsinthematrixarenumb eredaij, ,thenumb erofcolumnsintheCmatrixmustb eequaltothenumb mmatrix,andDisanm nedasfollows:E=C n mD m k= mq=1c1,qdq, mq=1c1,qdq, mq=1cn,qdq, mq=1cn,qdq,k n kTherearetwonotablesp rstiscalledtheinnerpro ductordotpro duct,whicho ccurswhentwovectorsofthesamelengtharemul tipliedtogethersuchthattheresultisascala r:v z=v 1 nz n 1=( vn) =n i=1viziThesecondiscalledtheouterpro duct:v n 1z 1 n= ( vn)= znvn n ,theresultingei,jthelementofEwasjustthei nnerpro ,notethateveniftwomatricesXandYareb othn n,thenXY6=Y X,exceptinsp nedthewayitis:Considertwolinearmaps(that is,twosystemsoflinearequations)f(x) =Axandg(x) =BxwhereAism nandBisn neanewlinearmaphthatisthecomp ositionoffafterg:h(x) =f(g(x)).Thenthematrixthatrepresentsthel inearsystemhturnsouttob eexactlyAB,thatish(x) =f(g(x)) = nedtocorresp ondtothecomp ealinearmap-pingifforanyvectorsx1.

3 ,xm Xandanyscalarsc1,..,cm,f(c1x1+ +cmxm) =c1f(x1) + +cmf(xm). n kThefollowingprop +0= ,itisnotnecessarilythecasethatA=0orB= erofcolumnsmustequalthenumb n nThereasonitiscalledtheidentitymatrixisb ecauseAI=IA= ,Symmetric,andTransp oseMatricesAsquarematrixisamatrixwhosenu mb erofrowsisthesameasitsnumb , ertythatai,j=aj,iforallitselements, oseofamatrixA,denotedA isamatrixsuchthatforeachelementofA ,a i,j=aj, ,thetransp oseofthematrix 1 2 34 5 67 8 9 is 1 4 72 5 83 6 9 .NotethatamatrixAissymmetricifA=A .Thefollowingprop ertiesofthetransp osehold:1.(A ) = (A+B) =A +B .3.( A) = A .4 LinearAlgebra4.(AB) =B A . k,thenA isk esexceptalongthediagonal: ann ertriangularifallofitsentriesb elowthediagonalarezero ann ,andislowertriangularifallitsentriesab ovethediagonalarezero ann.

4 ,thenwecallBtheinverseofA,anddenoteitA , ertiesofinverseshold:1.(A 1) 1=A2.( A) 1=1 A 13.(AB) 1=B 1A 1ifB 1,A (A ) 1=(A 1) otentMatricesAmatrixAisorthogonalifA A=I(whichalsoimpliesAA =I).Inotherwords, otentifitisb othsymmetricandAA= otentmatricesareesp neanumb ede 1matrix(a)isa,andisdenoteddet(a). 2matrix(a bc d)isad det(d) b det(c).The rsttermisthe(1,1) (1,2) ,withthe rsttermb eingaddedandthesecondtermb 3matrix a b cd e fg h i isaei+bfg+cdh ceg bdi ewrittenasa det(e fh i) b det(d fg i)+c det(d eg h).Canyouseethepattern?Inordertoobtainth edeterminant,wemultiplyeachelementinthet oprowwiththedeterminantofthematrixleftwh enwedeletetherowandcolumninwhichtheresp ,startingwithp nitionofthedeterminantofannthordermatrix ,itisusefultode nethe(i,j)thminorofAandthe(i,j)thcofacto rofA: LetAb eann ,jb ethe(n 1) (n 1) (Aij)iscalledthe(i,j)thminorofA.

5 ThescalarCij= ( 1)i+jMijiscalledthe(i,j) nitions,wenoticethatthedeterminantforthe 2 2matrixisdet(A) =aM11 bM12=aC11+bC12,andthedeterminantforthe3 3matrixisdet(A) =aM11 bM12 cM13=aC11+bC12+ ,wecande nethedeterminantforann nsqaurematrixasfollows:det A n n =a11C11+a12C12+ + ,acofactorexpansionalonganyroworcolumnwi llb ofofthisasssertionisleftasahomeworkprobl emforthe3 :Findthedeterminantoftheupp erdiagonalmatrix 1 0 02 3 04 5 6 Thedeterminantis:aC11+bC12+C13=a det(e fh i) b det(d fg i)+c det(d eg h)== 1 det(3 05 6) 0 det(2 04 6)+ 0 det(2 34 5)= 1 3 6 = 18 Nowletsexpandalongthesecondcolumninstead ofthethirdrow:aC12+bC22+C32= b det(d fg i)+e det(a cg i) h det(a cd f)== 0 det(2 04 6)+ 3 det(1 04 6) 5 det(1 02 0)= 3 6 = 18 Imp ortantprop ertiesofthedeterminant: det(I) = 1whereIistheidentitymatrix det(AB) = det(A) det(B) IfAisinvertible,det(A 1) =1det(A) det(A ) = det(A) Aisorthogonalifandonlyif|detA|=1De nitionThefollowingde nitionwillb eimp ortantsubsequently:Ann nmatrixAiscalledsingularifdetA= :b1=a11x1+a12x2+ +a1nxnb2=a21x1+a22x2+ + +am2x2+ +amnxnwhichcanb ewritteninmatrixformby m 1= amn m n n 1,orb= :MathCamp7 Givenalefthandsidevectorb,howcanwe ndasolutionxtob=Ax?

6 Givenaco e cientmatrixA,whatcanwesayab outthenumb erofsolutionstob=Ax,foranyb?Howcanwetell whetherasystemhasoneuniquesolution?Let's startwiththe erationsTherearethreetyp esofelementaryrowop erationswecanp erformonthematrixAandthevectorbwithoutch angingthesolutionsettob= erationstoSolveaSystemofEquationsArowofa matrixissaidtohavekleadingzerosifthe(k+ 1)thelementoftherowisnonzerowhilethe ,thematricesA= 4 20 70 00 0 , B= 1 0100 8 30 06 areinrowechelonformwhilethematricesA= 1 2 30 4 50 6 70 0 8 , B=(0 12 4) ,Bwouldb einrowechelonformifwep erformedtheelementarymatrixop ,wecanp erformelementarymatrixop ,considerthematrixA= 1 2 34 8 61 1 1 .Bytakingthethirdrowandsubtractingitfrom the rstrow,weobtainthematrixA1= 0 1 24 8 61 1 1 8 LinearAlgebraWecanalsosubtractfourtimest hethirdrowfromthesecondrowA2= 0 1 20 4 21 1 1 Nowsubtractfourtimesthe rstrowfromthesecondrowtoobtainA3= 0 120 0 61 11 Thenrearrangetogetthematrixinrowechelonf ormA4= 1 110 120 0 6 Wecansolveasystemofequationsbywritingthe matrix c1| c2| |.

7 Cm|bm ,calledtheaugmentedmatrixofA,anduseeleme ntaryrowop :LetA= 1 2 34 8 61 1 1 asb (1,1,1) .Thentheaugmentedmatrixis 1 2 3|14 8 6|11 1 1|1 Performingthesamematrixop erationsasb efore,wehave 1 2 3|14 8 6|11 1 1|1 0 1 2|04 8 6|11 1 1|1 0 1 2|00 4 2| 31 1 1|1 0 12|00 0 6| 31 11|1 1 11|10 12|00 0 6| 3 Wecontinuetherowop erationsuntilthelefthandsideoftheaugment edmatrixlo oksliketheidentitymatrix: 1 1 1|10 1 2|00 0 1|12 1 1 1|10 1 0| 10 0 1|12 1 1 0|120 1 0| 10 0 1|12 1 0 0|320 1 0| 10 0 1|12 MathCamp9 Noticethatthisimplies 32 112 = 1 0 00 1 00 0 1 x1x2x3 x=(32, 1,12),sowehavefoundasolutionusingelement aryrowop ,ifweformtheaugmentedmatrixofA,reducethe lefthandsideofthematrixtoitsreducedrowec helonform(sothateachrowcontainsallzeros, exceptforthep ossibilityofaoneinacolumnofallzeros)thro ughelementaryrowop erations,thentheremainingvectorontherigh thandsidewillb 'sRuletoSolveaSystemofEquationsCramer'sR uleisatheoremthatyieldsthesolutionstosys temsoftheformb=AxwhereAisasquarematrixan dnon-singular, 0:LetAb (x1.)

8 ,xn)ofthen nsystemb=Axis:xi=det(Bi)det(A)fori= 1,..,n, :ConsiderthelinearIS-LMmo delsY+ar=I0+GmY hr=Ms M0whereYisthenetnationalpro duct,ristheinterestrate,sisthemarginalpr op ensitytosave,aisthemarginale ciencyofcapital,I=I0 arisinvestment,mismoneybalancesneededp erdollaroftransactions,Gisgovernmentsp ending, (I0+GMs M0)=(s am h) (Yr).ByCramer'srule,wehaveY= I0+G aMs M0 h s am h =(I0+G)h+a(Ms M0)sh+amr= s I0+Gm Ms M0 s am h =(I0+G)m s(Ms M0)sh+amDep endingonthesizeofA,solvingasystemusingCr amer'sRulemayb efasterthansolvingitusingelementaryrowop eawarethatCramer' outlinearsystemconcernstheexistenceofsol utions:Howcanwetellwhetherasystemhaszero ,oneormoresolutions?Inordertotacklethisp roblem,westartbyde ningtheconceptof"linearindep endence". endenceThevectorsv1,..,vmarelinearlydep endentifthereexistscalarsq1.

9 ,qm,notallzero,suchthat:m i=1qivi= ,..,vmarelinearlyindep endentiftheonlyscalarsq1,..,qmsuchthat:m i=1qivi= 0areq1= =qm= :Thevectors 100 , 010 , 320 arelinearlydep endentsince3 100 + 2 010 + ( 1) 320 = 0 Example2:Thevectors 100 , 010 , 302 arelinearlyindep endentsincetheonlyscalarsq1,q2,q3suchtha tq1 100 +q2 010 +q3 320 = 0areq1=q2=q3= nitionoflinearindep endenceanddep ,rk(A),isthenumb eroflinearlyindep endentrowsorcolumnsinamatrix.(Notethatth enumb eroflinearlyindep endentrowsisthesameasthenumb eroflinearlyindep endentcolumns).Thereforerk(A) min{numb erofrowsofA,numb erofcolumnsofA}.Amatrixissaidtohavefullr ankifrk(A) = min{numb erofrowsofA,numb erofcolumnsofA}.Whenamatrixisinrowechelo nform,itiseasytocheckwhetheralltherowsar elinearlyindep endence, ,thenthematrixwillhavelinearlydep ,inthematrixA= 1 2 34 8 61 1 1 MathCamp11intheexampleab ove,allrowsarelinearlyindep endentb ecauseitsrowechelonformA4= 1 110 120 0 6 ersofSolutionsLet'sbuildsomeintuitionbyl o (b1,b2),wecanviewthetwoequationsy1=a1x1+ b1x2andy1=a2x1+ (x1,x2)isap ointthatliesonb ,twolinescanintersectonce,b eparalleltoeachotherorb rstcase,therewillb eonesolution(onep ointofintersection),inthesecondcasethere willb enosolution(nop ointofintersection)andinthethirdcasether ewillb ein nitelymanysolutions(in nitelymanyp ointsofintersection).

10 Therefore,asystemoftwoequationsandtwounk nownscanhavezero,oneorin nitelymanysolution,dep :Itcanhaveeitherzero,oneorin outthep ossiblenumb ersofsolutionswhenwelo okatthedimensionofasystemandtherankofits co e erthanmisthenumb erofequationsinthesystemandthenumb erofrowsofAandthatnisthenumb erofvariablesinthesystemandthenumb erofcolumnsofA. Ifm < n, ,b=Axhaszeroorin (A|b),b=Axhasin nitelymanysolutionsforeverybAsystemwithmoreunknownsthanequationcanneverhaveoneuniquesolution.(Example:TwoplanesinR3cannotintersectinonlyonep (nosolution)orintersectinaline(in nitelymanysolutions)).IfweknowthatAhasmaximalrank,namelym,thenweknowthatthesystemhasin nitelymanysolutions.(Continuingtheexampleab ove, ,butthatdo esnothelpusinnarrowingdownthenumb erofsolutionsinthiscase.) Ifm > n, ,b=Axhaszero,oneorin ,b=AxhaszerooronesolutionforeverybAsyste mwithmoreequationsthanunknownsmayhavezer o,oneorin nitelymanysolutions.