07 applic

7 Various Applications of Rational Canonical Forms 7.1 An Application to commuting transformations THEOREM 7.1 (Cecioni 1908, Frobenius 1910) LetL:U7!UandM:V7!Vbe given LTs. Then the vector space ZL;Mof all LTsN:U7!Vsatisfying MN =NL has dimension sX k=1tX l=1deg gcd(dk;Dl); whered1;:::;dsandD1;:::;Dtare the invariant factors of LandMre- spectively. COROLLARY 7.1 Now takeU=VandL=M. ThenZL;Lthe vector space of LTs satis- fying NL=LN; has dimension sX k=1(2s2k+ 1) degdk: proof Omitted, but here's a hint: gcd(dk;dl) =dkifkl; i.e. ifdkjdl dlifk>l ; i.e. ifdljdk: N.B. LetPLbe the vector space of all LTs of the form f(L) :U7!U f2F[x]: ThenPLZL;Land we have the following. . . THEOREM 7.2 PL=ZL;L,mL= chL: 131 proof First note that dim PL= degmLas IV;L;:::;LdegmL1 form a basis for PL. So, sincePLZL;Lwe have PL=ZL;L,dimPL= dimZL;L ,degmL=sX k=1(2s2k+ 1) degdk ,s= 1 ,chL=mL: proof (a sketch) of Cecioni-Frobenius theorem. We start with the invariant factor decompositions U=sM k=1CL;uk andV=tM l=1CM;vl wheremL;uk=dkfork= 1;:::;s , andmM;vl=Dlforl= 1;:::;t . LetMN =NL. . . )MnN=NLn8n1 )f(M)N=Nf(L)8f2F[x]: Dene vectors w1;:::;ws2Vbywk=N(uk), and observe dk(M)(wk) =dk(M)(N(uk)) =N(dk(L)(uk)) =N(0) = 0: Then we have the Denition: LetWbe the set of all ( w1;:::;ws) such that w1;:::;ws2V and dk(M)(wk) = 08k= 1;:::;s: We assert that Wis a vector space and the mapping N7!(w1;:::;ws) is an isomorphism between ZL;MandW; proof is left as an exercise. 132 Now let wk=tX l=1ckl(M)(vl)k= 1;:::;s andckl2F[x]: N.B. f(M)(vl) =g(M)(vl) say ,Dljfg: So, if we restrict cklby the condition degckl<degDlifckl6= 0 (29) then thecklare uniquely dened for each k. Exercise: Now let gkl= gcd(dk;Dl): Then from the condition dk(M)(wk) = 0, show that Dl gkljckl (30) i.e. that ckl=bklDl gklbkl2F[x]: (31) Then the matrices [ ckl], wherecklsatisfy (30), form a vector space (call itX) which is isomorphic to W. Then in (31), (29)() degbkl<deggkl ifbkl6= 0: Clearly then, dimX= dimZL;M=sX k=1tX l=1deggkl as required. EXAMPLE 7.1 (of the vector space X, whens=t= 2) Say [deggkl] =2 0 1 3 : 133 ThenXconsists of all matrices of the form [ckl] ="(a0+a1x)
D1 g110
D2 g12 b0
D1 g21(c0+c1x+c2x2)
D2 g22# =a0D1 g110 0 0 +a1xD1 g110 0 0 +b00 0 D1 g210 +


