05 rational

5 The Rational Canonical Form Herepis a monic irreducible factor of the minimum polynomial mTand is not necessarily of degree one. LetFpdenote the eld constructed earlier in the course, consisting of all matrices of the form f(B); f2F[x], whereB=C(p), the companion matrix ofp. (We saw that if deg p=n, then Fp=fa0In+


+an1Bn1ja0;:::;an12Fg: Letf=f(B), wheref2F[x]. Then this new symbol has the following properties: (i)f+g=f+g;fg=fg; (ii)f=0,pjf; (iii)f=g,pj(fg); (iv)f1exists,pdoes not divide f. Note : Ifp=xc, thenFp=F. THEOREM 5.1 Nh;pbecomes a vector space over Fpif we dene fv=fv=f(T)(v): First we must verify that the above denition is well{dened, that is, independent of the particular polynomial fused to dene the eld element f. So suppose f=g. Thenf=g+kp; k2F[x]. Hence fv= (g+kp)v=gv+k(pv) =gv+k0 =gv; asv2Imph1(T)\Kerp(T) and consequently pv= 0. The four addition axioms hold as Vis already a vector space over F; The remaining vector space axioms then follow from the left F[x]{module axioms: (i) (f+g) =(f+g)v= (f+g)v=fv+gv=fv+gv; (ii)f(v+w) =f(v+w) =fv+fw=fv+fw; 105 (iii)f(gv) =f(gv) =f(gv) = (fg)v= (fg)v; (iv)1v= 1v=v. Remark: AnF{basis forNh;pwill be anFp{spanning family for Nh;p, but will not, in general, be an Fp{basis forNh;p. The precise connection between F{independence and Fp{independence is given by the following theorem: THEOREM 5.2 Vectorsv1; :::;vrform anFp{basis forNh;pif and only if the vectors v1; T(v1); :::; Tn1(v1) v2; T(v2); :::; Tn1(v2) ............ vr; T(vr); :::; Tn1(vr) form anF{basis forNh;p. COROLLARY 5.1 h;p= dimFpNh;p=1 degpdimFNh;p=(ph(T))(ph1(T)) degp: The exposition for p=xcnow goes over to general p, with small changes. We again have the decreasing sequence of dimensions: 1;p


b;p1; where1;p= dimFpKerp(T) =(p(T)) degp. Also 1;p+


+b;p=(pb(T)) degp; (24) wherepbkmT. There is a corresponding dot diagram where the number of dots in the h{th row from the bottom represents the integer h;p. We also have a similar theorem to an earlier one, in terms of the conjugate partition e1


e 1 of the partition (24) above, where =1;p= dimFpKerp(T) =(p(T)) degp. 106 THEOREM 5.3 Vectorsv1;:::;v 2Vcan be found with the property that pe11v1;:::;pe 1v form anFp{basis for Kerp(T). Moreover (i)mT;vj=pej; (ii) Kerpb(T) =CT;v1


CT;v . In conclusion, if mT=pb1 1


pbt t, we now have the direct sum decompo- sition V=tM i=1 iM j=1CT;vij; wheremT;vij=peij iand ei1=bi:::ei i form the conjugate partition for the dot diagram corresponding to pi. Here i=(pi(T)) degpi: TakingT{cyclic bases ijforCT;vij, then gives a basis =t[ i=1 i[ j=1ij forV. Moreover [T] =tM i=1 iM j=1C(peij i): The matrix on the right is said to be in rational canonical form . If instead, we take the following basis 0 ijforCT;vij 0 ij:8 >>>< >>>:vij; T (vij); :::; Tn1(vij) pi(T)(vij); Tp i(T)(vij); :::; Tn1pi(T)(vij) ............ peij1 i(T)(vij); Tpeij1 i(T)(vij); :::; Tn1peij1 i(T)(vij); 107 (withn= degpi) which reduces to the Jordan basis when pi=xci, it is not dicult to verify that we get a corresponding matrix H(peij i) called a hypercompanion matrix, which reduces to the elementary Jordan matrix Jeij(ci) whenpi=xci: H(peij i) =2 666664C(pi) 0


0 N C (pi)


0 0N


0 ............ 0


N C (pi)3 777775; where there are eijblocks on the diagonal and Nis a square matrix of same size asC(pi) which is everywhere zero, except in the top right{hand corner, where there is a 1. The overall eect is an unbroken subdiagonal of 10s. We then get the corresponding rational canonical form: [T]0 0=tM i=1 iM j=1H(peij i): Computational Remark: We can do our computations completely over F, without going into Fp, as follows. Suppose v1;:::;vrform anF{spanning family for Nh;p. Then we could, in principle, perform the LRA over Fpon this spanning family and nd an Fp{basisvc1; :::; vcR. A little thought reveals that if we had instead applied the LRA algorithm over Fto the expanded sequence: v1; T(v1); :::;Tn1(v1);:::;vr; T(vr);:::;Tn1(vr); we would have obtained the F{basis forNh;p: vc1; T(vc1); :::;Tn1(vc1);:::;vcR; T(vcR);:::;Tn1(vcR) from which we select the desired Fp{basisvc1; :::; vcR. LetA=2 66666641 0 0 0 0 2 1 0 0 0 2 1 0 1 0 0 2 2 2 0 1 0 1 2 0 0 0 1 1 1 1 0 0 0 0 13 77777752M66(Z3). HeremA=p2; p=x2+x+ 22F[x]; F=Z3. 108 p(A) =2 66666640 0 0 0 0 0 0 2 0 2 1 0 0 1 2 2 0 1 0 1 1 0 1 2 0 0 1 2 2 2 0 0 0 0 0 03 7777775; (p(A)) = 4; 1;p=(p(A)) degp= 2. p2(A) = 0; (p2(A)) = 6; 2;p=(p2(A))(p(A)) degp=64 2= 1: Hence we have a corresponding Fpdot diagram:
N2;p

N1;p We have to nd an Fp{basisp(A)v11forN2;pand extend this to an Fp{basis p(A)v11; v12forN(p(A)). AnF{basis forN(p2(A)) isE1;:::;E 6. Then N2;p=hp(A)E1;:::;p (A)E6i and the LRA give p(A)E2as anFp{basis forN2;pso we can take v11=E2. We nd the columns of the following matrix form an F{basis forN(p(A)): 2 66666641 0 0 0 0 2 1 0 0 1 1 1 0 1 0 0 0 0 1 0 0 0 0 13 7777775: We placep(A)E2in front and then pad the resulting matrix to get 2 66666640 0 1 1 0 0 0 0 0 2 2 0 0 1 2 0 1 2 0 1 1 2 0 0 1 2 1 0 1 2 1 1 0 2 1 1 0 2 0 0 0 1 0 0 0 1 1 1 0 1 0 0 0 1 0 0 0 0 1 13 7777775: The rst four columns p(A)E2; Ap(A)E2; E1; AE 1of this matrix form a LR F{basis forN(p(A)) and hence p(A)E2; E1form anFp{basis forN(p(A)). So we can take v12=E1. 109 ThenV6(Z3) =N(p2(A)) =CTA;v11CTA;v12. Then joining hypercompanion bases for CTA;v11andCTA;v12: v11; Av 11; p(A)v11; Ap(A)v11andv12; Av 11 gives a basis v11; Av 11; p(A)v11; Ap(A)v11;v12; Av 11forV6(Z3). Finally if Pis the non{singular matrix whose columns are these vectors, we transform Ainto direct sum of hypercompanion matrices: P1AP=H(p2)H(p) =2 66666640 1 0 0 0 0 1 2 0 0 0 0 0 1 0 1 0 0 0 0 1 2 0 0 0 0 0 0 0 1 0 0 0 0 1 23 7777775 Explicitly, we have P=2 66666640 0 0 0 1 1 1 0 2 0 0 1 0 1 1 2 0 0 0 0 1 1 0 2 0 0 0 1 0 0 0 0 0 0 0 13 7777775: 5.1 Uniqueness of the Rational Canonical Form Suppose that T:V!Vis a linear transformation over Fand thatis a basis forVsuch that [T] =tM i=1 iM j=1C(peij i): (25) where ei1:::ei i1 (26) andp1;:::;ptare distinct monic irreducible polynomials. We show that the polynomials piand the sequences (26) are determined by the transformation T. First, it is not dicult to show that =t[ i=1 i[ j=1ij; 110 where ij:vij; T(vij);:::;Tnij1(vij) andnij= degpeij iandmT;vij=peij i. Then we have the direct sum decom- position V=tM i=1 iM j=1CT;vij: Also if we write bi=ei1, we have Kerpbi i(T) = iM j=1CT;vij and hence V=tM i=1Kerpbi i(T): Then from equation (25) above, it follows that mT= lcmpeij i=pb1 1


pbt t; thereby determining p1;:::;ptup to order. Then it can be shown that if 1 hbi, thenNh;pihasFpibasis pei11 ivi1;:::;peijh1 ivijh; whereei1;:::;eijhare the integers not less than h. There are consequently dim FpiNh;pi=h;pisuch integers and hence the number of integers ei1;:::;ei iequal tohis equal to h;pih+1;pi, which depends only on T. In other words, for each i, the sequence ei1;:::;ei i depends only on T. 5.2 Deductions from the Rational Canonical Form THEOREM 5.4 (pbi i(T)) degpi=ai wherepai ijjchT, andpbi ijjmT. 111 Note that this determines bi|we may evaluate (ph i(T)) degpi forh= 1;2;:::until we get a value of ai. Then that h=bi. PROOF9a basis forVsuch that A= [T] =tM i=1 iM j=1C(peij i): So chT=tY i=1 iY j=1chBi;j where, for brevity, we write Bi;j=C(peij i). Hence chT=tY i=1 iY j=1peij i =tY i=1p iX j=1eij i =tY i=1p(pbi i(T)) degpi i as required. THEOREM 5.5 chT=mT,9 a basisforVsuch that [T] =C(pb1 1):::C(pbt t) wherep1;:::;ptare distinct monic irreducibles and b1:::bt1. Note that if ch A=mA(i.e.T=TAin the above), we say that the matrixAisnon-derogatory . PROOF 112 ( chT=tY i=1chC(pbi i)=tY i=1pbi i; mT= lcm (pb1 1;:::;pbt t) =pb1 1:::pbt t= chT: )Suppose that ch T=mT. We deduce that the dot diagram for each piconsists of a single column ofbidots, where pbi ijjmT; that is, dimFpNh;pi= 1 for h= 1;2;:::;bi: Observe that (ph i(T)) degpi2N; for it may be written hX j=1(pj i(T))(pj1 i(T)) degpi =hX j=1dimFpNj;pi2N: Then, for each i= 1;2;:::;t we have the following sequence of positive integers: 1(pi(T)) degpi<(p2 i(T)) degpi<:::<(pbi i(T)) degpi=ai: Butai=bihere, as we are assuming that ch T=mT. In particular, it follows that (ph i(T)) degpi=h forh= 1;2;:::;bi andh= 1 gives (pi(T)) degpi= 1 = i: So the bottom row of the i-th dot diagram has only one element; it looks like this: bi8 >< >:
...
113 and we get the secondary decomposition Kerpbi i(T) =CT;vi1: Further, if=11[


[t1, wherei1is theT{cyclic basis for CT;vi1, then [T] =tM i=1 iM j=1C(peij i) =tM i=1C(pbi i) =C(pb1 1):::C(pbt t) as required. THEOREM 5.6 mT=p1p2:::pt, a product of distinct monic irreducibles, if and only if 9a basisforVsuch that [T] =C(p1):::C(p1)|{z} 1times. . . . . . C(pt):::C(pt)|{z} ttimes: (27) Note : This is a generalization of an earlier result, namely that a trans- formation is diagonable if and only if its minimum polynomial splits into a product of distinct linear factors. PROOF (Assume9such that (27) holds. Then mT= lcm (p1;:::;p 1|{z} 1;:::;pt;:::;pt|{z} t) = lcm (p1;:::;pt) =p1p2:::pt: )AssumemT=p1:::pt. Thenbi= 1 fori= 1;:::;t (i.e. thei-th dot diagram has height 1) and 9such that [T] =tM i=1 iM j=1C(pi); aseij= 18i;j. 114 5.3 Elementary divisors and invariant factors 5.3.1 Elementary Divisors DEFINITION 5.1 The polynomials peij ioccurring in the rational canonical form of Tare called the elementary divisors ofT. Similarly the elementary divisors of a matrixA2Mnn(F)are the polynomials peij ioccurring in the rational canonical form of A. THEOREM 5.7 Linear transformations T1; T2:V!Vhave the same elementary divi- sors if and only if there exists an isomorphism L:V!Vsuch that T2=L1T1L: PROOF \only if". Suppose that T1andT2have the same elementary divisors. Then9bases; forVsuch that [T1] = [T2] =A: Then we have the equations T1=TA  T2=TA : Hence T11 =TA= T21 ; so 1 T11  =T2; or L1T1L=T2; whereL=1  is an isomorphism. \if". Suppose that L1T1L=T2. Then mT1=mT2=pb1 1


pbt t;say; also for all iandh, because ph i(T2) =ph i(L1T1L) =L1ph i(T1)L; 115 we have (ph i(T2)) =(ph i(T1)): Hence for each pi, the corresponding dot diagrams for T1andT2are identical and consequently the elementary divisors for T1andT2are identical. COROLLARY 5.2 LetA; B2Mnn(F):ThenAis similar to Bif and only if AandB have the same elementary divisors. PROOF Ais similar to B, 9Pnon{singular, with P1AP=B , 9Pnon{singular, with T1 PTATP=TB , 9Lan isomorphism, with L1TAL=TB: 5.3.2 Invariant Factors THEOREM 5.8 LetT:V!Vbe a linear transformation over F. Then there exist non{constant monic polynomials d1;:::;ds2F[x], such that (i)dkdividesdk+1for1ks1; (ii) vectors v1;:::;vs2Vexist such that V=sM k=1CT;vk; wheremT;vk=dk. Remark : Ifis the basis for Vobtained by stringing together the T{cyclic bases for each CT;vk, we obtain the matrix direct sum [T] =sM k=1C(dk): This matrix is also said to be in rational canonical form. PROOF 116 Lets= max ( 1;:::; t) and if 1itand i< js, dene eij= 0 andvij= 0, the zero vector of V. Now arrange the polynomials peij i;1it; 1jsas atsrectangular array: pe1s 1


pe11 1......... pets t


pet1 t Let d1=pe1s 1


pets t;:::;ds=pe11 1


pet1 t be the products along columns of the array, from left to right. Then d1;:::;dsare monic non{constant polynomials and d1jd2j


jds: AlsoCT;vij=f0gifvij= 0, soVis the direct sum of the following ts T{cyclic subspaces: CT;v1s


CT;v11......... CT;vts


CT;vt1 Then by Problem Sheet 5, Question 15(b), if we let v1=v1s+


vts;:::;vs=v11+


vt1; we havemT;v1=d1;:::;mT;vs=dsand CT;v1=CT;v1s


CT;vts ...... CT;vs=CT;v11


CT;vt1: Consequently V=CT;v1


CT;vs: DEFINITION 5.2 Polynomials d1;:::;dssatisfying the conditions of the above theorem are called invariant factors ofT. There is a similar denition for matrices: if A2Mnn(F)is similar to a direct sumsM k=1C(dk); 117 whered1;:::;dsare non{constant monic polynomials in F[x]such thatdk dividesdk+1for1ks1, thend1;:::;dsare called invariant factors ofA. So the invariant factors of Aare the invariant factors of TA. THEOREM 5.9 The invariant factors of a linear transformation T:V!Vare uniquely dened byT. PROOF Reverse the construction in the proof of the above theorem using Ques- tion 15(a) of Problem Sheet 5, thereby recapturing the rectangular array of elementary divisors, which in turn is uniquely determined by T. EXAMPLE 5.1 SupposeT:V!Vhas elementary divisors p2 1; p3 1; p3 1;p2; p2 2; p2 2; p4 2;p3; p3; p4 3; p5 3; p5 3: Form the rectangular array 11p2 1p3 1p3 1 1p2p2 2p2 2p4 2 p3p3p4 3p5 3p5 3 Then the invariant factors of Tare obtained by respectively multiplying along columns: d1=p3 d2=p2p3 d3=p2 1p2 2p4 3 d4=p3 1p2 2p5 3 d5=p3 1p4 2p5 3: THEOREM 5.10 Ifd1;:::;dsare the invariant factors of T:V!V, then (i)mT=ds; (ii)chT=d1


ds. 118 PROOF SupposeB= [T] =Ls k=1C(dk) is the canonical form corresponding to the invariant factors d1;:::;dsofT. Then mT=mB= lcm (mC(d1);:::;mC(ds)) = lcm (d1;:::;ds) =ds: Also chT= chB=sY k=1chC(dk)=sY k=1dk: We shall soon see that the invariant factors of a linear transformation or matrix are of independent interest. For example the invariant factors allow us to calculate the dimension of the vector space ZL;Mconsisting of all linear transformations N:U!Vwhich satisfy the equation MN =NL, where L:U!UandM:V!Vare given linear transformations over F. It turns out that there is a more direct way of nding the invariant factors ofT. To introduce this algorithm, we need to discuss an interesting equivalence relation on Mmn(F[x]), which in turn leads to the so-called Smith canonical form of a matrix over F[x]. 119