I N T E R L A C I N G I N E Q U A L I T I E S F O R E I G E N V A L U E S O F S U M S O F M A T R I C E S By E R N E S T A F A R I B. Sc., University of Cape Coast, 1982 A T H E S I S S U B M I T T E D I N P A R T I A L F U L F I L L M E N T O F T H E R E Q U I R E M E N T S F O R T H E D E G R E E O F M A S T E R O F S C I E N C E in T H E F A C U L T Y O F G R A D U A T E S T U D I E S D E P A R T M E N T O F M A T H E M A T I C S We accept this thesis as conforming to the required standard T H E U N I V E R S I T Y O F B R I T I S H C O L U M B I A March 1989 © E R N E S T A F A R I , 1989 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of M frT H E IV\ UtTf CS The University of British Columbia Vancouver, Canada Date MM-CH X<j t,$<1 DE-6 (2/88) a b s t r a c t We begin with some historical remarks in section 1, where we present the basic interlacing inequalities. In the rest of the thesis we discuss R.C.Thompson's contributions to the subject. His main concern is to extend the inequalities to include more than just one of the (n — 1) x (n — 1) principal submatrices. It is clear that for each such submatrix, the interlacing inequalities are valid, but the resulting set of inequalities is not sufficient to guarantee the existence of a matrix whose principal submatrices have eigenvalues satisfying these inequalities. We have included two examples to show that Thompson's inequalities are necessary. n Table of Contents abstract ii Acknowledgement iv 1 INTRODUCTION 1 2 TRIVIAL AND NONTRIVIAL EIGENVALUES 3 3 QUADRATIC AND LINEAR INEQUALITIES 5 4 GENERALIZATION TO FORMS 17 5 GENERALIZATION TO SINGULAR VALUES 25 Bibliography 29 i n Acknowledgement I wish to express my thanks to Dr. Roy Westwick for his guidance, sound criticism and most of all, for his endless patience with me throughout the preparation of this work. I also thank Dr. G. Maxwell for reading the manuscript and providing valuable criticisms and comments. Thanks to my other teachers at U .B .C . from whom I benefitted much; especially Dr. E. Luft and Dr. K . Lam for their encouragement on many timely occassions and in words and deeds reminding me of the necessity of hard work. I express my gratitude to the Mathematics Department of U .B .C . for its generous financial support. I also thank my friend Mr. E . Akita for lending me his personal computer and giving me computer terminal tutorials for the typing of this work. I am also grateful to Ms. Sherry Armstrong for typing several drafts of this work. My appreciation to my beloved wife Comfort for accepting my emotional ups-and-downs, during my study, merrily providing a lovely home and constantly upholding me with prayers. This work is respectfully dedicated to Comfort Afari. iv S e c t i o n 1 I N T R O D U C T I O N The origins of the interlacing inequalities for the eigenvalues of a n X n matrix and its principal ( n - 1 ) x (n - 1) submatrix is generally attributed to investigations by the renowned mathematician Augustin-Louis Cauchy (1789 - 1857) [3]. His results appeared as early as 1829. Cauchy found that if H is an n - square real symmetric matrix with eigenvalues A i , . . . , A n ordered so that A a > A 2 > ••• > A n (1.1) and if H(i\ i) denotes the principal (n - 1) - square submatrix of H obtained by deleting row i and column i with eigenvalues . . ., /xn_i ordered so that > > > (1.2) then Ai > Mi > A 2 > • • • > A n_j > ^ n_i > A n (1.3) These are known as the interlacing inequalities. In 1957, Ky Fan and Gordon Pall [5] published the converse of the above results and also showed that it holds for Hermitian matrices. The results by Ky Fan and Pall are as follows: Given real numbers A i , . . . , A n and . . . , fin_1 satisfying (1.1), (1-2) and (1-3), there exists a n-square Hermitian matrix H with eigenvalues Aj,. . . , A„ and 1 Section 1. INTRODUCTION 2 (n - l)-square principal submatrix with eigenvalues fij,.. ., Ltn-i Subsequently, there have been several papers extending these ideas in various ways. The principal contributor is R.C. Thompson who has a series of papers which we will be describing. S e c t i o n 2 T R I V I A L A N D N O N T R I V I A L E I G E N V A L U E S o Given A, a n X n diagonalizable matrix with eigenvalues A i , A 2 , . . . , A n and principal submatrices A ( l \ l ) , . . . ,A(k\k) (k fixed,1 < k < n) we know that interlacing inequalities holds seperately. These are Ai < fin < A 2 < fil2 < • • • < A n_! < filin-i < A n (2.4) Assume that real numbers A; and fil3 are given satisfying (2.4). It is not in general true that an A can be found such that its first k principal submatrices have these fiXJ as their eigenvalues. In fact suppose for A l 5 . . . , A n , we assume that every set of k interlacing systems of inequalities can be realised by a matrix A with eigenvalues A l 5 . . . , A n and k principal submatrices A( i \ i ) . This implies the strong condition that each of the eigenvalues has multiplicity at least k. It is stated precisely in the following theorem. T h e o r e m 2.1 Let k be fixed, 1 < k < n. As U varies over all unitary matrices the eigenvalues Mil < • • • < Mi,n-1 of the principal submatrices H(i\ i) of H = U D U'1 where U is unitary and D = diag(Aj., A 2 , -. . , A n ) 1 < i < k, independently assume all values permitted by the inequalities (2.4) if and only if each distinct eigenvalue of H has multiplicity at least k. 3 Section 2. TRIVIAL AND NONTRIVIAL EIGENVALUES 4 In order to address the problem of what extra conditions are needed on the eigenvalues of A so that the inequalities are sufficient to guarantee the existence of A, Thompson [10] defined the trivial and nontrivial eigenvalues for matrices. Let A a < A 2 < • • • < A 5 be the distinct eigenvalues of A, where A„ has multiplicity ea, 1 < a < s; ej + • • • + es = n. A( i \ i ) has \ a as eigenvalues with multiplicity ea — 1 or larger. Thus \ a with multiplic-ity ea — 1 are always eigenvalues of A( i \ i ) , 1 < a < s. These are called the t r iv ia l eigenvalues of A( i \ i ) . There exist s - 1 additional eigenvalues of A( i \ i ) denoted by Mil < Mi2 < • • • < M*,s-1 and these are called the nontr iv ia l eigenvalues of A( i \ i ) . They satisfy Ai < Mil < A 2 < /xi2 < • • • < A s _ i < M z , 5 - i < A s (2.5) It may happen that the nontrivial eigenvalues of A(i \ i ) are not all distinct and that some of the nontrivial eigenvalues of A( i \ i ) equal some of the trivial eigenvalues. S e c t i o n 3 Q U A D R A T I C A N D L I N E A R I N E Q U A L I T I E S Thompson [11] established a new set of inequalities involving the eigenvalues of a matrix form except in certain special cases where they degenerate into inequalities involving arithmetic means of the relevant eigenvalues. Let H, H(i \ i ) , A t , ^ be defined as in section 2. We have of course the Cauchy inequalities (2.4). Thompson inequalities are : A and its principal (n - 1) - square submatrices. These inequalities are quadratic in E n Aj Mi,j — 1 f^ij Aj Xj — Aj_i Aj+i — Xj > 1, 1 < j < n . (3.6) n E < i , 1 < j < n. (3.7) In (3.6) the factor and in (3.7) the factor are absent if j = l . 5 Section 3. QUADRATIC AND LINEAR INEQUALITIES 6 Again, in (3.6) the factor Aj+i — Aj and in (3.7) the factor Pij ~ Aj Xn — Aj are absent if j=n. Thompson referred to the inequality (3.6) as the upper quadratic inequality based on Xj and he referred to the inequality (3.7) as the lower quadratic inequality based on Xj. He said "quadratic" because of the fact that the left sides of (3.6) and (3.7) are polynomials of degree two in Liir Notation: Let n j A j + 1 = n'1 YL^i\ 1 ^ 3 < s- (3-8) i.e. jAj+i is the arithmetic mean [3] of the nontrivial eigenvalues of the H(i \ i) belonging to the interval [Aj,Aj+1]. (n - l j r a -^ j + n _ 1 A J + 1 <j A J + 1 < n - 1 A j + (n - l ) n - 1 A J + ] , 1 < j < n (3.9) are referred to as Linear inequalities. [5] In order to get examples where the quadratic inequalities are seen to be necessary, we display the case n=3 explicitly. Let H be a 3-square Hermitian matrix with distinct eigenvalues Ai < A 2 < A 3 (3.10) Section 3. QUADRATIC AND LINEAR INEQUALITIES 7 Let H(3 \ 3) denote the principal 2-square submatrix of H obtained by deleting row 3 and column 3. Let M n < M12 M21 < M22 ( 3 - 1 1 ) M31 < M32 be the eigenvalues of H(3 \ 3). The Cauchy interlacing inequalities assert that Ai < M n < A 2 < M12 < A 3 Ai < M21 < A 2 < M22 < A 3 (3.12) Ai < M31 < A 2 < ^ 3 2 < A 3 . For the upper quadratic inequalities we get M n — Ai M21 — Ai / x 3 1 — Aj + 7 1 , > 1 (3.13) A 2 — Ai A 2 — Aj A 2 — Aj => M i l + M21 + M3i >' 2Aj + A 2 A 2 . ~ M11 M12 — A 2 ^ A 2 — fj,2i M22 ~ A 2 ^ A 2 — fj,31 H22 ~ A 2 ^ ^ ^ ^ A 2 — Aj A 3 — A 2 A 2 — A^ A 3 — A 2 A 2 — Aj A 3 — A 2 A 3 ~ M12 A 3 — ^ 2 2 ^ A 3 — ^ 3 2 ^ ^ ^ ^ A.? — Ao A 3 — A 2 A 3 — A 2 Section 3. QUADRATIC AND LINEAR INEQUALITIES 8 Ml2 + M22 + m32 < A 2 + 2AS For the lower quadratic inequality, we get + + ( 3 . i 6 ) A3 — Ai A3 — Ai A3 — A]^ Mn + ji2\ + M31 < 2Ai -t- A 3 A 2 — Mil ("12 ~ A 2 ^ A 2 — M21 M22 ~ A 2 ^ A 2 — /X31 ^32 — A 2 ,^ ^ ^ A 2 — Aj A 3 — A 2 A 2 — Ai A 3 — A 2 A 2 — A x A 3 — A 2 A 3 — M12 A 3 ^ /x22 ^ A 3 — fi32 < ^ ^ ^ A 3 — Ai A 3 — Ai A 3 — Ai =*> M12 + M22 + M33 > Ai + 2A 3 We note that (3.14) and (3.17) have the same left hand side so they imply equality (both equal to 1). While (3.13), (3.15), (3.16), (3.18) give rise to the linear inequalities. We get 2Aj + A 2 < M11 + M21 + Msi < 2A : + A 3 (3f19) Ai + 2A 3 < M12 + M22 + M32 < A 2 + 2A 3 (3.20) Now, if we consider the example for the case Ai = 1,. A 2 = 2, A 3 = 3 the linear inequalities become 4 < M11 + M21 + M31 < 5 (3.21) Section 3. QUADRATIC AND LINEAR INEQUALITIES 9 7 < Ml2 + M22 + M32 < 8 (3.22) and (3.14) and (3.17) become (2 - Mn)(Mi2 - 2) + (2 - II21)(JI22 - 2) + (2 - / i 3 i )v>32 - 2) = 1 (3.23) If M n = M21 = M3i = A , then clearly (3.12) is valid but (3.13) fails. If M i l = Ml2 = M21 = M22 = M31 = M32 = A 2 then the linear inequalities (3.13), (3.15), (3.16), (3.18) are all valid but (3.14) is not. Now for fixed k, with k < n, let Qn^ denote the set of all sequences {ii,i2, • • •, ifc} of integers such that 1 < i i < i 2 < • • • < ifc < 'n. The number of sequences in Qn^ is Section 3. QUADRATIC AND LINEAR INEQUALITIES 10 Let A[tu\o;] denote the principal submatrix of A lying at the intersection of rows and columns i j , i 2 , • • • ,ik- The submatrix A[u>\a;] is Hermitian arid let be the eigenvalues of A[a>\u>]. The Cauchy interlacing inequalities asserts that Aj < < Xj+n-k, l<J<k (3.24) Thompson [15] established the following bounds on the arithmetic mean of the LtWJ as io varies over Qn^ and j is fixed: ^ , ^r^n—k+j—r — I n \ n-k r=0 E < E * " A i + r (3-25) where *r = Er(n- l , n -2 , . . . , f c){nf = f c + 1 z}- 1 , 0 < r < n - k (3.26) n — /c E * r = 1 (3.27) r = 0 £V(n — 1, n — 2,. . . , fc) denotes the elementary symmetric function of degree r on the integers n - 1, n - 2, . . .,k. The significance of the inequalities (3.25) is that they provide convex combinations of Aj, Aj.fl,. .. , \ 3 + n - k which are bounds for the arithmetic mean, over all k X k principal submatrices of A, of the j th eigenvalue of each of these submatrices. That (3.27) holds follows immediately by setting A = 1 in the polynomial identity Section 3. QUADRATIC AND LINEAR INEQUALITIES 11 n ; ^ ( A + j) = £ Er{n - 1, n - 2,..., k)Xn~k+r. (3.28) r = 0 Iii order to see what these inequalities look like, we produce here explicitly, the case n = 4, k = 1, 2, 3. Now for n = 4, k = 1, we get u) = {i,}, 1 < ix < 4 u, = { l } , {2}, {3}, {4}. Let A[{1}\{1}], A[{2}\{2}], A[{3}\{3}], A[{4}\{4}] denote the prm-cipal submatrices of A . Let . < M{1}1, M{2}1, • M{3}1, M{4}1 be the eigenvalues of A[o>\tc>]. X, ^ 1 = ^{^{l}! + ^{2}1 + M{3}1 + M{4}l} (3.29) 1 y utQnk 3 X * r A i + r = * 0 A i + * i A 2 + * 2 A 3 + * 3 A 4 (3.30) r = 0 3 X * r A 4 _ r = * 3 A i + * 2 A 2 + * i A 3 + * 0 A 4 .(3.31) r = 0 Section 3. QUADRATIC AND LINEAR INEQUALITIES 12 Now 24 ^ ( 3 , 2,1), * 2 * 3 - £ , . ( 3 , 2 , 1 ) *o = " - £ 0(3,2,1) 24 0 < r < 3 ^ 2 ( 3 , 2 , 1 ) ^ 3 ( 3 , 2 , 1 ) n? = 1 (A + j ) = £ £ r ( 3 , 2 , l ) A 3 - r r=0 (3.32) (3.33) A 3 + 6A2 + 11A + 6 = £ 0 (3 ,2 ,1 )A 3 + £ x (3 ,2 ,1 )A 2 + £ 2 (3 ,2 ,1)A + £ 3 (3 ,2 ,1)A° ^ (3 ,2 ,1 ) = 1 £i(3,2,1) = 6 (3.34) £ 2 ( 3 , 2 , 1 ) = 11" £3 (3 ,2 ,1) = 6 From (3.32) and (3.34) we get 0 24 ' From (3.30), (3.31), we get 1 4 ' 2 24' 3 4' 1 1 11 1 V* * r A i + r = — Ai + - A 2 + — A 3 + - A 4 (3.35) ^ + 24 4 24 4 ^ ; r = u Section 3. QUADRATIC AND LINEAR INEQUALITIES 13 E * r A 4 - r = 7 * 1 + ^ 2 + 7 * 3 + ^ 4 (3.36) Finally, we get 1 1 1 1 1 1 , , 1 , 1 , 11 , 1 , - A i + — A 2 + - A 3 + — A 4 < - { M { i } i + M { 2 } i + M { 3 } i + M{4}i} < 24 * + 4 2 + 24 3 + 4 • (3.37) For n = 4, k = 2 u = { i i , ^ } , 1 < i\ < "i-2 < 4 i.e. " = {1 ,2} , {1,3}, {1,4}, {2,3}, {2,4}, {3,4}. Le tA[{ l ,2} \{ l ,2} ] , A[{1,3}\{1,3}], A[{1,4}\{1,4}], A[{2,3}\{2,3}], A[{2,4}\{2,4}], A[{3, 4}\{3, 4}] denote the principal submatrices of A. Let M{1,2}1 < M{l,2}2, M{1,3}1 < M{1,3}2, M{1,4}1 < M{1,4}2, M{2,3}1 < M{2,3}2, M{2,4}1 < M{2, 4 }2, M{3,4}1 < M{3,4}2, be its eigenvalues. Section 3. QUADRATIC AND LINEAR INEQUALITIES 14 Now for j = 1 ' i Y 1 i J ^2 fJ-tol = -{M{1,2}1 + M{1,3}1 + M{1,4}1 + M{2,3}1 + M{2,4}1 + M{3,4}l} (3.38) E * r A i + r = * 0 A i + * i A 2 + * 2 * 3 (3.39) r = 0 ^ * r A 3 _ r = * 2 A i + *aA 2 + * 0 A 3 ' (3.40) r = 0 For j = 2, we get y 2 y we<?42 E = g{M{l,2}2 + M{1,3}2 + M{1,4}2 + M{2,3}2 + M{2,4}2 + M{3,4}2} ( 3-4l) V ^ * r A 2 + r = * 0 A 2 + # i A 3 + * 2 A 4 (3.42) r = 0 V J * r A 4 _ r = * 2 A 2 + * a A 3 + # 0A 4 (3.43) r = 0 From (3.25), (3,26), (3.27) we get 12' 1 * 2 = 2 Section 3. QUADRATIC AND LINEAR INEQUALITIES 15 Finally, we get for j = 1,. 1 5 1 1 1 5 1 2 12 12 ~ 6^ { 1 , 2 } 1 +^ { 1' 3 } 1 + / i { l l 4 } 1 +^ 2' 3> 1 + M^' 4> 1" ," / /-f 3' 4> 1 - 1 2 A l + 1 2 A 2 + 2 A 3 (3.44) and for j = 2 , we get 1 5 1 1 1 5 1 2^2 + —A 3+ — A 4 < -{M{1,2}2 + M{2,3}2 + M{2,4}2 + M{3,4}2 + M{1,3}2 + M{1,4}2 < ~ A 2 + ~ A 3 + ~A 4 . (3.45) We now consider n = 4, k = 3. u> = {ti,i2,i3}, 1 < H < l2 < *3 < 4 a; = {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}. F o r j = l 2_, ~ -{M{1,2,3}1 + M{1,2,4}1 + M{1,3,4}1 + M{2,3,4}l} (3.46) 3 / w e Q 4 3 1 £ * r A l + r = tfoAi+ * a A 2 (3.47) r = 0 X * r A 2 - , = * i A a + * 0 A 2 (3.48) r = 0 For j = 2, we get - l 4 1 „ 1 2^ ^2 - - JM{1,2,3}2 + M{1,2,4}2 + M{l,3,4}2 + M{2,3,4}2} (3.49) 3 / weQi3 ^Section 3. QUADRATIC AND LINEAR INEQUALITIES 16 and X * , A 2 + r = *oA 2 + * i s (3.50) r = 0 VJ* rA 3_ r = *,A 2 + * 0 A 3 (3.51) r=0 *4 Finally, we get - A l 4- -A 2 < -{M{1,2,3}1 + M{1,2,4}1 + M{1,3,4}1 + M{2,3,4}l} < ^ A l + |A 2 (3.52) and -A 2 + -A 3 < - { / / { i i 2 , 3 } 2 + M{1,2,4}2 + M{1,3,4}2 + M{2,3,4}2} < ~A 2 + ~A 3. (3.53) S e c t i o n 4 G E N E R A L I Z A T I O N T O F O R M S In the previous sections we mentioned the links between the roots of det(XIn — A ) — 0 (the eigenvalues of A) and the roots of det{XIn^ - A(i\i)) = 0, ? = l , 2 , . . . , n , (4.55) (the eigenvalues of A(i \ i ) ) . Where A is an n-square Hermitian matrix and A( i \ i ) denote the principal submatrix of A obtained by deleting from A both row i and column i . For fixed i , the roots of (4.55) interlace the roots of (4.54) and this is the Cauchy interlacing inequalities. Let C be an n-square positive definite Hermitian matrix. Thompson [17] obtained new links between the roots of the determinantal equations. det(XC - A ) = 0 (4.56) and det(XC(i\i) - A(i\i)) = 0, i-l,...,n (4.57) The roots of (4.56) are real (they are the eigenvalues of C ~ 2 A C ~ i ) . It is a fact, not quite as well known as the Cauchy inequalities, that the roOts of any one of the equations (4.57) interlace the roots of (4.56). (4.54) 17 Section 4. GENERALIZATION TO FORMS 18 Some of the results obtained in the previous section concerning the Cauchy inequalities may be extended to the roots of (4.56) and (4.57). N o t a t i o n : In this section, we shall let be the roots of (4.56) and let Vii <••• < Vi,n-1 be the roots of (4.57). The numbers Ai, • • -, A n need not be distinct. The ideas of trivial and nontrivial eigenvalues as discussed in section 2 are also employed here. Let /Hi with multiplicity et, for i = 1, 2,. . . ,s be the distinct numbers among Ai, • • • , A n . Let 7 l < ' ' • < In be the eigenvalues of C. Section 4. GENERALIZATION TO FORMS 19 • ,ii«r Let /(A) = de/(AC - /I) and f{i)(X) = det{\C(i\i) - A(i\i)). Hence the number \ij with multiplicity e j_i , ' l< j < s arranged such that Ml < M2 < ' ' " < Ms are always eigenvalues of /(i)(A), called the t r iv ia l eigenvalues of /(j)(A). The remaining eigenvalues denoted by &!<•••< 6 , s- l are called the nontr iv ia l eigenvalues. Thompson [17] established the first interlacing principle as stated in the following theorem. Theorem 4.1 Let C be positive definite, and let V < A 2 < ••• < A n be the roots of (4.56). For fixed i , let Vii < • ' • < Vi,n-1 be the roots of (4.57). Section 4, GENERALIZATION TO FORMS 20 Then Vii ? • • • ) ^ ? t , n — 1 interlace Ai, . . . , A n ; that is, Ai < Vn < *2 < Vi2 < • • • < K-i < Vi,n-i < K- (4-58) Thompson developed new generalizations of the interlacing principle that was derived in the previous sections which he called the second interlacing principles. Let j be fixed with 1 < j < s. Define polynomials G3(X) and H0(X) by G,(A) = t h " 1 + . . - + 7 - 1 _ e i ) / ^ - + ± (71- 1 + • • • + 7 " 1 ) / ^ , (4-59) t=l A - t = j + 1 * -, H:{\) = t ( 7 i " 1 + • • • + 7 e - ( 1 ) / ^ 1 + £ ( 7 ^ + • • • + T ^ - e , ) * (4-60) Where f(X) = detCWJ=,(X-H) (4.61) Gj(X) (respectively H^X)) is alternately positive and negative when evaluated at LLS, .. . , Hence G:(X) (resp. and H:(X) has exactly one root in each interval ( M l ,M2 ) , (M2,M3 ) , - - - , ( M s - l , M s ) Let a be the unique root of GJ(X) in [fij, and let j3 be the unique root of Hj(X) in Section 4. GENERALIZATION TO FORMS 21 L e m m a 4 .2 a<(3. The second interlacing principle is stated in the following theorem T h e o r e m 4.3 (Second Interlacing Principle) Let j be fixed, 1 < j < s. With a and j3 as above, we have: (i) either ilj = = • • ' = (nj = OL or for at least one i , we have di > (ii) either 6j = (23' — " ' ' = (nj = P i or for at least one i , we have . ( a < P -Thompson showed how the quadratic inequalities and linear inequalities developed in section 3 may be generalized to the situation under discussion in this section. T h e o r e m 4.4 Let s > 1, for 1 < j < s, we have ^ i i j H > 7 i ( E 7 n V r ) (4-62) t=l Mj — Mj-1 + 1 — Mj r = l and t M j ^ 1 ^ H < 7n(E7;1) (4.63) i=\ Mj ~ Mi Ms — Mj r = i Section 4. GENERALIZATION TO FORMS 22 R e mark: Formula (4.62) is called the u p p e r q u a d r a t i c i n e q u a l i t y and (4.63) is called the lower q u a d r a t i c inequality. When j = l, the factors involving Mj — (i,j-l are understood to be absent in these formulas, and when j=s, the factors involving Mj are similarly understood to be absent. If we delete (ij Mj Mj+i — Mj we obtain the inequality (4.64) below. If we delete instead Mj ~ d,j-i Mj ~ Mj-i we obtain (4.65) below. . These inequalities (4.64) and (4.65) bound the a r i t h m e t i c mean of the T h e o r e m 4.5 Let 5 > 1. Then: 1 71 ~ T2 &,j-i ^ ^jMj-i + (1 - <t>j)H-> i — 2,3,..., s, (4.64) n ~. 1 n - Yl(v - faN+i + i1 ~ ^ )Mj, j = 1,2, • • • ,s - 1. (4.65) n i—\ Here ^ = -7i(Evi-r)> and Section 4. GENERALIZATION TO FORMS 23 0 < <f>3 < 1. R e m a r k : In (4.64) we have a convex combination of and fij which serves as an upper bound for the arithmetic mean of the (by interlacing, we only know that this arithmetic mean lies in [MJ-I, Mj]- hi (4.65) we have similar convex combination of LL3 and //j+i which bound from below the arithmetic mean of As our final result, we show how the bounds on the arithmetic mean of the re-developed in section 3 may be generalized to the situation under discussion in this section. Let Qnk denote the set of all sequences to = . . . , ij.} of strictly increasing positive integers not exceeding n. The number of sequences in Qnk is Let A[u;\a>] denote the principal submatrix of A lying at the intersection of rows and columns ii:.. . , ik. Let denote the roots of det(\C[to\iv] - A[u\u\) = 0 (4.66) It follows from the theorem (4.5) that if reQnik+1, and r 3 OJ , then the roots of det{\C[T\r] - A[T\T)) = 0 (4.67) Section 4. GENERALIZATION TO FORMS 24 are interlaced by the roots of (4.66) . It therefore follows that A j < (wj < A j + n-k, j — 1,2, ... ,k for LoeOnk Thompson [17] generalized the bounds on the arithmetic mean discussed in section 3 by finding convex combinations of A j i A j + i i • • • Aj+n-k, which serve as upper and lower bounds for the arithmetic mean / n \ E (t»j k / ueQnk of the jth root (fixed j) of all the different equations (4.66) Let Er(a1,. . . , ak) denote the elementary symmetric function of degree r on k variables. Theorem 4.6 For fixed j and k, 1 < k < n — 1, 1 < j < k, we have ^ ^ ^ r A n — k+j — r ^ n \ -1 r=0 n — k E ^ < E ^ j + r (4,68) wnere '^Y-k-rEJn- 2 L , T I - 1 - ^,...,k + l - ^ : 0 < r < n - &, (4.69) n — k (4.70) r = 0 S e c t i o n 5 G E N E R A L I Z A T I O N T O S I N G U L A R V A L U E S We examined, simultaneously all the k-square principal submatrices of an n-square matrix A in the previous sections. Usually A has been symmetric or Hermitian, and much of our effort has centered around the well-known fact asserting that the eigenvalues of an (n - l)-square principal submatrix of Hermitian A always interlace the eigenvalues of A . In this section, we mention and discuss the singular values of the submatrices (not necessarily principal submatrices) of an arbitrary matrix A due to Thompson.[18] Now a brief summary of certain particular cases of the results developed by Thompson that merit special attention is given. Let A be an nxn real or complex matrix and let <*i > ct2 > • • • > ctn be the singular value of A, defined to be the eigenvalues of positive semi definite matrix (AA*)i. Let B = Ai: be the (n - l)-square submatrix of A obtained by deleting row i and column •j, and let be singular values of B. 25 Section 5. GENERALIZATION TO SINGULAR VALUES 26 The first theorem developed by Thompson yields, as a special case, these interlacing inequalities : c*i > Pi > « 3 , a 2 > P2 > « 4 , at>Pt> a*+2, 1 < t < n - 2 (5.71) « n - 2 > Pn-2 > Ctn, That inequalities (5.71) are the best that can be asserted is shown by (a special case of) Theorem 5.3. It follows from theorem 5.3 that,if arbitrary nonnegative numbers Pi > • • • > Pn-l are given satisfying (5.71), there will always exist unitary matrices U and V such that the singular values of (UAV)ij are Pll • • • yPn-l . Of course, A and U A V always have the same singular values Section 5. GENERALIZATION TO SINGULAR VALUES 27 We now give the definition of the singular values of a rectangular matrix. D e f i n i t i o n 5.1 Let A be an m X n matrix. The singular values (5.72) of A are the common eigenvalues of the positive semi definite matrices and (A* A)*. ( Here A* is the Hermitian adjoint of A ). Since AA* is m - square and A*A is n - square, the eigenvalues of (AA*)* and (A* A)' do not coincide in full. However, it is well known that the non zero eigenvalues (including multiplicities ) of these two matrices always coincide. It is frequently convenient to define at to be zero for min(m,n) <t< max(m,n). Then a]> •••> o 4 a z ( m , n ) and the roots of A^4* (respectively A* A ) are the first m (respectively n) of these numbers. Section 5. GENERALIZATION TO SINGULAR VALUES 28 We now state the first theorem due to Thompson.[18] Theorem 5.2 Let A be an m x n matrix with singular values (5.72). Let B be a p x q submatrix of A, with singular values A > & > ••• >/?min( P,,). (5.73) Then « t > A, i = 1,2\ ... ,mm(p,q), (5-74) A > al+(m-P)+(n-g),2 < min(p + q - m,p + q - n). (5.75) We state the second theorem , also due Thompson . Theorem 5.3 Let A be an m X n matrix with singular values (5.72). Let arbitrary non negative number (5.73 be given, satisfying both (5.74) and (5.75). Then m - square unitary matrix U and n - square unitary matrix V exist such that the singular values of the p x q submatrix (UAV^i-i,. . . . • • , J,] of U A V are the numbers (5.73). We remark that the nonincreasing condition (5.73) is actually superfluous. More precisely, we have Theorem 5.3(a). Theorem 5.3(a) Let arbitrary numbers A.) • • • ) Anin(p,g) be given,such that (5.74) and (5.75) hold. Then the conclusions of Theorem 5.3 are valid. Bibliography [l] Carlson, David; Minimax and interlacing theorems for matrices, Linear Algebra and Appl. 54 (1983), 153 - 172. [2] Carlson, David and Marques De Sa, E; Generalized minimax and interlacing theo-rems, Linear and Multilinear Algebra, 15 (1984), 77 - 103. [3] Cauchy, Augustin; sur l'equation a l'aide de laquelle on determine les inegalites seculaires des mouvements des planets; Oeuvres completes,second serie, vol.IX (1829),174 - 195. [4] Deutsch, Emeric and Hochstadt, Harry; On Cauchy's inequalities for Hermitian matrices, American Mathematical Monthly, 85 (1978), 486 - 487. [5] Fan Ky and Pall Gordon; Imbedding conditions for Hermitian and normal matrices, Canad. J. Math.9 (1957), 298 - 304. [6] Hershkowitz Daniel, Mehrmann Volker, Schneider Hans; Eigenvalue interlacing for certain classes of matrices with real principal minors, Linear Algebra and Appl. 88 (1987), 373 - 403. [7] Johnson, C.R. and Robinson, Herbert; Eigenvalue inequalities for principal subma-trices, Linear Algebra and Appl. 37 (1981), 11 - 22. [8] Langer, Heinz and Najman, Banko; Some interlacing results for indefinite Hermi-tian matrices, Linear Algebra and Appl. 69 (1985), 131 - 154. 29 Bibliography 30 [9] Sodupe, Maria-Jose; Interlacing inequalities for generalized singular values, Linear Algebra and Appl. 87 (1987), 85 - 92. [10] Thompson, R. C ; Principal submatrices of normal Hermitian matrices, Illinois J. Math.10 (1966), 296 - 308. [11] Thompson, R. C. and McEnteggert, P; Principal submatrices II: The upper and lower quadratic inequalities, Linear Algebra and Appl. 1 (1968), 211 - 243. [12] Thompson, R. C ; Principal submatrices III: Linear inequalities, J. Res. Nat. Bur. Standards, sect. B,72, (1968) 7 - 22. [13] Thompson, R. C ; Principal submatrices IV: On the independence of the eigenvalues of different principal submatrices, Linear Algebra and Appl. 2 (1969), 355 - 374. [14] Thompson, R. C ; Principal submatrices V: Some results concerning principal sub matrices of arbitrary matrices, J. Res. Nat. Bur. Standards, sect. B, 72 (1968), 115 - 125. [15] Thompson, R. C ; Principal submatrices VI: Cases of equality in certain linear in equalities, Linear Algebra and Appl. 2 (1969), 375 - 379. [16] Thompson, R. C ; Principal submatrices VII: Further results concerning matrices with equal principal minors, J. Res. Nat. Bur. Standards, sect B, 72 No.4 (1968), 249 - 252. [17] Thompson, R. C ; Principal submatrices VIII: Principal sections of a pair of forms, Rocky Mountain J. Math, vol 2 No. l (1972) 97 - 110. [18] Thompson, R. C ; Principal submatrices IX: Interlacing inequalities for singular val ues of submatrices, Linear Algebra and Appl. 5 (1972), 1 - 12.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Interlacing inequalities for eigenvalues of sums of...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Interlacing inequalities for eigenvalues of sums of matrices Afari, Ernest 1989
pdf
Page Metadata
Item Metadata
Title | Interlacing inequalities for eigenvalues of sums of matrices |
Creator |
Afari, Ernest |
Publisher | University of British Columbia |
Date Issued | 1989 |
Description | We begin with some historical remarks in section 1, where we present the basic interlacing inequalities. In the rest of the thesis we discuss R.C.Thompson's contributions to the subject. His main concern is to extend the inequalities to include more than just one of the (n — 1) x (n — 1) principal submatrices. It is clear that for each such submatrix, the interlacing inequalities are valid, but the resulting set of inequalities is not sufficient to guarantee the existence of a matrix whose principal submatrices have eigenvalues satisfying these inequalities. We have included two examples to show that Thompson's inequalities are necessary. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-08-14 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0080411 |
URI | http://hdl.handle.net/2429/27387 |
Degree |
Master of Science - MSc |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-UBC_1989_A6_7 A32.pdf [ 1.6MB ]
- Metadata
- JSON: 831-1.0080411.json
- JSON-LD: 831-1.0080411-ld.json
- RDF/XML (Pretty): 831-1.0080411-rdf.xml
- RDF/JSON: 831-1.0080411-rdf.json
- Turtle: 831-1.0080411-turtle.txt
- N-Triples: 831-1.0080411-rdf-ntriples.txt
- Original Record: 831-1.0080411-source.json
- Full Text
- 831-1.0080411-fulltext.txt
- Citation
- 831-1.0080411.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0080411/manifest