The Matrix Equation F(A)X - XA = O Citation Parker, Joseph A. Jr. (1976) The Matrix Equation F(A)X - XA = O. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/X6W2-T505. https://resolver.caltech.edu/CaltechTHESIS:04072017-144744158 Abstract In this work, all matrices are assumed to have complex entries. The cases of F(A) - XA = O where F(A) is a polynomial over C in A and F(A) = (A * ) -1 are investigated. Canonical forms are derived for solutions X to these equations. Other results are given for matrices of the form A -1 A * . Let a set solutions {X i } be called a tower if X i+1 = F(X i ). It is shown that towers occur for all nonsingular solutions of (A * ) -1 X - XA = O if and only if A is normal. In contrast to this, there is no polynomial for which only normal matrices A imply the existence of towers for all solutions X of P(A)X - XA = O. On the other hand, conditions are given for polynomials P, dependent upon spectrum of A, for which only diagonalizable matrices A imply the existence of towers for all solutions X of P(A)X - XA = O. Item Type: Thesis (Dissertation (Ph.D.)) Subject Keywords: (Mathematics) Degree Grantor: California Institute of Technology Division: Physics, Mathematics and Astronomy Major Option: Mathematics Thesis Availability: Public (worldwide access) Research Advisor(s): Taussky-Todd, Olga Thesis Committee: Unknown, Unknown Defense Date: 21 May 1976 Funders: Funding Agency Grant Number Caltech UNSPECIFIED Record Number: CaltechTHESIS:04072017-144744158 Persistent URL: https://resolver.caltech.edu/CaltechTHESIS:04072017-144744158 DOI: 10.7907/X6W2-T505 Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 10133 Collection: CaltechTHESIS Deposited By: Benjamin Perez Deposited On: 07 Apr 2017 22:41 Last Modified: 23 Aug 2024 22:43 Thesis Files Preview PDF - Final Version See Usage Policy. 11MB Repository Staff Only: item control page