. . . and so on. EXAMPLE 7.2 The most general 33matrix which commutes with others. LetA2M33(Q)such that there exists non-singular P2M33(Q)with P1AP =C(x1)C((x1)2) =2 41 0 0 0 01 0 1 23 5=J;say, whereC(p)denotes the companion matrix of p, as usual. ThenP= [u1ju2jT(u2)]whereT=TAand mT;u1=x1; mT;u2= (x1)2: AlsoV3(Q) =CT;u1CT;u2. Note that the invariant factors of Tare(xa)and(x1)2. We nd all 33matricesBsuch that BA=AB; i:e: TBTA=TATB: LetN=TB. ThenNmust satisfy N(u1) =Bu1=c11u1+c12u2 and N(u2) =Bu2=c21u1+c22u2 whereckl2Q[x]:(32) Now [deg gcd(dk;dl)] =1 1 1 2 so [ckl] =a0b0(x1) c0d0+d1x 134 wherea0etc.2Q, so (32) gives Bu1=a0u1+b0(x1)u2 =a0u1b0u2+b0T(u2) (33) Bu2=c0u1+ (d0+d1x)u2 =c0u1+d0u2+d1T(u2): (34) Noting that mT;u1=x1)T(u1) =u1 andmT;u2= (x1)2=x22x+ 1)T2(u2) = 2T(u2)u2; we have from (34) that T(Bu2) =c0T(u1) +d0T(u2) +d1T2(u2) =c0u1d1u2+ (d0+ 2d1)T(u2): In terms of matrices, B[u1ju2jT(u2)] = [u1ju2jT(u2)]2 4a0c0c0 b0d0d1 b0d1d0+ 2d13 5 i:e: BP =PK; say orB=PKP1: This gives the most general matrix Bsuch that BA=AB: Note :BA=ABbecomes PKP1PJP1=PJP1PKP1 ,KJ =JK: 7.2 Tensor products and the Byrnes-Gauger theorem We next apply the Cecioni-Frobenius theorem to derive a third criterion for deciding whether or not two matrices are similar. DEFINITION 7.1 (Tensor or Kronecker product) 135 IfA2Mm1n1(F)andB2Mm2n2(F)we dene A B=2 64a11Ba12B


a21Ba22B


.........3 752Mm1m2n1n2(F): In terms of elements, (A B)(i;j);(k;l)=aijbkl |the element at the intersection of the i-th row block, k-th row sub-block, and thej-th column block, l-th column sub-block.4 EXAMPLE 7.3 A Ip=2 66666666666664a11 ... a11


a21 ... a21


......3 77777777777775; Ip A=2 64A0


0A


