Jordan Form Binder

JORDAN FORM BINDER Tabs: 1 2 3 4 5 6 +7 Es e ‘GontentsofJordanFormbinder: 1.7.05 Front: Overview &.TheN-space drawing andnotes onsame, relates topage 65ofMatthews notes. 2-"PBL onJordan form" --some summary notes onJandCmatrix,variousdetails. 3.™EE263 Notes" (and download pages) onJordan Form (Boyd, Stanford). €SNotes onhowtocompute aJordan form, +download (inMathematica). 5.*"Tom Leinster Notes" (and download pages) onJordan Form. 6."PlanetMath proofofJordanform"notesanddownload pages. 8.Matthews Chapter+-Linear Transformations e. 1 eJordanFormOverview Phi, 12.22.04 HowIgottothissubject. IwasreadingJim'spapersandsawmentionofFortranroutinestoget eigenvalues ofatridiagonal matrix bysomestrange QLmethod. Thisledmetodoabroad review of “matrices”, apieceofequipment lorigidleonmyshopfloor. Whén reading M&M, Isawtheirdiscussion ofgetting anarbitrary matrix to"triangular block diagonal form” which Icalled Pivot andTwist, andit ‘wasatorturous discussion. IlaterJeamed thatsomething called theSchur Decomposition getsyouby similarity toacompletely triangular form, soatleast thisresult wasconsistent withtheM&M discussion. Butthings werestillveryhazy. IreadtheFortran bookabout howyouactually compute eigenvalues and eigenvectors numerically using theQRiteration method, awonder oftheworld. Butinthetheory world, thereismoregoingonhere.JordandidJordanFormaround1870,seehisbio. |Camille Jordan, bytheway, wasFrench 1838-1922, anengineer andmathematician. . (Scehttp://www-groups.des.st-and.ac.uk/~history/Mathematicians/Jordan.html) Anarbitrarysquarematrixcanbebroughtbysimilarity toJordanCanonical Form.Thisformistriangularblock diagonal asM&M said,butalotmore isknown. Itisreally adouble direct sum. Theouter direct sumputstheeigenmanifolds intodirect sum(block diagonal), andthisisnowproved fromthePrimaryDecomposition Theorem whichKRMatthews derivesinhisnotesafterLOTSofpreparation. . Then within eacheigenmanifold, there isfurther direct sumaction. Youendupwith asetofsmall blocks with2ondiagonal, andonly1'sonfirstoffdiagonal, Within eacheigenmanifold, wehavethese facts: e (1)thetotalnumberofdiagonal elementsisofcoursethealgebraic multiplicity (sumofblockdims) (2)thenumberofJordanblocksisthegeometric multiplicity (3)thesizeofthelargest block istheminimal polynomial exponent bforthiseigenmanifold. Inmybasicstudyofmatrices, thenotionofa"minimal polynomial" nevercameup.Inowknowwhatitis.Ithasexactly thesameformasthecharacteristic polynomial, buttheexponents canallbelower. I know exactly howtocompute thispolynomial (inprinciple) foranymatrix A. Inorder to“fill out" theJordan structure ofaparticularmanifold,youneedthreenumbers:algemult, geomultandtheminpolyexponent, Insomecases,youdon'tneedallthrée,butingeneralyoudoneedall three.Youcanseethisbythinkingaboutthecasewherealgemult=4.Ithinkbeyond6x6youneedeven more information togettheform figured out. Whenthegeomultisfull,yougetallIx1blocksandyouarefullydiagonal, nosurprise.Whengeomultisonly1,thenyougetasingle fullsquare block. Ingeneral, eachsquare Jordan block doeshaveasetof “generalized eigenvectors" thatIknowhowtocalculate frommyEE263 notes. Foreachblock, onlyoneofthese(the“firstcolumn") isatrueeigenvector, theothersaresortoffillers. Justaswithafullydiagonalizable matrix,thesimilaritymatrixwhichtakesyoutoJordanformconsistsof |e theeigenvectors alongwiththesefillergeneralized eigenvectors. Thus,youcaninfactbuildthesimilarity 1 youneedtogetanymatrixAintoJordanCanonicalForm.[hadwonderedearlierhowthisworkedwhen t)youdidnothaveenougheigenvectors, Ithoughtmaybesomerepeated. NowIknowtheanswer. TheJordan form is“asfarasyoucango".Those blocks aretheprimitives. Your distance from non-diagonalness isreflectedbyhowmanyonesyouhaveonthatfirstoffdiagonal. Justasareminder, ifthematrix Ahasno"defects", meaning geo=algineachmanifold, thentheJordanformwillbefullydiagonal. Weseenowwhythishastobetrueifalleigenvalues aredifferent! Theauthors liketomake aparallel between these Jordan blocks andprime numbers: ‘A= sum ofirreducible Jordan blocks N=productofpowersofprime numbers Ineachcase, youhavereduced something tothemost basic primitive elements. Conelusion: IthinkIknow howtotakeanymatrix toJordan formnow,Icould doitmanually, But Maple hasasimple calljordan(A,’P’) which computes theformandthesimilarity which getsyouthere. I suspect thisprogram computes thebasiceigenvectors, thencomputes thegeneralized eigenvectors, then hasthesimilarity, andthenjustusesittogetJ. . ee Quis . eTheJordanFormNspacespicture PhL 1.7.05 SeeFigure 1below. Justexplaining what thisisapicture ofsgoingtotakealotofwords!Wearetalking aboutcomposite mappings oftheformp*'(T): U->V thenp(T):V-—W, foratotalmapping thathasthe formp(T): U>W.ThelefteggisU,themiddle eggisV,andweonlyshowthezeropointoftheright eggW.Weareinterested inh=1,2,3... b(b=minpolyfactor exponent), Ourpicture isdrawn forb=3, andweshow thethreehvalues h=1,2and3.Wearealways interested ontheloftinKer(p). Weknow thatdimKer(p°) =a,thealgemult. Andweknow thatdimKer(p)=1,thegeomult. Weknow from Matthews page 58thatthenullspaces inthelefteggarenested asshown, without equality. Inother words, weknow thatKer(p’) >Ker(p’) >Ker(p). Sothissequence ofkernel spaces isgetting smaller, while thecorresponding sequence ofimage spaces intheVeggisgetting larger. Think ofnullity+rank = constant astheexplanation forthisfact.Asnullity goesdown (smaller spaces ontheleft),therankgoes up(size ofdomain ontheright). Asanexample ofwhat thispicture shows, consider apoint inKer(p’) liketheoneshown as¢.We operate onthispointwithp’(T)andweendupwithapointinthespacewehavelabeled Im(p’). Allof thisregion isthengoing tomapunder thefinalpoperator into0intheWegg. Now itmaybethatsome points inK(p*)mapunderp*directly intothe0intheVegg,butOK,thefinalpmapping willstilltakeus to0intheWegg.Allpoints inK(p*) under thecombined mapping p*thenpmustendupat0inW.But theyendupinanintermediate zone inVwhich wehave called Im(p’). Nowwehaveabitofconfusion. When wesayIm(p*) hereandinthepicture, wereally mean the image orrange oftheoperator Matthews calls Qo,nottheoperator Q.Qoisdomain-restricted tooneof thekemels ontheleft.Forexample, wemight haveQ=p*withdomain being allofU,butQo=p?withdomainbeingonlyKer(p’).Ifwedidnotdothisrestriction,theimageareasintheVeggwouldbelarger, eandinfacttheywould probably haveregions which lieoutside thelargest circle intheVeggwhich isin factKer(p). ButIonlycareabout these"restricted" image regions, because Ionlycareabout starting offinoneofthe kemel regions onthefarleft. Because myimages intheVeggareforthe"restricted" operators, Ithink wecanidentify eachof theseregions withoneofMatthew's Na»spaces. Normally wearesupposed tothinkofanN-space asthe intersection (what Icalled across-hatched region elsewhere) ofanImage areawithKer(p) intheVegg, butwiththisrestricted meaning ofImage, thenested setofimages alllieinside Ker(p) asshown, sowe don'thavetothink about intersection. Theoutermost region intheVeggisNip=Ker(p). [AtleastI thinkthisisallcorrect, Icould bewrong. ] Sotosummarize: ontheleftwehaveasetofnullspaces which aredecreasing insize,andonthe rightwehaveasetofN-spaces thatare.increasing insizeandwhich aremaxing outatNiy=ker(p). When wesay"increasing insize", wemean thatweareadding oneormore newbasis vectors. For example, suppose Ns,has1basis vector andNo»has2andNi»has3.InMatthews notation, thismeans Usp=1andUap=2andviy=3.This isinfacthowwegettheMatthew's dotdiagram shown inour figure. Asyoumove outward toeachlarger Nspace, Matthews suggests thatyou"reuse"thebasis vectorsyou already haveandaddnewonesasneeded tothisset.Thisishisnotion of"extending" the basis. ‘Now let'sre-examine Matthew's example onpage 73which infacthasthedotdiagram shown, and ‘wewillusehisothernumbers inthisdiscussion aswell.Wearesuppose to"start off"atthetopofthedot diagram, which istosay,westartthinking about thesmallest nested Nspace which isNs.Wewantto findbasis vectors forthisspace. Hissuggestion fordoing thisisasfollows: (1)first,findbasisvectorsoverontheleftforspaceKer(p*).Inhisexample,dimKerp’=6=a,so e there areinfact6basis vectors. Tomechanically dothisofcourse requires significant work, butwe 1 wouldhaveMapledothatworkforus.Wewouldcomputethatmatrixp"(A)=(A-41)’[ithappensthat e 2=0inhisexample ],andwewould thenaskMaple tofindtheeigenvectors ofthismatrix. Inhis example, thisisasingle eigenmanifold with2.=0,andtherereally willbe6distinct eigenvectors since weknowthatdimKerp’=6,Matthews callstheseeigenvectors X;through Xs. (2)second,Matthews suggeststhatyouapplyp*toallthebasisvectorsthatyoufoundforKerp?and inthiswayyouwillgenerate asetofvectors which "span" Ny.Heusesacertain bracket (...)notation to indicateasetofspanning vectors,soherehewouldsayNs,=(p’Xs,p’Xa,p?Xs,....p’X«)andthis notation means "thespace Ny»isspanned bythevectors ....", Ofcourse weknow thatvs»=1,sothat tellsusthatthissetofspanningvectorscontainsonlyoneLIvector!Perhapsseveralofthemare0(under theactionofp’),andthenanyremaining onesmustbe"multiples" ofeachother.Couldwegetp*X2=0, forexample? Sure! This would justmean thatthebasis vector XofKp’isalsoabasisvectorofKp?. Youcouldimaginecreatingawholeworldofbasisvectorsoverinthelefteggbyasimilarextension idea.Inanyevent, weknow thatthesetshown above willhaveaviable basisvector forNsp.Let's assume itisp*uy.Then wecansimplifytosaythatNsy=(p*uy). Matthewsthenmoves ontothinkabout basisvectors forthenextlarger space Nz», Here-uses the ‘onewejustfound, which wehavecalledp?u,.Hethencomputes asetofbasisvectors (BV's) forKp*( andweknowthereare5ofthese),andthensaysNzy={p”u;,pY:,p¥2,pYs,....PY)whereheprependsouralready-found BV.weknow that02»=2,sooneofthepY;guyswillbeourpu;second BV,andwe willthensayNz»=(p*uj,puz).Notice thatwhenweworked withKp°,themapping operators werep*. Andnowwhenwearedealing withKp’,themapping operators arep. WethengothelaststepandweendupwithNip=(p*ui,p'u:, p°us),andthissetofBV'sworks for ourKer(p)spacewhichhasv1=3=geomult. e@ Nowweask:WHY doesMatthews suggest wekeepre-using previously computed BV'sandadding new ‘onestoextend asnecded? After all,wecould doitsome other way.Thereason isthis: Look atourresult Nip=p?uy,p'uz,p?us).ThefirstBVisnotonlyaBVforKer(p), butitisalsothe"maximal" BVofa cyclicsubspaceCthatisassociated withtheJordanblock.TheBV'sforthisCspaceare(p?mi,p'uy,p? 1u)). ThisCspaceisgeneratedbyvectoru;andhastheminpolyp®=p’"'=p**!.Ithasdimensione=3, anditisassociated withthefirstcolumnofthedotdiagram.Sotorestate:thisBVhastworolestoplay, ItisaBVforKer(p), anditisaBVforJs.Similarly, p'u,isaBVforKer(p), andisalsoaBVforJ>. Sotheplanintheabove example istofindviable vectors u;,us,andu;inUandfrom these wecan ‘compute boththeBV’sforKer(p) aswellasthematrix Pwhich getsustoJordan form. The"other" BV's fortheCspaces thatarenotinourKer(p) BVlistarecalled "generalized eigenvectors” andwecansee thatthereisnoquestion astotheirexistence. InMatthews scheme, youcantrivially compute thembyapplyingpowersofptothestartingu.Itisallprettyautomated! ; re Vv WwWv va eo ~ T V if g=Une. Smaller aNugwhye?1. x >, ; Ne ~ ‘ u @S$ s & | Ss ® Notes onLinear Operators ‘Theorem 1.LetT:U-+Vbealinearmapping. ThenUisfinite-dimensional iffKer(T)andIm(T) arefinite-dimensional inwhich case y dim(U)=dim(Ker(T)) +dim(im(T)). N=ull +nomk, Proof.(=)IfKisfinite-dimensional thensoisKer(T)sinceasubspaceofafinite-dimensional vector space isalsofinite-dimensional.”Also, ifU=Span(e,... ,e,),thenIm(T)=Span(T(e1),... ,T(es)) s0thattheimage of7isalsofinite-dimensional.VNowiff,...,f,isabasisforKer(T)andwe complete fry...» fstoabasis fir..+s fayfariy--» fotr ofVthenweclaimthatT(f.41),...sT(ferr) isabasisforIm(T). Indeed, theyspanIm(T) sinceT(f:)=---T(f,) =0,andifayT(foy1) +>.+6-T(For)=0wehaveT(a;fai++++rfotr)=Owhichimpliesaifait---Grforr =Bifit-+-bafs.Bringing allterms totheleftsidewegetadependence relation among fi,..., fits. Sincefisare linearly independent wegeta1=a2=---=a,=0.Thisyields dim(U) ~8+r—dim(ker(T)) +dim(Im(T)).. (€)NowsupposeKer(T)andIm(T)arefinite-dimensional. Letfy,...,fsbeabasisforKer(T) andlethy,...hy beabasisforIm(T).Wehavehy=T(fess)withfay... faa€U.Weclaim thatfir... fosr isabasis forU.Indeed, ifu€U,thenT(u)=aosT(fou+--+OnteTFete) whichimplies thatu—dy41 fey1—---—Qy4rforr €Ker(T) andhence that U=desifont—=Gearfate=Onfi+o +Sof which gives u=a1f;++--@s4rfesr andhence thatfi,...fs4r generate U.Toshow linear inde- pendenceofthesevectorssupposethataif;+---Gsirfoer =0.ApplyingTtobothsidesyields eGaba+++@atrhie =Owhich givesdys1=---=Guy=0sincehy,.../y arelinearly independent,Butthena;f;+---a,f,=0whichgivesa,=+++=a,=0bythefactthatf;, dots,f,arelinesrly independent.Thus dim(U/) =r+¢=dim(Ker(T)) +dim(Im(T)). a Corollary 2.LetT:U+VS: V-+Wbelinear mappings suchthatKer(S) andKer(T) arefinite-dimensional. Then dimKer(ST)=dimKer(T)+dim(Ker(S)1Im(T)). \ Proof.WefirstnotethatKer(Z)Cker(ST)andthat aweY, xy aa ueker(ST)<>ST(u)=0<>T(u)€Ker(S).nIm(T). ~a1K NowletZo:Ker(ST) =+Wbethelinearmapping defined byrestriction of7toKer(ST). ‘Then[Kerto)=Kex(t) Tni(To)=Ker(S)Aim(T)fvhish yieldstheresult. a Corollary 3.dim(lcer(ST)) <dim(ker($)) +dim(ker(T)) withequality ifKer(S) ¢Im(T), inpareticular, ifTissurjective. ‘Theorem 4.LetT bealinear operator onavector space Vandleta1,a2,... ,axbedistinct scalars such thatdim(Ker(T ~a)"') ésfinite-dimensional for1<i <k.Then Ker((T —a1)"(T—ag)"---(T—a4))=Ker(T—ay)"+Ker(T—ag)"+--+4+Ker(T—ay)™. Proof. LetW=Ker((T —a:)"(T —aa)"*---(T—a,)g) andletWi=Ker(T—a,)"!.Wefirstprove thatdim(W; +--+ W,)=dim(W;) +---dim(W,). Forthisissuffices toprove thatifuy€Wi, withw+w2+--+we=0thenw,=wy=---wy=0.LetS;betheproduct oftheoperators e: a : (7—a5)" withj#i.Then,applyingS;tobothsidesofwy+---wy=0,wegetSi(t04)=0since ‘Si(w;)=0forj#4.Since5(Wi)CW,,therestriction ofS;toWiisalinearoperator onW;and Si=[ljgi(Ts—05)”,whereT;istherestriction ofTtoW;.Thatw,=0followsfromthefollowing ‘Lemma since Lemma5.if5isalinearoperatoronavectorspaceWandaisascalarsuchthat(S—a)"=0 thenS—bisinvertible foreveryb#a. Proof.Wefirstprovethisinthecasea=0,b=1.ThenS*=0sothat (1-S\L+949?4.0451 1454524..." g—St... ght], ‘Since twopolynomials in$commute wegetthat1—Sisinvertible withinverse 1+.5+S?+...+S*-1,Since$—1=~(S—1)weseethat~1isalsoinvertible. ThegeneralcasefollowsfromtheidentityS—b=(a-W(1-(6—a)""(S -a)). o Returning totheproofofTheorem4,wehaveZ=W,+Wa-+--+ WeCWsinceWiCW which implies that dimZ<dimW.But,byCorollary 3, dimW<dimW,+dimW,+-+-+dimW,=dimZ sothatdimZ=dimWandhencethatZ=W. fa] Corollary 6.IfTisalinearoperatoronafinite-dimensional vectorspace,thenTisdiagonalizable ifandonlyiftherearedistinct scalars a,,a2,...a, suchthat(T~ay)(T'— a)-+-(T —ay)=0. Wenowapplytheseresultstothecaseofthedifferential operator Dandtheleft-shift operator L.Since(D~a)(2**¥e**) =ate,wescethatSpan(e™,xe™,... ,x#—Te®*)CKer(D~a)*.Butthe rd functions ¢%*,ze%,... ,2*~te** arelinearly independent andso,sincedimker(D —a)*<k,theyareabasisforker(D —a)*.Hence, forexample, Ker(D —1)(D~2)?Ker(D —3)°is5-dimensionalwithbasise*,e*,ze,Sx,ze**,xe%*_Inthecaseoftheleft-shift operator Lwehave, inthecasea#0, (Z~a)(n'#a") €Span((a”), (na), ++,(n'a")) sothatSpan((a"), (na®),... ,(n'*a") CKer(L—a)*, Butthesesequences arelinearly independent‘andsoareabasisofKer(L—a)sincedimKer(L—a)<k.Hence,forexample, dim(Ker(L ~1)(L—2)°(L ~3)?=5 with basis (1),(2"),(n2"), (3"),(n3"), (n?3"), Asanother example, consider theproblem offindingaformula fors,=13+294...+n3, Let¢=(gn).Then(L~1)(s)=((n+1)°~n°)=3(n2)+3(n)+(1)whichisinthekernel of(L—1)%.Hence»isinthekernelof(L—1)*sothatthereareconstantsA,B,C,D suchthat Sn=A+Bn+On?+Dn®. Theconstants A,B,C,Dcanbefoundbysolvingthesystemofequations obtained bysettingn=0,1,2,3. Particularsolutions tonon-homogeneous difference andrecurrence equations canbesometimes foundbytransforming thenon-homgeneous equation intoahomogeneous one.Forexample, the equation (L—1)(L~2)z =(1)canbetransformed intoahomogeneous onebyapplying theoperatorL~1tobothsidesoftheequation obtaining (Z-1)?(L—2)x=0.‘Theoperator L—1waschosen tokilltheright-hand sideoftheequation. Thus t,=a-+bn+2".Theterma+c2"canbe omittedasitisinthekernel of(L—1)(L~2).Wethuslookforaparticular solution oftheform >=bn.Theconstant 6canbefound bysubstitution inthegivennon-homogeneous equation. A similar procedure applies todifferential equations. e 2 NaNnn soe le: e TS)ee/Gree Kes \OAT e ‘ Ano=KuSa dT hate =OT. alr}©kn(sr) ftv'=KG) AinVomdainWare+dinOT"dain.PonTAa(BrALS) @ Jat 2 e PALonJordanForm PhL 1.4.05 Several authors havecontributed bitsandpieces tomyunderstanding ofthissubject, butnoauthor hasgivenacleanlinearpresentation, soIwillhereattemptmyownintegration. 1.The Jordan Block. Consider aJordan Block ofdimension 3x3, 10 010) (400 010 100 J=[01] =[001]+) 040] =]001] +a) 010/=c+ar 00% 000 00m 000 001 Wehaveisolated amatrix calledChere.Asshown onpage33ofMatthews (apartfromtranspose), thisis thecompanion matrix fortheminimum polynomial f(x)=x*.Thatis,wehavethatC?=0.Asyoukeep raisingthepowerofC,youkeepshiftingtherowofI'stotheupperrightuntilitfinallyshiftscompletely awayandyouhaveacompletely zeromatrix left.Hereisamoredetailed example withk=4 0100 0010 0001 0000 [0010] ,fooor 0000] 4{oo00“=!0001}“=l0000]°=}0000] “o000 e 0000 0000 0000 0000 Toseewhythisishappening, notethatyoucanwriteCjz=Bj:torepresent theinitialdiagonal ofonesinthefirstoffdiagonal. Thenwehave (Ce =ZmCinCo=EnSymSusie=Syne (Ce =mCynCate=EmSj2eaSao =83s ands0on Recallthewayyouatesupposed tofindtheminpolyofamatrix: keepraisingthepoweruntilyougeta linearcombination oflowerpowers. Normally whenyoudothiswithsomearbitrary matrix C,yougetsomething likethisatsome point, Chag?=aC+=att . withsomecoefficients aj.Wecanrewrite thisas(thinkay=1) a0?+aC!+...+ayy +CF=0 or e f(C)=0 wheref(x)=x*+agix®!+...+ap 1 a e andthenf(x)istheminpolyformatrixC.Inourspecialcase,wegetthis: Ceo k=4 f(x)=xt Notice thatthelower powers C,C’,C’cannot beexpressed aslincomsofprevious powers, because the onesareinthewrong place. ThatisWHY theminpolyisC. Sofar,then, wehave shown this fact: Theorem 1:Theminpolymc(A) ofthekxkmatrix (JAl)=Cisgiven byme(A) =A, andme(C) =CX=0. Theorem 2:Theminpolym,(A)ofthekxkmatrix Jisgiven by(A-Au)‘. Proof: WeknowthatminpolyofCism(C)=CXwhich wecanwriteas(J-ArI)*,Wecanthenexpand thisthingtogetJ*~4,3"!+...=0,andthisthenmustbetheminpolyforthematrixJ.Anylowerpower ofJ(belowJ*)cannotbeexpressedasalincomoflowerpowers.SomJ)=(J-Ail)‘.Butnowwritethis interms ofascalarargument Atogetmj(A)=(A-Au). Theorem 3:Thecharpolychy(x)ofthekxkmatrix Jisgiven bychy(A) =(A-Au)‘,sowecanregard kasthealgebraic multiplicity oftheeigenvalue A,ofthe matrix 5. Proof:chy(A)=det(J-AL)=(-aa),justmanuallydothedet,theoffdiagonalI'shavenoeffect. e Comment: TheJordan Block isconstructed justtogetthisveryresult: theminpoly=thecharpoly. Usually theminpolyhasalower exponent, butnothere! Theorem 4:The matrixJhasonlyoneeigenvector (x,0,0,0...) andthushasgeometric multiplicity =1. Proof: Theeigenvector problem isthis:Jv=”,v, which isthesameasCv=0which tellsusthatve;=0 fori=0,1,2... Thus,oureigenvector is(vo,0,0,0....). Wecanregard thisastheoneeigenvector ofthenullspace ofmatrixC=(J-A).Thenullityofthis space isthen 1. Conclusions reached concerning theJordan blockJofdimension kwithdiagonalelements Ay: (1)Jhas charpoly=minpoly=(A-2u)* (2)Jhasoneeigenvalue 2,andthateigenvalue hasanalgebraic multiplicity ofk (3)Thasageometric multiplicity of1anditsonlyeigenvector is(vs,0,0,0....) 2.Direct Sum ofJordan Blocks with same eigenvalue Ay 2 Supposewenowconstructalargermatrix(dimk=ky+kz)bydoingadirectsumof2Jordanblocks, t) bothofwhichhavetheSAMEeigenvalue Ay: Ahn @)a Thefirstblockhasminpoly(2-24)",thesecond has(1.-1). Whatistheminpolyforthelargermatrix?Theresultisderivedonpage36ofMatthews. IfweletC=A@B,thenheshowsthat me=lom(ma, mp) *Jom=leastcommon multiple’ Weneed topausetoprovethisimportant result: ‘Theorem 5:IfC=A@B, thenme=lem(ma, mp). Proof: Assume thatmeissomepolynomial {(x).Thenweknowthat: . §(C)=0=F(A@B)=f(A)@f(B)which=>f(A)=0and(B)=0. This says thatm,|fandms|f.Itsaysma|f,forexample,becausem,isthelowestdegreepolythat satisfiesma(A)=0,soiff(A)issomeotherpolywithf(A)=0,thenmamustdivideinto£Now,we wanttoknowthelowestdegreepolyf{(x)that.canbedividedbybothma(x)andmy(x),Thisisexactly whatlem(ma(x),mp(x))is.Andifthef(x)sofoundisinfactthepolyoflowestdegree,thenitmustbe etheminpolyofC.Therecanbenopolyoflowerdegree thatsatisfies therequirement ma|fandma|f. Nowweapplythistheorem toourdirectproduct situation. Wehavem=(A-A,)'andmp=(A=ma)? ‘Theanswer isthatlem(ma, ms)=(A-4)™*"). Forexample, ifwehavema(A-A.)and wehavemp=(2-21),then(2.~21)’canbedividedbybothm,andmp.Sowecaneasilyextendthisidea toshow thefollowing Theorem 6:Suppose weconstruct amatrix bycombining multiple Jordan Blocks ofvarious sizes,but which allhave thesame eigenvalue 21, A=h1®la Oly @... ‘ThentheminpolyforAisgivenbyma=(A-2,)MAX€142.8.-)_ Thisconclusion isreinforced onpage37ofMatthews. Comment: Ifyouarestaring atthematrix Ajustdescribed, youcaneasily seewhich submatrix hasthe largest dimension, callitkesx=MAX(ki, ks,...).Later, whenwecombine matrices A,fordifferent cigenvalues 2;tomakeastilllargermatrix B,andwhenwetalkabouttheoverall minpolyforthislargermatrixB,itwillhaveafactor(A-24)!"forourparticular submatrix A.So,thesizeoflargestJordanblockineach2manifold equalstheexponent oftheoverallminpolyforthematrixA. e Theorem7:ForthesamematrixAshowninTheorem6,thecharpolyisgivenby(2.-Ai)t!*#2*~, 3 Neenneeeeeeee Proof:Whenwehaveanyblockdiagonalform,weknowthatwecanmultiplythesub-determinants to t)getthetotaldeterminant, sointhiscasewecanmultiplythecharBolysofthe sub-matrices, andthatthen Jeads toasum ofexponents asshown. 3.Primary Decomposition Suppose wearegiven some matrix Tandwehavecomputed itscharpolyandminpolytobe: chr(A) =(A=a)" (A=An) my(A) =(Aa)! =Aa) where weknow thata;>bybecause weknow thatmz(A) |chx(A). Then: Theorem 8:According tothePrimary Decomposition Theorem onpage 61ofMatthews, wecandecompose ourvectorspaceV,inwhichthismatrixTacts,intoapairofsubspaces, V=ViOV2 where Vi=N((T-Ail)") withv=a, N[X]means"NulispaceofmatrixX" eV2=N[(T- aD") withv=a, where theexponent b;istheknaxmentioned earlier foreachsubspace i=1and2.Sob;willbethesizeof thelargest Jordan blockineachofthetwosubspaces. Remember: ;istheminpolyexponent. Thea,are thealgebraic multiplicities ofeach subspace. Nothing issaidhereabout geometric multiplicity, butweknowthatgeomultisthenumber ofJordan blocks ineach subspace. Wealso know these facts: N[(T-AiD'] hasv=geomult1N[(T-a1)'] hasv=geomult2 These nullspaces arethe“eigenmanifolds" ofStakgold, Herewehaveunityexponents. 4.TheCyclic Subspace Business Following Matthews page54,weimagine some“vector specific" minpolymry(T)v =0rather thanthe more general minpolymy(T) =0.Thisspecific thing hastodivide thenormal minpoly. Theorem 9:Iffisanypolynomial andvissomevector inV(thespace inwhich Tacts), thenthesetof allvectors oftheformf(T)vformsasubspace ofV.Thisiscalled theT-cyclic subspace generated by theveetor v,andthissubspace isaT-invariant subspace, anditisrepresented asCry. 4 se Proof;Ithinkthesubspacepartfollowsfromusuallinearitystuff.Thatis,f,(T)and,(T)makeasum e thatisinthesamespace, soitisclosed under addition, ete.Nowsuppose wisinCr.y.Thenw={(T)vfor some polynomial f.Then Tw=Tf(T)v =g(T)v which isalsointhespace since gisjustsome other polynomial. Theorem 10:Inthesituation described inTheorem 9,assume thatforvector vwehave some vector- specific minpolymy,(T) ofdegree k.Recall thatvisthegenerator vector ofthesubspace Cry.Thenthe following vectors formabasisinCry: {v,Tv,TYy,....T*'v}ThisistheT-cyelic basis, This theorem hasaproofonpage55,56ofMatthews whichIhavenotread. Theorem 11:Again inthesituation oftheprevious twotheorems, ifweworkintheT-cyclic basis, thenthematrixTisnoneotherthanthecompanion matrixoftheminpolymry. This isshown onpage 56Matthews. Application ofthePrevious Theorems. Suppose m(A) =2*. Thisisapolyofdegree k,andwecan formtheT-cyclic basisoftheorem 10:Cry: {v,Tv,Ty,....T*'y}where weuseT’everywhere. Moreover, thematrix T'inthiseyclic basisisgiven(according totheorem 11)bythecompanion matrixwhichcorresponds tomr,(A)~2,andweknowfromearlierworkthatthismatrixisexactlythematrixCwediscussed insection1above,thematrixwitifallzerosexceptforthefirstoff-diagonal ofones. Now ifwedefine TastheshiftT’=(T-241),wecandowhat wedidinsection 1above andclaim e thatmrs(X)=(A-2i)*isthev-specific minpolyforoperatorT.Furthermore, theT-cyclicbasisisnow Cry{-v,(T-Ay,(T-dal)’,....(P=av} ‘ThematrixT="+2,1isthennoneotherthanJ,thekxkJordonBlockmatrixwitheigenvalue Ay. Comments: So,wehavenowleamed thattheJordan Block ariseswhenyoutakeasyourbasisvectors thestrange set{v,(T-AiD)v, (T=4D, ...(T=MEV}. Status: Atthisstopping point,wehave"come downfromabove" withtheprimary decomposition toget asetofsubspaces V;andV2,andwehave"come upfrombelow" withsomestrange cyclic subspacegizmotocreateoneJordanblock.Itremainstoconnectthesetwoworlds. Status 1/7/05. Things arenowpretty wellconnected, IthinkIamdonewiththissubject fornow,after spending quiteafewdaysonit.Results areallinabinder andinadirectory. 5 5 e E263Notes PL 1.7.05 Thisisa10pagesetoflecture notesfromwww.stanford.edu/class/ee263/jef.pdf fromProf.Steve Boyd, see sitehttpy/www.stanford.edu/class/ee263/ formorestuff.Thisisagoodplacetogoforlotsofstuff. This was oneofthefirstsetsofnotesIgotfortheJordanstuff,andIdidnotunderstand themthefirsttime,sonowhavingdonealltheMatthews work,wecancomebackandlookatwhatBoyd’hastosay. Page10-2HerewegetJ=T'ATandheshowsthe1'softheJblockontheupperoffdiagonal, whereasMatthews putsitonthelower. Iamnotmuch concemed about thistranspose issue. HecallstheJordan block "upper bidiagonal”. Allcomments onthispage arenowclear. When Ifirstreadit,Ididnoteven know ifthematrix Jwasthesame dimension asmatrix A.HereferstoTasasimilarity. ‘WhydoesherestricttoAhavingrealmatrixelements?Idon'tthinkthisisnecessary,butIagreethat ifyoudo,Jcanstillbecomplex since eigenvalues canbecomplex. Page 10-3. Comment thatnooneusesJCFfornumerical work, onlyforexact work. Then hewrites thechar poly forAwith variable sinstead ofxor2,andhisn,aremyaj,thecharpoly exponents whichareofcourse thealgemults. Next, hecomments thatifallthenj=1,Acanbediagonalized. Iknow thisistrue, Athenhasall eigenvalues different, Next, dimKerp=#Jordan blocks. Inow understand thistobetruesince each Jordan block has geomult=1,anddimKerp=geomultoftheentireA.WhathereallymeansisthatdimKerp;isthe numberofJordanblocksintheeigenmanifoldpi*.Ifyouthendothisoveralleigenmanifolds,thenthe etotalnumber ofJordan blocks inthefinalJisinfact2dimKerp;.Sowetickhimforvagueness onthis point. ‘Nowcomes hisfamous "more generally" claim. Heistalking about dimKp*herefork=1,2..., and thesearetheu(p*)ofMatthews. Consider ourMatthew’s second example whichwejustwroteupwiththeFigureIVisiopicture.Inthatcasewehadv(p*)=6andn;=6forouroneeigenmanifold. Sointhiscase,hisequationiswrong.HesaysdimKp’=min(3,6)=3.Maybeonthelefthemeansthesumoverallsuchspaces, inwhich casehisLHS=;dimKerp=5,v(p?) butthisisnothing useful toanyone! SoIthinkourguyhasscreweduphere.Hecomments aboutthe"sizesoftheJordanblocks".Iknowthesearethe heights ofthecolumns inthedotdiagram. Well, itistruethatwehavev(p")=dimKerp*andthenfrom thesenumbers wecancompute thevy.»numbers usifig'the subtraction rule,andfromthose wecangetthedotdiagram,andfromthatwecangetthesizesoftheJordanblocks.Butwedonothavethesimple claimhemakesthatv(p')=someexpression. Icannotevenascribeanymeaningtohissummation | notation. Butthegeneralideaisthatfromthev(p")youcanfigureoutthesizesoftheJordanblocks, that claim istrue. Next, heclaims thatTp((A)T’=(J-2,)which Iknow isthecompanion matrix. Hethenshows thatas youtakehigherpowersofthismatrix,itsoonbecomesallzeros.ThisisjusttheidedthattheminpolyofCmatrix(andoftheJmatrix)isthefulldimension ofthematrix.Inhiscase,theminpolyisofdegree3 andwecansayC?=0, Hislaststatement concerns anoffdiagonal power (Jj-Ai).Icouldverify thisIsuppose bybruteforcecomputation, butIdon'tseeanyusefortheresult,soIwon'ttrytoverifyit. Page10-4NowwearegoingtoexaminethematrixTwhichMatthews callsP,InsteadofexpressingTin r)columns,heputsitintogroupsofcolumnscalledT;.Well,hereisaninteresting facttokeepinmind: 1 Neenn neers | SoifwearethinkingaboutAT=T[Jy®Ja],wecanbreakthisintotwoseparateproblems: AT) =Tyh and AT =Tah soIagreewithhisgeneral breakdown intoAT;=Ti;.Thenyoutakeoneofthesegroups ofcolumns and saythis: T=[viVowVar)whereaj=hisnj=thealgemultoftheJblocki. | eThese v'sarethensingle column vectors. Wethengethisniceresult thatthefirstcolumn (only) ofonea T;group isatrueeigenvector. Theothercolumns haveaslightly different equation andtheyarecalled thegeneralized eigenvectors. Ihavederived allthisstuff. NowinMatthews, wegotasimilar situation,buttherethegeneralized eigenvectors formedthecyclicbasisofaTcyclicsubspaceforJ.Well, Ithink Icanmake theconnection asfollows. Hisgeneral equation isthis: (A-ADVij=Vij-l j>luptoj=a =PiVij=Vij-l sowehave: PiVi2=Vil» PiVI3=Vi2, PIVI4=Vi3 ....PiVia= Vial whichIcanrewriteas(forthecasea=4) iYvia=iFvi3=i)! Vi2= vil (i) vig=Wi)Vi3=¥i2 (Pi) vid=v3 iY via=vid SohereweseetheMatthews ideathatyougetthebasisvectorsoftheJ,spacebyapplyingpowersofpto @agenerator vector which here isvi.,andthehighestpower(pj)°vj4thengivesyouthetrueeigenvector 2 e Vj1,andalltheotherpowersgiveyouthosegeneralized eigenvectors, soweareonthesamepage!Whatyouwould really likeistofirstfindvj,,thengenerate thevarious otherguysbyapplying powers ofp. Page 10-5 Now suddenly wearelooking ataLinear Differential System LDS dX/dt =AXwhere Ais amatrix. Thiswasalsotouched upon inMatthews. Here Boyd suggests doing achange ofbasis asshown togetamuch simpler problem inwhich thematrix Jisused, Let's look more intothis: dX/dt=AX => TlaX/dt =T'ATT'X > dX/dt=[J, @F]X’ Wecannowbreak ourtallvector X'intoX'=[....J'= [xi"xyJ’and theproblem thendecouples into thissetofsmaller problems: dx'fdt=J,x', 1/justashesays. Now,theiindextellsyouwhich Jordan block. Let'slookjustatasingle Jordan blockforsomefixedi, andalsolet'sgetridoftheprimes fornow, knowing where weare.Then wehave dvidt=Jx andifweassume Laplace s=iwsineaction, wecanwrite thisas e Jx=sx Butremember that J=C+Al andthatCy,=841.sowecanwriteourequation as (CHAD x=sx > EaBjor +ABix)Xe=SX} > XpFAX 8 > Xyils +a /s=x; andwethengetthisJordan ehain picture xyuls 4/ tsatsr)~ xls +2xls=x; wherewehaveone"stage"foreachcomponent ofthevectorx.Justthinkofthe1/sboxasanintegration operatorifyoulike.Sowithineacheigenmanifold, youcansolveyoursysteminthismanner, then combineallthesolutions intothefullX'vector, thentransform backtotheoriginal space. Lot'sofwork. 3 Page10-6Resolvent,ExpoofJ.Nowwelookatthemeaningofp"'.Thisisamatrix.Itistheinverseof r) p,andwefindasimpleclosedformresultforp",Whenwewritep"p=I,wehaveproductoftwo triangulars isatriangular. Hedefines F;tomean adiagonal of1'sandthisallows theniceform shown for“t pt Henextshows thatyoucancompute exp(th), andhisresult islikeMatthew's result onpage83,exceptwehavethetranspose issueinthedefinition ofJ. Whatisthe"resolvent"? Itisexactlytheinverseofp,something Iamtemptedtocallapropagator. Butresolvent isastandard name fortheinverse secular operator. Page10-7Generalized modes.WereturntooursystemoffirstorderODE'sasshown.Wecansolveitasshownonpagebottomusingtheexpostuff(asMatthews did).Ifwepickthespecialt=0startingvectorasshownatthetopofthepage,thenforalllatertime,thevectorx(¢)iscontrolled onlybyoneoftheJordan blocks ofourmatrix A.Youthink ofthisasifitwere avibrational normal mode. Then atthe bottom youseethatwithageneral starting vector x(0),youhaveactivity inallthe"modes". can seethatthisisawhole newsubject thatonecould study, Inever heard ofitbefore. Page 10-8 Here hesimple states theC-Htheorem. Page 10-9,10 Thecorollary hereisthatorarbitrary powers ofA,youhaveabasisthatisafinite number ofpowers, asdetermined byC-H(orperhaps bytheminpoly,butthatisnotmentioned). Hedirectly Proves thislittle corollary based ontheC-Hwhich makes 7(A) =0.IfAisinvertible,thesameclaimof finite basis applies tonegative powers ofA. e Page10-11.HisproofofC-H.HefirstassumesAcanbediagonalized intoA,thenC-Hisquiteeasyto showsinceallmatricesarediagonal. Eachone.hasa0somewhere onthediagonalandtheeffectofall the zer0sistoKilltheresult so(A)=0,sothatmeans (A)=0.Moregenerally, wecangetAintoJform. Thenyoucanshowthat(Ji)=0foreachiasshown, andthenthedirectsumbusiness tellsyouthatthe fullx(J)=0,andsox(A)= 0.ThisisaniceproofIthink!ButyouhavetousetheJordanform,soit depends where youarestarting yourcircle oflogic. Comments: Thisisanicelittlelecture Ithink, lotsofgoodtopics arereached. Hepresents adirect method forcomputing thematrix T.Youcannot saythathe"proves" theJordon Form inthesense that Matthews does. Heassumes it,andthencomputes Twiththatassumption. Hethentouches onthese applications: system offirstorder DE's, resolvent, generalized modes, andtheC-Hideaandwhat it implies, SeekeReeneeenaneaasasesenseseananneeseseesnenneaneeneeses Comments ontheEE263 Lecture 10Document ‘These aremyoriginal notesonthislecture whenIknewverylittleabout thesubject. These notesaddasmallamount tomypicture which isstillveryincomplete. Page2statestheJordan blockformwhichInowseebetter.AtfirstIthoughtmaybetheTwerenon-square,butnotso.Sopage2 eisjustfine. 4 eee ePage10-3, Page3isfullofmysteries. Iagree withthefactthatdimN(AI-A) =geometric multiplicity ofthe manifold associated witheigenvalue 4.AndIknow fromtheabove notesthatthisequals thenumber of Jordan blocks forthis4(butIdon'tknowwhythatshouldbeso).Thenextlinewhereauthorsays"more generally" ~thismeans nothing tomeatall.Iamnotgrokking amajor point here, andauthor isnot helping meatallwith words. ‘Now Idoknow fromtheTLnotes above thatinK(A) wehavefactors like(AI-A)'where risthe algebraic multiplicity. AndIknow thatthere isathing called "theminimal polynomial" which hasthe samefactor butpossibly raised toalower power (AI-A)‘.IntheTLnotespage8Iagreed withthefact thatthisexponent smustbemaxofthesizesofalltheJordanblocksassociated withthisparticular 2.But this does not seem torelate. Recall fromearlier workthatKer(A-I) isthenullspace whose dimension misthegeomult ofthis eigenvalue A,thenumberofdifferent eigenvectors. Wearesomehow breaking thisnullspace downintom distinctnullspaces, eachofwhichhasgeomult=1.ThisisexactlyTL'sExercise3.Andwealsoknowthat thesumofthedimsofthese subspaces isr,thealgemult. Sowearedoingafactorization likeso: (Al-A)®=(AT-A)!(AT-AP(AT- A)? 6=algemult 3=geomult andweassociate eachfactorwithoneofthese newnullspaces. AHA...! (asonesays). WeknowthattheK(A)equation isinvariant undersimilarity, thatisvery easytoshow andIhavedoneit.Soconsider theabove product inthelanguage ofJ @(I-08 =QI-D'Al-I~OI-D? 6=algemult 3=geomult Suppose forthemoment thattheentire Jhasonlythisoneeigenvalue A,buttherearethreeJordan blocks | whichwewillcallJ=diag(t,,Ja,Js)whichare1,2and3indimension. Intheaboveequation,IandJare |bothinblockdiagonal form,sothismeanswehaveadirectsumviewandwecanlookonlyataparticular |block,inwhichcasewegetthis: | (A-J)’=QL-J)!Al-JPI- I)? 6=algemult 3=geomult i=1,20r3 Ourcharequation isjust(AI-J)°=0forourhypothetical matrix. Butwithin eachnullspace, wewantto have(AI-J)“*"5 =0.Thiswillthensaythat(AI-J)""S x=0forallx,sothen dimKer [(AI-J)"""S j=dimNS. writeas dimN(I-A) =k Nowourpage3notesshowthat,withJ;defined asitis(theJordan Block), wedoinfactget (AL-5)**5=0, Oneachpower, theonesslideuponediagonal, andthentheyslideoff,justthewaymy littleUH,theorem saystheyshould. Sothisatleastmotivates theformoftheJordan Block. Ontherightabove,wehavesomething thatatleastresembles whatisonpage10-3ofthenotes.NowwecouldnevertalkaboutdimNSbeinglargerthanthealgemultofthat A. ‘NowinamoregeneralmatrixwithseveraldistinctA;,wedogetthe"offdiagonal"powersasshown ‘onthebottomofpage10-3.Ihavenotcheckedthematrixontheright,butIcanseeitwillbesomething ©tune. s @ ress Nowwegetanothersmalliotaofinsight.IfwesimplyassumethatsomeTexiststoconvertAtoJ,what canwesayabout thismatrix T?Well, wecertainly cansayAT=TJ,thewayweusedtosayAA=TA. where Awasadiagonal matrix. Because Jisinblock diagonal form, wecanwritethisasAT;=Ti;where theJjarethesmall square Jordon blocks, andtheT;aregroups ofcolumn vectors ofTwhich: wecan associatewiththatJ;.Ihaveshowngraphically howthisworksonthatpage.Sowehaveadecoupling oftheproblem somewhat. Wethenlabelthecolumns ineachT;.IliketosaythisasT°=[v,°,v2",v3"..... vy]Weneedto ‘maintain some kindoflabel"i"tosaywhich T;setofcolumns wearetalking about. ButthenIleave off theilabelandjustthinkabout ONEoftheseTblocks. Wethenfindtheseinteresting facts: (1)Thefirstcolumnv,®satisfiesAv,°=A;viandsoitisatrueeigenvector of2;,Remember thateachJordanblockonlyhasonetrueeigenvector, andthisisit!! (2)Theothercolumns satisfy equations likeAvs°= a,vs+v3.Thisisclosetoaneigenvector equation, butwehavetheextra termontherightwhich istheprevious column! Weknow thatthese other columns cannot betrueeigenvectors since eachblock hasonlyone,sothese other columns arecalled the generalized eigenvectors. They aresome kindofdummies tofillouttheTblock. Itisnotclear tome looking atthisequation Av3=2;v3+v9whether ornotthereisasolution. Iguessifthereisnot,thatdetermines thewidthoftheTblock,whichistosay,thatdeterminesthesizeofthisJordanblock. | @ rmceros Thavetoskipotherpagesbecausetheyarespecialized totheapplication ofthisEE263courseatStanford,butthelasttwopages8and9aregood.Hefirstmakes a"statement" aboutwhatyoumeanbyapolywith matrix coefficients, thenhestates theC-Htheorem andgivesanice2x2example ofit. Page 10-9 Thefirstparthereisthe"corollary" toC-Hwhich saysanypower A*canbewritten asalincom of powers ofAuptoN-1,whichIagreewith.Thesecondpartisbasicallythesameproofof"thecorollary” thatIputintomy"matrix research" notes, butIthinkmydetails aremuchbetter, hisisalittlefudgy. OfcoursethisproofdependsontheC-Htheorem, Page 10-10. ‘ThisisawaytoshowthatA”canalsobeexpanded inthesamelincom ofpowers ofA,hence wecando | anynegative powers asclaimed earlier ifAisinvertible. Page 10-11 ‘Nowcomes thisguy's "proof" oftheC-Htheorem itself. Itisallontheverybottom oneline.ItassumesthatwecangotoJordanform,andthenitusestheideathatthepowersofthematrices vanishifyoupick e‘outtherightoneforeacheigenvalue. Notice thatthen;hereareNOTthealgemults, theyaretheJordan 6 a blockdimensions. SoheusesJordandecomposition toproveC-H,whichisifnothingelseinteresting, @ Again, thefactthatthesecular equation istrueinAorJisused. Tthink Ihave nowsqueezed themostjuice thatI-can outofeachofthese 10-page papers which Ihave printed andwritten on.Butweneed more info! LS f Jordan canonical form 10-1 e Lecture 10 Jordan canonical form EE263 Autumn 2004 eJordan canonical form ©generalized modes Cayley-Hamilton theorem e : Jordan canonical form 10-2 e Jordan canonical form what ifAcannot bediagonalized? anymatrix A€R™"” canbeputinJordan canonical form byasimilarity transformation, i.e. J TIATH=J= me Jy6%wt whereAe ri 1 J,= Ai €Cri ® = ned ri iscalled aJordan block ofsizen;witheigenvalue .; (son=rh,ra eJisupper bidiagonal ¥ eJdiagonal isthespecial case ofnJordan blocks of sizenj=1V Jordan form isunique (uptopermutations ofthe blocks) v canhavemultiple blockswithsameeigenvalue eanahutwoah Desamesige! . Jordan canonical form 10-3 e note:JCFisaconceptual tool,neverusedinnumerical computations! we5%i? 2(8)=det(sI —A)=(5—Ay)"+++(s—Ag)@<— PRM hence distinct eigenvalues =>n;=1=Adiagonalizable ” ToMullepacer dimN(AI —A)isthenumber ofJordan blocks with eigenvalue \_=thegeemuhic muhple;A». more generally, dimN(AI—A)F=wymin{k,ni} sofrom dimN(AI—A)*fork=1,2,...wecan determine thesizes oftheJordan blocks associated @ witha efactor outTandT',AJ-A=TAI-J)T ©for,say,ablockofsize3: Dare GH)LH=LH, 010) —~Jooi AI-H=|001} Ad-F)P=|000} (Aar—J)?=0 000 000 ¢forotherblocks (say,size3) Oi=Ag)EBOG—Ag)?(=1)/2(5—Ay)? AI—J)* = 0 (Ay—As)* —h(Aj —Ax) 0 0 Qj—4) e .Jordancanonicalform TOAos)~TAeTb 10-4 @suppose TAT =J=diag(h,..., Jae .BBipcatia express T’as iN . ah re yOse where7;€C"*"arethe,columns“ofT-associatedwith ithJordan block J; TTe1, +(OCH[RP4 v wehaveAT;=TJ Se aT ye yan’ State PSL| letT;=[vinvi2+++Ving” °oodNa7 @ thenwehave: “Er Lary, Avi =divi, i.e., thefirst column ofeach T;isaneigenvector associated withev.\;“ datapne: algal dbs bad!) B40" detcare,clhthe!” for7=2,...,ni, Mir|g) |ao = Avi=Uija+Avi AY;=VtWN | Aw=r% \jrt thevectors v;1,... Vin, aresometimes called generalized eigenvectors e@ 24,Ay=ay,+ Aq=av +e ete, ahoK, : Jordan canonical form 10-5 e consider LDS¢=Ax bychange ofcoordinates x=T%,canputintoform a= Jz system isdecomposed intoindependent ‘Jordan block systems’ &;=J;Zj @ EnEnaTey 1/s1/s LS eee Jordan blocks aresometimes called Jordan chains (block diagram shows why) e Lo © Jordancanonical frm .10-6 e Resolvent, exponential ofJordan block resolvent ofkxkJordan block with eigenvalue .\: s-r -1 7 (sf—.h)7!= soA7 a s—x Xs (s—A)7 (s—Ay?+++(8—AY“*wires + acee (s—2)(8-2) +1 "(say =(s—A) +(s—\A)PA +--+ (s—Aya ewhereF;isthematrixwithonesontheithupper | diagonal _— OF. | byinverse Laplace transform, exponential is: ett=eM(4th +--+ (OU/(k- 1)Fa) 1t--- t/(k—1)! =em1---th?/(k —2)! 1 Jordan blocks yield: repeated polesinresolvent 4 e@termsofformt?e™ine“*/ © dancanonical frm 10-7 e Generalized modes consider ¢=Az, with 2(0)=ay04 +++++Gn,Vin, =Tra thenx(t)=Te#&%(0) =Tye?#a ©trajectory staysinspan ofgeneralized eigenvectors ©coefficients haveformp(t)e™, wherepispolynomial e esuchsolutions arecalledgeneralized modesofthesystem withgeneral20)wscaywrite q,a(t)=e“*x(0)Cre =£Te*(SFx(0)) where St T1=/: ‘TSy hence: allsolutions of¢=Az are linear combinations of @(generalized) modes 4 | wreplu. e As(M-~-)A (Aearm-“\ =(- \ weA An.weMAS e =AA @ a Jordancanonical form 10-8 e Cayley-Hamilton theorem ifp(s)=ap+ais+--+ +a,8* isapolynomial and AER", wedefine p(A) =apI +ayAt+---+a,A* a theorem:foranyA€R”™*”wehave ¥(A) =0,where ¥(s) =det(sI —A) | . 12 @/example: withA=FAlwehave X(s)=s?—5s—2,so X(A) =A?-5A-2I 710 12=[35|55‘|~2r =0 e :Jordaneg6nicalform CLpoorwihOur 10-9 ecetollary: foreveryp€Z:,wehave owA?€span{I,A,A’,..., Av} (and ifAisinvertible, alsoforp€Z) .Kaikiol 1.€., every power ofAcanbeexpressed aslinear combination ofJ,A,...,A"~1 proof: divide X(s) intos?togets?=q(s)X(s) +r(s) r=a9+018 +--+ +Qy-18""! isremainder polynomial then AP=q(A)¥(A) +r(A) =r(A) =al+ajAt+---+ QnA”! e oa; Jordan canonical form 10-10 eforp=—1:rewrite C-Htheorem 6X(A) =A"tanaA" 14+--++ aol=0 I=A(—(a1/ap) —(a2/a9)A —+++—(1/09) A") (Aisinvertible <>ap#0)so A!=—(a1/ao)I —(az/ag)A —«++—(1/a9)A™? i.e.,inverse islinear combination ofA*, k=0,...,n—1 e @ ar: * Jordan canonical form 10-11 e Proof ofC-Htheorem firstassume Aisdiagonalizable: T-!AT =A #(s) =(8—Ax)+++(8=An) since X(A) =X(TAT) =TH(ANT"! itsuffices toshow V(A) =0 e (A)=(Aal)<=(A—Aa) =diag(0, 2—A1,.--,An —Ade +++diag(Ai —An,..-;An-1 —An,0)=0 ee nowlet’sdogeneral case: T-!AT =J (9) =(6— MJB (8— AQ suffices toshow V(Jj;) =0 010---]™ H(H) =(HAD |00Le] oe(mAg =0 (i-AD" e a i e Notesfromhttp://www.ma.iup.edu/projects/CaleDEMma/JCF/jefS.html PhL1.7.05 ‘Nowthesenotesarefinallycomprehensible tome.AtfirstIdidnotknowwhatwasgoingon.Notation isalltext,soalittleugly.Thenicepartisthatit.usesMathematica toquicklyanswerquestions. Inthis thing, theauthor directly computes theJordan form fortwosample matrices. Here ishow hedoes it: (1)write your matrix A,find outitseigenvalues. You want topick anAthat hassome repeated eigenvalues tomakeitnon-trivial. Hedoesthis. (2)compute theeigenvectors. Here hefinds outthatonedouble 2.hasonly oneeigenvalue, thesecond is reported asallzeros. What does Maple dointhissituation, let'ssee! U,2,{vector([1, 0,O31, (2,1,{vector([0, 1,1])}] value, mult, vector ‘SoMaple justsays onlyoneeigenvector for2=1. (3)next, youhave tocreate themissing generalized eigenvector using AvO= devi +¥,0 e But,justlet'snowremovethe(i)superscriptandjustthingofthe v;ascolumns oftheoverall T.Then we d have (A-Aly= v1 andweknow v;=(1,0,0) and4=Iandweknow A.SowejusttellMaple tosolve thisinhomogeneous equation forv2,andMaple does thisandgives us(x,2,1) foranyx,butMathematic says (0,2,1) asa viable solution. (4)You arenow done. You have your T,anddosimilarity onAtogetJ.Isuspect youneed toalways put 0inwhen youcanforanunspecified numberasintheabovecase. 1 Finding theJordanCanonical FormofaMatrix http://www.ma.iup.edu/projects/CalcDEMma/JCF/jcf5.htm! iFinding theJordan Canonical Form ofaMatrix eLet'sbeginwithamatrixA. Inf8]:= Clear (Jal; A={{1,1,-1},{0,0,2},{0,-1,3}}7 Matrixrorn[a] Out[8]= aoa o 0 2 o 1 3 WewillputAinJordan form. Dodothisweneed tofindanonsingular matrix Ssuch that Inv(S)ASI, where JistheJordan form. This matrix $willbemade upofeigenvectors and "generalized eigenvectors" asweshall see. First, wemust find theeigenvalues ofA. In9]:= ew, Out[9]= {2, 1,2} ‘Younotice thatAhasarepeated eigenvalue. This does notnecessarily mean thatAdoes nothave a : fullcomplement ofeigenvectors. Let'ssee. In{10]:= Eigenvectors al Out{10]= {{2, 0,oO}, (0, 0,O}, (0, 1,2}} Notice thatbylisting aneigenvector of{0,0,0}, Mathematica istellingyouthatAdoesnothaveafullcomplement ofeigenvectors. Wemust search for"generalized eigenvectors". Aneigenvector vsolves thematrix equation Av=lambda v [or(A-lambda I)v=0, where|istheidentity matrix]. Ageneralized eigenvector v(i)willsolvethe ematrixequation Av(@)=lambda(i) v@i)+vGi-1) lof4 1/7/2005 3:34 PM Finding theJordan Canonical Form ofaMatrix hitp:/hwwvw maiup.edu/projects/CaleDEMma/JCF ef5.htral [note thatv(i)represents asubscript). Here v(ji)isthegeneralized eigenvector corresponding totheeigenvector v(i-1) @ _Teisesaston canbewriten(Atambeag) DvePmvGe1). v(1)=the first eigenvector, v(2)=generalized eigenvector togowith v(1), andv(3) isthesecond eigenvector. Ageneralized eigenvector will goineach slotthatMathematica gives thezero vector as aneigenvector. InfI]:= idnearSolve[A-1 TdentityMatrix(3],{1,0,0}) Out{11]= {o, 2,a) Wehave justfound v(2), thegeneralized eigenvector togowith v(1)={1,0,0). Wenow have three vectors toform thenonsingular matrix S.Inv(S)AS should give ustheJordan form ofA. Inf12]:= | SaTranspose [{{1,0,0},{0,2,1},{0,1,1}})7 Matrix¥orm(S] Out{12]= 100 @ .:: 0 1 2 Inf13]:= gaxtnverse[S] .R-87 NatrixPorm[aal Out{13]= 2 100 0 1 0 0 0 2 Lét's tryanother one. Infl4:= Clear [3,8] Inf15]:= Ba{{2,-1,2,0},{0,3,-1,0},{0,1,1,0},{0,1,-3/5}}; e Matrixrorn(B} Out{15]= 2of4 17172008 3:34 PM, Finding theJordan Canonical Form ofaMatrix bttp:/Avww.ma.iup.edu/projects/CaleDEMma/ICF /jcf5.html 2 1 2 0 0 3 -1 06 @ .::. a re Inf16]:= Bigenvalues [3] Out{16]= {2, 2,2,5) ‘You notice thatBhasarepeated eigenvalue. This does notnecessarily mean thatBdoes nothave a fullcomplement ofeigenvectors. Let's see. Inf17]:= Bigenvectors (B] Out{17]= {{1, 0,0,0}, (0, 0,0,Of, {0, 0,0,O}, {0, 0,0,1)} Notice thatbylisting aneigenvector of{0,0,0,0} twice, Mathematica is tellingyouthatBdoesnothaveafullcomplement ofeigenvectors. Wemustsearchfor2"generalized @ icccvectors" Inf18):= LinearSolve[B-2 IdentityMatrix(4] ,{1,0,0,0}] Out[18]= 2 {0, 1,a,-} 3 Let's keep going... Inf19]:= Lineargolve(B-2 IdentityMatrix(4],{0,1,1,/2/3}) Out[19]= 5 {o, 2,2,-} 9 ‘We now have our four vectors forthematrix S. eIn{20]:= SeTranspose [{{1, 0,0,0},{0,1,1,2/3},{0,2,1,5/9},{0,0,0,1}}17 30f4 1772005 3:34 PM. Finding theJordan Canonical Form of«Matrix htp:/ivww-mea.iup.edu/projects/CaleDEMma/CF jef5.html MatrixForm(S] eOut(20]= 1 0 0 0 o 1 2 0 o 1 1 0 205 °0393 Inf21]:= JB=aInverse[S] .B.8; MatrixForm[JB) Out[21]= 2 1 0 0 o 2 1 0 eo 0 2 0 0 0 0 5 UptoJordan Canonical Form : 4o0f4 1/7/2005 3:34 PM. - eTomLeinsterNotes PhL 12.19.04 These areexcellent notes onthesubject ofMinimal Polynomials andJordan Canonical Form. Def: anannihilating polynomial p(a) =0.Inthissection, think ofo=asquarematrixA.Sothis polynomial isliketheK(A) =0result oftheCayley-Hamilton theorem. Def: aminimal polynomial m(«) isshelowest degree poly thatdoes m(c) =0.Clearly, m(«) |p(a), which notation means thatmdivides evenly intop,noremainder. Ihave then stated Prop 2. Prop 1:every matrix o:hasexactly oneminimal polynomial. Proof issketchy, seems reasonable, ‘Onpage 2,hewrites theK(A) buthisnotation isza(t), Which isofcourse det(at -tI),secular. Ther'syou seehere arethealgebraic multiplicities. Theclaim isthattheminimal polynomial looks similar, buteach exponent issomething intherange (I,algmult), orashewrites it1<s)<1. Tam unsure how youwould show thatm(a) really isanannihilator. You have tobuild itandseeifitis zeroornot. That is,isthematrix m(«.) equal tothezero matrix? Itcertainly seems reasonable thatsuch a thing might exist thatisjustapiece ofK(a). [Inowknow howtofindm(a) foramatrix a,sothisisnot asconfusing asonfirst reading. ] Ifmatrix isdiagonal, thenm(q) =K(c.). This isbecause allpowers are1andyoucannot goanylower. e Lemma4isSylvester's trianglelawofnullity,andInowseethatKeristhewaysomepeoplesay Nullspace. Heactually proves thislawright insitu,butIignoretheproof. ‘How does heusethisLemma onthebottom ofpage 3?There arethree claims made atthebottom (1)thefirstlinesaysdim(V) =dimNullspace of(K(A)). Weknow thatK(A) =0from C-H, soweknowthatK(A)x=0forallxinV,sothatcertainlymeansthatthedimofthis nullspace isV,soOK. (2)Hereheissayingthatdim(V)islessthanthesumofthedimsofthe nullspaces ofeach factor, andthis isjustSylvester generalized tomanyfactors,sothisisfinetoo.ThinkoftheRHSasbeingdimN;+dimNz+etc=thesumofdimsofabunchofnullspaces. TheideahereisthatN(ABC...) cannotexceedthe sum ofthedimensions oftheindividual nullspaces. (3)Inthelastline,youcanjustre-express thisasdim(Nj®Nz ...)where youmake anewspace N= Ni@Ny ...byjustsuperposing theother nullspaces. Sodim(V) <RHS oflastline.Ithink inthecasethat ‘each nullspace hasdimension 1,which isthecasefordiagonalizable A,thenthe<isreally =because we areadding upNnumbers thatareall1. Still Iamconfused astowhat thepoint ishere. Itisthesentence stated atthetop,butIloseit. 1 Onpage4welearnthishiswordfor"similarity"is“conjugates, thisisthefirsttimeIhaveseenthis r) usage.M&Mcalledthemsimilarity ofcollinearity. Wearereminded herethatnearlyeverything is conserved under asimilarity, anditisjust likeachange ofbasis. Onpage 5wegetthedefinition ofaJordanblockandtheideathatwearegoingtowriteAinblock diagonal form which isadirect sum (Ithink Iconjectured thisdirect sum notation early onwhen first reading M&M, andhere itisintheflesh). Page 6then states theBigTheorem without proof: BigTheorem: Any matrix Acanbeconverted byasimilarity toJordan Canonical Form. Inthisform, youhavethedirectsumofblocks. Here arethekeyresults: (1)theeigenvalues areonthediagonal andeach eigenvalue appears anumber oftimes equal toits algebraic multiplicity. Thus must bethecasesince det(J -AI)=K(A) =theusual thing. (2)Adegenerate eigenvalue 21canhaveseveralJordanblocksofvarious sizes.Thesizeofthe largest block inthisgroup tellsyoutheexponent touseforthefactor (A.2)"intheminimal polynomial. (3)ThenumberofJordanblocksforadegenerate eigenvalue A,isthegeometric multiplicity ofthat2. Onpage 9wehave a6x6example, andhegoesthrough alltheabove items forthisexample. t)Warningisissued:eveniftwomatriceshowallinvariantsthesame,theymaynotbesimilarity conjugates. ‘Now back topage 6-7. (1)ThisJordan thing isMUCH stronger thantheSchur theorem which justsaysyoucantransform into upper triangular with some similarity. (2)Theblock structure isakintothenotion ofbreakinganumberintopowersofprimes. Exercise 1:Here welook atjustoneJordan block thatisdxdforsome 2.Thekeypoint Ilear here is thatthismatrix onlyhasoneeigenvector! Soithasgeomult =1byitsconstruction. That eigenvector is just(1,0,0..). Exercise 2:Here welook atthedirect sum ofjusttwoblocks CandD.Most things areobvious, butitem biswhere wehave something new. You want toconstruct theminimal polynomial forC®D. Suppose thesetwomatrix CandDhavethesameeigenvalue. Suppose KC(A) contains (4.-24)*andKD(A) has (A-Ai)?.Well,weknow theoverall K(A)willhave(A-41)*,butwhatabout theminpolm(X)? Eachof theabove factors hastodivide evenly intom(A) otherwise youcanshow thatmisnotaminpol.This is whywegetthenotion thatm=(2.-24)°because wecandoboth(A=Aa) Aa)?and(A=24)"(A=a)?withnoremainder, sowehavetotaketheMAXofthe twoexponents. 2 Exercise3:Nowwelookatanarbitrarysetofblocksallforthesame2.Weknowthateachblockhas e@ geo=1,soifthere aregblocks, then geo=g.Soboom, weseewhy thegeomult isthenumber ofblocks inthebigJordan formresult. Secondly, thepower intheminpolyisagain going tobethemaxofallthe powersof(A.-a1)foreachblocktogetthatcommondivisoreffectasabove.OfcoursenowK(A)haslotsoffactors, andthiscomment applies only tothefactor for2,anditsJordan blocks. Exercise 4:Now wegoouttothefullmatrix andstate thefinal results. Results arethesame, theyjust apply separately foreach A;manifold. MyComments: (1)Itwould benice toseeaproofofthebigtheorem. (2)1 don't understand why theminimal polynomial isimportant. 3 Z ‘ Minimal Polynomial and Jordan Form ‘Tom Leinster ‘Theideaofthesenotesistoprovide asummary ofsomeoftheresults you need forthiscourse, aswell asadifferent perspective from thelectures. Minimal Polynomial LetVbeavectorspaceoversomefieldk,andleta:V—+Vbealinearmap (gn‘endomorphism ofV"). Given anypolynomial pwith coefficients ink,there isonendomorphism p(a)ofV,andwesaythatpisanannihilating polynomial foraifpa)=0. v ‘Our first major goal istoseethat foranya,theannihilating polynomials caneasily beclassified: they're precisely themultiples ofacertain polynomial‘mq.Wereachthisgoalonthenextpage.Letussaythat apolynomial misaminimal polynomial fora(note:‘a', not‘th)ft e«mfa)<0 *ifpisanynon-zero polynomial with p(a) =0,then deg(m) <deg(p) «theleadingcoefficient ofmis1(ie.mismonic). (We don’t assign adegree tothezero polynomial. Note that thelast condition implies m#0.)‘We'dliketobeabletotalkabouttheminimalpolynomial ofa,andthefollowing result legitimizes this: Proposition 1Thereispreciselyoneminimalpolynomial fora. on, SketchProofEristence: Firstprovethatthereexists»non-zeroannihilatingpolynomial, esinyour notes (Singthefact that thespace ofendomorphisms onVisfinite-dimensional). Thereisthenanon-zeroannihilating polynomial, ok,Mofleastdegree,“and ifcistheleadingcoefficient ofMthen3Misaminimal:polynomial. Uniqueness: Suppose that mand m’aredifferent minimial polynomials. ‘Then m—m! isnon-zero byassumption, and isanannihilating polynomial. Butmandm’havethesamedegree, andeachhasleading coefficient 1,som—m!hasdegreelessthanthatofm.Thiscontradictsminimalityofthe/” degreeofm. 1 @ Lwillwritemafortheminimalpolynomialofa,Moreimportantthanthe ont? | factthatithasminimal degreeisthisresult(our“firstmajorgoal’): pone’iti ialp,pla)=;ayes8ope ee Proposition 2Foranypolynomialp,p(a)=0¢mal?anSidesPDam“ee Proof«iseasy.For=,weusetheresultyoumightknowas‘Buclid’salgorithm’ or‘the division algorithm’: there arepolynomials qand rsuch that P="Ma+Pandriseither0orhasdegreelessthanthatofma.Now, t(a) =pla) —g(a): ma(a) =0-0 =0, 80bydefinition ofminimal polynomial, r=0.Hence malp. / o ‘Youmightcomparethisresulttoasimilaroneaboutleastcommonmultiples: ifandbaretwonaturalnumbersand{theirleastcommonmultiple, thenwhatmatters most about !isnotthat it’s‘least? intheliteral sense oftheword, but that anumber isacommon multiple ofaand 6ifandonly ifitisamultiple of 1.Inother words, thecommon multiples areprecisely themultiples ofJ. Anexample ofProposition 2inaction: theCayley-Hamilton Theorem saysthatxa(a)=0,wherexqisthecharacteristic polynomialofa,andsowv conclude thatmalxa-a Fromnowon,let’sassumethatthefieldkweareworkingoveristhefield \, ofcomplex numbers, C.‘This makes lifemuch easier, because allpolynomials split into linear factors. Inparticular, wecanwrite e Xa(t)E(tAJP(E-ANwhereAi,..-,Ax atedistinctscalarsandrj>1foreachi.OFcourse,d1y..+)Xkarethedistinet eigenvalues ofa.7 ‘The bigtheorem concerning minimal polynomials, which tells youprettymucheverything youneedtoknowaboutthem,isasfollows: Theorem 3The minimal polynomial hastheform ‘taa(t)=(B=Ar)*+(t=Aa)* (+) forsome numbers a,with 1<4<1j. Moreover, aisdiagonalizable ifandonly ifeach 9=1. Lotsofthingsgointotheproof,Let’stakeitstepbystep. Firstofall,weknowtheCayley-Hamilton Theorem(itselfquitealarge/ result);andasobservedabove,thistellsusthatmahastheform(+)with7je,welX 8ST * 1 Secondly, weneed toseethat each s;>1,ie.that every eigenvalue isaroot oftheminimal polynomial. So,leti€{I,---k} andletvbeaA;-cigenvector. Foranypolynomialp,wehavep(a)v=p(AJv,andinparticularthisholds |forp=mg: hence ma(A;)u =0.But»isnonzero (being aneigenvector), s0 mal) =0,asrequired/ 2 Thirdly, suppose weknow that ais diagonalizable. This means ithasabasis | ofeigenvectors, whoseeigenvalues are\i,...,, allit’seasytocalculate that (t=) (t=Aa) isanannihilating polynomial fora.Sothis isthemlnimal polynomi Finally, then, wehave toshow that ifallthes;’sare1(ie. theminimal polynomial splits into distinct linear factors) then aisdiagonalizable. There's1proofofthiswhichIlikeandIbelieveisdifferenttotheoneinyournotes,so T'llwrite itoutinfull. Itgoes viaalemma: Lemma41fU2+V—2.Warefnite-dimensional vectorspacesandlinear1 maps,then S— Keune =DulagaceYdinKex(v9)<dimKer(y)+dimKE)RSivesleds LOW),MIR Proof Observe that Ker(728) =6-1(Ker(y)). (Byusing ‘8-? Iamnotsug- gesting that isinvertible; this isthenotation forthepre-image orinverse image ofasubsetunderafunction,asexplainedinNumbersandSets.) ‘Now, consider thefunction Bs B(Ker(y)) —+ Ker(), u aad Blu). Applying therank-nullity formula weget e dimB~(Ker(7)) =dimIm(6’)+dimKer("), andadding tothisourinitial observation andthefacts that Im(A’) <Ker(7) and Ker(") <Ker(@), thelemma isproved. o ‘The hard work isnow done. Supposing that allthes;are1,thecomposite ofthemaps voc yoe, aoa y is0.So dim(V) =dimKer((a— AiZ)e-+-0(a =Axl) SdimKer(a —Ay)+--+dimKer(a—AJ) =dim(Ker(a —4,1) ®--- @Ker(a —AxJ)), + where theinequality comes from theLemma (and aneasy induction), and the second equality isjustified bythefact that thesum oftheeigenspaces isadirect sum. Hence thesum oftheeigenspaces has thesame dimension asV,i.e.this sumisV,andaisdiagonalizable. : , aes Invariants van |‘When two square matrices areconjugate,yououghttothinkofthemasessen- tially thesame. It’sjustamatter ofchange ofbasis: if_B =P-!AP then A andBare‘thesame butviewed from adifferent angle’. (The change ofbasis, orchange ofperspective, isprovided byP.) Asimiler pointisthatthematrix ofalinearmapdepends onachoiceof basis; adifferent choice ofbasis gives adifferent butconjugate matrix. So,for instance, ifwewant todefine thetrace ofalinear endomorphism asthetrace ofthematrix representing it,then inorder forthis tomake sense wehave to checkthat trace(P~! AP)=trace(A) forany nxnmatrices A,P with Pinvertible. Afancy way ofputting this is‘trace isinvariant under conjugation’. Thethings which areinvariant under conjugation tend tobethethings which ‘areimportant. ‘So,what aretheinteresting ‘invariants’ oflinear endomorphisms (orsquare: matrices, ifyouprefer)?Certainly: ©theeigenvalues W ©their algebraic multiplicities “ ©their geometric multiplicities (i.e.thedimensions oftheeigenspaces) V «©thecharacteristic polynomialW e *theminimal polynomial. (infact, thecharacteristic polynomial tells you exactly what theeigenvalues and algebraic multiplicities are, soitwasn’t really necessary tomention them separately” Recallthatthealgebraic multiplicity ofaneigenvalue )isthepower of(¢—A)occurring inxq(t).) ‘Tothislistwemight alsoadd: ©the trace ~ the determinant .©theranky” ©thenullity. However, these four arealready covered bythefirst list. The trace ofanendo- morphism oofann-dimensional space is (-1)""1 (coefficient of™~?inxa(t)).¥ ‘Thedeterminant ofaisdet(a~0.1) =xa(0)Y The rank isnminus themulity; andthenullityisdimKer(a~0.1),whichis0if0isnotaneigenvalue, andisthegeometric multiplicity of0ifitisaneigenvalue,// 4 Moreover, alook attheminimal polynomial tellsyouataglance whether the matrix (ormap) isdiagonalizable—another important property, again invariant under conjugation. So,theconclusion isthat thecharacteristic polynomial, minimal polynomial andgeometric multiplicities tellyouagreat dealof interesting information about amatrix ormap, including probably alltheinvariants youcanthink of.Usuallyittakesanappreciable amountofworktocalculatetheseinvariants foragivenmatrix. Inthe next section, we'll seethat for amatrix inJordan canonical form they canbereadoffinstantly.‘Bewarnedthattheinvariants I'vementioned don’ttellyoueverything: thereexist pairs ofmatrices forwhich allthese invariants arethesame, and yetthe matrices arenotconjugate. Anexample isgiven inthenext section. 4/ Jordan Canonical Form Inthis section I'llmostly work with matrices rather than linear maps, just for achange. You should befairly happy about switching between thetwo modes ofthought. Tilstatethemaintheorem(theproofofwhichisoffthesyllabus),thenI'll trytoexplain what thepoint isandhow thefiner details work. First weneed some notation. Let A1,...,Am besquare matrices, and let A 0 0 0md rA=| 04” : ) 0 0 Am ‘hesquarematricesA;canbeofdiferentsizes;thysIfAris@nexm4matricthenAisanxnmatrix, wheren=n;+--++1%m¥The entries‘0’denotezero matrices ofthe appropriate sizes. For convenience, Iwill write the matrix on theright-hand side of(t)as AO Am.V Foranyd>1andcomplex number 4,letJbethedxdmatrix Al Al AL Je nok v Al Al a where alltheunmarked entries are0.This isaso-called Jordan block, (Note‘thatwhend=1,itisjustthe1x1matrix(A).) 5 ‘The bigtheorem is: ‘Theorem 5LetAbeasquare matrix ofcomplex numbers. Then there are natural numbers m,n1,...;fim 21andcomplex numbers pi1,-..Hm such that Aisconjugateto IL)B--@IKm), ) Moreover, ifAisalso conjugate to TP@--@sim? thenm!=mandthereisapermutationo€Smsuchthatforalli,wehave N= No(s) andHy=Hotty ‘Youarenotrequired toknow theproof. Amatrix oftheform (¢)issaid to bbeinJordan canonical form, orJordan normal form. The‘moreover’ partsays thattheJordan canonical formofamatrixiasunjqueasitpossibly couldbe:that is,unique uptopermutation oftheblocks.YThere’s noway itcould be genuinely unique, since foranysquare matrices C’andD(perhaps ofdifferent sizes), thetwomatrices C’@ DandD®C areconjugate. So,what’s thepoint oftheJordan canonical form? Here arethree answers: Anapproximation todiagonalizability Ifasquare matrix orlinear endo- morphism canbeputintodiagonal formthenitisveryeasytoworkwith, and onemight atfirst hope that every matrix isdiagonalizable. But this isn'ttrue.Aneasyexampleis e 01), oo}* itscharacteristic polynomial is#2,soitsonlyeigenvalue isOYbutthe cigenvalues ofadiagonal matrix aretheentries onthediagonal, sothe onlydiagonal matrix itmight beconjugate tois0.’However, theonly matrixconjugateto0ig0itself.¥, eon”So.noteverymatrixisdiagonslizable “Butwodolexbwthateverycom.yyw‘plexmatrix(square,a5usual)isTinnguladatte inchbanewasort of ‘approximation. The Jorden theorem isamuch, much more incisive state- ment than this. Ofcourse, every matrix inJordan canonical form isupper ‘triangular; infact, itlooks like # + # * # where theentries labelled +areany complex numbers, theentries labelled #areeither 0or1,and alltheunlabelled entries are0.(But notevery 6 matrix ofthisform isinJordan canonical form: exercise.) Insummary, wecanviewtheJordantheoremasbeingthenext-best thingtothestatement,feveryrmatrisidlagonalzable andha Ciagonalisable’,and't Instheadvantage ofbeingtrue Aconvenient way ofdisplaying invariants Earlier wediscussed theim- portant ‘invariants’ ofsquare matrices: those quantities which don’t changeunderconjugation (andcanthereforebeassignedtolinearendontorphisms).. Allltheones we(probably) know about can, eswesaw, bederived from thecharacteristic polynomial, theminimal polynomial andthegeometricmultiplicities oftheeigenvalues. GivenamatrixinJordancanonical form, thesecanbereadoffimmediately,withoutanyneedforcalculation.I'll JLshowyouhowtodothisinamoment, 4+ Like prime factorization Any natural number n>1isequal topip2-++Pm forsome sequence p1,...,Pm ofprime numbers; thissequence isunique, ut fortheobvious fact that theprime factors canbepermuted. This statement hasatlear resemblance totheJordan theorem, where theJor- * danblocks J(®play.the roleoftheprimenumbers, Theyarethe‘building locks’ ofsquare matrices, just astheprimes arethebuilding blocks of natural numbers. ‘This provides aneat way tothink about the theorem. Infact, there isa very general theorem which has asspecial cases both theJordan theorem andtheunique prime factorization ofnatural numbers, butthat’s way beyondthiscourse.(It'saresultfromthetheoryofringsandmodules: enamely, theclassification offinitely generated modules over aprincipal ideal domain.) Ipromised toshow you how lots ofinteresting invariants can beread off immediately from amatrix inJordan canonical form. T'lllead you uptothis ° via_a sequence ofexercises: 0 Exercise 1Showthatforanyd>1andA(¢C,thematrixJ{has:’ a YaAjasitsonlyeigenvalue K(A)=(A->S oN ve° ini i ¢ why? orf ys]= ./».minimal polynomial (t—4)}¢—Why7. ofla]|) Vv©.characteristic polynomial (t—)*,andthat icmultiplici i vayA/M V4.thegeometric multiplicity of\is1. . vi) “ale wy A\e Exercise2(Shorterthanitlooks.)LetCandDbeanysquarematrices. OFoyever vy&Show that {eigenvalues ofC@D}={eigenvalues ofC}U{eigenvalues ofD}. 7 Y,Showthatforanypolynomial p,p(C'®D)=0ifandonlyifp(C)=0and p(D) =0¥and deduce that mcgp|p ifandonly ifmclp andmplp. (Inan appropriate sense, mcg istheleast common multjple ofmgandmp.) ‘Then deduce thatforanycomplex number A, : 3 3egseuss GSee 3"=max(s,s!} A , , eaeswheresisthepowerof(t—A)occurring inmcep(t) (whenit’sbeen CASI (I4)writtenasaproductoflinearfactors),andsimilarly sformgands'for mp. Sc. Show thatxogp(t) =xo(t).xp(t)- Deduce thatforanycomplex number » Werte where r,r’andr”aredefined asintheprevious part ofthequestion, but with thecharacteristic polynomial instead oftheminimal polynomial. J4.Showthatforanycomplex number A, g=9+9 whereg!isthegeometricmultiplicity of\inC@D,andsimilarlygfor CandgforD.(If\isnotancigenvalue ofCthengisbydefinition 0: soinany case, g=dimKer(C —J). The same convention applies tog! andg”.) e Exercise 3Let\beacomplexnumber, let9,d1,...dy benaturalnumbers, andletA=J)6.--©J\*), Showthatforthematrix A, a.theonly eigenvalue is\ Yb. thepowerof(tA)inmaismax{dh,...,dy} Yc,thepowerof(t—2)inx4isdy++++d Jd.thegeometric multiplicity ofAisg. Exercise 4LetA1,...,Ax becomplex numbers, letd},...,d{*,...,dh,...df"benatural numbers (superscripts don’t indicate powers), andlet A= I) 6.00 0-08), Show that forthematrix A, a,theeigenvalues areAi,.-.,\e .thepower of(t—As)inmaismax{d},...,d%*} .thepowerof(t—4)inx4isdf+--++9" d.the'geometric multiplicity ofA;isgi. 8 can; e Let's re-express theresults ofthis final exercise. Itsays that given amatrix inJordan canonical form, *theeigenvalues aretheentries down thediagonal ©ma(t)=(t=A)"+++(t—Ak)*where9;isthesizeofthelargestA,-block {|inA(andtheA,’sarethedistincteigenvalues) ©xa(t) =(¢- Ar)" ++ (t—As)" where rjisthenumber ofoccurrences of 2onthediagonal |‘+thegeometric multiplicity ofAyisthenumber ofA;-blocks inA. ‘Thiscoversallthemajortheory,andifyou'vegotthisfarthenyoucanbepleasedwithyourself. Hereareareacoupleoffurtherpoints.Someofyouaskedmeforanefficientmethodofcalculating theJordanformofagiven matrix. The badnews isthat there isn’t onethat Iknow of.‘The good news, however, isthat forsquare matrices ofsize6x6orless, youcanwork out theJordan form bycalculating thecharacteristic and minimal polynomials and thedimonsions oftheeigenspaces. Forexample, suppose you're given a6x6 matrix and you calculate that itscharacteristic polynomialis(t-3)*(t~i)?, that itsminimal polynomialis(t—3)"(t—1)?, thatthe3-eigenspaceis3-dimensional, andthatthei-eigenspace is1-dimensional. Thenthediagonalismadeupof4 copiesof3and2ofi.Thereare3Jordan3-blocks,thelargestofwhichis2x2, which means that their sizes are2,1and1(since they addupto4).Similarly, there isjust one Jordan é-block, which is2x2.Sothe Jordan canonical form ofthematrixis r) 310000 030000 003000 000300 ooo0081 ooo0008 Asarathertediousexercise, youcanshowthatthislineofreasoningwill always tell you exactly what theJordan canonical form ofasquare matrix is when itisatmost 6x6. However, itdoesn’t always work forlarger matrices. For ‘example, suppose you're told that a7x7matrix has characteristic polynomial t?,minimal polynomial t°,andthat thedimension ofthe0-eigenspace is3.Then thematrix could beconjugate toeither one oftheJordan canonical forms eo, Wes? es, which arenotconjugate toeach other (bytheuniqueness part oftheJordan theorem). ‘The moral ofthis last example isthat ifyou have two nxnmatrices infrontofyou,thenevenifalltheinvariants youcanthinkofarethesameforJeach (eg. eigenvalues, rank, nullity, characteristic polynomial, trace, determi- nant, minimal polynomial, geometric multiplicities), itdoes notfollow that the matrices areconjugate toeach other. 9 ' e PlanetMath's ProofofJordan PhL 1.7.05 Guman's ProofofJordanDecomposition This guyisGuido Mauas, aStudent ofMathematics, Buenos Aires, Argentina. He"owns" thelittle chunk ofthePianetMath "encyclopedia". Inowregardthisjustasasummary ofthe detailed work that Matthews has done. Guido uses aastheb;,theexponents oftheminpoly. Theprimary decomp result isthen clearly stated. He then talks abouta"restriction" ofoperatorTtokerp°,justthewaythatMatthew's did(andthatIdoin mylater document onthissubject with Visio drawing). Hethenlooksatp:kerp’>kerp’,whichisalittledifferent fromwhatIhavedone,butOK.Welookforabasis forKerp*,thespace which hasalgemult ~a,Thebasis ofKp*iswritten astheunion of thebases oftheJordan cyclic subspaces. Each ofthese isgiven asB,;where i=overall eigenmanifold index,ands=thesecondary cyclicsubspace label.HewritesB,;aspowersofpactingonsomeassumedgenerating vectorwhichhecallsv,;.Theunionofthese iscalled justB;. Now finally wecome tothelastsection ofthis1pager proof. Author wants toshow directly that, given thecyclic basis above, wecanderive thattheJordan Block looks like. Iwill dothisinmyown language: (1)Definep=(T-AI)asusual.Writep"'=pp)=(T-A)p!. Thus,Tp=p"!+2pi, e (2)Wenowusethisresulttoevaluateourmatrixelements: Jy=<ptv|T|py> =<pkv|Tp=<pty|(pil+Ap)v=Sues+ABy : =Cytly=(C)ytywhichsaysJ=C™+AL. where Jamreferring back tomyPhL notes onthecompanion Cmatrix. The only difference isthat we haveCinsteadofC™.Sobasicallyourauthorhasderivedtheshapeofthe Jblock. Question :Ihavehadtoassumethat<p*v|p'v>=5,5.HowcanIverify this? Inacyclic subspace asgenerated byvector vwehavethisbasis: {v,pv,p’v,p’v...}.Thissubject is discussed (thank goodness) onpage 55ofMatthews. Well, thisisquite interesting. Intheentire Matthews presentation, wedeal only with vector spaces and theassociated notions ofspanning and linear independence. There isnonorm, nometric, noscalar product! Hehasnoneed forsuch things. Onpage 56when wewant toknow what thematrix looks like forouroperatorT,wefindthecolumnsofthe matrix simply byapplying theoperatortothevectorsofthe basis. Inthismanner, hefinds thecompanion matrix Cthatmatches theminpolofvector v. Solet'sgoback toourderivation above tothepoint where wehave: Tplv =plv+apy. p=(T-AD 1 ‘WenowfindthecolumnsofourmatrixTbyapplyingTtothebasisvectorsoneatatime.Wemakethis eassociation between basis vectors and column vectors: pv+[1,0,0,0]' p'v~»[0,1,0,0]" Then T(pV) =p'v +2p°v=[0,1,0,0}' +[2,0,0,0]'=[, 1,0,OF ‘Now once wemake theabove association, thenyes,wecansaythatunder thescalar product induced bytheassociated E°,ourbasisvectors areorthonormal, andthenwedohave<p*v|p!v>mo =8,j.But thisisnottheobvious scalar product thatyouwould getdirectly from E* <p*v|p'v>nw #[p*v]" [p'v]=v"(p)"py=somehugemessandnotjust8; ‘Ananalogous situation would betoimagine twounitvectors inE?thatarenotorthogonal. Thedirect E? scalar product would show non-orthogonality, butmy“induced” scalar product would show orthog. We arejustassociating each "position" inthecolumn vector with abasis vector. Idon't know what theofficial term fordoing thisis,Ihave used theword induced, maybe associated isbetter. 2 PlanetMath: proofofJordancanonical formtheorem http://planetmath.org/?op=getobj&from=objects&id=5709 (moreinfo}Function Decomposition [email protected] sas Math forthepeople, bythepeople. Encyclopedia |Requests |Forums|Docs"Sande|| Login AproofofJordan canonical formtheorem | (Proof) create newuser This theorem canbeprooved combining thecyclic decomposition theorem and theprimary decomposition theorem. Byhypothesis, thecharacteristicname:[—__] polynomial ofTfactorizes completely overF’,andthensodoestheminimal pass: [_______] polynomial of7”(oritsannihilator polynomial). Thisisbecause theminimal Ee) polynomial of7"hasexactlythesamefactorsonLX],asthecharacteristic forgetyourpassword? Solynomial of7’.Let'ssuppose thenthattheminimaYpolynomial ofT° MainMenu factorizesasir=(X—A1)™...(X—A,)*Vweknow:byteprimary sections - a:Encyclopaedia decomposition theorem, thatV=@jazker((T —A:)*") “LetTibetheime SisBooks restriction ofT'toker((T—A:1)*) ‘Weapplynowthecyclic Expositions: decomposition theoremtoeverylinearoperator meta (Qi— Add): ker(P —A.) ker(T —;1)°*_ weknow thenthat Requests (74) Orphanage (3) ker(T—A,2)**hasabasisBioftheformUnclass'd (1) Unproven(274)By=BisBosU---UBassuchthateachBssisoftheform eCorrections (72) Bag={eis(T—diana(P—As)?¥an--os(PAs)a}. talkbackPollsN Forums Let'sseethat7’ineachethie-"oyclic sub-basis" BsjisaJordanblock: Feedbackee Bug Reports ‘Simply notice thefollowing factabout thiepolynomials: X(X—r)) =(X-A)H 4X(K-AP- (X-A)H = loadsy=P+X(X-AY—6) Shapshols(X—a) 4(XX 4A)(K A: =(XK—aPP +A(X —a information —_—,andthenT(T—AT(vas)=(T—As)***(uns) +A(T—A)?(ve). Docs Clase:fcaien So,ifwealsonoticethat(7—At}&*Z*(v.;) =0,wehavethatT’inthisjews Legalese sub-basis istheJordanblock 4History 1aChangeLog Ai00.08Tene hat 1% 0.04 olds . 086 000.1 % So,taking thebasis B=Bi) Ba... UB, lof2 12/20/2004 11:12AM. PlanetMath: proofofJordancanonicalformtheorem bttp://planetmath org/?op=getobj&efrom=objects&tid=5709 ,wehave that 7’inthisbasis has aJordan form. e Thisformisunique(exceptfortheorderoftheblocks)duetotheuniqueness ofthecyclic decomposition. “proof ofJordan canonical form theorem" isowned (viewpreamble) Viewstyle:[HTMLwithimages,Ki)SREB This object's parent. Cross-references: decomposition, blocks, order, polynomials, Jordan block, cyclic, basis, linear operator, restriction, factors, annihitator polynomial, minimal polynomial, characteristic polynomial, primary decomposition theorem, cyclic decomposition theorem, theorem This isversion 4ofproofofJordancanonicalformtheorem,bomon2004-03-15, modified 2004-03-15. Object idis5709, canonical name isProofOfJordanCanonicalFormTheorem, Accessed 978 times total. Classification: AMSMSC:15A18(Linearandmuttiinearalgebra;matitheory:Eigenvalues, singularvalues,ande ‘igenvectors) Pending Errata andAddenda None. Discussion Style:[Threaded ifExpand: [1Order: [Newostfirstij]AE Nomessages. Interact rate|post|correct|updaterequest |addexample |add(any) : 20f2 1/7/2005 3:08 PM