THE MATRIX EQUATION F(A)X - XA = 0 Thesis by Joseph A Parker Jr. In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy California Institute of Technology Pasadena, California 1976 (Submitted May 21, 1976) ii ACKNOWLEDGMENTS I want to thank my wife Kathy for her love and encouragement. The topic of this thesis was suggested to me by my adviser, Dr. Olga Taussky Todd. I would like to thank her for her patience and the effort she spent on my work. I have enjoyed working with her. Finally, I would like to thank the California Institute of Technology for their financial support through research and teaching assistantships. iii ABSTRACT In this work, all matrices are assumed to have complex entries. The cases of F(A)X - XA = 0 where F(A) is a polynomial over ~ in A and 1 F(A) = (A*)- are investigated. Canonical forms are derived for solutions X to these equations. Other results are given for matrices of the form A -1 A*• Let a set of solutions {X.} be called a tower if X. 1 = F(X.). 1 -- 1+ 1 It is shown that towers occur for all nonsingular solutions of (A* ) -1 X - XA = 0 if and only if A is normal. In contrast to this, there is no polynomial for which only normal matrices A imply the existence of towers for all solutions X of P(A)X - XA = O. On the other hand, condi- tions are given for polynomials P, dependent upon the spectrum of A, for which only diagonalizable matrices A imply the existence of towers for all solutions X of P(A)X - XA = O. iv TABLE OF CONTENTS ACKNOWLEDGMENTS ii ABSTRACT iii •• INTRODUCTION CHAPI'ER NOTATIONS AND PRELIMINARIES 4 2 THE EQUATION A-*X - XA = 0 7 3 COSQUARES 18 4 THE EQUATION P(A)X - XA = 0 • . • • . 5 TOWERS IN P(A)X - XA = 0 REF'ERENCES • • • • • • • • • • • • • • • • • • • • • • • • • • 24 37 56 INTRODUCTION In this work, all matrices are assumed to have complex entries and all polynomials are assumed to have coe f ficients in the complex field. Many of the results hold for other fields, but no mention or use of this will be made here . This work originated from a study of the matrix equation ,1 • 1 ) where A and X are nXn complex matrices. This equation arose in the work of DePrima and Johnson [3] where it is shown that a matrix A is a cosquare, ie. A = B-1 B* for some matrix B, if and only if there exists a nonsingular solution X to (1.1 ). In the present investigation, all solutions of this equation are considered. In Chapter II, canonical forms are developed for solutions to (1 .1 ). It is also shown that if the condition of DePrima and Johnson is weakened to one requiring only the existence of a normal, singular solution X to (1.1) then there exist matrices B and C where B is a cosquare, but C is not a cosquare such that -1 * X - XB B = 0 and *-1 c x - xc = o. Thus it is shown that this weakened condition does not imply the existance of a nonsingular solution to (1 . 1) and that even if a nonsingular solution of (1 .1) exists, there may still be interesting singular solu- 2 tions to the equation. In the work of DePrima and Johnson [3] they study the matrices A and B where A = B-1 B* • In Chapter III we concentrate on all the non- singular solutions to (1 .1 ), including those solutions X such that * A= X-1 X. Included are spectral restrictions on solutions to (l .l) in the case that A is a cosquare and conditions on the set of all solutions to (1 .1) which imply that A is unitary or normal. In [1] Choi has the result that a cosquare A = B-1 B* is normal if and only if B2 is normal. In Chapter III we give another condition. In particular, the cosquare A is normal if and only if for each nonsingular solution X of (1 .1) it follows that X* -1 is also a solution of (1 .1 ). This result may be used to prove the result of Choi without the use of the Fuglede-Putnam theorem [9] which Choi uses. In light of the above theorem, the follow- ing problems arise. Consider the matrix equation 1.2) P(A)X - XA =0 where P is a polynomial. Problem 1 .3: For what polynomials P does the fact that the set of all solutions to (1 .2) is closed under the operation x~ P(X) imply that A is normal? In Chapter IV we develop the tools to attack this problem by giving canonical forms for the solutions to (1.2). gives spectral restrictions on such solutions. This chapter also This work is an exten- sion of the work of Drazin [5] who dealt with the equation 3 €AX - XA = 0 where € is a complex scalar. In Chapter V Problem 1 .3 is answered negatively. Theorem 5 .2 shows that there are no polynomials which satisfy the conditions of Problem 1.3. However, there are polynomials which satisfy the follow- ing revised problem. Problem 1 .4: For what polynomials P does the fact that the set of all solutions to ( 1 .2) is closed under the operation X ... P(X) imply that A is diagonalizable? We continue in Chapter V to give sufficient conditions on P, depending on the spectrum of A, in order that P satisfy Problem 1 .4. However, these conditions are shown to be not necessary. tions are given whi ch are necessary, but not sufficient. Other condi- 4 CHAPI'ER I NOTATIONS AND PRELIMINARIES The following definitions, notations and theorems are assumed in this work. Definition 1: Let A and B be square matrices, then the direct sum of A and B, denoted by A(±) B is the matrix Likewise, if A1 , ••• ,An are square matrices, then n @ A.1 = i::l Definition 2: n-1 @A. ( i=l ) i (±> A • n The Kronecker product of A= (aij) and B = (bij), denoted by A® Bis the matrix, C = (cij) = (aijB). Definition 3: The spectrum of a matrix A is the set of eigenvalues of A and will be written o(A). Definition 4: The matrix A is called a cosquare if there exists a * nonsingular matrix B such that A= B-1 B. Definition 5: (As used in [1 ]). The matrix A is called a block monomial matrix if A= (A .. ) is a block matrix with at most one nonzero block in each 1J row and column. 5 Definition 6: ... a A matrix of the form lr ~ ..• 0 or 8 0 1j ~rr rxk for k > r 0 · .. 0 akr kXr is called upper triangular Definition 7: The matrix A is called nonderogatory if the Jordan normal form of A contains only one Jordan block for each distinct eigenvalue of A. Definition 8: Otherwise, A is called derogatory. A set of solutions {Xi} is a tower starting with x1 for the equation F(A)X - XA = 0 if X. 1 = F(X.) for all i. l+ l -1 will be denoted by A-* Notation 1 : The matrix A* Notation 2: The nxn identity matrix will be denoted by I . Notation 3: The nxn matrix consisting of ones in the (i,i+l) position for i n = 1, .•• ,n-1 and zeroes elsewhere will be denoted by U. n Theorem 1 : The matrices A and B are similar if and only if A and B have the same elementary divisors. Theorem 2: , A is a cosquare if and only if A-1 is similar to A* . (see [3]). 6 Theorem 3: For given nxn matrices A and B, the map X ~ AXB, determines a linear transformation on the set of nxn matrices, that is, a vector 2 space of dimension n • 2 If the matrix Xis rewritten as an n x1 vector of its columns, then the matrix representative of this transformation T can be expressed as B ®A . Theorem 4: {see [10)). Given matrices A and B, mXm and nXn resp., then the equation AX - XB = 0 has a nontrivial solution X if and only if A and B have an eigenvalue in common. {see [10]). Theorem 5: The cosquare A = B-1 B* is normal if and only if B2 is normal. (see [1 J). Theorem 6: Let A be a nonsingular complex nxn matrix. 2 with A > O, ..• ,An > 0. values of AA* be A2 , ••• ,An 1 1 number. Let y be a nonzero Then the matrix is similar to a diagonal matrix and its eigenvalues are (see [16]). Let the eigen- 7 CHAPI'ER II THE EQUATION A-*X - XA = 0 In the work of DePrima and Johnson [3] properties are derjved for the matrices A and B where A = B-1 B* . If A = B-1 B* then it is clear that Bis a nonsingular solution of the equation (1 .1) A-*X - XA = O. In this chapter we investigate all solutions of this equation both in the case that A is a cosquare and in the case that A is not. We also deal with special subsets of solutions other than the set of solutions such that A = X-1 X* • Theorem 2.1: Let A be an nxn normal cosquare with distinct eigenvalues for i = k+ 1 , •.. , s. Then, X is a solution of ( 1 • 1 ) if and only if X is uni tarily similar by the similarity diagonalizing A to the form where dim X. =dim Y. = m., the multiplicity of A. in A, for i l. and dim X. l Proof: 1 l l = m.l for i = k+l, .•• ,s. = 1, ... ,k Otherwise, X. and Y. are arbitrary. l. l By the work of DePrima and Johnson [3], A a cosquare impli es that * = SA -1 S-1 A fo r some matrix S. --1 Thus if A. i s an eigenvalue of' A, t hen "- is also 8 an eigenvalue of A with the same multiplicity. Therefore, by a simultaneous unitary similarity of A and X, we may assume that A = l 'A ['1 I 0 omlr; \.1 I 0 k~ <±> Ak 1 I <±> • • • <±> 0 - -1 A I k + ~+1 (!) • • • As I m s ~ and x = for i, j [ xij] = i, ••. ,s where Xis partitioned according to the pa rtition of A induced by the direct sum representation given above . Since A -*X - XA = O, - -1 A. I l l 1) i i 2) - -1 A. I m. l J m. J [A jlmj] = x . . - X.. lJ lJ A.I l m. l = 1 , .•• , k and j = k+1, ••• ,s. A I ['i mi] 1 0 j m. X .. lJ - X. . lJ 0 J - -1 ;...j =0 rm. J for i =0 0 m. l 0 3) m. J = l, ••• ,k. -X. -1 . I for i j xlJ .. - xlJ .. X.. I 0 for i, j A I 0 m. = k+ 1 ' ... 's and j = 1 ' ... 'k. 0 9 [u ] 4) i m. l - x .. X .. lJ lJ [u J J m. J = 0 for i, j = k+ 1 ' ••. 's .. Furthermore, since the 1'.. are distinct for i l r j, the only solution of equations (1) - (4) is the zero matrix. If i = j, then equation (1) is satisfied if and only if xl..l = where X. and Y. have dimension m.Xm. and are otherwise arbitrary, and l l l l equation (4) is satisfied for any arbitrary X. .• ll Therefore, Xis transformed into the required form. Conversely if A is diagonal end X is in the form derived above A-*X - XA = 0 by the derivation above. Therefore, if U is eny unitary matrix (uxu* ) (UAU* ) = o. * Thus, UXU* is a solution of (1.1) for UAU. Theorem 2.2: Let A be an nxn complex, nonsingular matrix with distinct ~-1 --1 eigenvalues A. 1 ,t.. 1 , .•• ,A.k,A.k ,>-.k+l'''''""s'"-s+l'''"'A.t where for i I A.i I f. 1 = 1, ••• ,k, and lt..il = 1 for i = k+l, ... ,s, and A.s+l''" ' '""t not covered by the previous two cases. Then if Xis a solution of (1 .1 ), Xis congruent to 10 where zi] o [ k x, = @ Y. i=l l 0 where Y. and Z. are of dimensions p.Xm. and m.Xp. respectively with l l 1 l 1 - -1 mi and pi being the multiplicities of Ai and Ai 1 in a(A) respectively, s (±) i=k+l z.1 where the Z. are of dimension m.Xm., and [O] is of the proper dimension. l Proof: l l Let S transform A* into the direct sum of Jordan blocks t = .~ (Y.i I n. + Un. ) l=1 l l * where the Y. are the eigenvalues of A, not necessarily d isti nct. l 2 Then, considering X as an 1xn vector x of its columns, the equati on X - A*XA = 0 can be rewritten via Theorem 1 as Following the treatment of Davis [2], where 11 - -1 @ S-1 ) x corresponds to ( 8 - -1 )X( 8 - - 1 )*. and ( S Thus, it is sufficient to consider equivalently t t + U T]. X = [@Y.I + U )X((t)Y.I . 1 1 n. n. . 1 i n n. 1 l= 1 1 l= i Let X = (X .. ) be a partition of X corresponding to t he Jordan normal lJ form of A. Then, X . . = B.X .. B. * lJ 1 lJ J where B. = y .I 1 1 n. 1 We may assume that the Jordan blocks of A are ordered according to the distinct eigenvalues of A and that the blocks corresponding to pairs A. 1 --1 and~. 1 are adjacent. In otherwords, we may partition A into the form k k (Ef)B . )Ef)( (±) B.) ·11 1= " k l= + ll where B.1 Bi 1 0 0 Bi2 = 1 for i = 1, ••. ,k such that o(B. 1 ) ='A. and o(B. ) = }:~ . l l l2 1 12 Partition X = (Xij) according to the Bi. i ~ j as in Theorem 2.1. Then, Xij = 0 for Now partition each X.. according to the 1.1. natural partition of B., 1. x1.1. .. = Then * (1 ) * (3) B . A .. B. 1. 1 1.1. l. 1 *1. 1.1. 1. B.X .. B. = B. A .. B. 1.2 l.1. 1. 1 * (2) * (4) B. A .. B. l. 1 l.1. 1. 2 B. A .. B. l. 2 l.1. 1.2 Thus X - A*XA = 0 implies that x~'.) and X~~) = 0 for i 1.1. 1.1 = 1, •• • ,k. Therefore, X is congruent to the desired form. Theorem2.3: There exists a nonsingular, normal matrix X satisfying ( 1 • 1 ) if and only if A is uni tarily similar to a kxk block matrix A= (Aij) where k is the number of distinct eigenvalues A , ••• ,\k 1 of X and the dimension of A .. is the multiplicity of \. , and letting 11. l A-*= (Bij) for i,j = 1, ••• ,k be a conforming partition of A-* with Y.. 1.J = \,/\j for i,j = 1, •.• ,k. l Furthermore, the above similarity diagonalizes the nonsingular, normal solution X. Proof: Assume that there exists a nonsingular, normal solution X of (1 .1 ) . Then, by a unitary transformation of A and X, the matrix X may 13 be assumed to be in diagonal form with the eigenvalues of X ordered such that equal eigenvalues are adjacent on the diagonal. Partition A and A-* according to the blocks of equal eigenvalues in x. Let A = (Aij ) and A-* = A 1) Then ( l . 1 ) implies -*D-DA=O where A and D are the transformed A and X respectively. Thus A . . = ;\ ,/;\ .B . . 1J J ]_ 1J where A.]_ for i = 1, •.. ,k is the ordering of the eigenvalues of X given by the particular unitary transformation. Conversely, let k X= @;\.I . 1 l.= i m.]_ with ;\i distinct and nonzero for i = 1, ..• ,k. block matrix form of the theorem. Then, Let A be in the kXk -*X - XA = O. A If U is any unitary matrix, then * where A = UAU* and x,= uxu. 1 Theorem 2.4: Furthermore, x,is normal. There exists a normal, singular matrix X satisfying (1 .1) if and only if A is unitarily similar to 14 where A and A are square, nonsingular matrices and the dimension of 1 4 A is the nullity of X and A-* is simultaneously similar to 4 -* A-* = where A-* is partitioned as A. Al B2 0 A4-* Here A and A-* have the same structure 1 1 as A and A-* in Theorem 2.3 with respect to the nonzero eigenvalues of X and A and A-* correspond to the zero eigenvalues of x. 4 4 In addition, and Furthermore, the above similarity diagonalizes x. Proof: The proof of Theorem 2.4 follows that of Theorem 2.3 until equation (1 ) A-*D - DA = O. D = ( In this case, ~\.I ) i=l 1 mi Let A= 0 @ [o] = [Dl0 oJ1. 15 and A be partitioned as D. -* = Thus A-*D - DA = 0 implies that B D - DA = 0 1 1 1 1 1) =0 2) 0 - D1A2 3) B3D1 - 0 = 0 4) 0 - 0 = o. Equations (2) and (3) give the correct zero blocks in A and -* , and the dimension of A A 4 is the multiplicity of 0 as an eigenvalue of X. Furthermore, A*A-* = A-*A* = I. Thus A-* = where and =0 Then (1) and the fact th~t B1 = A1-* implies 16 -* have the same structure as A and A -* in Theorem 2.3 Thus A1 and A1 for the nonzero eigenvalues of x. Conversely, let X = ~ ( . 1 f-.I ) l. m. l.= with all t-. distinct and nonzero for i l. matrix form of the theorem. <±) [o] l. = 1, ••. ,k. Let A have the block Then, A -*X - XA = O. If U is any unitary matrix, then where ~ = UAU* and ~ = UXU* • Corollary 2.5: Furthermore, X is normal and singular. Let X be a normal, singular matrix satisf'ying equation (1 .1) for some matrix A. Then there exist matrices Band C such that B-*X - XB = 0 and c-*x - xc = 0 with B a cosquare, but C not a cosquare. Proof: In Theorem 2.4, let A and B be zero matrices. 2 3 Choose 17 with A1 and A4 cosquares. Then -*X - XB = 0 B and B is a cosquare. Choose u* with A a cosquare and A nonsingular, but not a cosquare. 1 4 c-*x - xc = 0 but C is not a cosquare. Then 18 CHAPrER III COSQUARES The aim of this chapter is to apply the results of Chapter II to the special case of solutions X such that A = X-1 X* • Notice that this is a nontrivial restriction since for a cosquare A, there are 1 * always solutions Y of (1 .1 ) such that Ar Y-1 Y. This is easily seen since in (1 .1) the set of solutions is closed under scalar multiplication, but the set of all matrices X such that A = X-1 X* is not closed under scalar multiplication. Theorem 3.1 is a special case of Theorem 2.1. This result is then used to derive spectral restrictions for the components of a cosquare. Theorem 3.1: Let N = A-1 A* then N is normal if and only if A is unitarily similar to k (±) i=1 0 Yi Bi s (±) B.* ]. (±) i=k+l qi.I 1 m.]. 0 where B. is a nonsingular matrix for all i, and 'V. all distinct and l l Yi and tfli nonzero for all i. Proof: By the work of DePrima and Johnson [3], N =A -1 A* implies * = SN -1 S-1 for some matrix S. Thus if Y is an eigenvalue of N, N __ then y , is an eigenvalue of N with the same multipl i city. Therefore, 19 since N is normal, N may be assumed, by a unitary similarity, to b e of the form 0 ® ... ® 0 ® Sk l I + --1 Y1 I ml with y, ands. all distinct and IY.l ~ 1 and ls.I l 1 l ll\+1 ® . . . (f) s I s ms = 1. l Notice that A-1 N-* = NA -1 , thus -1 by Theorem 2.1. -1 Furthermore, N A = A-* Therefore, B.* = y -1 . A. l * -1 for i = 1, •.. ,k and ~i Ai= Ai for i = k+l, .•. ,s. Thus A- l 1 l is unitar- ily similar to k ® i=l [ -1 0 <±l q). I * A.l <±l i=k+l mi s y. A. l l 0 -1 l 1 ....J where coj = ~/sj and, A is unitarily similar to k © i=l -* Y.A. l l 0 s (f) -1 A.l Conversely, let 0 (f) i=k+l ~.I · 1 m. 1 UAU* be of the form required by the theorem . 20 Then UA = _, AU * * = (UAU* ) _, (UAU* ) * = :] i~l - _, -] ( k .(£) 1=1 [ y -1 [ ( y.B. Y.I = B.1 k (±) i=l l s (±) i=k+ 1 <±> 0 l (£) i=k+l (£) * Bi 0 l s 0 1 l x m.l $ i I m.l = 0 m. s (!) i=k+l l (±) 0 ~~'r ) -1 Y.i I m. <pk+l <pk+l l Therefore, A -1 A* = N is normal. Corollary 3. 2: r -y-1 y Then -y-1 ~ F a ( N ) = l y 1 ' 1 ' •• • ' k' k '-;,k+ 1 ' • .. ' "" s 1) where Let N = A-1 A* be normal~ } ls.I = 1 for i = k+l, • • • ,s and l 2) where j = 1 , ••• , m.l and A. lJ . • E R+ for i = 1 , ••• , k and j = 1 , •.. , m . . J Proof: Part (1) follows from the work of DePrima and Johns on [ 3]. Part (2) follows f rom the theorem and Lemma 3. 5 of Thompson [16) (s ee Th eorem 6 of chapter 1 above). The final two theorems of this chapter give nec e ssary and suff i cient condit i ons for a cosquare to be normal or unitary in t erms 21 of the set of solutions of (1 .1 ). Theorem 3.3: Let O = ( X: X-1 AX =A -* ). Let A be a cosquare. Then the following are equiva lent. 1) A is unitary. 2) There exists a pair of matrices S and S-1 S* E O. 3) For each S E O, the matrix S-1 S* E O. Proof: Clearly, if either of (1) or ( 3 ) holds, then (2) holds. -* = SAS -1 then Conversely, let A A = S-1 A -*S and A = S-*A-*S*• Thus A-* = S*AS -* and A-* = SAS -1 . Therefore * -* = SAS -1 S AS or 1 Therefore, if A-*= s- 1s A(s- s*)-l, then A-*= A and A is unitary . In otherwords, if there exists a single pair S and S-1 S* E O t hen A is un i tary. Therefore, (2) ~ (1 ). Let TE Obe another matrix. Then th e above argument shows t ha t T -1 * = AT -1 T* 'f A or T -1 * T A(T -1 * -1 = A. T ) 22 However A is unitary. Thus T-1 T*A(T-1 T*)-1 = A-* and T-1 T* E O. Therefore, (3) holds. Let A = B-1 B* Theorem 3.4: Let 0 = ( X: X-1 AY.. = A-* } • Then the following are equ i valent. Proof: 1) A is normal. 2) . norma 1 . B2 is 3) For each X E G, the matrix X-* E O. (1):;. (3). Taking the * ture required by Theorem 2.1. -1 of a solution preserves the struc- Therefore, for each XE O, the matrix X-* E (). (3) ~ (2). ti on of ( 1 • 1 ) • Since B is a solution of ( 1 • 1 ) , B-* is also a s olu- Therefore, (B*B-1 ) B-* - B-*( B-1 B*) = 0 or ( B*)2 B-1 - B-1( B*)2 = O. Thus B(B* )2 - (B* ) 2 B = O. 2 Therefore, B i s normal. (2 ) ~ (1)• From Choi [ 1 ] • 2 Choi [l] shows that A i.s normal if and only i f B i s normal. In his proo f he applies the Fuglede-Putnam theorem [9] to show that 23 (1) ~ (2). Theorem 3.4 gives an alternate proof of this result in the finite dimensional case without the use of the Fuglede-Putnam theorem [9]. 24 CHAPI'ER IV THE EQUATION P(A)X - XA = 0 The aim of this chapter is to develop decomposition theorems like those of Chapter II for the matrix equation P( A )X - XA = 0 1.2 ) where P is a polynomial. These results will be us ed in Chapter V to prove an analogue of Theorem 3.4. tions for solutions of (1 .2). We also develop spectral restric- In all of these theorems, we will assume that there exists a nonsingular solution of (1 .2). As a result we will use the following lemma. Let A be a matrix, P(X) a polynomial such that equation Lemma 4.1: (1 .2) has a nonsingular solution. Then P(x) is a one - to - one mapping of cr(A) = tA.: i=l , ••. ,sand A. distinct} onto itself. In par1 l ticular, if P(Ai) = Aj then the multiplicity of Ai equals the multipl i city of Aj' and the Jordan normal forms of A and P(A) are the same . If P(A)X - XA = 0 has a nonsingular solution, then P(A) and A Proof: are similar. Therefore, (P(Ai): i=l , ... ,s} = tA.: i=l, ... , s} i nclu1 ding multiplicit i es. Theorem 4.2: Furthermore, the Jordan normal form is preserved. Let A be a diagonalizable matrix, P(X) a polynomial such that equation (1 .2) has a nonsingular solution and cr(A) = tA .: i=l , . . . , s} l wi th A. distinct and the multiplic j ty of A. being m.. 1 l l Let a be a per- mutation of 1, ... ,s defined by P(A.) =A(')' with cycl e decomposition 1. a .• •ak. 1 a i Assume that the eigenvalues of A are numb er ed accor di ng 25 to this cycle decomposition. Let S be a similarity which diagonalizes A and preserves the ordering of the eigenvalues, A1 , ••• ,As. Then X is a solution of (1 .2) if and only if SXS -1 is some block monomial matrix corresponding to a with diagonal blocks of dimension m.• l Proof: The assumption that A is diagonalizable implies that, by a similarity S, the equation P(A)X - XA = 0 may be reduced to P(D)Y - YD = 0 where Y = SXS -1 and D is a diagonal matrix of the eigenvalues of A with eigenvalues arranged according to the ordering A , ..• ,As· 1 Partition Y into a block matrix (Y .. ) and D into (D.) according to the blocks of lJ equal eigenvalues in D. l Thus P(D)Y - YD = 0 implies P( A. )Y .. - Y .. /.. l 1J 1J J for i, j = 1 , ••• , s. and i,j = 1, .•• ,s. =0 Therefore, Y.. = 0 for P(A . ) ft.., ie. j 1J l J f a(i) This is the desired form for Y and results in the desired form for x. Notice that the particular form of S is not used. Therefore, any similarity of this type results in the same decomposition. Conversely, if Y.. = 0 for j lJ f a(i) and i,j = 1, ••• ,s, then P( A . )Y. . - Y .. /. . = 0 1 for i,j = 1, ••. ,s. 1J 1J J Therefore, P(D)Y - YD= 0 and hence P(A)X - XA = 0 26 -1 where X = S DS for some matrix s. Theorem 4.3: Let A and P(A) be as in Theorem 4.2 except that A is not assumed to be diagonalizable. Let S be a similarity transforming A into Jordan normal form and arranging the Jordan blocks according t o Then X is a solution of equation (1 .2) if and only if SXS -1 = = (Y.) is a block monomial matrix corresponding to a with diagonal l blocks of dimension m., and l P( A . )Y. - Y. A . = 0 1 for a(i) ~ j. l lJ Here A. is the submatrix of the Jordan normal form of A l consisting of the direct sum of the Jordan blocks corresponding to the eigenvalue A. •• l Proof: Let P(A)X - XA = o, then SP(A)XS-l - SXAS-l = 0 or (SP(A)s- 1 )(sxs- 1 ) - (sxs- 1 )(SAS- 1 ) = o. Therefore, A may be assumed to be in Jordan normal form with eigenvalue blocks arranged according to the ordering t.. 1 , ..• ,A.s. a corresponding block diagonal form. P(A) will be in Partitioning A = (A.) and Y = (Y.j) l l according to the blocks of equal eigenvalues in A implies that 27 = 1 , ••• , s . f or i, j Then, Y.. 1J = 0 for a(i) /= j, since in this case P(A.) 1 and Aj have no eigenvalues in common. Conversely, i. f Y is a block monomial matrix corresponding to ~, he permutation a and P(Ai)Y . - Y.A. = 0 1 ror a( i) = j where i, j J 1 = 1 , •.. , s then P( A)Y - YA = 0 and thus P(A)X - XA = 0 where X = S -1 YS. In (1 5 ], Taussky-Todd investigates the connection between equat ion 1 .2 and Galois theory. The following example illustrates this c onnection. Example: Let s be a seventh root of unity, then s satisfies: x !tu rthermore, a 1 6 + x 5 + x 4 + x 3 + x2 + x + 1 = 0. = s + ~ will satisfy: f(x) = x 3 + x 2 - 2x - 1 = 0 and there exist rational polynomials p (x) and p (x) such that f(x) has 1 2 r oots a , p (a ) , and p (a ) where 1 1 1 2 1 p (x) 1 = x2 - 2 and p (x) and p (x) act as cyclic permutations on the roots of f(x). 1 2 if A is any 3X3 matrix with characteristic polynomial f(x), then by the above theorem p.(A)X - XA = 0 has solutions X where 1 Thus 28 -1 s.xs. 1 1. = 0 xl 0 0 0 x2 x3 0 0 and -1 S.AS.1 1 = al 0 0 0 Pi (al ) 0 0 0 p.(p . (al )) 1 1 with x , x and x arbitrary, i=l,2. 1 2 3 We will now derive spectral restrictions for the solutions of equation (1 .2). Lemma 4.4: For this we need the following lemma. Let A= (A .. ) be a block monomial matrix corresponding to 1.J a cyclic permutation. Let the diagonal blocks of A be square of dimension n. for i=l, ••• ,s. Then 1 s-1 - ( fl A. i=l Proof: . l )A l ) • 1,1+ By a similarity transformation, we may replace A by 0 A12 0 0 0 A' = SAS -1 0 = 0 A s-1 , s Asl 0 0 s 29 Then A.I nl -A12 0 0 0 AI - A' = 0 -A s-1, s 0 -A sl 0 0 A. I n s Multiplying on the right by I nl O 0 0 0 0 0 gives I n s 30 AI -A12 nl 0 0 0 IA.r - A 'I ::;: 0 0 (1 ) -A s-1 , s -Asl 0 0 1 where -A( )::;: _,_-l A A • s1 s- 1 ,s s 1 ).I n s Notice that the (s-1 )x(s-1) principal submatrix of the right hand side is an (s-1 )x(s-l) block matrix of the same type as Al - A. Therefore, Al n1 -A12 0 0 0 l).I-Al:::: 1~1 ns I 0 -A 0 -A ( 1 ) 0 sl 0 Iterating this procedure s - 2 times yields n+n = A. s s- 1 + ••• +n 3 AI s-2,s-1 n s-1 31 ( s-2 ) , -( s-2) h were - Asl = -h s-2 Il (A. l . ) A • Multiplying i=1 1+ '1+2 s1 -A 12 -A{s-2) s1 on the right by 0 gives /..I n1 - A 12 X. - l A( s- 2 ) -A sl 12 = -A(s-2) 0 sl Therefore, n +n _ + ••• +n n 1 3 A 2 I AI s = As n +n = As s- 1 + ••• +n 2 I A.I A ( s-2) I 12 s1 - A. -1 A nl - t... -s+l s-1 n A .. i=1 1,1+ 1 nl = A s1 I= s-1 Il A . . 1 . 1 l.= Lemma 4.5: and ;., 2 Let A and B be txt l.,l.+ Jordan blocks for the eigenvalues ;., 1 respectively. Let P(x) be a polynomial such that P(A. ) = A. • 1 2 Then X = {x .. ) is a solution of P(A)X - XB = 0 if and only if X satislJ fies the following. for i Proof: 1) X is upper triangular. 2) X .. = P'(>, )X. 3) xi,i+ .. j 1 ll . 1+1 ,i+ 1 fori=1, ••. ,t-1. = 1 , ••. , t-1 and j = 1 , ••• , t- i-1 • Let J j be the matrix consisting of all zeroes except for ones on the jth upper diagonal. Then Thus P(A)X - XB = 0 implies ••• + P(t-l )P·1) (t+l)! =0 or Comparing the entries of the matrices on the left and right hand sides row by row, starting with the last row and working up, shows that X satisfies conditions (1), (2) and (3). Conversely, these conditions may be seen to be sufficient by multiplying out the left hand side. 33 Theorem 4.6: In addition let n (i) Let A and a be as in Theorem 4.2. be the multiplicity of any ei genvalue correspond i ng to the cycle Let X be any particular solution of P(A)X - XA = O. a J... Then there exist = 1, .•. ,k and j : 1, ... ,n ( i) such that complex scalars bij for i la.I 1 cr(x) = u ( u [A: A i = bijl ) j Conversely, for any set ofb .. EC, for i J.J = 1, ••• ,k and . t s a sou 1 t ion . y h aving . th is . se t as J.. t s spec= 1 , ... ,n ( i ) th ere exis 1 n(i) eigenvalues, trum. In particular, for any prescribed set of ~ ~ J. i=l there exists a solution Y with cr(Y ) containing these eigenvalues. 2 Theorem 4.7: 2 Let A be as in Theorem 4.6 except t hat A is nonderogatory, but not assumed to be diagonalizable. Let X be any particular solution of P(A)X - XA = O. complex scalars b . . for i Then there exist J.J = 1, ... ,k an d J. = 1 , ... ,n ( i) sueh th a t la.I a (X) = U ( U [A: A i j 1 = b J.J .. } ) • Conversely, for any set of bij EC with i j = 1, •.. ,k and = 1, ... ,n (i) and la.IJ. b .. J.J = n t=l )n c J.1., . ,P '('11..n lh ( i) . -J where cit E ~, and Ait is the ordering of the eigenvalues of A based on the cycle decomposition ~l ••• ~, there exists a solution Y1 having this set as its spectrum. In particular, for any prescribed set of k 34 eigenvalues, there exists a nondiagonalizable solution y , with cr(Y ) 2 2 containing these eigenvalues. Proof of Theorem 4.6 and Theorem 4.7: As in Theorem 4.3, reduce X to the direct sum of block monomial matrices, each corresponding to a single cycle a .. l. A further permutation similarity will put each X(i) into the form 0 0 0 0 0 0 0 where each X~i) is square, and sxs by Lemma 4.5. J Therefore, Lemma 4.4 states that the characteristic polynomial of x(i) is A. n.-ja. lmi i i. A. la.I i. I la. I c. > s - ni. x. 1 j=l J If A is diagonalizable, then the x3i) may be chosen arbitrarily and Theorem 4.6 follows. If A is nonderogatory, then each X(i) is triangular with diagj onal 35 ( i) (cP'(A)n -l, by Theorem 4.3 and Lemma 4.5. Therefore, is triangular and has diagonal la. I l ( l l1 c .. P'(A .. )n j=l lJ JJ - , .. . ' Thus Theorem 4.7 follows. where c . . E ~. lJ Theorem 4.8: (.) 1 Let A be as in Theorem 4.7 except that A is derogatory. In addition, let m. be the number of elementary divisors for any eigenl k value corresponding to the cycl e a. and m = E m. • l i=1 Then for any pre- l scribed set of rn complex numbers, there exists a matrix Y with P(A)Y - YA = 0 and o(Y) containing this set. Reduce X as in Theorem 4.3. Proof: Then, by Lemma 4.4, the charac- teristic polynomial of x(i) is n.-la.i jm.i >. i 'A la.I1 la.I x< 1 I s - Il j=l where X~i) for j J 1·_) j = 1, ... , la.I are the blocks of the block monomial l matrix X(i) which are not required to be zero. are all square and of the same dimension. By Lemma 4.1, these Parti ti.on each X~ i) J according to the Jordan structure of the corresponding eigenvalue in A. Then by Theorem 4.3 and Lemma 4.5, each block in X~i) is an J upper triangular matrix whose final column may be chosen arbitrarily and still give a solution of P(A)X - XA = O. In particular, by choosing the final columns of the lower blocks to be (O, ••• , o)T, the resulting matrix will be upper triangular with each diagonal block contributing one arbitrary element to the diagonal. Therefore, m. of the eigenvalues of a solution may be 1 chosen arbitrarily for each cycle a .. 1 Thus a matrix Y may be construc- ted with any set of m eigenvalues in cr(y) and P(A)Y - YA = 0. 37 CHAP!'ER V TOWERS IN P(A)X - XA = 0 In this chapter, we wish to derive a result for the equation P(A)X - XA = 0 1.2) which is analogous to Theorem 3.4. Problem 1 .3: The natural analogue is to consider For what polynomials P does the fact that there exists a tower for each solution of (1.2) imply that A is normal? To attack this problem, we derive conditi.o ns on P which are necessary and sufficient for the existence of towers. Theorem 5.1: Let A be a diagonalizable matrix, P(X) a polynomial such that equation (1 .2) has a nonsingular solution, and cr(A) = (A.: i l. = 1, ••• ,s} with A. distinct. l. = Then there exists a tower for each solution of (1 .2) if and only if the following two conditions hold. 1) P(A.) =A(') i a i for some permutation a with order say t. 2) P(X) = ~ a.Xit+l for all solutions X of (1 .2). . 0 l. l.= Proof: Since P(A)X - XA = 0 for some nonsingular X, condition (1) is necessary. By Theorem 4.2, P(X) is a solution for all solutions X if and only if P(X) and X are simultaneously similar, by the similarity given in Theorem 4.2, to the same block monomial form. words, there exists a matrix S such that In other for all i,j = 1 , ... ,s with i f a(j) and for all solutions X of (1 .2). t Let P(X) = E ck~ for t I+. E k Each X must reduce to the s ame k=O k -1 block monomial form as X and P(X). some i, j, k and X with i Otherwise, ( SX S f a(j). .1 ) .. r 0 for l.J However, since SXS-l is a block monomial matrix, each block ( SXk S-1 ) .. is the product of blocks of l.J SXS-l. In particu l ar, if (S~S-l ) .. f O, the blocks are some of the nonzero blocks x1 , ••• , Xs of SXS l.J -1 . Therefore, if (S~S-l ) .. f 0 for blocks may be chosen arbitrarily. this i and j, then P(X) = O. However, by Theorem 4.2, these l.J This is a contradi ction. Since ~ must reduce to the same block monomial form as X, we have k = it+l where + t is the order of the permutation a , and i E I . Therefore, condition (2) is necessary. Conversely, conditions (1) and (2) result in a matrix P(X) which reduces to the same block monomial form as X. Therefore, by Theorem 4.2, P(X) is also a solution. Corollary 5.2: Let P be a polynomial and A be a normal matrix with o(A)=lA.:i=l, l. ... ' s} with A.. distinct such that there exists l a tower for each solution of (1 .2). abl~ but Then there exists a diagonaliz- nonnormal matrix B such that there exists a tower for each solution of P(B)X - XB = O. Proof: Since towers exist for solutions of P(A)X - XA = O, P satisfies 39 conditions (1) and (2) of the theorem for some permutation a and set of p. : i = 1, ••• ,s}. eigenvalues i matrix with the same spectrum as A. and (2) of the theorem for Let B be a nonnormal, diagonalizable Then P satisfies conditions (1) cr(B) and a . Therefore, there exists a tower for each solution of P(B)X - XB = o. Corollary 5.3: Let A and P(X) be as in the theorem, except that A is not assumed to be diagonalizable. If there exists a tower for each solution of (1 .2), then conditions (1) and (2) of the theorem hold. Proof: In the proof of the theorem, to show the necessity of condi- tions (1) and (2), we needed that there exists a nonsingular solution, X reduces to a block monomial form, and there exists a tower for each solution X. By Theorem 4.3, X also reduces to a block monomial form in the case that A is not assl.Ulled to be diagonalizable. Therefore, the proof of the theorem holds in this case. Corollary 5.2 shows that there are no polynomials which satisfy Problem 1-3. However, Theorem 5.1 does suggest another problem. Problem 1 .4: For what polynomials P does the fact that there exists a tower for each solution of (1 .2) imply that A is diagonalizable? To attack this problem, we need results like Theorem 5.1 for nondiagonalizable matrices. Theorem 5.4: Let P(X) and A be as in Theorem 5.1 except that A is nonderogatory, but not assumed to be diagonalizable. If there exists 40 R tower for every solution of (1 .2), then in add i tion to conditions (1) and (2) of Theor em 5.1, one of the f ollowing t wo conditions holds. 1) P(x) = ax. 2) For each t..., one of the following holds. 1 a) p(k \ " . ) = 0 for k=l, ••• ,m . -1. 1 1 and P(k)("A.) = 0 for k=2, ••• ,m.-1 and 1'. fixed b) P' ('A.) = 1 1 1 1 by a. c) la'I ~ =1. fl P'(t...)a j=l J ,,., here mi is the multiplicity of "'Ai in A and is the set of all e igenvalues in the same cycle a' of a as t.. .• 1 Furthermore, there exists a tower for each solution of (1 .2) if, in addit ion to the conditions of Theorem 5.1, one of the following two conditions holds. 1) P(x) = ax.. 2) For each t..., one of the following conditions holds. 1 a ) p( k) p, . ) = 0 for k=l, ••• ,m. -1 • 1 1 and P(k)(~.) = 0 for k=2, •.• ,m.-1 and 1'. fixed b) P' (7'. ) = 1 1 1 1 by a. c) _lql la'I = 0 for n P'(t.. )la'T = 1 and P(k)(t...) 1 j . 1 J= k = 2, •.• ,m(t... ). 1 Proof By Corollary 5.3, conditions (1) and (2) of Theorem 5.1 are s necessary. Let X = ~ X.1 be in Jordan normal form and look at each X1.• i=l 41 Let f.. = A. l. , Y = (y J.k) = X.l where J k = 1 , .•• ,t ' and J, ........ _,...., l 0 , 1I ) Y is upper triangular 2 I) y .. JJ 3 I) Then, = P'(A.)y. 1 . forj=1, .•. ,-f, -l J+ ,J+ 1 k+l p( m) ().,) Yj,j+k = P'(A.)yj+l ,j+k+l + ~ m1 m=2 for j yj+m,j+k+l = 1, ••. ,.f,-1 and k = 1, .•. ,.f,-j-1 by Theorem 4.3 and lemma 4.5, where X. is the Y. of the theorem. l l In particular, the diagonal of Y equals We begin by considering the case of A. fix ed by a. If A. is fixed by a, then Y will lie on the diagonal of X. ponding block of SP(X ) S -1 is P(Y). Therefore, the corres- Thus, the d i agonal of P(Y) is The matrix P(Y) must also satisfy (2'). In particular Thus, since by condition (2) of Theorem 5.1 P has no constant term, 0 or yl,J,. =0 or ,f, = 1 or P(X) = aX for some a such that a is an tth root of 1. However, Yu, is arbitrary. Thel'ef'ore, P'(7') = l ,O or A is a simple eigenvalue or P(x) = ax. Consider the off diagonal elements of Y. Let Y = D + C where D = (d.) is the diagonal of Y. There are two cases depending on P'(A.). l 42 Case 1 : Let P' (A.) = 1. Thus, (2') implies D = dt I. Then, ( 3') applied to Y impli e s 4) Therefore, k-1 and the first upper diagonal of of (D + C) k dt C is the first upper diagonal since C is upper triangular and has z ero diagonal. There- fore, . . 1 ( ( D + C )k ) i,1+ k-1 dp c. = 'V . 1 i,1+ Thus, by ( 3 ') it i s necessary that k-1 d,f, where d{ c i' i + 1 = = (D + c)~z· Combining with (4) above, k-1 d, 'V c. 1 . 2 + l+ ,i+ P( 2 )(A.) 2 d, 'V = k-1 p( 2 )(>,) d, c. 1 . 2 + d: 'V l+ 'l+ 2 'V 43 or (k~l) 2 Thus, P( )(A) = O or d.f, k the diagonals, d_f, = dt. k-1 p(2 )p.) dt dt = p(2\_~ 2 2 di· =(k~ll d-r,· However, from consideration2 of k Therefore, since dt is arbitrary, P( )(A) = o. Proceed to the next upper diagonal where (3') now implies c 1, . .l+2 and a similar argument gives P( 3 )(A) = o. diagonal, P(i)(A) Case 2: Likewise for each upper = 0 for i = 2, ... ,t-1. Let P'(A) = O, then (2') implies the diagonal of Y is (o, ... ,o,d-t ). Thus, (-/ ) .{,... 2 .{,... ' 2 Therefore, P( )p. ) = 0 for k.·>1. 1 = 0 for k>l . From ( 3') Substituting this back into Y and checking the next upper diagonal gives P( 3 ){\) = 0. P( i) p,) = 0 for i == 1 , ••. , t-1 • Likewise, '!his concludes the case of "A fixed by a. Now consider the case of "A not fixed by a. Then, from condi- tion (2) of Theorem 5.1, P(X) = g(Xlal )X where g is a polynomial in xlal. Thus, using the fact that Y is a block monomial matrix, 44 la'I n Y i=1 where Y.l for i i = 1, ... , la I are the blocks of sxs- 1 corresponding to 1 all the eigenvalue~ Ai in the same cycle a 1 la' I ( n i=1 j,k=1, ••• ,t. illL Y. )la' I of a as Y = Y and G = (gjk) = g(H) for 1 From (2') it is necessary that Y·l l.g.l l· = p '(A 1 )t-i yUgi·i·. Thus, again using (2'), Since Ytt and g.u_ are arbitrary, either or for i 1 Since X is a solution of (1 .2), ea ch Y. i s upper tr i an- P( Y ) . . = y .. g . . 1 ll ll ll = 1, ... ,t. and A= A • l gular by (1 '). for i 1 = 1 , ... , t. Since each Y. is upper triangular, l 45 g,. ""g(( ll la'I la'I rr P'(~.) II (Y.)u) j=l J j=l J j~l,I ) Therefore, (6) implies for i=l , .•• , . la'I 7) IT . 1 J= P'(t...) ]1~1., = 1. J Therefore, the first set of conditions of the theorem are neces;.; ary for the existence of a tower for each solution of (1 .2) If P satisfies conditions (1) and (2) of Theorem 5.1, P(X) will reduce to the correct block monomial form. Therefore, let P(X) satisfy ·the second set of conditions of the theorem and consider P(X) one block 3t a time to show that condit i ons (1 '), (2'), and (3') hold for P(X). If P(x) = ax, then P(X) is clearly a solution for all solutions ){. 0 for k= 1 , ••• , m. - 1 , then by ( 1 ' ) , ( 2 ' ) , and ( 3 ' ) l Y. has the form l 0 1) Yt where y. are arbitrary for i=l , ••• £. 1 Since Y is a block monomial matrix, P(Y). will consist of sums and products of blocks of this type. l Thus, P(Y). is again of this type. l If P'(f...) = 1 and P(k)(f...) = 0 for k=2, ... 1 m.-l and f... is fixed l l l 1 by a, then it is clear from the proof of the necessity of these conditions that (1 '), (2' ), and (3') are satisfied. the correct form. Thus P( Y). is of l 46 JQL la'I If [II )ja'f = 1 and P(k\1'.) =0fork::i2, .•. ,m.-1 then l P'(1'.) J . 1 J= l P(Y).l will consist of sums and products of the form P' £-2 (1')y£-1 £-1 ' 2) P' (1' )y ££ By condition (2) of Theorem 5.1, P(X) = Xg(Xlal) a nd the products in g will consist of powers of the product of the bloc ks of Y i n t he same cycle of a as 1' .• l Thus, i t can be shown that if ( 14- = la'! II P'(1'.)]la'I j=l J P(Y).l. will again be of type 2. Therefore, the second set of conditions of the theorem are sufficient to insure the ex i stence of a tower for each solution of equation 1 .2. Theorem 5.5: Let P(X) and A be as in Theorem 5.1, except that A is derogatory, not assumed to be diagonalizable. If there exists a tower for each solution of (1.2), then P satisfies condi t ions (1) and (2) of Theorem 5.1 and one of the following two conditions holds. 1) P(x) = ax. 2) For each eigenvalue 1'., one of the following holds. l. 47 a) p(k)(A.) = 0 for k=1, ••• ,m(1'.). 1 1 b) P'("- . ) = 1 and P(k)(A.) = 0 for k:::-2, ••• ,m(A.) and A. is 1 1 1 1 fixed by a and all the Jordan blocks of A corresponding to A. have the same dimension. l la' I c) TI P' (1'.) ] j=l J j~l 1 = 1. where m(A.) + 1 is t he maximum dimension of the Jordan blocks of A 1 corresponding to A. and {A.} is the set of all e i genvalues in the same J 1 cycle a' of a as 1' .• 1 Furthermore, there exists a tower for each solution of (1 .2) if, i n addition to conditions (1) and (2) of Theorem 5.1, one of the following two condit i ons holds. 1) P(x) = ax. 2) For each eigenvalue 1'., one of the following conditions holds. 1 a) p(k)(1' . ) = 0 for k=1, ••• ,m(1' . ). 1 1 and P(k\x . ) = O for k=-2, ••• ,m(\.) and"· is b) P'(1'.) = 1 1 1 1 fixed by a and all the Jordan blocks of A corresponding to 1' i have the same dimension. Ia' I c)[ _l_gL_ n P'(1'.)]la'T=1andP(k)(1'.)=0for . 1 J= J 1 k=2, ••• ,m(1'.) and all the Jordan blocks of A 1 48 corresponding to A. have the same dimension. 1 Proof: By Corollary 5.3, conditions (1) and (2) of Theorem 5.1 are By Theorem 4.3, it is necessary that P(A. )Y. - Y.A. = O 1 1 1 J a( i) • j, where A. is the submatrix of the .Jordan normal form of necessary. for 1 A consisting of the direct sum of the Jordan blocks corresponding to A·• 1- Let Y be any of the Y., and let the corresponding A. and A. be 1 1 J S 11 SI k~l~ and t~l A~ respectively, where each Ak and At is a Jordan block. Then by Lemma 4.1, the resulting partitions of Ai and Aj above are the same. Let Y = (Ykt) be the corresponding partition of Y. Then P(Ak )Ykf, - YktA~ = 0 fork= 1, .•• ,s' and t = 1, ... ,s'. Applying Lermna 4.5 to this equation implies that for each Z = Ykt = (zij) for i = 1, ••• ,m and j 1 ") Z is upper triangular 2") z 3") z m-1,n-1+ . . t = 1, •.• ,n . . = P'(A.)z . . fori=1, .•• ,min(m,n)-1 m-1,n-1 m-1+ 1 ,n-1+ 1 = P' ( A.)z m-1+ . 1 ,n-1+t+ . 1 + t+l p( j) ( /...) I: - - - - Z m-1 +j,n-i+t+l j=2 j ! for i = 1, ••• ,min(m,n)-1 and t = 1, ••• ,min(m,n)-i-1. Thus, the final column of each Z is arbitrary. If there exists a tower for all solutions of (1 .2), then it is necessary that P(X) is a solution for all choices of the final columns of the Ykt • the blocks In particular, assume that A{ and A~' are the largest of Ak and A~ respectively, and choose the final columns of the 49 Ykt to be zero for all (k,t) /= (1, 1 ). Because of the relations (2") and (3"), this choice results in Ykt = 0 for all (k,t) f (1 ,1 ). 0 y = 0 0 and P(Y) = P(Yl 1 ) Q 0 0 Thus Therefore, the problem of finding solutions P(Y) is contained in the problem of finding solutions P(Y 11 ). However, this is the case of Theorem 5. l~, since A{ and A~' are nonderogatory. Therefore, it is necessary that P(k)(A) = 0 fork= l , ••• ,m(A) la'I or [ . Il P' ( >J J=l j~l, 1 J = 1 or A is fixed by a and P' (A) = 1 and P(k)(A) = O fork= 2, ... ,m(A) or P(x) =ax where m(A) + 1 is the maximum dimension of the Jordan blocks of A corresponding to A and [ t.. } j is the set of all eigenvalues in the same cycle a' Consider the case of P'(A) = l and t.. fixed by a as A = A. 1 • and not all of the Jordan blocks of A corresponding to A having the same dimension. Again, we may choose the final colwnns of Ykt to be (o, ... ,o)T for all (k,t) f (1,1 ), (2,2), (1,2) or (2,1) where the dimension of Y11 is assumed to be greater than the dimension of Y • 22 Then 50 .... Y11 * * * 0 Y11 Y11 0 Y12 . * * 0 0 0 Y11 Y21 Y12 Y22 . 0 * .. * 0 Y21 0 0 0 0 Y22 0 0 where this is a new partition of Y obtained by partitioning Y into 11 four blocks with the second diagonal block having the same dimension as Y22 • Let the dimension of Y11 and Y be nl and ~ for this new 22 partition. Then (yk) .. 11 for i = 1, ••• ,n; and for i = n;+1, ••• ,n;+n2, where f is a polynomial in y 12 and y21 with positive coefficients. Since it is necessary that (~) .. 11 1. -- 1 , ••• , .n'+n' , 2' . = (~).1+1 ,1+ for 1 However, 51 f(y 12 ,y 21 ) f 0 for all y preserves the diagonal. 12 ,y if k > 1. 21 Therefore, only P(x) = ax Therefore, conditions(l) and (2) are neces- sary. Conversely, as in Theorem 5.4, conditions (1) end (2) of Theorem 5.1 are necessary and it is only necessary to check that the transformation x~ P(X) preserves the internal structure of each Yk. If P(x) = ax then clearly towers exist for all solutions X. If P(k)(A) = 0 fork= 1 , ••• ,m(A), then all blocks Yk are of the form 0 where m' = m(A)+l. of this type. Sums and products of blocks of this type are again Therefore towers exist for all solutions X. If (k) P'(A) = 1 and P (A)= 0 for k=2, ..• ,m(A) and 1' is fixed by a, then all blocks Yk are of the form 0 where m' = m(A)+l. of this type. Sums and products of blocks of this type are again Therefore towers exist for all solutions X. If 52 la'I lal JI P'('A) j=l ]f(i'f = 1 and P(k)('A.) = 0 for k=2, ••• ,m(1') then all blocks Yk are of the form P'(1')m'-1 Ym' P' (1' )m' -2 Ym'-1 Since condition (2) of Theorem 5.1 is satisfied, the sums and products of this type occuring in P(X) will be of this type. Therefore towers exist for all solutions X. For a polynomial P and a matrix A to satisfy Problem 1 .4, it is necessary that P and A satisfy the conditions of Theorem 5.1 but fail to satisfy the necessary conditions of Theorem 5.4 and Theorem 5.5. 53 Examples: Consider the following polynomials pl {x) = -x3 1 3 P (x) = -(x - 3x) 2 2 P (x) = §(-3x5 + 10x3 - 15x) 3 Each of these polynomials acts as a permutation of 1 and -1. Let A be any matrix with 1 and -1 as its only e i genvalues where the Jordan structures for 1 and -1 are the same. Then each of the polynomials above satisnes the conditions of Theorem 5.1. pl I ( 1 ) = - 3 pl I ( -1 ) = -3 Therefore, P 1 does not satisfy the necessary conditions of Theorem 5.4 and Theorem 5.5. P '(1)=0 2 p2 I ( -1 ) : 0 p2"(1) =3 p2"(-l) = -3 Therefore P 2 does not satisfy the necessary cond it ions of Theorem 5.4 and Theorem 5.5 if there is a Jordan block in A with dimension greater than 2. In particular, P does not satisfy Problem 1 . 4 2 if the dimension of A is less than or equal to 4. 54 P '(1)=0 3 P 1 (-l) = 0 3 P II (1) = 0 3 p II ( -1 ) = 0 3 p (3)(1) 3 p (3)(-1) 3 = - 15 = - 15 Therefore, P 3 satisfies Problem 1 .4 if there exists a Jordan block in A of dimension greater than 3. f O. In general, if Pis a polynomial of degree n then P(n)(A.) Thus, if P'(A.) = 0 or 1 for some eigenvalue A. of A and the dimension of A is less than or equal to 2n, then P will not satisfy Problem 1 , 11 for A. Theorem 5.6: Let 0 t t = [ ~ a.x . 0 l= ea,t..,, ••• ,A.s = [P E Ola! '!:' ~ it+l l : P(A.. ) =A. 1. a(i) for i = 1, • • . ,s}. Let a,1..,, ••• ,A.s = 0 for i = [P : xP E Ola! and P(A..) 1. a,A. , •.. ,A. = [P E '!:'a,t..,, •.. ,t..s : P has minimal degree, q0 1al}. 1 s Let with t,t EI+ and a. complex} . 1. = 1, ..• ,s}. Let Then \ ... ,l\s \ and = (P0 + xP1 % + x~) where po € ea,l\,, Q _ , Q_ ~ -vi Proof: E qi a,/\, , ... ,/\, 1 s and xP1 E 0 Ia I . We drop th e subscripts a,A. , •.• ,A. for clarHy. 1 8 clear that e = [p + xQ: P E A and Q E Y}. 0 0 to show that '!:' First, i t i s Therefore, it is suffic i ent = {P1 Q0 + ~ : xP1 E 0 and %' Q, E ~ } • 55 Let Q E 'f with degree qlal and - c x 1 (q-q0 )1 al % E .P. Let R = Q 1 % where c 1 is the leading coefficient of Q.. in 'f and the degree of Rl is less than the degree of Q. (q-~-1 )lal = R - c x 1 2 Rt = Rt-l Then , R is 1 Let R = 2 %where c 2 is the leading coefficient of R1 , then t b.lal E a .x i Q is of degree q 1al, the minimal degree. 0 0 i=1 i Then ~ E t q, and Q = E bilal a ix i=l Q + Q1 0 Let = P1 % + ~ with % E ~ then P1 Q0 E 'f. Furthermore, if ~ E ~ and ~ E 'f then ~ + ~ E 'f. Therefore, P1 % + Q E '¥ for 1 Conversely, if xP 1 all xP E 0 and %0., 1 E .P. E 0 and Thus'?'= (P 1 % + ~ : xP1 E 0 and Q Q 0 1 E ~}. REFERENCES 1• Choi, Man·· Duen. "Adjunct.ion and Invers ion o f Invertible HilbertSpace Operators." Indiana Univ. Math. Jour. 23 (1973) : 41 3-419. 2. Davis, c.w. " Elementary Divisors of t he Stein Transformation X ... X- CXC * ." SIAMJ. Appl. Math. 27 (1974): 492-494. * in GL(n,c)." 3. DePrima, C.R., and Johnson, C.R. "The Range of A-1 A Linear Algebra and Appl. 9 (1974) : 209-222. 4. Djokovic, D.V. "On Some Representati ons of Matrices." in Linear and Multilinear Algebra. 5. Drazin, M. P. "A Reduction of the Matrix Equation AB ::: EBA ." Cambridge Philos. Soc. 47 (1951) : 7-10. 6. Fan, Ky. "Generalized Cayley Transforms and Strictly Dissipat i v e Matric e s." Linear Algebra and Appl. 5 ( 1972) : 1 55-172. 7. Fan, Ky. "On Real Matrices w:ith Positive Definit e Symmetric Component." Linear and Multilinear Algebra. l ( 1973 ) 1- LL 8. Fan, Ky. Appl. "On Strictly Dissipative Matrices." To appear Linear Algebra and 9 ( 1974) : 22 3-241 . 9. Fuglede, B. "A Commutativity Theorem for Normal Operators." Nat. Acad. Sci. 36 (1950): 35- l+O. 10. Givens, W. * Roth, W.E. Proc. Elementary Divisors and Some Properties of the Lyapunov Mapping X ... AX +XA • Argonne National Laboratory Report 11. Proc. "On Direc t Produc t Matrices." 6456 (1961 ). Bull. Amer. Math. Soc. 40 (1934) : 461-468. 12. Singh, U.N., and Mangla, K. "Operators with Inverses Similar to their Adjoints." PAMS 38 (197 3 ) : 258-260. Taussky, O. "A Remark Concerning the Similarity of a Fin ite Matrix * A and A." Math. z. 117 (1970) 189-190. 14. Taussky, o. "Hilbert's Theor em 90 in Matrix Rings." Multilinear Algebra. l (197 3 ) : 5-8. 15. Taus sky, ation. 16. Thompson, R.C. "Some Matri x Factorization Theorems." Journal of Math. 33 (1970) : 763-810. o. Linear and "A Matrix Generalization of Galois Theory." In prepar- Pacifi c 57 17. Thompson, R.C. "Dissipative Matrices and Related Results." Algebra and Appl. 11 {1975) : 155-169. Linear