Linear Algebra: Linear Systems and Matrices - Quadratic ...

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

3 Thenthematrixthatrepresentsthelinearsyst emhturnsouttob eexactlyAB,thatish(x) =f(g(x)) = nedtocorresp ondtothecomp ealinearmap-pingifforanyvectorsx1,..,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.

4 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 . ,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).

5 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.

6 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.

7 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? Givenaco e cientmatrixA,whatcanwesayab outthenumb erofsolutionstob=Ax,foranyb?Howcanwetell whetherasystemhasoneuniquesolution?

8 Let'sstartwiththe 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.

9 Bytakingthethirdrowandsubtractingitfromt he 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| |.. 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.

10 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.)