On the Lyapunov Transformation for Stable Matrices Citation Loewy, Raphael (1972) On the Lyapunov Transformation for Stable Matrices. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/EXGT-0968. https://resolver.caltech.edu/CaltechTHESIS:05092016-130648083 Abstract The matrices studied here are positive stable (or briefly stable). These are matrices, real or complex, whose eigenvalues have positive real parts. A theorem of Lyapunov states that A is stable if and only if there exists H ˃ 0 such that AH + HA* = I. Let A be a stable matrix. Three aspects of the Lyapunov transformation L A :H → AH + HA* are discussed. 1. Let C 1 (A) = {AH + HA* :H ≥ 0} and C 2 (A) = {H: AH+HA* ≥ 0}. The problems of determining the cones C 1 (A) and C 2 (A) are still unsolved. Using solvability theory for linear equations over cones it is proved that C 1 (A) is the polar of C 2 (A*), and it is also shown that C 1 (A) = C 1 (A -1 ). The inertia assumed by matrices in C 1 (A) is characterized. 2. The index of dissipation of A was defined to be the maximum number of equal eigenvalues of H, where H runs through all matrices in the interior of C 2 (A). Upper and lower bounds, as well as some properties of this index, are given. 3. We consider the minimal eigenvalue of the Lyapunov transform AH+HA*, where H varies over the set of all positive semi-definite matrices whose largest eigenvalue is less than or equal to one. Denote it by ψ(A). It is proved that if A is Hermitian and has eigenvalues μ 1 ≥ μ 2 …≥ μ n ˃ 0, then ψ(A) = -(μ 1 -μ n ) 2 /(4(μ 1 + μ n )). The value of ψ(A) is also determined in case A is a normal, stable matrix. Then ψ(A) can be expressed in terms of at most three of the eigenvalues of A. If A is an arbitrary stable matrix, then upper and lower bounds for ψ(A) are obtained. 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: 8 March 1972 Funders: Funding Agency Grant Number Caltech UNSPECIFIED Ford Foundation UNSPECIFIED Record Number: CaltechTHESIS:05092016-130648083 Persistent URL: https://resolver.caltech.edu/CaltechTHESIS:05092016-130648083 DOI: 10.7907/EXGT-0968 Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 9710 Collection: CaltechTHESIS Deposited By: INVALID USER Deposited On: 09 May 2016 22:20 Last Modified: 01 Jul 2024 21:52 Thesis Files Preview PDF - Final Version See Usage Policy. 15MB Repository Staff Only: item control page