.........3 75: (Tensor-product-taking is obviously far from commutative!) 7.2.1 Properties of the tensor product of matrices (i) (tA) B=A (tB) =t(A B); t2F; (ii)A B= 0,A= 0 orB= 0; (iii)A (B C) = (A B) C; (iv)A (B+C) = (A B) + (A C); (v) (B+C) D= (B D) + (C D); 4That is, the (( i1)m2+k;(j1)n2+l)-th element in the tensor product is aijbkl. 136 (vi) (A B)(C D) = (AC) (BD); (vii) (BC) D= (B D)(C D); (viii)P(A (BC))P1= (A B)(A C) for a suitable row permutation matrixP; (ix) det (A B) = (detA)n(detB)mifAismmandBisnn; (x) Letf(x; y) =mP i=0nP j=0cijxiyj2F[x; y] be a polynomial in xandyover Fand dene f(A;B) =mX i=0nX j=0cij(Ai Bj): Then if ch A=sQ k=1(xk) and ch B=tQ l=1(xl), we have chf(A;B)=sY k=1tY l=1(xf(k; l)); (xi) Taking f(x; y) =xygives chA B=sY k=1tY l=1(xkl); (xii) Taking f(x; y) =xygives ch(A InIm B)=sY k=1tY l=1(x(kl)); Remark: (ix) can be proved using the uniqueness theorem for alternating m{linear functions met in MP174; (x) follows from the the equations P1AP=J1andQ1BQ=J2; whereJ1andJ2are the Jordan forms of AandB, respectively. Then J1 andJ2are lower triangular matrices with the eigenvalues k;1km andl;1lnofAandBas diagonal elements. Then P1AiP=Ji 1andQ1BjQ=Jj 2 137 and more generally (P Q)1sX i=0tX j=0cij(Ai Bj)(P Q) =sX i=0tX j=0cij(Ji 1 Jj 2): The matrix on the right{hand side is lower triangular and has diagonal elements f(k; l);1km;1ln: THEOREM 7.3 Letbe the standard basis for Mmn(F)|i.e. the basis consisting of the matrices E11;. . . . . .;Emn and be the standard basis for Mpn(F). LetAbepm, and T1:Mmn(F)7!Mpn(F) be dened by T1(X) =AX. Then [T1] =A In: Similarly if Bisnp, and T2:Mmn(F)7!Mmp(F) is dened by T2(Y) =YB, then [T2] =A In (whereis the standard basis for Mmp(F)). proof Left for the intrepid reader. A hint: EijEkl=0 ifj6=k; Eilifj=k COROLLARY 7.2 LetAbemm, Bbenn, Xbemn, and 138 T:Mmn(F)7!Mmn(F) be dened by T(X) =AXXB. Then [T] =A InIm Bt; whereis the standard basis for Mmn(F). DEFINITION 7.2 For brevity in the coming theorems, we dene A;B=(A InIm Bt) whereAismmandBisnn. THEOREM 7.4 A;B =(A InIm Bt) =sX k=1tX l=1deg gcd(dk;Dl) where d1jd2j


jdsand D1jD2j


jDt are the invariant factors of AandBrespectively. proof With the transformation Tfrom corollary 7.2 above, we note that A;B = nullityT = dimfX2Mmn(F)jAX=XBg = dimfN2Hom (Vn(F);Vm(F))jTAN=NTBg and the Cecioni-Frobenius theorem gives the result. LEMMA 7.1 (Byrnes-Gauger) (This is needed in the proof of the Byrnes-Gauger theorem following.) Suppose we have two monotonic increasing integer sequences: m1m2


 ms and n1n2


 ns 139 Then sX k=1sX l=1fmin(mk;ml) + min(nk;nl)2 min(mk;nl)g0: Further, equality occurs i the sequences are identical. proof Case 1 :k=l. The terms to consider here are of the form mk+nk2 min(mk;nk) which is obviously 0. Also, the term is equal to zero i mk=n+k. Case 2 :k6=l; without loss of generality take k<l . Here we pair the o-diagonal terms ( k;l) andl;k. fmin(mk;ml) + min(nk;nl)2 min(mk;nl)g +fmin(ml;mk) + min(nl;nk)2 min(ml;nk)g =fmk+nl2 min(mk;nl)g+fml+nk2 min(ml;nk)g 0; obviously: Since the sum of the diagonal terms and the sum of the pairs of sums of o-diagonal terms are non-negative, the sum is non-negative. Also, if the sum is zero, so must be the sum along the diagonal terms, making mk=nk8k: THEOREM 7.5 (Byrnes-Gauger) IfAismmandBisnnthen A;A+B;B2A;B with equality if and only if m=nandAandBare similar. proof A;A+B;B2A;B =sX k1=1sX k2=1deg gcd(dk1;dk2) +tX l1=1tX l2=1deg gcd(Dl1;Dl2) 2sX k=1tX l=1deg gcd(dk;Dl): 140 We now extend the denitions of d1;:::;dsandD1;:::;Dtby renaming them as follows, with N= max(s;t): 1;:::; 1;|{z} Nsd1;:::;ds7!f1;:::;fN and 1;:::; 1;|{z} NtD1;:::;Dt7!F1;:::;FN: This is so we may rewrite the above sum of three sums as a single sum, viz: A;A+B;B2A;B =NX k=1NX l=1fdeg gcd(fk;fl) + deg gcd( Fk;Fl) 2 deg gcd(fk;Fl)g: (35) We now let p1;:::;prbe the distinct monic irreducibles in mAmBand write fk=pak1 1pak2 2::: pakrr Fk=pbk1 1pbk2 2::: pbkrr 1kN where the sequences fakigr i=1,fbkigr i=1are monotonic increasing non-negative integers. Then gcd(fk;Fl) =rY i=1pmin(aki;bli) i ) deg gcd(fk;Fl) =rX i=1degpimin(aki;bli) and deg gcd( fk;fl) =rX i=1degpimin(aki;ali) and deg gcd( Fk;Fl) =rX i=1degpimin(bki;bli): Then equation (35) may be rewritten as A;A+B;B2A;B =NX k=1NX l=1rX i=1degpifmin(aki;ali) + min(bki;bli) 2 min(aki;bli)g =rX i=1degpiNX k=1NX l=1fmin(aki;ali) + min(bki;bli) 2 min(aki;bli)g: 141 The latter double sum is of the form in lemma 7.1 and so, since deg pi>0, we have A;A+B;B2A;B0; proving the rst part of the theorem. Next we show that equality to zero in the above is equivalent to similarity of the matrices: A;A+B;B2A;B= 0 ,rX i=1degpiNX k=1NX l=1fmin(aki;ali) + min(bki;bli) 2 min(aki;bli)g= 0 ,sequencesfakig;fbkigidentical (by lemma 7.1) ,AandBhave same invariant factors ,AandBare similar ()m=n): EXERCISE 7.1 Show if if P1A1P=A2 andQ1B1Q=B2 then (P1 Q1)(A1 ImIn Bt 1)(P Q) =A2 InIm Bt 2: (This is another way of showing that if AandBare similar then A;A+B;B2A;B= 0:) 142