ON THE LYAPUNOV TRANSFORMATION FOR STABLE MA TRICES Thesis by Raphael Loewy In Partial Fulfillment of the Requirements For the Degree of Doctor of Philosophy California Institute of Technology Pasadena, California 1972 (Submitted March 8, 1972) ii ACI<I\l"OW LEDGMEN TS I wish to thank my advisor Professor Olga Taussky Todd, whose advice, encouragement and criticism made this thesis possible. I am also indebted to Professor F. Bohnenblust for many discussions and helpful suggestions. Financial support from the California Institute of Technology by way of Teaching Assistantships and Ford Foundation Fellowships are grateful! y acknowledged. iii ABSTRACT The matrices studied here are positive stable (or briefly stable). These are matrices, real or complex, whose eigenvalues have positive real parts. A theorem of Lyapunov states that A is stable if and only if there exi sts H > 0 such that AH+ HA* = I. Let A be a stable matrix. Three aspects of the Lyapunov transformation LA: H ~AH+ HA >,'< are discussed. 1. Let C (A) = [ AH+HA,:< :H ;i: O} and C (A) = [H:AH+HA* :<!: 'J}. 2 1 The problems of determining the cones C (A) and C {A) are still un1 2 solved. Us ing solvability theory for linear equations over cones it is proved that C {A) is the p ol ar of c {A,:c), and it is also shown that C {A) 2 1 1 =C 1{A -1 ). The inertia assumed by ma trices in C 1{A ) is characterized. 2. The index of dissipation of A was defined to b e the ma x i - mum number of equal eigenvalues of H, where H runs through all matrices in the interior of c {A). 2 Upper and lower bounds, as well as some properties of this index, are given. 3. We consider the minimal eigenvalue of the Lyapunov trans- form AH+ HA>:<, where H varies over the set of all positive semidefinite matrices whose largest eigenvalue is less than or equal to one. Denote it by \'{A). eigenvalues µ. 1 <? µ. 2 It is proved that if A is Hermitian and has <? ••• ~ µ.n > 0, then \'{A) = - {µ. 1 -µ.n) 2 /{4{µ. 1+µ.n) ). The value of \f{A) is also determined in case A is a normal, stable matrix. Then l\'{A) can be expressed in terms of at most three of the e igenvalues of A. If A is an arbitrary stable matrix, then upper and lower bounds for w{A) are obtained. iv TABLE OF CONTENTS Page ACKNOWLEDGMENTS ii ABSTRACT iii NOTATIONS . v mTRODUCTION •• 1 CHAPTER I On the Range of the Lyapunov Transformation 5 II The Index of Dissipation 24 III The Minimal Eigenvalue of the Lyapunov Transform • • • • . . ... 37 BIBLIOGRAPHY 68 v NOTATIONS A nxn matrix with complex elements complex conjugate and transpose of A R(A) tr(A) trace of A null( A) null space of A Lyapunov operator corresponding to A, see definition on page 6 s(A) Stein index of A, see definition on page 13 In(A) inertia of A, see definition on page 12 Ix(A) index of dissipation of A, see definition on page 24 I identity matrix direct sum of the matrices A 1 and A 2 diagonal matrix of order n with a , a , ... , a 1 2 on the main diagonal n v 2 n -dimensional linear space of nxn Hermitian matrices over the real numbers H,K Hermitian matrices PD set of all nx n positive definite matrices PSD set of all nxn positive semidefinite matrices n-dimensional Euclidean space over the complex numbers n-dimensional Euclidean space of the real numbers. 1 INTRODUCTION This thesis is concerned with positive stable (or brief! y stable) matrices. These are matrices, real or complex, whose eigenvalues have positive real parts. A most important result concerning stable matrices is Lyapunov's theorem. Theorem (Lyapunov [13]). The nxn matrix A is stable if and only if there exists an nxn positive definite Hermitian matrix H such that ,.. AH+HA" =I. Here A denotes an nxn matrix with complex elements, and A>:C is the complex conjugate and transpose of A. H and K denote Hermitian matrices. Throughout this work We write H > 0 if H is positive definite and H ~ 0 if H is positive semidefinite. The identity matrix is denoted by I. Lyapunov 1 s theorem is a special case of some theorems proved by Lyapunov, establishing conditions for the stability of solutions of differential equations. Because of its importance we give a brief account on some of its proofs and generalizations. Gantmacher [8] and Bellman [2] give proofs which use differential equations. Bellman even proves that if A is stable, then the unique solution of the matrix equation AH+ HA* = K is given by the explicit form H =f 00 0 >!c e -AtKe -A t dt 2 Givens [9] Other proofs are given by Hahn [ 10] and Tauss ky [21]. proved it via the generalized field of values F H(A) with respect to the metric !!xii~= x*Hx, given by the positive definite matrix H. Here FH(A) = [x~:cAGx: llxllH = l}. For a fixed matrix A, the transformation LA: H ..... AH+ HA >:C , 2 which is a linear transformation from the real n -dimensional space of Hermitian matrices into itself, is called the Lyapunov transformation. The eigenvalues of this transformation are A..+ A.., i, j = 1, ... ,n, l J where A. , A. , •.. , "-n are the eigenvalues of A, e.g., [9], and [22]. 1 2 The elementary divisors of the Lyapunov transformation were found by Givens [9]. The fact that LA is a linear operator, and that the posi- tive semidefinite matrices form a closed, convex, self-polar cone enables one to use here the solvability theory of linear equations over cones. Indeed, Berman and Ben-Israel [ 4] proved the Lyapunov theorem in this way. This approach will be used here to obtain some further properties of the Lyapnnov transformation. To describe some generalizations of the Lyapunov theorem, we need the concept of the inertia of a matrix. For an nXn matrix A which has n{A) eigenvalues with positive real parts, 'V(A) eigenvalues with negative parts, and 5(A) purely imaginary eigenvalues, we call the ordered triple (n(A), 'V(A), 5(A)) the inertia of A, written In(A) = ( n(A), v(A), 5(A) ). Let A have eigenvalues A. , A. , ... , "-n· 1 2 Taussky [21] showed:if A..+>....-:# 0, i,j = 1,2, ... ,n, then there exists l J H such that AH+HA* =I, and this H satisfies In(H) = In(A). Ostrowski and Schneider [15] proved that there exists H such that AH+ HA>:C > 0 3 if and only if o(A) = O. In(A) = In(H). Furthermore, AH+HA* > 0 implies that Carlson [6], and Carlson and Schneider [5], investi- gated the matrix inequality AH+ HA* ~ 0. They obtained bounds for In(H) in terms of In(A), or as a function of rank (AH+ HA~~). However, the relation of In(H) to In(A) in this case is much more complicated and is not fully understood. Tauss ky [20, 21] showed that every complex (real) stable matrix . is unitarily (real orthogonally) similar to a matrix of the form (I+S)D, where Sis skew-Hermitian (skew-symmetric) and Dis a positive diagonal matrix. There is a close connection between stable .matrices and convergent matrices, namely matrices all of whose eigenvalues are of modulus less than one. transformation. The connection originates from the Cayley Thus, if A is stable then C = (A+ I) - l(A - I) is con- vergent. 1 Conversely, if C is convergent then A = (I - C)- (1+ C) is stable. Stein [17] proved that a matrix C is convergent if and only if there exists H > 0 such that H - CHC* > O. Tauss ky [23] showed that Lyapunov's theorem is equivalent to Stein's theorem. Many questions concerning stable matrices and the Lyapunov transformation remain unsolved, despite the extensive research described above. them. It is the purpose of this thesis to consider some of In Chapter I the following two problems are discussed: Deter- mine C (A) 1 = (AH+HA* :H ~ O} and c 2 (A) = (H :AH+HA* ~ O}. These are the image and the inverse image of the cone of positive semidefinite matrices under the Lyapunov transformation, respectively. 4 These problems slightly modify problems of Taus sky [24, 25], who asked what are the interiors of C (A) and C (A). 1 2 Using the solvability theory for linear equations over cones it is proved that C (A) is the 1 polar o f the cone C (A*). 2 but in fact equivalent. Th us, t h e two probl ems are not unrelated, It is also shown that C (A) = C (A 1 1 -1 ). Stein and Pfeffer [19] found the range of BH+HB>.\ where H runs through all positive definite matrices and B varies over all matrices similar to the fixed matrix A. Restating their result in terms of A itself, we characterize the inertia vectors which are assumed by matrices in the interior of C (A). 1 This result leads to the characterization of inertia vectors assumed by matrices in C (A). 1 The index of dissipation of a stable matrix is defined by Taus sky [25] to be the maximal number of equal eigenvalues of H, where H runs through all matrices in the interior of C (A). 2 Upper and lower bounds, as well as some properties of this index, are given in Chapter II. In Chapter III we consider the minimal eigenvalue of the ... Lyapunov transform AH+ HA .... , where H varies over the set of all positive semidefinite matrices whose largest eigenvalue is less than or equal to one. Denote it by \r(A). The value of W(A) is determined in case A is normal and stable, while upper and lower bounds for w(A) are obtained for a general stable A. 5 CHAPTER I ON THE RANGE OF THE LYAPUNOV TRANSFORMATION In this chapter the range of the Lyapunov transformation is considered. More precisely, for a fixed stable matrix A, what is the image of the cone of positive semidefinite matrices under the transformation H _, AH+HA*? This problem is unsolved to date, and here some observations about it are made. Let A be a matrix of order nxn with complex elements (unless otherwise specified), and A~'f. be its complex conjugate and transpose. The trace of A is denoted by tr(A), and the null space of A by null( A). The trace function satisfies tr(AB) = tr(BA) for every pair A, B of nxn matrices. Let H and K denote Hermitian matrices. Hermitian matrices is denoted by V. space over the real numbers. The space of all nXn 2 This is clearly an n -dimensional Moreover, an inner product can be put on this space, by defining (H, K) = tr(HK). This is the ordinary inner 2 product if we look on matrices as n -dimensional vectors The set of nxn positive definite matrices is denoted by PD, and we write H > 0 if H E PD. The set of nxn positive semidefinite matrices is denoted by PSD, and we write H ~ 0 if H E PSD and H l ~ H 2 if H l - H 2 ~ O. The identity matrix is denoted by I, its order should be clear from the text. 6 We let En(Rn) be the n-dimensional Euclidean space over the complex (real) numbers. n The inner product in En(Rn) is denoted by n (x, y), where x, y EE (R ). The following definitions are the starting point. Definition 1. The matrix A is called positive stable (or briefly stable) if all its eigenvalues have positive real parts. Definition 2. For any matrix A let R(A) =A+A~:·. Note that hence- forth both R(A) and A+ A* are used. Definition 3. The transformation LA: V -+ V defined by LA(H) = R(AH) = AH+HA* is called the Lyapunov transformation. operator. ( 1) LA is called the Lyapunov Note that we use the term Lyapunov transformation, rather than the longer term Lyapunov transformation corresponding to A, since we usually consider a fixed matrix A, and no confusion should arise. Stable matrices are characterized by the Lyapunov theorem. Theorem 1 (Lyapunov [13]). The matrix A is stable if and only if there exists H > 0 such that R(AH) = I. A brief survey of the various proofs of this theorem is given in the Introduction. Lyapunov's theorem characterizes stable matrices, but leaves open many questions concerning these matrices. The 7 following two problems, due to Taussky, are discussed in this chapter. Problem 1 [24]. Let A be a stable matrix. What is the range of the Lyapunov transformation if H runs through the set PD? Problem 2 [25]. Let A be a stable matrix. What is the set of Hermitian matrices H such that R(AH) > 0? It is our purpose to show that these seemingly unrelated problems are equivalent. The proof makes use of solvability theory of linear equations over cones. To establish the proof we need some additional theorems and definitions. The following theorem determines the eigenvalues of the Lyapunov operator LA. Theorem 2 [9 ], [22]. A , A. , ... , "-n· 1 2 Let A be an nxn matrix with eigenvalues Then the eigenvalues of the Lyapunov operator LA are A..+ A., i,j = 1,2, ... ,n. 1 J The proof of Givens [9] makes use of Kronecker products of matrices. Taussky and Wielandt [22] find the required eigenvalues by choosing an appropriate basis. Henceforth it is assumed that A is a stable matrix, unless otherwise specified. Corollary 1. Let A be a stable matrix. LA is one-to-one. matrix only. Then the Lyapunov operator In particular, its null space consists of the 0 8 Proof. This follows immediately from Theorem 2. (I) Definition 4. n Let S c E , S nonempty. The set S is said to be a convex cone if (II) (a) )..S c S (b) s + s c s. n for every A ~ 0 • Let S c E , S nonempty. The polar of S, written sP, is defined by n [y EE :Re(y,S) ~ O} . The polar set is defined similarly over Rn, with the Re obviously omitted. It is known that sP is always a closed convex cone, see, e.g. , [3]. The next lemma is an immediate consequence of the wellknown fact that a closed convex set S of En and a point of En which does not belong to S can be separated by a hyperplane. Lemma 1 [3]. n Let S c E , S nonempty. Then S = sPP if and only if S is a closed convex cone (here sPP = (SP)P). The lemma leads to the following solvability theorem of linear equations over cones. We need this theorem to establish the equivalence of problems 1 and 2. Theorem 3 [3]. let b E Em. Let T be an mxn matrix with complex elements, and Let S c En be a closed convex cone and assume that null( T) + S is closed. Then the following are equivalent. 9 (a) Tx = b, x ES (b) T~ E sP implies Re(b, y) ~ O. has a solution. To prove the equivalence of Problems 1 and 2, we define the following closed convex cones. (2) C (A) 2 = (H:AH+HA' ~ O} )!c ( 3) It follows from Corollary 1 (since A is assumed to be stable) that the sets defined in Problems 1 and 2 are the interiors of C (A) and c (A), 1 2 respectively. Thus, in order to prove the equivalence of Problems 1 and 2, it suffices to show that the determination of C (A) and C (A) 2 1 are equivalent problems. Theorem 4. This is shown in the next theorem. Let A be a stable matrix. Then, and Proof. This theorem follows from Theorem 3. T of Theorem 3 by LA. We replace the matrix Correspondingly, Em and En are replaced by V, the linear space of nXn Hermitian matrices over the real numbers. We let S be PSD, the set of nxn positive semidefinite matrices. well-known that PSD is a closed convex cone. Moreover, PSD is a self-polar cone, namely PSD = PSDP, e.gf, [4]. Corollary 1 that null( LA) = (0 }. It is It follows from Hence null( LA) + PSD = PSD, and the 10 assumptions of Theorem 3 are satisfied. We show L; = LA*· (LA (H), K) It remains to find L;. To see it, let H, K EV. Then, = (AH+ HA):<, K) = tr(AHK+ HA*K) = tr(HKA+ HA)',cK) = (H, A*K+ KA) = (H, LA*(K)) To complete the proof, let KEV. if K = LA (H ) for some H 0 0 E PSD. Then KE C (A) if and only 1 By Theorem 3 this is equivalent to: LA~,c(H) ~ 0 implies But, LA):c(H) ~ 0 if and only if HE C (A*). 2 only if K E C (A*)P. 2 (K, H) ~ 0 Hence, KE C (A) if and 1 This proves the first part of the theorem. Replacing A by A*, we get C (A*> = c (A)P. 1 2 Since c (A) is a 2 closed convex cone, it follows from Lemma 1 that c (A) ~ c (A)PP. 2 2 Hence, completing the proof. Having proved the equivalence of Problems 1 and 2, we can now concentrate on Problem 1, or, equivalently, the determination of C (A). 1 The next theorem, which follows immediately from Lyapunov's theorem, gives us some information about c (A). 1 Theorem 5 [23]. Let A be a stable matrix, and le~ K be a given posi- tive definite matrix. positive definite. Then the unique solution of AH+ HA):c = K is 11 Proof. The uniqueness follows from the fact that LA is one-to-one. By Sylvester's law of inertia, there exists nonsingular matrix T such that TKT * = I. Hence, The matrix TAT- l is stable. Thus, by Theorem 1 (Lyapunov's theorem) THT* > 0, and consequently H > O. Another proof of Theorem 5 can be given, using Bellman's integral representation to the solution of AH+ HA* = K. For further details, see the Introduction. Corollary 2. Proof. c 1(A) ~ PSD • This follows immediately from Theorem 5 and the closedness of Cl (A}. Using Theorem 4 we can prove the following theorem. Theorem 6. Proof. Let A be a stable matrix. We first show that c (A) = c (A 2 2 Let H E c (A), so R(AH) ~ O. 2 R(A -1 H) ~ O. ). We want to prove that Since R(AH) ~ 0, we have A- 1AHA- l so -1 * + A- 1HA*A-l * ~ 0 12 1 This proves that R(AH) :2: 0 implies R(A- H) :2: 0, or H E c (A) implies 2 -1 H EC (A 2 ). Hence c (A) c C (A 2 2 C (A -1 ) c C (A). 2 2 -1 ). Hence C (A) 2 is also stable, we get c (A*) 2 Similarly, as A = C 2 (A -1 ). -1 is also stable, * Replacing A by A , which = C 2 (A- 1*). To finish the proof, we notice that by Theorem 4 Theorem 6 gives rise to a new problem. satisfy C (A) 1 What matrices B = C 1(B)? This question is not discussed here. We proceed to generalize theorems due to Stein, and Stein and Pfeffer, concerning C (A). 1 We notice that so far only Corollary 2 gives us some information on the structure of C (A). 1 In fact, almost nothing is known about C (A), for a fixed stable A. 1 The approach of Stein and Pfeffer is to allow the matrix A to vary. To describe their results, we introduce some more concepts. Definition 5. Let A be an arbitrary matrix having n(A) eigenvalues with positive real parts, V(A) eigenvalues with negative real parts and <5(A) purely imaginary eigenvalues. The ordered triple In(A) = (n(A), v(A), &(A)) is called the inertia of the matrix A. n(A) + v (A) + o(A) Definition 6. = n. The vector w = ( w , w , w ), whose coordinates are non1 2 3 negative integers and satisfy w vector. Obviously, 1 + w2 + w3 =n, is called an inertia 13 Definition 7. Let A be an arbitrary matrix, having distinct eigen- values A. , A. , ... , A.r. 1 2 The index of A.., 1 :s:: i :s:: r, is the maximum num1 ber of linearly independent eigenvectors corresponding to it, i.e., the dimension of its eigenspace. The Stein index of A, written s(A), is defined here to be the maximum of the indices of the A. .. 1 We assume now that A. , A. , ... , Ar are the distinct eigenvalues 1 2 of A. We write m = s(A) and we may assume without loss of generality that the index of A. equal to m. ( 4) 1 is We can now describe the degrees of the elementary divisors corresponding to the A.. as follows: 1 A.l: nll ~nl2 ~ •· · ~nlm >O A.2: n2 l ~ n22 ~ · · • ~ n2m ~ O ( 5) We agree that if n .. lJ = 0 for some i and j, the corresponding elemen- tary divisor does not e;xist. It is obvious that the arrangement described above can be done. Also, r m ~ ~ nkJ. = n • k= 1 j=l ( 6) 14 We are ready to state the results of Stein [18], Stein and Pfeffer [19], and their generalizations. Theorem 7 [18]. Let K EV. The following are equivalent: (a) K has at least one positive eigenvalue, i.e. , n(K) ::!: 1. (b) R(AH) There exists a stable matrix A and H > 0 such that = K. This theorem determines what matrices can be written in the ,t, form AH+HA"'', where not only H runs through the set PD, but A is allowed to vary over the set of stable matrices. The proof of Stein is a constructive one, but is too complicated to be described here. Ballantine [l] gives an inductive proof. Theorem 8 [19]. matrix. Let A be a stable matrix, and let K EV be a given Let m = s(A) be the Stein index of A. Then the following are equivalent: (a) K has at least m positive eigenvalues, i.e. , n(K) <:!: m. (b) There exists a nonsingular matrix T and H > 0 such that This theorem, due to Stein and Pfeffer, gives the range of BH + HB*, where H runs through the set PD, and B varies over the set of all matrices similar to the given matrix A. We want to link the Stein-Pfeffer theorem to the problem of finding C (A). 1 we need the following lemma. To do it, 15 Lemma 2. Let A be a stable matrix, let K EV, and let T be a nonThen there exists H > 0 (H ~ 0) such that R(AH) singular matrix. if and only if there exists H 0 > 0 (H 0 =K ~ 0) such that R(TAT- 1H 0 ) = TKT*. Proof. Assume that AH+HA~~ We choose H 0 = K. Then, = THT*. Now, H > O (H :<!: 0) implies H 0 > O (H 0 ~ O), and the proof of the first part is completed. The second part follows similarly. We can now restate Theorem 8 (Stein-Pfeffer) in terms of A alone. Theorem 9. Let A be a stable matrix, and let w inertia vector. = (w1 , w2 , w3 ) be an Let m = s(A) be the Stein index of A. Then the fol- lowing are equivalent: Proof. (a) w1 ~ m. (b) There exists H > 0 such that In(AH +HA*> (a)~(b). We choose K 0 = w. EV, such that In(K ) = w. 0 Theorem 8, there exist T nonsingular and H 0 By > 0 such that = K 0 • We let TKT* = K 0 . Sylvester's law of inertia asserts that In(K) = In(K ) = w. It follows now from Lemma 2 that 0 R(TAT -1 H ) 0 there exists H > 0 such that R(AH) = K. of the proof. This completes the first part 16 (b):+(a). This follows immediately from the corresponding part in Theorem 8. Note: Theorem 9 characterized the inertia vectors which are assumed by matrices in the interior of C (A). 1 Theorems 10 and 12 below generalize Theorems 7 and 9, by allowing H to be nonnegative definite. The more interesting theorem is 12, which determined the inertia vectors assumed by matrices in Theorem 10. Let K EV. The following are equivalent: (a) K has at least one positive eigenvalue, i.e. , TT(K) (b) There exists a stable matrix A and H ~ 0 such that ~ 1, or K = O. R(AH) = K. Proof. (a)a+(b). For K = 0 choose any stable matrix and H = O. For K -:!. 0 with rr(K) ~ 1 apply Theorem 7. (b)=+(a). matrix and H ~ O. Let R(AH) = AH+ HA* = K, where A is a stable Assume that K -:!. 0 and TT(K) = O. It follows from Corollary 2 that there exists H R(AH ) = -K. 0 0 ~ 0 Then -K E PSD. such that But the Lyapunov operator LA is one-to-one, implying = -H 0 . On the other hand, H ::?: O and H 0 ~ 0 imply H =H 0 = O. Thus K = 0, contradicting our assumptions. This completes the proof. that H To generalize Theorem 9, we need the following theorem of Carlson, which considers the elementary divisors of a block triangular 17 matrix (over the complex numbers). Theorem 11 [7]. For proof, see [7]. Let B be a block triangular matrix of the form B = where B 11 and B 22 are square matrices. Let A be an eigenvalue of B. Let the degrees of the elementary divisors associated with A be a :<!:a 1 2 :2: ••• :2:aq inB, b 1 ~b ~ ... 2 ~ cw in B 22 • ~btinB 11 and c 1 :<!:c 2 ~ .. Then for all i we have a . SI: b. i:: a. w+1 i i (7) at+·1 ~ c.1 Ca.1 where by definition a. = 0 if i > q. 1 Theorem 12. Let A be a stable matrix, and let m = s(A) be the Stein index of A. Suppose that Al, A , ... , Ar are the distinct eigenvalues of 2 A, and that the degrees of the corresponding elementary divisors are given by (5). Let w = (w 1 , w2 , w3 ) be an inertia vector. t = min( w1 , m) Denote (8) Then the following are equivalent: (a) where the right-hand side is defined to be 0 if t = O. (9) 18 (b) Proof. There exists H :;<: 0 such that In(AH +HA*) We assume that w satisfies (9). (a)~(b). = w. If w :;<: m, then 1 the fact that (b) is true follows from Theorem 9, while for w 1 is satisfied by H = O. consequently i, = 0 (b) Hence we can assume that 0 < w < m, and 1 = w1 . Let j be an arbitrary positive integer such that 1 ~ j ~ m. Let A. be the direct sum of Jordan blocks of orders n ., n ., .•. , n ., cor1J 2 J J r J responding to A. , A. , •.• , A.r, respectively. 1 2 Thus, the order of A. is J r n. = I; n .. lJ J i= 1 The Stein index s(A .) of A. is obviously equal to one. J J nonsingular matrix T such that There exists a ( 10) the right-hand side being the direct sum of the matrices A , A , .• 1 2 We define now real diagonal matrices K. of order n. as follows: J J diag( 1, *, ••. , *) K. J = { j=l,2, ••. ,w , 1 0 The places denoted by >:< in K , K , •.• , Kw can be filled by any non1 2 1 positive numbers, provided that exactly w of them are negative. 2 This 19 is possible since (9) holds. Consider now a fixed j, 1 ~ j ~ w . 1 Since n(K .) = s(A .) = 1, J J it follows from Theorem 9 that there exists H . > 0 of order n. such J J that In(A.H.+H.A~) = In(K .). We further choose H . = 0 for J J J J J J w +1 ~ j :e m, and define the following direct sums: 1 and The matrix H is positive semidefinite and satisfies, by ( 10), 1 In(R(TAT- H)) = In(K) = w Applying Lemma 2 we finish the proof that (a).+(b). (b)-+(a). n The proof is by induction on n, the order of A. = 1 the proof is trivial. For Assume that (b)-.(a) for all stable matrices of order less than or equal to n-1, and consider the given matrix A. ~Denote AH+ HA· = K. w1 = n(K). Case 1. By our assumption In(K) = w, so in particular There are three cases. w1 > m. In this case (9) holds trivially, since we have J, = m. Thus, the right-hand side of (9) is equal to n, by (6). Case 2. w1 = O. by definition. In this case the right-hand side of (9) is equal to 0, We also know from Theorem 10 that the left-hand side of (9) must be 0, so (9) holds in this case. Case 3. d 0 < w <m. 1 =n - n (K) = n - w1• Note that in this case J, = w 1. We let 20 Since A. A. 1 1 is an eigenvalue of geometric multiplicity m for A, * is an eigenvalue of geometric multiplicity m for A • eigenspace of A Denote the * corresponding to A. 1 by S. Let µ. , µ. , .•. , µ.d be the d nonpositive eigenvalues of K, and · 1 2 let x , x , ••• , xd be an orthonormal set of corresponding eigenvectors. 1 2 Let L [x , x , .•. , xd J be the linear space spanned by x , x , ..• , xd. 1 2 1 2 We have m+d = n+m- w1 >n so there exists a vector y, (y, y) • • xd ]. = 1, such that y ES n L [x 1 , x 2 , .. We write d y =6 i= 1 a..x. 1 1 We have and d y*Ky = 6 i= 1 Also, 0 :!! y*Ky = y*(AH +HA *)y = since H :!! 0 and Re(A. ) > O. 1 Hence, * * y Ky = y Hy = 0 . 21 Now, H C!: 0 and y*Hy = 0 imply that Hy= 0, by the variational characterization of the eigenvalues of a Hermitian matrix [8, Vol. I, Moreover, the restriction of K to L[x ,x , ... ,xd] is 1 2 Chapter 10]. negative semidefinite, so for the same reason Ky= 0, We now let Ube an nXn unitary matrix with the vector y in its first column. Then, 0 u*Au = * u*Hu = ~ :] = ~ :J u*KU where H 1 and K 1 are n-lxn-1 Hermitian matrices, A 1 is an n-lxn-1 matrix, and * denotes a column vector whose coordinates are irrelevant. The equation AH+ HA* = K implies u* AUU*HU + u*Huu* A *u = u*Ku , so consequently, 22 The matrix K w , while H 2 those of A. 1 ~ O. 1 satisfies rr(K ) = rr(K) = w and \J(K ) = \J(K) = 1 1 1 The elementary divisors of U*AU are equal to Let the elementary divisors of A denoted by n! ., j = 1, 2, ... , m; i = 1, 2, ... , r. lJ 1 corresponding to Ai be It follows from Theorem 11 that n~. ~ n .. , lJ lJ i = 1,2, ... ,r; j = 1,2, ... ,m . (It also follows from Theorem 11 that n~m-l ~ n 1 m > 0, so the Stein index s(A ) '::!: m-1, but we don't use this fact here.) 1 Applying the induction hypothesis for the stable matrix A 1 we find that This completes the proof of the theorem. Theorem 12 gives some indication on the structure of C (A). 1 by characterizing the inertia vectors which are assumed by matrices in c (A). 1 We illustrate this theorem in the next example. Example. Let A be a stable matrix of order 45, having Al, A , A , 2 3 A as its distinct eigenvalues. 4 divisors of A be given by: Let the degrees of the elementary 23 "-1: 8 6 4 2 "-2= 5 3 3 1 "-3: 2 2 A.4: 4 3 The Stein index of A is 4. 2 The following inertia vectors w are assumed by matrices in c (A). 1 All inertia vectors with w 1 ~ 4. If wl = 3, all inertia vectors with w2 ~ 42-3 = 39. If wl = 2, all inertia vectors with W2 ~ 33-2 = 31. If wl = 1, all inertia vectors with w 2 ~19-l = 18. If wl ::: 0, only the vector (0, 0, 45). We finish this chapter with the following corollary. Corollary 3. Let A be a stable matrix. Then C (A) = PSD if and only 1 if A is a scalar matrix, i.e., A= A.I for some complex number A with Re( A.) > O. Proof. Obviously, if A is a scalar matrix then C (A) = PSD. 1 The converse follows immediately from Theorem 12 and the following easily verified fact: A is a scalar matrix if and only if s(A) = n. (Here n denotes, as usual, the order of A.) 24 CHAPTER II THE lliDEX OF DISSIPATION Let A be a stable matrix. We kn.ow that there exists H > 0 such that R(AH) = AH+ HA* > O. However, it need not be true that R(A) =A+ A~~ > O. In fact, very little is kn.own about the relation between the eigenvalues of A and R(A). dissipative if R(A) > O. The matrix A is said to be It is natural to ask how "close" is a stable matrix A to a dissipative matrix. One of several possibilities to define "close 11 is discussed in this chapter. We need the following definition, dut to Taussky. Definition 1 [25]. Let A be a stable matrix. The index of dissipation of A, written Ix(A), is the maximum number of equal eigenvalues of H, where H runs through all positive definite matrices with R(AH) > 0, i.e. , H E interior of c (A). 2 Recall that R(AH) > 0 implies H > 0, by Theorem 5, Chapter 1. Upper and lower bollllds, as well as some properties of the index of dissipation, are given in this chapter. It should be pointed out that the exact meaning of this index remains unclear. We start with some general observations on Ix(A). Throughout this chapter A denotes an nxn stable matrix, 1lllless otherwise specified. Z5 Theorem 1. Suppose AH+HA>~ > O. Proof. + H -1 A > O. Then H- 1 (AH+HA>::)H-l = A>:(H-l But, if H has k equal eigenvalues so does H -1 , and this proves Ix(A) s; Ix(A>~). Similarly, one shows Ix(A *) s; Ix(A), and the first equality follows, Also, AH+ HA>:( > 0 implies A - l(AH + HA>:()A -1>!( = A- 1 H+HA- 1 >~ > O. 1 Hence Ix(A) s; Ix(A- ). Similarly, one shows ~ Ix(A), completing the proof. Ix(A - l) We let Al (D Az be the direct sum of the matrices A 1 and AZ. It is quite natural to ask: Problem, Is ( 1) We would like to be able to get an affirmative answer to the question, but, unfortunately,( 1) will be proved under some restrictions on A 1 In the following we let or Az. where A 1 and AZ are stable matrices of order p and q, respectively. Here p+ q = n. Proof. Let k. = Ix(A.), i = 1, Z. 1 1 There exists a matrix H., such that 1 1 is an eigenvalue of H. of multiplicity k. and R(A.H.) > 0, i = 1, Z. 1 1 1 1 26 Let H = H 1 e H 2 • Then R(AH) = R(A 1H 1) e R(A 2 H 2 ) > 0, and 1 is an eigenvalue of H of multiplicity k 1 + k . 2 This completes the pro of. Before proc eeding, we recall the well-known interlacing in equalities between the eigenvalues of an nxn Hermitian matrix H and an n-1 xn-1 principal submatrix of H. The Interlacing Inequalities [8, Vol. I, Chapter 10]: Let H be an nxn Hermitian matrix with eigenvalues A.. 1 ~ A.. 2 ~ ••• ~ "-n· Let K be an n-1 xn-1 principal submatrix of H with eigenvalues Then (2) The next theorems describe situations where ( 1) holds. Note: In a matrix partitioned into blocks, a ':~ denotes a block whose entries do not matter for our purposes, while 0 denotes a block whose entries are all equal to zero. Lemma 2. Let A 2 = (a) be a 1X1 matrix, and let A = A 1 © A2. Then Ix( A) = Ix(A l) + 1. Proof. Let k = Ix(A ). 1 to prove that Ix(A) s: k+ 1. Lemma 1 implies that Ix(A) ~ k+ 1. It remains So let H be a matrix with r equal eigen- values and satisfying R(AH) > O. value of H of multiplicity r. We can assume that 1 is an eigen- We write 27 where H 1 is an n-1 xn-1 principal submatrix. Then R(A H ) 1 1 R(AH) = [ ):c Now R(A H ) > 0, since all principal submatrices of a positive definite 1 1 matrix are themselves positive definite. Also, it follows from the interlacing inequalities that 1 is an eigenvalue of H least r-1. Hence r-1 s k, completing the proof. Lemma 3. Let Ube an nxn unitary matrix. Proof. 1 of multiplicity at Then Ix(A) = Ix(U;'<AU). This follows from the identity u*(AH+HA*)U = (U*AU)(U*HU) + (U*HU)(U*AU)* and the fact that H and U*HU have the same eigenvalues. Theorem 2. Let A 2 be a qxq normal matrix, and let A= A 1 6:) A • 2 Then Ix(A) = Ix(A I) + Ix(A ) = Ix(A l) + q . 2 Proof. We first note that Ix(A ) = q, because A normal and stable 2 2 implies R(A ) = A +A~'< > O. 2 2 This proves the second equality. ZS AZ is unitarily similar to a diagonal matrix. Hence, by Lemma 3, we can assume without loss of generality that AZ is a diagonal matrix, and write Az = diag (d , dz, •.• , dq). 1 The proof is by induction on q. For q = 1 the situation is exactly that of Lemma Z, so the theorem is true. Let q be an inte- ger greater than one, and assume that the theorem holds for all diagonal matrices of order less than or equal to q - 1. Defining B = diag (d , dz, .•. , dq_ ), we get 1 1 A= 0 d q Applying again Lemma Z we get Ix(A) = Ix(A <;9 B) + 1, while using the 1 induction hypothesis we find Ix(A 9 B) = Ix(A ) + q - 1. 1 1 Hence Ix(A) = Ix(A ) + q, completing the proof. 1 Theorem 3. Let AZ be a qx q ma~rix such that R(Az) > 0, and let A= A @Az. 1 Then Proof. Clear! y Ix(Az) = q, as R(Az) > O. It is well-known [14, p. 67] that every matrix is unitarily simi- lar to a lower triangular matrix. Hence, by Lemma 3, we may assume without loss of generality that Az is a lower triangular matrix. The proof is by induction on q. to Lemma Z. For q = 1 the theorem reduces So let q be an integer greater than 1, and assume that the theorem holds for all triangular matrices of order less than or 29 equal to q-1. where A 22 We write is a q-1 Xq-1 matrix and A 33 is a 1 Xl matrix. Accordingly, A has the following block form A = Al 0 0 0 A22 0 0 A23 A33 It is enough to prove that Ix(A) ~ Ix(A ) + q, since Ix(A) :<!: 1 Ix(A ) + q by Lemma 1. 1 So let H be a Hermitian matrix having 1 as an eigenvalue of multiplicity r, and R(AH) > O. Partition H conform- ably with A, H Hll Hl2 Hl3 * = Hl2 H22 H23 * * H23 H33 Hl3 Then R(AlHll) R(AH) = AH+HA* ):c *A* = A 22Hl2+Hl2 1 * * AlH12+Hl2A22 R(A22H22) ):c * ):c ):c > 0 . 30 ' The positive definite principal submatrix of order n-1, sitting in the upper left corner of R(AH), is equal to 0 R A But 1 is an eigenvalue of 12 [:~l12 : 22 ] of multiplicity r-1 at least, by the interlacing inequalities. R(A ) > O. 2 + q-1. H* 12 22 Also, A 22 satisfies R(A 22 ) > 0, since It follows from the induction hypothesis that r - 1 ~ Ix(A ) 1 Hence r s: Ix(A ) + q, and the result follows. 1 Theorem 3 is stronger than Theorem 2, because the latter is a special case of Theorem 3. It remains to be seen whether the assumption that R(A ) > 0 can be dropped in proving (1). 2 easily shown that ( 1) holds for matrices A 1 and A 2 It can be with p+q =n s: 4. The remaining part of the chapter is devoted to obtaining upper and lower bounds for the index of dissipation. We recall that n(H) denotes the number of positive eigenvalues of the Hermitian matrix H. Theorem 4. Proof. Let k = Ix(A). Ix( A) S: rr(A +A*) ( 3) There exists a matrix H > 0 having 1 as an eigenvalue of multiplicity k, and R(AH) > O. a unitary matrix U such that Therefore there exists 31 where I is the identity matrix of order k and D is a real diagonal Let B = U):cAU. matrix. Then Partitioning B c onformably with K, we find that l R(Bl 1) R(BK) = Hence R(B 11 ) > O. ):c The interlacing inequalities imply that n(B + B*) ~ k. But B+B* = u*(A+A*)U, so n{A+A*) = n(B+B*) ~ k. This completes the proof. The next question to ask is, obviously, whether equality holds in (3). It turns out that the answer is no, and so it seems certain that the index of dissipation of a matrix has no simple meaning. An example showing that strict inequality is possible in (3) follows the next corollary. Corollary 1. 32 Proof. Let a. be an arbitrary nonnegative number, and let R(AH) > O. It was previously proved (see proof of Theorem 1) that R(AH) > O 1 1 implies R(A- H) > 0, and thus R((A+ a.A- )H) > O. Ix(A) We conclude that ~ Ix(A +a.A - l) ~ TT ( R(A +a.A - l}) the second inequality following from Theorem 4. Since a. is arbitrary, the proof is complete. Example. ):c rr(A+A} We exhibit a 3x3 matrix A such that Ix(A) = 2. = 1, while Let A 1 6 4 = 0 2 6 0 0 3 Then A-1 1 -3 14/3 = 0 1 /2 -1 0 0 1/3 R(A - l) = R(A} 2 6 4 = 6 4 6 4 6 6 2 -3 14/3 -3 1 -1 14/3 -1 2/3 33 It is easy to see that n(A+ A~.c) = 2, because A+ A* has positive trace and a negative determinant. However, the matrix R(A+ O. 3A -l) = 2. 6 5. 1 5. 4 5. 1 4. 3 5. 7 5.4 5. 7 6. 2 has only one positive eigenvalue, so by Corollary 1 we have Ix(A) = 1. Finally, we get a lower bound for the index of dissipation. The index of dissipation is invariant under unitary similarity (Lemma 3), so without loss of generality we may assume that A is a triangular matrix. Actually, we shall assume only that A is block triangular. The following characterization of positive definite matrices, due to Haynsworth, is required for our purposes. Theorem 5 [11]. Let Then H > 0 if and only if H be a Hermitian matrix. 11 > 0 and . ca11 e d t h e S c h ur . H* H- lH The ma t rix 1s 12 11 12 complement of H Theorem 6. 11 in H. Let A be a block triangular matrix, partitioned into blocks as follows: 34 A= 0 0 The matrices A 11 , A 22 , A respectively, where p+q+r 33 0 are square matrices of orders p, q, r, =n (p and/or r can be zero). If R(A 22 ) >0 then Ix(A) 2: q. Proof. R(A 13 3 There exist H 1 and H 3 such that R(All H ) > 0 and 1 H ) > 0, because A and A are stable matrices. 11 33 33 3 Let 13 1 and be positive real numbers, to be determined later, and let H = s H 1 1 e I e 13 3 H 3 . Here I denotes the identity matrix of order q. Hence, R(AH) = 13 R(A H ) 1 11 1 Al2 >'' A" 12 R(A22) l33H3A>i3 '" l33H3Az3 We shall show that for sufficiently large 13 1 and sufficiently small 13 3 we have R(AH) > 0, and this will establish the proof. Since R(A 22 ) = A 22 + A~ 2 > 0, also (4) 35 for sufficiently large 13 , by a continuity argument. 1 We choose s which satisfies (4) and fix it. the principal sub- For this choice of 13 1 1 matrix of R(AH) is positive definite. It suffices to show, by Theorem 5, that its Schur complement is positive definite for sufficient! y small 13 . 3 Indeed, calculating this Schur complement we get HA* 1 3 23.J • ( 5) A* 12 We chose H 3 we choose 13 3 so that R(A H ) > 0 and 13 so that (4) is satisfied. 1 33 3 If sufficiently small, then the matrix given in (5) is positive definite, by a continuity argument. This completes the proof, since 1 is an eigenvalue of H of multiplicity q. Corollary 2. Let A have a system of r orthonormal eigenvectors. Then Ix(A) ~ r. Proof. Let x , x , ••• , xr be a system of orthonormal eigenvectors of 1 2 A, and let t.. t.. , .•• , '-r be the corresponding eigenvalues. 1 2 Let Ube a unitary matrix having x , x , .•. , xr as its first r columns. 1 2 Then 36 u*Au where D = diag P,. , A. , •.• , \r). 1 2 since D + D~:c > O. =[ DO The result follows from Theorem 6, 37 CHAPTER III THE MINIMAL EIGENVALUE OF THE LYAPUNOV TRANSFORM Throughout this chapter we consider a fixed stable matrix A of order n (n > 1). In Chapter I we discuss the problem of finding C (A), 1 the image of PSD (the cone of positive semidefinite matrices) under the Lyapunov transformation. being solved. cussed. As indicated, this problem is far from In this chapter a different aspect of the problem is dis- Corollaries 2 and 3 of Chapter I show that C (A) strictly 1 contains PSD, unless A is a scalar matrix. Thus, if A :f. AI, there exist matrices of the form AH+ HA*, H with negative eigenvalues. <!: 0, We would like to know how negative can the eigenvalues of the Lyapunov trans£ orm AH+ HA* become. To make the question meaningful, we have to restrict H to a bounded subset of PSD. A precise formulation of the question to be considered will be given following some additional definitions and notation. Let H be a Hermitian matrix. Its eigenvalues will usually be denoted by a. (H) and a.n (H) satisfy the variational characterization 1 38 >:< a.I (H) = max x Hx (x, x) = 1 a. (H) = n min x *H x (x,; x)='l ( 1) see, e.g. , [8, Vol. I, Chapter 10 ]. Definition 1. Here x denotes a column vector. Let S be a convex subset of a linear space over the real m The linear combination ~ 0.x. j= 1 J J is said to be a convex combination of xl, x2, ... , xm if ej ~ 0, j = 1, 2, .. m ..• m, and ~ e. = 1. j= 1 J numbers, and let x , x , ••• , xm ES. 1 2 Definition 2. Let S be a convex subset of a linear space over the real numbers, and let f be a real valued function defined on S. We say that f is a concave function if it satisfies for every x, y E S and 0 s 8 s: 1 the inequality f(0x+(l-0)y) Note: ~ 0f(x)+(l-0)f(y) . It follows immediately from this definition that (!£ e.x.) ~ ~ 0.f(x.) m f ~= 1 J J j= 1 J ( 2) J for every convex combination of points x , x , ..• , xm E S. 1 2 We are ready to state the problem to be considered in this chapter. Let J = {H: H EV and OS:HS:I}. ( 3) 39 Problem. Find W(A) = min [a (AH +HA,:<) } H EJ n ( 4) The number *(A) is well defined, since a (AH+ HA,:<) is a conn tinuous function of H, and J is a compact set. It gives us the minimal eigenvalue of the Lyapunov transform AH+ HA>:<, where H runs through I all matrices in J. In what follows the value of *(A) is determined in case A is a normal matrix, while lower and upper bounds for *(A) are given in the general case. To find *(A) we start with some observations on J and the function a (AH+ HA,:<). n First, note that for every nxn unitary matrix U we have UJU* =J • ( 5) Next, the set J is compact and convex (in the space V). Moreover, it follows from ( 1) that for every H, K E J and 0 ~ 0 s: 1, implying that a (AH+HA,:<) is a n concave function on the convex set J. We claim now that in order to find w(A) it is enough to consider a (AH+ HA*) only on the extreme n points of J. lemma. This follows immediately from (2) and from the following This lemma is essentially known [16] even in more general spaces, but a brief matrix theory proof is given for the sake of completeness. 40 Lemma 1. Let P. = diag( 1, 1, ••• , 1, O, ••• , O) J \.._..,--' j times j=O,l, •.• , n . ( 6) The extreme points of J are exactly the projection matrices, i.e. , the matrices of the form UP .U>:\ where U is an arbitrary nxn unitary J matrix and j = 0, 1, ..• , n. Moreover, every H E J can be written as a convex combination of (a finite number of) extreme points of J. Proof. From (5) it follows that His an extreme point of J if and only if UHU* is, where U is an arbitrary unitary matrix. Hence it suffices to find what real diagonal matrices are extreme points of J. D = diag(d , d , ••• , dn) E J. 1 2 So let Since every number in the open interval (0, 1) is a convex combination of 0 and 1, the matrix D cannot be an extreme point, unless all the main diagonal entries are equal to 0 or 1. Conversely, we show that if d. = 0 or d. = 1 for all j, 1 :S: j s: n, D is J J an extreme point. We can assume that D , where I is the 0 I identity matrix of order q for some 0 :S: q :S: n. Suppose that D = [o o] = 9H+(l-e)K for some H,K E J and 0<8<1. Partitioning Hand K con- formably with D, we find that 8H ll + ( 1- 9) K 1l = 0. 41 But H ::!: 0 and K ::!: 0 imply H K 12 = O. = K 11 11 = 0, and consequently H 12 = Furthermore, together with 0 s H 22 ~ I and 0 ~ K 22 $ I imply H 22 = K 22 = I. This completes the first part of the proof. In proving the second part of the lemma we can again consider only real diagonal matrices. we may assume that 1 ~ d 1 We let D = diag(d , d , .•. , dn), where 1 2 ~ d 2 ::!: ••• ~ dn ~ O. The decompos i tion n D where dn+l = 0 and d 0 = :6 (d . - d ·+ l) P . j=O J J J = l-d 1 , describes Das a convex combination of extreme points of J, completing the proof. We denote now P. = [UP .U~:c: U an arbitrary unitary nxn matrix}, J J (7) j=O,l, ... ,n, ,,, W.(A) = J min fa (AH+ HA'")} HEP. n J j=O,l, •.• , n . The sets P . are compact, hence the W.(A) are well defined. J J from (4), (8) and Lemma 1 it follows that W(A) = w.(A) J • (8) Moreover, (9) 42 We shall use (9) to find w(A) by evaluating the W.(A). Note that J P = [O} andP =[I}, so w (A) = O and w (A)= a (A+A*). 0 n n n 0 Notation: From now on all vectors are column vectors with n com- ponents, denoted by x, y and these letters with subscripts. The com- plex conjugate and transpose of x is denoted by x>:c, and the transpose t of x by x. Lemma 2. Let 1 ~ j :C n. The following are equivalent: HEP . . J (b) There exist vectors x , x , •.• , xj such that 1 2 (a) k, J, = 1, 2' ... ' j ' ( 10) and j H Proof. * ):c Hence H = UP .U for some unitary J J Denote the columns of U by x , x , ••. , xn. Also, denote 1 2 (a):9(b). matrix U. :6 = k=l ~~ LetH EP .• the unit vector with 0 in all places except 1 in the k-th entry by e k, k = 1 , 2, . . . , n. Then j H = UP.lfc = J :B ~{ k=l Hence the vectors x ,x , .•. ,xj satisfy (10). 1 2 (b)~(a}. Suppose that x , x , •.. , xj satisfy (10). 1 2 We can find vectors xj+ 1 , •.. , xn such that x 1 , x 2 , •.. , xn form an orthonormal basis. The 43 matrix U, whose k-th column is ~· is a unitary matrix and satisfies H = UP .U,~. J Corollary 1. H Er n- 1 if and only if there exists a vector x such that (x, x) = 1 and H = I-xx,~. Proof. This follows immediately from Lemma 2. Relations among the w.(A) The purpose of the next theorems is to prove that ~(A) = w (A). 1 For each vector x, such that (x, x) = 1, we define ( 11) Lemma 3. Let x be a vector such that (x, x) = 1. Then a 1(M(A, x)) ~ o = a 2 (M(A, x)) = .. . . = a n- 1 (M(A, x)) ~an (M(A, x)) . Proof. e 1 ( 12) There exists an nXn unitary matrix U such that Ux = e , where 1 is the unit vector whose first component is equal to 1 and all other components are equal to O. ,,, Let B = UAU"' = (b ..). lJ Let f(A.) be the characteristic polynomial of M(A, x). Then We have 44 This completes the proof. Lemma 4. Proof. Recall that the trace function satisfies tr(A A ) = tr(A A ) for 1 2 2 1 every pair of matrices A 1 and A 2 of orders mx p and pX m, respectively. Moreover, the trace of a 1x1 matrix is equal to its single entry. Using these properties, Lemma 2 and the variational characterization of the smallest eigenvalue of a Hermitian matrix, we ge t min a.n(M(A,x)) = min min i~(Axx':c+xx':cA>:~)y (x, x)=l (x, x)=l (y, y)=l w (A) = 1 = min min [tr ( y':c Axx* y + /:~xx':~ A':~ y) J (x, x)=l (y, y)=l = min min [tr(Axx':cyy':c) + tr(y/:Cxx>:CA>:C)J • (x,x)=l (y,y)=l Replacing A by A* we get w (A':~) = min min [tr(A':Cxx>:Cyy':c) + tr(yy':~xx>:cA)] ( x, x) = 1 ( y, y) = 1 = min min [tr(xx':cyi~A*) + tr(Ayy':Cxx*)] ( x, x) = 1 ( y, y) = 1 = min min [tr(yy:o,icxx,:C A*) + tr(Axx':Cyy>:c)] = w (A) 1 (x, x}=l (y, y)=l 1 Theorem 1. Proof. We first prove that Wn(A) :<!: w (A). 1 We have • 45 Also, it follows from ( 12) and the trace properties that for each vector x, such that ( x, x) = 1, Hence, by Lemma 3, a. (M(A, x)) :e x*(A+ A *)x n We conclude that w (A) = 1 min a. (M(A, x)) S min x*(A+ A *)x = a. (A+ A~c) = n n (x, x)=l (x, x)=l It remains to prove W1 (A) ~ W2(A) ~ •.• ~ wn-1 (A). n-2. Let 1 :;; j s We prove that w/A) ~ Wj+l (A). ·'c There exists a matrix H. E P. such that a. (AH.+H.A''} = w.(A). n J J J J J By Lemma 2 we can write j ~ ~{ H. = k=l J where x , x , ••• , xj satisfy ( 10). 1 2 There exists a vector y such that (y, y) = 1 and ):< * ):< W.(A) = a. (AH.+ H .A ) = y (AH.+ H .A ) y • J n J J J J We look now on the linear subspace spanned by x , x , ..• , xj, y. 1 2 j ~ n-2, there exists a vector xj+ 1 ( 13) S.ince such that ( x j+ 1 , ~) = 0 j+ 1 , k ' k=l,2, ••. ,j+l, ( 14) (xj+ 1 , y) = 0 46 Define now j+ 1 = :6 x. x.* = HJ. + xJ.+ xJ+: ~- k=l K 1 I< It follows from Lemma 2 and (14) that Hj+l E Pj+l" the last equality following from ( 13) and ( 14). 1 Moreover, Applying again the varia- tional characterization ( 1), we get W.(A) J • Theorem 2. Proof. It is enough to show that w (A) = *n- l (A), by Theorem 1. 1 Using Corollary 1, ( 11), properties of the trace function and Lemmas 3 and 4, we get: a.n (AH+ HA *) = [ * min a. A(I·xx ) +(I-xx*''~ )A''] n (x, x)=l = min min y* [A( I-xx*) + (I-xx*) A *Jy (x, x)=l (y, y)=l = min min [y*(A+A*)y - y*(Axx*+xx*A*)y] (y,y)=l (x,x)=l = [y*(A+A*)y - max y*(Axx*+xx*A*)y] min (y, y)= 1 (x,x)=l = [y*(A+A*)y max tr(l'<Axx*y+ y>:Cxx*A*y)] min (y, y)=l (x, x)= 1 47 = [ y *(A + A*) y min max tr ( x >.~ yy*A x + x *A* yy~~ x )] (x, x)=l (y, y)=l = [y,..(A+A )y - max x'"(yy A+A*'!c yy'')x] min (x, x)=l (y, y)= 1 ... .,, * * = min [y*(A+A*)y - et (M(A*, y))] 1 (y, y)=l = min (y' y)= 1 = min (y, y)=l w(A) = Corollary 2. w1(A) and w(A) Proof. = w(A*) • The proof follows from Theorems 1 and 2, Lemma 4 and (9). Computation of W(A) for Normal and Hermitian Matrices We use Corollary 2 to find W(A), by computing w (A). 1 A is a normal and stable matrix In case V(A) is determined precisely, while for a general stable matrix only upper and lower bounds are given here. We assume now that A is a given normal and stable matrix. From (5) and the identity U(AH +HA*) u* = ( UA U*) ( UHU*) + ( UHU*) ( UA u*) >:c it follows that V(A) = W(U* AU), for every nxn unitary matrix U. Hence 48 we can assume that A is a diagonal matrix, and we write ( 15) Here A. = µ.. + i\1. ' J J J ( 16) j=l,2, •.. ,n where i = J-1, and µ. , µ. , •.. , µ.n and 'J 1 , v , .•. , vn are real numbers 2 1 2 satisfying We define ( 1 7) so A= DR + iDr Obviously, A =A* if and only if D = O. 1 Let ·x = (sj) be a column vector with coordinates i.; , i; 2 , ... , sn' 1 satisfying (x, x) = 1. Recall that W(A) = where w1(A) = M(A, x) is defined by ( 11). nomial of M(A, x). min etn(M(A,x)) (x, x)=l Let f x 0 . ) be the characteristic poly- Since A is a diagonal matrix, it is easy to verify that f 0 .) = x An- 2 fA 2 -2r~ µ..ls.12\A+ l l ~=l J J ) ,:; Ii; J. i;k Iz [ ( AJ.+;::J.)(Ak+\k) - (A J.+A,J (\J.Hk) JI. ~j<kSn Jj 49 ~: fx(A.) depends only on the Isj I , so we can assume from now on (for the case of normal A) that x has only real entries. This and the computation of a (M(A,x)) from f (A.) give n x a (M( A, x)) = 6n µ, • j= l n s2. - ~~n6 µ. . s2)2 . + ·= l J J ( 18) J J Denoting 6( x) = n (6 j= l 2)2 + J J µ. . S . ( 19) we have t.(x) > 0 and t.(x) 2 4 ~ 2 2 µ. • s . + 2 L1 µ. . µ.ks . s k j=l J J l~j<k~ J J = 6n Since (x, x) = 1, we get 6(x) (20) Also, n 2 2 2 2 s.2 + 1 ~j<k~ 6 ( v. - 2v. vk + "'k >s. sk = 6 J J J µ. ~ j= 1 J J 6 n j= l 2 2 µ.J. s j 50 + 6n v.2 s .2 (1 - s .2 ) - 2 j= 1 J J J 6 1 $ j<k$n v. vk s .2 sk2 = 6n J j= 1 J ( µ. .2 + v.2 ) s .2 - (n 6 v. s .2)2 J J J j= 1 J J so ti(x) can be written in the following form: 2 ll(x) = 2 6n ( µ. .2 + v.2 ) s .2 - ( 6n v. s.2) = x t (DR + DI2.) x - ( x t D 1x) 2 . j= 1 J J j= 1 J ( 2 1) J J Thus, n 2 ~ a. (M(A, x)) = 6 µ..$ . - ll(x) n j= 1 J J The last expression can be written in a homogeneous form of degree two, using the fact that (x, x) = xtx = 1. Indeed, We are interested in the minimum of a. (M(A, x)), subject to the n equality constraint (x, x) = 1. We use the method of Lagrange multi- pliers and look on the function a.n (M(A, x)) - S(x, x) where S is a Lagrange multiplier. The real vector x = ( sJ.) mini- mizes a. (M(A, x)), subject to (x, x) = 1, only if the equations n oa.n (M(A, x)) ae: . -J and 2se:-J. = 0 ' j = 1, 2 •••. , n , 51 n (x, x) = ~ s~ = 1 j= 1 are satisfied. J Writing these equations in detail we get: t 2 2 t J [2µ..-6(x) -i [µ. .2 +-.;.2 +x(DR+Dr)x-2(xDix)\) . }-213 i;. = 0 , J J J J j J = 1,2, •. .,n , (23) n ~ s~ = 1 j=l J Since a. (M(A, x)), in the form given by (22), and (x, x) are homon geneous functions of degree two, it follows from Euler's theorem on homogeneous functions that if x and 13 satisfy (23) then 13 = a.n (M(A, x)) • (24) To simplify subsequent computations we make, for the time being, the following assumptions: Assumption (a). The matrix A is given by (15). We may assume without loss of generality that Al , A , .•. , An are distinct. 2 Otherwise, suppose that Al, A , .•. , Ar (r < n) are the distinct numbers among 2 A , A , •.. , An' and define B 1 2 = diag(A 1 , A2 , .•. , Ar). It follows from (22) that w (A) = w (B), and B is a matrix of . order r with distinct eigen1 1 values. Assumption (b). Consider the points (µ..,\I.), j = 1, 2, ... , n, in the Cartesian plane. We assume that no four of these points lie on one J J 52 proper circle. This assumption will be removed later by a continuity argument. Let the vector x minimize ex. (M(A, x)), subject to (x, x) = 1. n Then for all indices j such that 2µ. - 6(x) J s.J -:/: 0 the equation -i [µ.2 + v.2 +xt (DR+D 2 2 t )x - 2(x D x)v.} - 2S = 0 J 1 J 1 (25) J must hold. Hence all the corresponding points ( µ., v.) lie on one J J proper circle. Because of assumption (b) it follows that x has at most three nonzero components, and in the Hermitian case at most two nonzero components. Thus, in order to find w(A), we need only consider vectors with at most three nonzero components (two at most in the Hermitian case) and satisfying (23). Case 1. We investigate three cases. The vector x has exactly one nonzero component. case it follows from ( 18) that Cl (M(A, x)) = O. n ning of this chapter, w(A) scalar matrix. In this As indicated in the beg in- ~ 0 with equality holding if and only if A is a But, by assumption (a), A is not a scalar matrix, and hence the required minimum is not attained at x. Case 2. The vector x has exactly two nonzero components. So let 1 $ k < t ~ n, and assume that all the components of x are equal to zero except sk and s;,• We denote (26) and 53 2 = s. , J J j = k, J, • 'Tl· (27) Equations (23) are rewritten here as j = k, 1. ' (28) and 1\ + 11,e = 1 ; 7\ > 0 ; Tl,e > 0 • (29) In order to solve these equations we assume further that \l~.e > O. It is not difficult to remove this restriction after finishing the calculations. We use here the expression (20) for ti(x), so we have Subtracting the equations for j = k and j = .t in (28) gives 2 2 2 J-i [(µk-µ..t)+(vk-v.t) 2 2 2 2 2µk.t - [ µkT\+µ.tn.t+vk..e'r\c'rl..e - 2( vk - v t)( 1\ vk+ ri .e v.t)} = o and substituting n.t 2 µk.t = 1 -1\ gives the equation 2 2 2 2 µk - µ .t + \lkt - 2 \)k.t1\ = ----2.----.2..----..2......_..2~~---2---2......... f (30) [µ. 1. + (µ.k - µ .t + \lk1) 1\ - \lk.t T\c] We show that (30) possesses a solution in (0, ~]and, conversely, every solution of (30) must lie in (0, ~ = µ .t' for then T\c = iJ. This is obvious in case i is the only solution of (30). In case µk > µ .t the right-hand side of (30) for ~ = 0 is lal'lger than the left-hand side 54 of (30), while the right-h'a nd side of (30) for ~ :a: ~is smaller than the left-hand side. Rewriting (30) leads to the following quadratic equation, 0 . Its only solution in (O, ~] is ( 31) where we define Hence It remains to determine an(M(A, x)). given by (31), and n .e = s~ = 1 - TJk. are uniquely determined. We know that nk = s~ is Hence the modulii of sk and s J, Substituting these values into a (M(A, x)) and n using (30), we get 2 2 2 ..1. an (M(A, x)) = ~µ.k + Tl J,µ. J, - [ T)kµ.k + n# J, + ~ T)J, vkJ,] 2 2 ]~ = µ. J, + ~µ.kl, - [µ. 2J, + ~(µ.k2 - µ. 2.e) + ~( 1 - ~) vkJ, 2 2 2 2 2 2 2 2 ~ = µ. + µ.k J, ( ( µ.k J, + vk J,)( µ.k - µ. J, + vk J,) - [ µ.k i ~ J, + vk J,) eJ } e 2 2 2 2 vk ;, ( µ.k J, + vk J,) 55 2 2 2 µk - µ i, + \)k i, 2µki, 2 2 2 2 2 2 2 2 2 .1. 2 \)ki,[(µki,+ ~.e)(µk - µ p,+ \)k,e> - [µkiµki,+ ~i,) 9] } +~~~~~~~~---~_,..~-,,,~~~~~~- Zµki,\)k i, (µki,+ \Jki,) Hence, and a.n (M(A, x)) Substituting for 8 from (32) we finally get a.n (M(A, x)) or (33) 56 2 The last formula was obtained tmder the assumption that '1ct > o. However, (33) remains meaningful if we put vkf, = 0. Indeed, if '1c.e = 0 we can still show by similar calculations that if x satisfies (28) and (29), then a. (M(A, x)) is given by (33). n We define <Pk,e = (34) lSk<f,S:n. = It follows from the preceding calculations that if the vector x has exactly two nonzero components and satisfies equations (23), then for some Case 3. k, t; 1 s: k < f, s n . The vector x has exactly three nonzero components. (35) So let 1 s: k < t < m s: n, and assume that all the components of x are equal to zero except sk' st and Sm· It follows from (25) that the points (µ ., v.), j J J lie on a proper circle. = k, f,, m, must Hence, if this is not the case, there exists no vector x which satisfies (23) and whose only nonzero components are sk' st' Sm· This explains the fact that for Hermitian matrices we have to consider only Cases 1 and 2. If there exists a proper circle passing through ( µ ., v.), J J j =k, t,m, let (cktm'~ f, m) and rktm denote its center and radius, respectively. Thus, 57 (µ.-ckn) J x,m 2 +(v.-dkn) J x-m 2 j = k, P,, m • (36) But, rewriting (2 5) we get .1.2 ( µ . - 6( x) 2) J t + ( v. - x D 1x) J 2 .1. t 2 2 = - 2 13 .6( x) 2 - x (DR + DI ) x + .6(x) + (xt D 1x) 2 , j = k, p,, m • (3 7) Comparing (36) and (3 7) and substituting for .6(x) using (21), we find that the following equations must be satisfied by x: 1- .6(x) 2 2 2 t 2 .1. = [xt (DR+ D )x - (x D x) ] 2 = ck.tm 1 1 t x D x 1 t xx (38) = d ktm (39) =1 (40) 8 = 2 rkp,m - 2ck,em . ( 41) Let 11· = J s.J2 > 0 , j = k, .t, m • Since .6(x) > 0, it follows that x satisfies equations (38), (39), and ( 40) if and only if ck .tm > 0 and the following linear system has a positive solution for ~· 11.e' 11m: ~ ~ + v ,e 11.t + vm 1\n = dk.tm 2 2 2 2 2 2 ( µk + vk) ~ + ( µ P, + \J ;,> 11,e + ( µm + vm) 1\n (42) 2 2 = ck P,m + dk .tm • 58 We are ready to conclude the discussion of Case 3. We see that it is possible that there exists no vector x which satisfies (23) and whose only nonzero components are sk' s ;,' Sm· Such a vector exists if and only if the following conditions are satisfied. = k, ;,, m. (i) There exists a proper circle passing through(µ,., v.), j (ii) cki,m > 0. (iii) The linear system (42) has a positive solution for T\:• nt' nm . J J If these conditions are satisfied, the modulii of sk' st' t;m are uniquely determined. Moreover, we conclude from (24) and (41) that an (M(A, x)) = ~ = - 2 rkJ,m 2cki,m ( 43) so a (M(A, x)) is uniquely determined. n Finally, we define 2 ki,m 2cki,m r ~ki,m if conditions (i), (ii), (iii) are satisfied = 1 :Ck< 1, <m :S:n • 0 (44) otherwise This completes the investigation of the three cases. Recall that this investigation was carried out under assumptions (a) and (b). We are ready to find W(A) for a normal matrix A, foil owing the next elementary lemma. Lemma 5. Let s > 0, Tl > 0 and s ~ T). Let 59 h( i;, ri> and Then (Here, naturally, hE: and h denote partial derivatives.) ri Proof. Trivial. Theorem 3. Let A = A~:~ be a positive definite matrix with eigenvalues lfr(A) Proof. Again we may assume without loss of generality that A = DR, where DR is given by (17). of A are distinct. We further assume that all the eigenvalues We know that lfr(A) min a:n (M(A, x)) • (x,x)=l w1 (A) is attained at x, such that (x, x) = 1, only if x satisfies (23). Under our assumptions, this vector x has at most two nonzero components. The discussion of Cases 1 and 2 shows that there exist k and J,, 1 ~ k < ;, ~n, such that a.n(M(A,x)) = <lkp,' where Here the expression for c,ok,R, is a specialization of (34) for the 60 Hermitian case. Since there are only a finite number of cpk.t' we get where the second equality follows from Lemma 5. The theorem remains true if the eigenvalues of A are not distinct by the remark of assumption (a). This completes the proof. Let A be a normal stable matrix of order n (n ~ 2) with Theorem 4. .1. >:c eigenvalues Al, A , ••. , An' and suppose that A r A • 2 ( 1) If the eigenvalues of A are distinct, then min ~(A) rv~<.eSn min cpki,; min 1 S:k<.t<mSn ~ki,ml for n ~ 3 1} (45) = for n = 2 where the numbers cpk.t and ~ki,m are defined by (34) and ( 44), respective! y. (2) If the eigenvalues of A are not distinct, suppose that Al, A , ••• , Ar are the distinct numbers among Al, A , ••. , An. 2 2 Let B be any normal matrix of the order r (r <n) whose eigenvalues are Al, A , .•. , Ar. 2 Then ~(A) = ~(B), where ~(B) can be calculated by part ( 1). Proof. It is enough to prove part ( 1) of the theorem by the remark of assumption (a). Thus assume that A. , A. , .•• , A.n are distinct. 1 2 61 We may again assume without loss of generality that A is a diagonal matrix, given by (15) and (16). We further assume that no four of the points (µ..,\J.), j = 1,2, .•. ,n, lie on a proper circle. J J The value W(A) = w (A) is attained at x, such that (x, x) = 1, only 1 if x satisfies (23). Under our assumptions, this vector x has at most three nonzero components. The discussion of cases 1, 2, 3 shows that there exist k and J,, 1 1.:k < ..e ~n, such that an (M(A, x)) = m. , ,..Kl, m, 1 ~k< J,<m ~n, such that an(M(A, x)) = ~k.tm" or k, ..e, Since there are only a finite number of <Ok.t and ~kJ,m' the result follows. To complete the proof, we notice that every normal matrix can be arbitrarily approximated by a normal matrix with the property that no proper circle passes through four of the points ( µ.., \J.), j = 1, 2, ... , n. J J Since w(A) depends continuously on the entries of A, the proof is complete. Remark. We conclude from Theorem 3 that if A is a Hermitian matrix, then l\l(A) depends only on its largest and smallest eigenvalues. Theorem 4 provides an algorithm for the computation of W(A) for a normal matrix A. It also proves that for a normal, but not Hermitian, matrix l\l(A) can be expressed in terms of at most three eigenvalues of A. However, the precise identification of these eigenvalues depends on the location of the points ( µ. 1 , v 1), ( µ. , \J2 ), ... , ( µ.n' \Jn) in the Cartesian 2 plane. Finally, it is clear from the proof of Theorem 4 that w(A) can 3 be determined in a number of steps which is proportional to n , if A is an n x n diagonal matrix with distinct eigenvalues and n is sufficiently large. We illustrate Theoren 4 in the following examples. 62 Examples. (1) Let A= diag(2, 2+i, l+i, 1). Easy calculations give 1 cp 12 = - ! (17 2 - 4) 1 2 <P13 = <P24 = -(10 -3) 1 <P14 = <P23 = 1 .1. 2 <P34 = - 2 (5 - 2) - rr ~123 = ~124 = 0 1 ~134 = cp234 = - b Here ~ 123 = ~ 124 = 0 by (44), since in both cases the system (42) has no positive solution. Hence, ~(A) = ~134 = ~234 (2) . Let A= diag(2, 2+i, 2+2i, 1+4i). 1 = - 'b Hence, 1 2 <012 = <P23 = - ! (17 - 4) 1 2 <P13 = -(5 - 2) 17 - Tb <.014 5 .1. 3 (2 2 - 1) = <P24 5 .1. -3(132_ 3) = <P34 = ~123 = ~124 = ~134 = ~234 = 0 Here ~ line. 123 = 0 by (44), since the points (2, O), (2, 1) and (2. 2) are on a Also, are negative. ~ 124 = ~ 134 = ~ 234 = 0 by (44), since c 124 , c 134 and c 234 We conclude that 63 w(A) 17 = cp 14 = - TI Upper and Lower Bounds for w(A) In this section upper and lower bounds for w(A) are given. first consider normal matrices. We Although w(A) was precisely deter- mined for a normal matrix A, the following inequalities seem to be useful. Theorem 5. Let A be an nXn normal, stable matrix with eigenvalues \! = max 1 ~j<k~n Iv. - "\:I J Then Proof. We use the results of the previous section. that A is a diagonal matrix. Let x = (s.) be a real vector (see the note preceding ( 18)) such that (x, x) = 1. J -- We have by ( 18) and ( 19) n 1 a (M(A, x)) = '6 µJ.i;J.2 - l:l(x) 2 n j= 1 Using (20) for l:l(x) we get We can assume 64 • s2]1. . ~ 6( x) t s Ln6 µ. 2 . s2~1. ~ + vG6 s2 . sk2Jt . [j=6nl µ. J2 J . ·= l J J " 1 Sj<k~ J 2 2 Hence, w(A) ~ min (x, x)=l s.u-~ { 6n .s . - [n6 µ. j=l µ..2 j=l J J 2 J J 2 ( 46) and w(A) ~ {n min (x, x) = 1 2 µ..~! j= 1 J J 6 [n6 22~1.} µ,.;. j= 1 2 - J J v max ( x, x ) = 1 J 2 E'.~ e: t -J -k :::. l 'J"<k....., C6 ;;:ir~ where x varies only over real vectors. Let DR be the real diagonal matrix defined by ( 17). It follows from (20) that the right-hand side of ( 46) is exactly w(DR), so by Theorem 3 n Also, (x, x) = 6 j= 1 s2J. = 1 implies n =t 6 j, k=l j#k = 1.2 [ Hence, sf s~ ~ E'.~J E'.2 - J=l ~ e:~J = t - t 6 s~ -J j, k=l j= 1 n - -k . J 65 l 4]i ~ min 6n i;. ( (x, x)=l j=l J 1 J],_2 = [:z-Tn 2 = completing the proof. We turn now to a general stable matrix A. The upper and lower bounds for w(A) are expressed in terms of Hermitian or normal matrices, for which we know how to find the w. To get bounds for W(A), we use a theorem due to Hoffman and Wielandt. Define for A= (ajk) ,., tr(A'''A) for arbitrary nxn matrices. Theorem 6 [12]. respectively. Let H and K be nxn Hermitian matrices with eigen- Then n 6 [a .(H)-a.(K) ] J J j= l 2 ~ !IH-Kll 2 The proof of this theorem uses convexity arguments, see [12]. Recall that 1+r(A) = W(U>:~AU} for any unitary matrix U, so we can assume without loss of generality that A is a triangular matrix. 66 Theorem 7. Let A = D + T, where D is a stable, diagonal matrix and Tis a strictly upper triangular matrix (so D = diag(a 11 ,a 22 , ..• , ann) ). Then where W(D) can be determined from Theorem 3 or 4. Proof. There exists a vector x such that (x, x) =1 and Also, M(A, x) = M(D, x) + M(T, x) so Theorem 6 implies Ian (M(A, x)) - an (M(D, x)) I s: II M( T, x) II But Hence, Similarly one proves w(D) ::2: w(A) - 211T11. completing the proof. To get another upper bound for w(A), we have to drop the assumption that A is a stable matrix. We note the following: 67 Remark. The assumption that A is a stable matrix is not essential in the discussion of this chapter. In fact, w(A), W1(A), W2(A), .•. ' *n(A), and the theorems proved about these numbers, remain valid even if A is not stable. In particular, w(A) = w (A) is still true, and we can find 1 w(A) by minimizing a (M(A, x)). n The only difference occurs in the previous section, where we compute w(A) for a normal and stable matrix A. There are still three cases to consider even if A is not stable, but we can no longer disregard Case 1, while Case 2 becomes more complicated. We do not repeat the calculations, but state the generalization of Theorem 3 to an arbitrary Hermitian matrix. As indicated, the proof differs only slightly from the proof of Theorem 3. Theorem 8. Let A= A * have eigenvalues µ. 1 :2: µ. 2 :2: • • • :2: µ.n. Then if W(A) = 2µ. if n The last theorem enables us to get an upper bound for W(A). Theorem 9. Proof. Let A be an arbitrary matrix. 1 ),'< Then W(A) S: W( mA +A )) . There exists a matrix H E J such that :2: ~ a n (AH+ HA*) + ~ a (A>:CH +HA) :2: ~ V(A) + n the last equality following from Corollary 2. t W(A*) = W(A) , This completes the proof. 68 BIBLIOGRAPHY [l] C. S. Ballantine, A note on the matrix equation H = AP+PA"\ Linear Algebra and Appl. 2 (2969), 37-47. [2] R. Bellman, Introduction to matrix analysis, McGraw-Hill, New York, 1970. [3] A. Ben-Israel, Linear equations and inequalities on finite dimensional, real or complex, vector spaces: A unified theory, J. Math. Anal. Appl. 27 (1969), 367-389. [4] A. Ben-Israel and A. Berman, Linear equations over cones with interior: A solvability theorem with applications to matrix theory, Report No. 69-1, Series in Applied Mathematics, The Technological Institute, Northwestern University, Evanston, Ill. , 1969. [5] D. Carlson and H. Schneider, Inertia theorems for matrices: The semidefinite case, J. Math. Anal. Appl. 6 ( 1963), 430-446. [6] D. Carlson, Rank and inertia bounds for matrices under R(AH) ~ 0, J. Math. Anal. Appl. 10 (1965), 100-111. [7] D. Carlson, Inequalities relating the degree of elementary divisors within a matrix, Simon Stevin 44 ( 1970), 3-10. [8] F. R. Gantmacher, The theory of matrices, Vols. I, II. Chelsea, New York, 1960. [9] W. Givens, Elementary divisors and some properties of the Lyapunov mapping X ..... AX+ XA*, Argonne Nat. Lab. Rep., 1961, ANL-6456. [10] W. Hahn, Eine Bermerking zur zweiten Methode von Lyapunov, Math. Nachr. 14 (1956), 349-354. [11] E. Haynsworth, Determination of the inertia of a partitioned Hermitian matrix, Linear Algebra and Appl. 1 ( 1968), 73-81. [12] A. J. Hoffman and H. Wielandt, The variation of the spectrum of a normal matrix, Duke Math. J. 20 (1953), 37-39. 69 [13] A. Lyapnnov, Probleme G~n~ral de la Stabilite du Mouvement, Ann. of Math. Studies 17, Princeton Univ. Press, Princeton, N. J., 1947. [14] M. Marcus and H. Mine, A survey of matrix theory and matrix inequalities, Allyn and Bacon, Inc. , Boston, Mass. , 1964. [15] A. Ostrowski and H. Schneider, Some theorems on the inertia of general matrices, J. Math. Anal. Appl. 4 (1962), 72-84. [16] S. Sakai, C -Algebras and W -Algebras, Springer-Verlag, Berlin, Heidelberg, New York, 1971. [17] P. Stein, Some general theorems on iterants, J. Res. Nat. Bur. Standards 48 ( 19 52), 82-83. [18] P. Stein, On the ranges of two functions of positive definite matrices, J. Algebra 2 ( 1965), 350-353. [19] P. Stein and A. Pfeffer, On the ranges of two fnnctions of positive definite matrices II, ICC Bull. 6 ( 1967), 81-86. [20] O. Taussky, A remark on a theorem of Lyapnnov, J. Math. Anal. Appl. 2 (1961), 105-107. [21] O. Taussky, A generalization of a theorem of Lyapnnov, J. Soc. Indust. Appl. Math. 9 (1961), 640-643. [22] O. Taussky and H. Wielandt, On the matrix fnnction AX+ X A , Arch. Rational Mech. Anal. 9 ( 1962), 93-96. [23] O. Taussky, Matrices C with Cn __, 0, J. Algebra 1 ( 1964), 5-10. [24] 0. Taussky, Matrix theory research problem, Bull. Amer. Math. Soc. 71 ( 1965), 711 [25] 0. Ta us sky, Positive definite ma tr ices, in "Inequalities, " 0. Shisha Ed., Academic Press, New York, 1967. * * 1 1