On the Set of Eigenvalues of a Class of Equimodular Matrices Citation Bradley, Gerald Lee (1966) On the Set of Eigenvalues of a Class of Equimodular Matrices. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/07K4-DM12. https://resolver.caltech.edu/CaltechTHESIS:09172015-130932781 Abstract The structure of the set ϐ(A) of all eigenvalues of all complex matrices (elementwise) equimodular with a given n x n non-negative matrix A is studied. The problem was suggested by O. Taussky and some aspects have been studied by R. S. Varga and B.W. Levinger. If every matrix equimodular with A is non-singular, then A is called regular. A new proof of the P. Camion-A.J. Hoffman characterization of regular matrices is given. The set ϐ(A) consists of m ≤ n closed annuli centered at the origin. Each gap, ɤ, in this set can be associated with a class of regular matrices with a (unique) permutation, π(ɤ). The association depends on both the combinatorial structure of A and the size of the a ii . Let A be associated with the set of r permutations, π 1 , π 2 ,…, π r , where each gap in ϐ(A) is associated with one of the π k . Then r ≤ n, even when the complement of ϐ(A) has n+1 components. Further, if π(ɤ) is the identity, the real boundary points of ɤ are eigenvalues of real matrices equimodular with A. In particular, if A is essentially diagonally dominant, every real boundary point of ϐ(A) is an eigenvalues of a real matrix equimodular with A. Several conjectures based on these results are made which if verified would constitute an extension of the Perron-Frobenius Theorem, and an algebraic method is introduced which unites the study of regular matrices with that of ϐ(A). 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): Todd, John (advisor) Bohnenblust, Henri Frederic (advisor) Thesis Committee: Unknown, Unknown Defense Date: 4 April 1966 Funders: Funding Agency Grant Number Caltech UNSPECIFIED NSF UNSPECIFIED Record Number: CaltechTHESIS:09172015-130932781 Persistent URL: https://resolver.caltech.edu/CaltechTHESIS:09172015-130932781 DOI: 10.7907/07K4-DM12 Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 9156 Collection: CaltechTHESIS Deposited By: INVALID USER Deposited On: 17 Sep 2015 21:14 Last Modified: 27 Feb 2024 20:37 Thesis Files Preview PDF - Final Version See Usage Policy. 19MB Repository Staff Only: item control page

ON THE SET OF EIGENVALUES OF A CLASS OF EQUIMODUL~ . MATRICES Thesis by Gerald Lee Bradley In Partial Fulfillment of the Requirements For the Degree of Doctor of Philosophy California Institute of Technology Pasadena, California 1966 (Submitted April 4, 1966) ii. ACKNCWLEDGEMENTS I wish to express my gratitude to Professor John Todd and Professor H. F. Bohnenblust for their advice and guidance during the preparation of this thesis. I also wish to thank the California Institute of Technology and the National Science Foundation for providing scholarships to finance rny studies and research. iii. ABSTRACT The structure of the setl{(A) of all eigenvalues of all complex matrices (elementwise) equimodular with a given n x n non-negative matrix A is studied. The problem was suggested by O. Taussky and some aspects have been studied by R.S. Varga and B.W. Levinger. I.f every matrix equimodular with A is non-singular, then A is called regular. A new proof of the P. Camion-A.J. Hoffman char- acterization of regular matrices is given. The set (;{(A) consists of m ~ n closed annuli centered at the Ea.ch gap, 'O , in this .set can be associated with a class of origin. regular matrices and with a (unique) permutation, 1L ( o). The associa- tion depends on both the combinatorial structure of A and the size of the aii • Let A be associated with the set of 1'c' 1 , 1r2 , ••• ,1rr, where each gap in C{(A) the 1lk • components. r permutations, is associated with one of Then r :::; n , even when the complement of Q(A) Further, i f 1r( 1) has n+1 is the identity, the real boundary points of Q are eigenvalues of real matrices equimodular with A • In particular, if A is essentially diagonally dominant, every real boundary point of Q(A) with is an eigenvalue of a real matrix equini.odular A • Several conjectures based on these results are made which if verified would constitute an extension of the Perron-Frobenius Theorem, and an algebraic method is iritroduced which unites the study of regular matrices with that of G{.(A) • I. JNTRODUCTION. We shall call two n x n complex matrices B • (b . .) 1J and C • (c 1 ) equimodular if I bij I • l cij I , i,j • 1,2, •• • ,n • Clearly the relation "B equimodular with G11 establishes an equivalence on the set of all n x n by ~(B) complex matrices, and we shall denote the class of all n x n a given matrix complex matrices equimodular with B • We shall denote by .Q(B) the set of all eigen- values of all matrices in x&(B) • When we discuss certain general features of c;((B) which do not depend on B , it will often be con- venient to refer to this set as the eigenvalue set of the eigenvalue set of a general matrix. B or even as It is the purpose of this thesis to investigate such eigenvalue sets. In this introductory section, we shall review what· is already known about eigenvalue sets and conduct a heuristic survey of problems toward whose solution we may profitably direct the course of our investigations. We shall also introduce definitions and notational con- ventions which recur throughout our work, and we shall state without proof several well-known results which we shall need in later sections. Not a great deal is known about the eigenvalue set of a general matrix. o. Taussky [ 2 J asked for a characterization of this set, and perhaps the best response to this request is found in a paper by Varga and Levinger [ 3 ] , in which the authors characterize the eigenvalue set in terms of minimal Gerschgorin sets (4,.5] This characteriz- 2. ation is particularly elegant for the eigenvalue set of an essentially diagonally dominant matrix, but becomes more complex in the general case. In Section IV, we shall once again have cause to refer to this paper, for one of the main results of that section is quite similar to a conjecture of Varga and Levinger, although the approach we use is . completely different from the method of minimal Gerschgorin sets. Aside from the paper of Varga and Levinger, the most important · guides we have for the investigation of the eigenvalue sets are the many results in the literature which deal with bounds on the set of eigenvalues of a given matrix. Perhaps the most important of these results are the Gerschgorin Disk Theorem and the Perron-Frobenius Theorem. These two results are stated in their entirety at the close of this section, but roughly speaking, the most important evidence they provide is that the eigenvalue set of a diagonally dominant matrix does not contain the origin and that i f A is a non-negative matrix, then the largest non-negative boundary point of ~(A) is an eigen- ·value of A • At this point, we can say very little about the eigenvalue set of a general matrix. However, we can prove that every such set has a certain basic form. Theorem o. Let B ~ ~· n x n complex matrix. symmetric about~ origin.£!.~ coinplex plane. ~ Q(B) is Furthermore, ..c;((B) is a closed set which has at most and every component ------ ·n components, -- .£!. Q(B) contains ~ ~ number .£! eigenvalues (counting multipli- cities) of ~ matrix in J (B) • J. Proof: First of all, if ex is a positive nurnber in {).. (B) , then ex is an eigenvalue of some matrix C in ;0(B) e is If any real number such that 0 ~ e < 2 'Tt , then ex e19 is an eigenvalue of ei9c , and since ei9c is in J(B) , it follows that ..Q(B) I z I a ex • contains every complex number on the circle Now, let R be any matrix .in s.J(B) other than B. known -- e.g. ( 7 ] -- that the eigenvalues of an n x n regarded as a function of n2 It is wellcomplex matrix complex variables are continuous functions of those variables. i.e. Since the domain of these functions ~(B) -- is a compact, connected set in complex En2 space, it follows that Q(B) is closed and that every component of Q(B) contain exactly the same number of eigenvalues of R plicities) as it does those of B • Since must (including multi- B can have at most n distinct eigenvalues and since R was chosen arbitrarily from ,0'(B) , this completes the proof of the theorem. Except for the basic form described in Theorem 0 , none of the features of the eigenvalue set of a general matrix is ;. i mmediatefy discernible. In fact, matrices which are very "similar" can have com- pletely different types of eigenvalue sets. For example, if I is the identity matrix, t hen .c;{(I) number, and let is the unit circle. Let k be a positive ~ .. diag (l/k, l/k2 , ••• , l/kn) • Then for each such 1\: , ~(Dk + I) consists of the union of n distinct circles. Thus, we see that two matrices which are "close" in the topological sense can have eigenvalue sets which do not even have the same number of components. It is just as obvious that two algebraically similar matrices may have entirefy different types of eigenvalue sets. For example, 4. let J be the matrix all of whose entries are equal to one. is orthogonally similar to the diagonal matrix Then D • diag (o,o, J •.• , n). Iz I ~ n , but Q(D) is clearly the union o:f the origin and the circle I z I • n • There:fore, We shall see later that Q (J) is the disk it appears that i:f we are to find a general technique for analyzing the eigenvalue set of a matrix, then very little can be gained by regard2 ing a matrix as a linear transformation or as a point in complex "FP space. Mindful of these preliminary observations, we shall begin our investigations of ~(A) with a view toward answering the following questions : 1. Is every real boundary point of t;<.(A) an eigenvalue of some real matrix in ;,tf (A) ? 2. If A and B are non-negative matrices such that under what conditions is it true that 3. B ~ A , (2(B)=:)c:l(A) ? Is there any essential di:fference between the case when .c;;:((A) contains the origin and the case when it does not ? 4. What causes the gaps between components in .,C2(A) ? Is it possible to predict whether a gap will appear in .c;2(A) without having precise knowledge of .(;<(A) itself ? 5. Under what conditions is one of the annuli which comprise ~(A) actually a circle ? In addition to the above questions, there are several other import- ant issues with which we shall deal in our investigations. However, it is di:fficult to motivate or even describe these problems until we have 5. introduced a certain amount of basic terminology. Therefore, each section will begin with a paragraph which describes and motivates the main ideas end results contained in the section, end in Section VI, at the end of our investigations, we shal1 summarize the main results of our work. It is convenient at this point to introduce a few basic definitions, notational conventions, and background results which will be used throughout our work. First of all, a complex matrix matrix in ~(B) B will be called regular i f every J (B) is non-singular. Equivalently, B is regular i f does not contain the origin. Italic capital letters such as n x n complex matrices. negative matrices. A,B,C, ••• will be used to denote The letter A wil1 be reserved for non- Script letters with subindices -- e.g. A 1 . , Q3 . . , J l.J ~ij' 6C;j' ~j' -- will be used to denote the determinant of the n-1 x n-1 submatrix formed by deleting the · from the n x n ith row and jth column complex matrix denoted by the corresponding italic capital letter -- e.g. used in the symbols A,B,C,T,V • ~(A) , {;{(A) Although script letters are also as well as in the symbols for certain other sets which will be introduced later, there should be no difficulty in deducing from the context in which a script letter appears whether it denotes a set or a determinant. (i,j)th entry is B • (bij) is a j B I will denote the non-negative matrix I bij I This symbol should not be confused complex matrix, the symbol whose If with the symbol sometimes used in the literature to denote the determinant of B • We shal1 always denote the determinant of B by (det B) • 6. The symbol I 11 will be used to indicate the end of the proof 11 of a theorem or a lemma. A set of n matrix positions which includes exactly one position from every row and every column will be called a generalized diagonal. For example, three of the 3 ! generalized diagonals of a are {<1,1), (2,2), (3,3)} {<1,1), (2,3), (3,2)} {<1,2), (2,3), (3,1)} • 3 x 3 matrix and A matrix whose only non-zero elements lie along a generalized diagonal will be called a generalized permutation matrix. Where we speak of such a matrix, we shall tacitly assume it to be non-singular -- i.e. we assume it has n non-zero terms. A matrix A will be called reducible if there exists a permutation matrix Q such that where A and A are square submatrices of A and 0 is a block 1 3 of zeroes. If A is not reducible, it will be called irreducible. Let A • (a . . ) 1-J be an n x n non •negative matrix. graph ~ A we mean the directed graph on directed from node #k to node #l nodes which has an edge if and only if example, consider the f ollowi ng matrix A • n 1 0 3 4 0 0 0 2 1 Then by the ak.t f. 0 • For 7. Then the following is the graph of A i node #2 A sequence of edges in the graph of A which begins at node ends at node #s will be called a path from node #r #r to node and #s • The graph of A is said to be strongly connected if there exists at least one path from each node in the graph to every other node. Equivalently, the graph of A is strongly connected if there exists a closed path in the graph which passes through each and every node. 1 The symbol L will denote the deleted summation n x n A 1=1 i:Fj complex t. i 't j matrix B • (bij) will be called diagonally dominant if we have the following inequalities for k • 1,2, ••• , n : I lbkkl > Ilbkj I j~IC . A complex matrix B will be called essentially diagonally dominant i f there exists a positive diagonal matrix · D such that BD is diagon- ally dominant. Let B • (bij) be an n x n complex matrix. Then the disk in the complex plane described by the .i nequality will be called the kth Gerschgorin disk of B • We say that this disk is isolated if its intersection with the union of the other (n-1) 8. Gerschgorin disks of B -i s void. Thus, it follows that an isolated Gerschgorin disk contains one and only one diagonal element of B • Finally, if is an n x n B complex matrix, then by the spectral radius. of B we shall mean the maximum of the moduli of the eigenvalues of B • j\ , Ji , •• • Thus, if 2 1 spectral radius of ,i\ are the eigenvalues of B , B is equal to max j/\ I~ K~1'\. k the I We conclude this introductory section by stating without proof five basic results which are used throughout our work. i) Let f be a continuous, real-valued function whose domain is a connected set in a finite-dimensional metric space. range of f Then if the includes both positive end negative numbers, it must also include zero. If the domain of f is also compact, then its range is a closed segment of the real line. ii) Gerschgorin ~ Theorem. Then all the eigenvalues of Gerschgorin disks of of B • Let B be a complex n x n B are contained in the union of the Furthermore, if the matrix. n kth Gerschgorin disk B is isolated, then this disk contains exactly one of the eigen- values of B • It follows from ii) that a diagonally dominant matrix B must be regular, since the union of the Gerschgorin disks of any matrix in ·~(B) iii) oannot contain the origin. Perron-Frobenius Theorem. ible matrix. Let A be a non-negative, irreduc- Then A has a simple, positive eigenvalue O< which is 9. equal to the spectral radius of A and which is associated with a positive eigenvector. A ~jBj , that Furthermore, if B is any complex matrix such then ex is greater than the spectral radius of B ·with the sole exception of the case when there exists a unitary diagonal matrix D and a real number which case 9 such that A • ( e ie)·DBD-1 , in B has a simple eigenvalue of modulus ex Clearly, this result implies that the largest positive boundary point of .G{(A) x5(A) is an eigenvalue of A , is such that iv) Let A~ IBI • B be a complex matrix. I+ B2 + B3 + ••• converges to radius of v) since every matrix B in Then the matrix power series (I-B)-l i f and only if the spectral B is less than one. A matrix is irreducible if and only if its graph is strongly connected. 10. II. REGULAR MATRICES The main purpose of this section is to introduce and develop a technique which will prove to be the crux of all our main results. Using this technique, we shall establish a natural means of associating each regular matrix with a permutation matrix, and as a by-product of this result, we give a new proof of a theorem of Camion and Hoffman which completely characterizes regular matrices. Finally, we obtain a property of non-negative regular matrices which will be used to a great extent in Section IV • We begin this section with a lemma which expresses analytically the obvious fact that a closed m-gon m line segments can be laid out in the form of if and only if the length of no single one of them exceeds the sum of the lengths of the rest. Lemma 1.1. numbers. Let x 1 '::! - ..• r x2 ~ ~ ,... x m be a set of i f and only if Suppose for real numbers Proof: 0. This can be written as "' follows that x 1 "' j j~z.xj e .e 1 e1 ,e2 , ... ,em we have -xl ei81 = ,,.. j we must have I ~j~~j • x 1 - x 2 • O since f:,x. ei9j and it .;::2 J To prove the converse, we use induction on x1 ~ x 2 , e1 ,e2 , ... ,em Then it is possible to find real numbers such that ~-negative m m • x 1 ~ x2 For m= 2 , by assumption. if 11. 7>t. In the general case '.... -~uppose we have the inequality x 1 ~ Then if we have j[.z.xj • x1 +xm~ j'I; xj we may apply the inductive hypothesis 2 to the m-1 numbers However, suppose ,.,_, Let z(e) = ( [ x +~, 1 ,.._, x 1 +~ > ~ xj J-2 xj) - xm • x 2 , ... ,~ to obtain the desired result. - xm ~ 0 • so that Then z(e) varies continuously between j "z. ,..., and ( [, xj ) - xm as j = 2. """ e1 with 0 ~ e1 ~ 1T. .,... , e varies between 1T and 0 • Since we (;~ xj ) - xm < x 1 ~ j~ xj it follows that I z(e1 )) = x1 for some Therefore, there exists a number e2 with 0 ~ e2 ~ 2 rr such that x 1 e ie2 .. This can be re-written as and the proof of the lemma is complete. I It may appear that we can gain little insight into the nature of eigenvalue sets of general matrices by concentrating on regular matrices, for "most" matrices are not regular. However, as we shall show in Section III, if A is a complex matrix and A is a positive number not in ,;;{_ (A) , then the translated matrix A - A I regular. must be This indicates that a characterization of regular matrices is of basic importance in discussing man~ of the features of the eigenvalue set of a general complex matrix. The following lemma is the first step in the derivation of such a characterization. ... 12. Lemma 1.2. An ~-negative n x n !£ ~ ~ (~) index ..... . i8 [lbkj I I (i3kj J e k j 1' 0 matrix A is regular!.£~ only and every matrix for any n B in el'e2 , ;••• ,en real numbers . J•i Proof: matrix A is not regular. Suppos~ B • (bij) in ~(A) Let ,J(A) , we have Then there exists a singular be a (row) index. k Then since B is singular, we must have " I L ( -1) i k-jl bkj 63_ • det B = 0 • kj Clearly this implies the existence of real numbers e 1 ,e2 , ..• ,en .,.. . such that [ I bk . I I k . I e iS j. = 0 . =I j sI J 63 J A is regular. Conversely, suppose let B be an arbitrary element of k be a (row) index and Suppose there exist real a ie· l~j l \~kj I e J = 0 . ,,8(A) • 7\. such that.[ numbers Let . J=I For j = 1,2, ••• ,n ., let 1j be the argument of the complex number .Then we have ~b j4:I kj {j3 i(0j - Yj) kj e B 0 0 Clearly, this implies the existence of a singular matrix differs from C which B only in the signs of the elements of the row . Therefore, this matrix C is in ~(A) , and this contradicts the fact that A is regular. Hence, it is impossible to find numbers ')'1 el'e2 , •.. ,en such that ~LI bkj 11 J ~ I arbitrary (row) index and since U3 kj I eiej • O . Since k was an B was chosen arbitrarily from ~(A) this completes the proof of the lemma. I Lemma 1.2 i ndicates that we can obtain valuable information about 13. regular matrices by investigating the set of complex numbers { bkl 18kl ' bk2 $k2 ' ••• ' \me kn} for a fixed row index k • We shall now combine the results of Lemma 1.1 and Lemma 1.2 to demonstrate an important property of this set, but in anticipation of this and later results, it is convenient to first introduce a function which proves to be a valuable tool in our investigations. Definition 1. B • (bij) Let be a complex n x n an arbitrary (row) index and matrix. Let s , an arbitrary (column) index. r be Then will denote the following function: I Frs(B) ... . I brsl I <Brs I - r1 brj I I (jJ rj I J~S Clearly, for fixed r and Fr5 (B) s , is a continuous, real- valued function of the elements of B if B is regarded as a point n2 in complex E space • . One reason why this function is so useful is contained in the following lemma. Lemma 1. 3. r and s Let ~ 2_ B such that C ~ Proof: Lemma 1.2. If there exist two indices then B k ~ l exist two indices matrix complex matrix. 0 (B) , ~ ~ ~ ~ regular. Fk£(C) / 0 If there for every B ~ regular. then The first statement is an obvious consequence of Now let for every matrix in k and .-t ..J (B) • Suppose exists a matrix C in ,J(B) 7\ \.( 1) /;:;- lk-jl be two indices such that B is not regular. FkL(C) / 0 Then there which is singular, and we must have c '° kj ~ kj • det C • 0 • 14. From this it follows that I Icktl I~k.tl ~[I ckj I I ~kjl ' ji::J, and we must have Fk.l(C) ~ 0 • tion that Fk,e<c) > 0 ' desired. I However, this contradicts the as sump- and we conclude that is regular, as B Now we prove a converse to the second part of Lemma 1.3 • Lemma 1.4. Let A be ---- ~ regular matrix. Then for each (~) ----- index k ' there exists ~ ~ only ~ (column) index 1 ,.. .i(k) - such that Fk£.(B) >o for all matrices B in ,0(A) • ------Proof: Let out the proof. k be a (row) index which will remain fixed through- Since A is regular, we conclude from Lemma 1.2 it is impossible to find real numbers Li 7\. that e ,e , ••• ,en such that 1 2 bkjl l<Bkjl eiej .. o • .j=I Choose )!, so that I bk.~) /~klJ -= 1 ~a;J bkjJ l©kj J • Then it follows from Lemma 1.1 that we must have I Ibk.ti )8ktl >I1~jl I Bkj I j Moreover, ;(, fK is unique in the sense that for m ft J, we must have I I 0 kml l $kml<[lbkj l JO~\·J I . J* 7"V Thus, we conclude that Fk.l(B) > 0 , index 1, depends only on k but we still must show that this and not on the choice of Assume that there exists a matrix C in _,0 (A) B from ..sJ (A) • such that 15. Fk.t (C) ~ 0 • Since Fkl is a continuous, real-valued function on ;J(A) , and since r.J(A) is a connected set in complex which contains both B and some matrix T in C , ~(A) • it follows that Fkt(T) a 0 for Fkt(C) > 0 for every matrix C Therefore, the (column) index ,£ depends only on the sJ(A) • (row) index k desired. space However, this contradicts the fact that A is regular, and we conclude that in ~2 and not on the choice of B from ~(A) , as I As a consequence of Lemma 1.4, we can now define the important concept of a pivotal position for a class of regular matrices. Definition 2. Let A be a regular matrix and suppose that is an ordered pair of indices such that that (k,£) B = (bij) Fk1 (A) > 0 • Then we say is a pivotal position for matrices in .rJ(A) , is any matrix in the pivotal element in the (k,£) and if J (A) , the element bkt will be called kth row of B • It follows from Lemma 1.4 that every row of a regular matrix contains exactly one pivotal element and that the position of this element is an invariant of the class J (A) • Moreover, we shall show in Lemma l.S that the set of ' pivotal positions of the class ~(A) is actually an invariant of a much larger class of regular matrices, which we shall now define. Definition 3. denote by ek'(B) Let B • (bij) be a regular n x n the set of all complex matrices matrix. We shall C • (cij) whose 16. elements satisfy the following inequalities for bkt where is the pivotal element in the I cks I~ lbks I for kth row of B (2.1) s • 1,2, ••• ,n i.e. such a matrix C is obtained from the pivotal elements in k • 1,2, ••• ,n : B by increasing (in modulus} B and by decreasing (in modulus) the others. For example, consider the matrix B• We shall see that 3 2 3 2 8 3 l 6 15 B is regular and that the pivotal positions of B are (l,l); (2,2); and (3,3) . .A/(B) is the following complex matrix: 5 0 1 2 9i 2 0 2+2i 15 regular n x n c• Lemma 1.5. Let A ~ ! Therefore, a typical member of matrix. Every matrix in is regular ~ ~ ~ ~ pivotal positions ~ matrices ~ c.A/(A) J(A) • Proof: To simplify .notation, we shall assume that non-negative matrix in A is the J (A) • We shall first prove the lemma for a subset of cA}(A) . and then proceed recursively to the completely general case. Let k be a fixed (row} index, and let.Alk(A) be the 17. set of all. complex matrices B a (bij) following inequalities for k • 1,2, ••• ,n : where a k.e. whose elements satisfy the is the pivotal element in the kth row of A. ri I bks I ~ aks s • 1, 2, • • • , n s l bij l .. aij i,j • 1,2, ••• ,n i " k In other words, cJ\/k(A) is the subset of v1/(A) which contains those matrices which differ from certain matrices in ~(A) elements of the kth row. only in the be an arbitrary matrix in 1J be the corresponding matrix in ~(A) . . th and · C are identical except for the elements of the k cJ\)k(A) , i.e. B row ; for and let C • (cij) j • 1,2, ••• ,n , satisfies the inequalities argument of fact that Let . B • (b .. ) (2.2) the modulus of the complex number (2.2) , and its argument is equal to the (2.2) , together with the Fkt(B) > 0 , since the minors of bkj • Then the inequalities Fkl(C) > 0 , ckj imply that B are identical with the minors of the corresponding elements of the kth row of C -- i.e. we have the elements of the i'l.3kj • ~ kj , kth row of j • 1,2, ••• ,n • arbitrarily from v1{CA) , matrix in cA/k(A) Now suppose (r,s) (B) ~ 0 • B was chosen it follows from Lemma 1.3 is regular and has . (k,l) but not for matrices in F Therefore, since that every as a p i votal po~ition. is a pivotal position for matrices in Jl (A) J (B) • Then we must have Frs (A) > 0 and Since v1/.k(A) 2 is a connected subset of complex En rs space which contains both A and B , it follows that there exists a 18. that .A.{CA) (T) = 0 • However, this implies rs T is not regular, and this contradicts the already established matrix T in such that F J\{CA) fact that every matrix in is regular. Hence, we conclude (B) > 0 , and (r,s) must be a pivotal position for all rs matrices in vt{CA) • Therefore, every matrix in ~k(A) is regular · that F and has the same pivotal positions as matrices in .rJCA) . Now, let U "" (u .. ) l.J be an arbitrary matrix in c!V(A) • We define the following sequence of matrices Vs = (v{j') Since ' where v <;J • rJ and vij U is in .A/(A) , ts·> u rj = aij we know that v we have already proved, it follows that same pivotal positions as matrices in cA{<v1 ) , and matrices in r ~ S j = 1,2, ••• ,n i > s j 1 v1 ,,. 1,2, ••• ,n is in Jt{CA) , and by what is regular and has the rJ (A) • Then v2 is in v clude that is regular and has the same pivotal positions as 2 (V ) and (A) • Proceeding in like fashion, we con1 Vn is regular and has the same pivotal positions as matrices in ,07(vn_1 ), .J7cvn_ 2 ), ••• ,,J7(v1 ) ,J J and ,J(A) , and since Vn = U by construction, this completes the proof of the lemma. Now we are in a position to prove our rirst main result, which says that if ;.J(A) A is regular, then the pivotal positions of the class lie along a generalized diagonal. In anticipation of future applications, this result will be stated in a slightly different, although equivalent form. 19. Theorem 1. Let tion matrix P A ~ ! regular matrix. such that ~ PA ~ there exists ! permuta- ! regular matrix !!! ~ whose pivotal positions lie along ~ ~ diagonal. Proof: class First we shall show that the pivotal positions of the ~(A) lie along a generalized diagonal. For this purpose, we consider the matrix B • (bij) conditions for whose elements satisfy the following k • 1,2, ••• ,n: if akt is the pivotal element in the kth row of A s = 1,2, •.. ,n b ks - 0 Clearly B is in cA/ (A) s ,. £. Therefore, by Lemma 1.5, B must be regular and have the same pivotal positions as matrices in However, each row of xf CA) B has exactly one non-zero element, and such a matrix can be non-singular if and only if it is actually a generalized permutation matrix. . Therefore, the pivotal positions of the class J (B) J (A) lie along a generalized and hence of the class diagonal. Let Q • (qij) be that permutation matrix whose elements satisfy the following conditions for -1 p .. Q • f 0 l if bkl qks = 0 if bks m 0 It is clear that PA is a regular matrix, and since qkl Let k • 1,2, ••• ,n m pre-multiplication by a permutation matrix merely permutes the rows of a matrix, we conclude that if (r,s) is a pivotal position in A , 20. then (s,s) is a pivotal position in PA. positions of PA . Corollarz .! ..!. Therefore, all the pivotal lie along the main diagonal, as desired. If A and P are as in Theorem l, then AP is also ------- -- ! regular matrix whose pivotal elements ~ ~ along ~ ~ diagonal. Proof: It is clear that pivotal elements of matrix, where AP AP is regular, and the location of the follows from the fact that BP is a diagonal B is the matrix defined in the proof of Theorem 1. Since the pivotal positions of a regular matrix A lie along a _generalized diagonal, it is clear that if tion matrices such that P1A and P 1 and P are permuta2 P2A both have all their pivotal positions along the main diagonal, then we must have Pl = P2 • This fact allows us to make the following definition. Definition 4. Let A be a regular matrix, and let (unique) permutation matrix such that positions along the main diagonal. If PA has all its pivotal Then we say that A is associated with P be that with P , I , that A is a regular matrix in normal ~· A is associated the identity matrix, we say The results of Theorem 1 and Lemma 1.5 indicate that a regular matrix in normal form behaves in many ways like a diagonal matrix. Indeed, we shall show that a regular matrix in normal form is actually essentially diagonally dominant, and this fact when combined with Theorem l gives the characterization of regular matrices which con- 21. stitutes Theorem 2. The following lemma is used primarily in Theorem 2 to provide a connection between Theorem 1 and the concept of diagonal dominance, but it is also a rather interesting result in itself. Lemma 2.1. Let A ~ !!! n x n !!£.!!-negative regular matrix~ normal ~' ~ ~ B • (bij) .!£!: k • 1,2, •.• ,n • bkk /' 0 values of B Proof: ~ ~~~parts,££!!!~ eigen- positive. Let ...::\ be an eigenvalue of real part of A is non-positive. k = 1,2, ••• ,n, Then for ~ !!:l matrix ~ v1/(A) ~ ~ since bkk ~ akk .J\/(A) since we have and Re A ~ 0 • B is in cA/cA) B , Write ?. B - 'A I It follows that and we have for is in is regular, and we This contradicts the B , and we conclude that the must be positive, as desired. In a recent paper, Camion and Hoffman B - I\ I k • 1,2, ••• ,n B - AI cannot be singular. assumption that I\ is an eigenvalue of real part of A /\ • Re~ + i Im .A • as bkk - Rei\• bkk +I Re~I ~ akk Therefore, it follows from Lemma 1.5 that conclude that and suppose that the [l] I proved that a matrix A is regular if .and only if there exists a permutation matrix P and a positive diagonal matrix diagonally dominant. D such that PAD is In Theorem 2, we obtain the same characterization as a consequence of Theorem 1 and Lemm(2.l, although in order to demonstrate the existence of a suitable positive diagonal matrix D , 22. we are forced to use a technique which has little in common with the rest of the work in this section. Theorem 2. Let A be an n x n !!,2!!-negative matrix. Then A regular if ~ only .!£ there exists ! permutation matrix P positive diagonal matrix D such that Proof: matrix in Suppose PAD PAD ~ is and a diagonally dominant. is diagonally dominant. Let B be any J (A) . Then PBD is diagonally dominant and must there- fore be non-singular. Hence, B was ~{A) , we conclude that A is regular. chosen arbitrarily from Conversely, suppose matrix associated with B is non-singular, and since A is regular. A , Let P be the permutation and let .B • PA • We must show that is essentially diagonally dominant. Let C • {cij) B be the matrix whose elements satisfy the following conditions: c ij • -b ckk • ij 1,j. 1,2, •.. ,n rj k • 1,2, ••• ,n bkk We shall first show that 1 c-1 is a non-negative matrix, and then we shall use this fact to show that B is essentially diagonally dominant. Choose <5 > 0 Let p{S) so am.a ll that the matrix S .. I- er C is non-negative. be the largest non-negative real boundary point of c;{(s) • Then it follows from the Perron-Frobenius Theorem that actually an eigenvalue of p(S) is S , and we must have the following: 0 • det { S- p(S)I ) ·• det [(I- <rC) - p{S)I] • det ( [1-p(S) J I - <rC) • 23. (1-p(S)) er Consequently, -1 is a real eigenvalue of C , and it follows from Lemma 2.1 that this eigenvalue must be positive. 1>p(S)~0 er is positive, we conclude that insures the convergence of the matrix series (I-S)- 1 • (~c)- 1 • to the matrix Since non-negative matrices, we conclude that negative, and since <1 >o .). S , Since and this inequality I + S + S2 + • • • and all its powers are (~c)- 1 • a-1c-1 is also non- it follows that c-1 is a non-negative matrix. Let e denote the transpose of the row vector n -1 and consider the vector x • C e x > 0 • know that Let i a is non-negative, we D be the positive diagonal matrix such that Then the vector for Since n (1,1, ••• ,1) , . CDe is positive, and this means we have, n 1,2, ••• n : I dicii - L;ci.d. > o u' J J Clearly, this is equivalent to the statement that C is essentially diagonally dominant, and this completes the proof of the theorem. Corollary 2.1. Let A be! ~-negative regular matrix, ~ ~ and D be as in Theorem 2. If B ,!:! ~ matrix ~ rAI (A) , P then PBD ,!:! ~ diagonally dominant. Proof: This is a simple consequence of the inequalities which arise in the definition of Corollary~·~· normal form. (2.1) , J1/ (A) • A diagonally dominant matrix ,!:! ! regular matrix in With Theorem 2, it is easy to see why the matrix B• 3 2 3 2 8 3 l 6 is which appeared on page 16 is regular • . Let ) D • diag (1, 1/2, 1/3) • Then we have BD • 3 2 1 1 3 4 ~) Since BD is di agonally dominant, it follows from Corollary 2.2 that B is a regular matrix in normal form. While the characterization of regular matrices given in Theorem 2 provides an excellent means of constructing examples of various types of regular matri ces, it would be desirable for certain purposes to have a more tractable test for non-regularity. For example, it is obvious that the matrix is not regular, but thi s is not an immediate consequence of Theorem 2, and using Theorem 2 alone, it is quite difficult to see why the matrix A • is not regular. l 2 2 0 1 l ~) However, in Theorem 3 we obtain a necessary condition 25. for the regularity of a matrix which is usually much easier to apply than Theorem 2. Theorem J.. Let A ~ product of the pivotal elements of A is greater than the product be fill n x n non-negative, regular matrix. Then of the elements of A which lie along any ~ generalized diagonal. Proof: Because of Theorem 1, it suffices to prove the theorem for regular matrices in normal form. pivotal elements of A Let Therefore, we assume that the are all diagonal elements. ( 1 ,11). (2,.lz), ••• , (n,.tn) be any generalized diagonal which contains at least one off-diagonal position, and let B = (bij) be that non-negative matrix whose elements satisfy the following conditions, for k = 1,2, ••• ,n bkk = akk bk k = aklk bkj = 0 Thus, j = 1,2, ••• ,n j ~ k,~k B has non-zero elements along only the main diagonal and the generalized diagonal under consideration. Furthermore, B is in J1/(A) and is therefore a regular matrix in normal form, by Lemma 1.5 • the permutation k ~.lk is not cyclic of order n , then If B is red- ucible, and the theorem follows by induction, since each diagonal block of a block triangular regular matrix must be regular. assume that k~..lk is cyclic of order n • Hence, we may Suppose we have 26. Then since the generalized diagonal under consideration contains at least one off-diagonal position, it follows that by decreasing only the off-diagonal elements of B , we can construct a non-negative matrix ' C = (cij) which is in tl\)(B) and for which we have n n n n 1\. 'I'\. .,,, ck.lk = ckk = bkk = ~"'I K"'"I 'n K•f akk K•I Since · k~.lk · is cyclic of order n, there exists a permutation matrix P such that I c11 C1,t1 c22 PCP' 0 . 0 ::: c' n-1,~_ I 1 f cn£n cnn However, the matrix C cannot be regular, for we have n cl~k n n -n. 11. ±. det(PCP') = tt•I cfak = K=/ n n. 71. ckk ± K"I K•I This contradicts the fact that all matrices in A/(B) ckk . are regular, and we conclude that the theorem holds in all cases. We conclude from Theorem .3 that i f the product of the elements along no single generalized diagonal of A exceeds the product of the elements along every other generalized diagonal, then A cannot be regular. For example, consider the following matrix: A -· 1 2 2 0 1 0 No generalized diagonal product exceeds products equal 2. 2, but two different .such Thus, no single generalized diagonal product 27. of A dominates the rest, and A cannot be regular. Unfortunately, as one might suspect, even if this condition is satisfied, it is in general not enough to guarantee that a matrix be regular. For example, the matrix A• 2 1 0 1 2 1 1 1 1 is equimodular with the singular matrix B• 2 -1 0 -1 2 1 1 1 1 even though the product of the diagonal elements of A is greater than the product of the elements along any other generalized diagonal. Despite its limitations, Theorem 3 will nevertheless prove to be the key to all our investigation in Section IV. We conclude this section with several results which are interesting in themselves but are isolated from th.e main body of our investigations. Theorem 4. normal form. Let A · be ~ Let n x n P be an ~-negative n x n regular matrix in permutation matrix ~ ~ D • diag (dl'd2 , • • • ,dn) · ~ ! positive diagonal matrix. Then PAP' , DA , AD , and DAD-1 are all regular matrices in normal form. 28. Proof: regular. Let It is clear that each of these four product matrices is We shall use Theorem 3 to prove they are all in normal form. (1,£1 ), (2,£2 ), ••• , (n,tn) Then the elements di agona1 o f , a , ... , a a 1 11 2 j2 ntn P.nAP' • PAP' PAP' , and every other product of which lie along a generalized diagonal is equal to a product of elements of Therefore, since also lie on a generalized In particular, the product of the diagonal elements of A equals that of elements of be any generalized diagonal. A which lie along a generalized diagonal. A is in normal form, it follows from Theorem 3 that PAP no such generalized diagonal product of elements of as the product of the diagonal elements of PAP 1 , and 1 is as great PAP' must be in normal form. Now let us consider the matrices DA • (di aij) (l,i1 ) , (2,12 ) , ... , (n,in) AD= (dj aij) • Let and be any generalized diagonal which contains at least one off-diagonal position. since A is in normal form, we have n n k•l Since Then n dk) ( n aktk) < ( n dk) ( n akk) -ndk kk k k•l k•l k•l k•l n dkak.tk - ( n n n n 8 •1 (1,£1 ) , (2,J2 ) , ~··1 (n,tn) was an arbitrary generalized diagonal, it follows from Theorem 3 that Similarly, we can show that n n·, k•l DA is in normal form. n aktk< n ~-1 d,tk a.!k~ , 29. and this allows us to conclude that since n-1 Theorem 5. matrix of · Proof: .!! principal submatrix .£! k be an integer such that principal submatrix of tion matrix 1 • A i.e. B is a sub- is an are A . l~ k 'n , and let B Then there exists a permuta- ~ A2 Theorem ~1. matrix in normal P such that . · PAP and A 2 ively. n x n B .!.:! ! regular matrix in normal form . Let k x k ~ I .!!!.£!whose diagonal elements~~ diagonal elements A Then where Finally, (DA)D-l • DAD-l is in normal form. A be ! ~-negative regular Let form, ~ ~ B be a is in normal form. is also a positive diagonal matrix, it follows from what we have already proved that of A • AD (n-k) x (n-k) k x (n-k) and I ~;- principal submatrix of (n-k) x k submatrices of A, A , respect- Therefore, since A is in normal form, it follows from that PAP' i s i n norma 1 f orm, and we see th at it s urf·ices to prove the theorem for the case when B • (b •. ) 1J is the submatrix of A whose elements satisfy bij • aij, for i,j • 1, 2 , •.• ,k . Now, let C be the n x n which has the following form: non-negative block diagonal matrix 30. where o1 , and o2 are k x (n-k) and (n-k) x k blocks of zeroes, respectively, and ... ' a ) • Then c D .. diag (ak+l,k+l , ak+ 2 ,k+2 ' C is in cA/(A) , and it follows from Lemma 1.5 that regu1ar matrix in normal form. U ~1 I 02 C , B is not regular, and let Suppose T .. D ~(C) , and this contradicts the fact that B must be regular. Therefore, is a .J (B). Then the singular matrix be a singular matrix in is in nn C is regular. Because of the block diagonal form of it follows from Theorem 3 that the product of the diagonal elements of B must be greater than the product of the elements of B which lie along any other generalized diagonal, and normal form. and since Since k B must be in was an arbitrary integer such that l~ k~ n B was an arbitrary k x k principal submatrix of A , this completes the proof of the theorem. Theorem 6. let A be an n x n Let ~-negative regular matrix, ~ P .!?! ~ permutation matrix associated with A . B Let ~ !!!l ~matrix in ~(A) ~~,!!!~pivotal elements of B Then we have det B > 0 . if are positive. if det P • +l and d~t B< 0 det P .. -1 • Proof: Let form such that C • PB • cii>O for Since C is a regular matrix in normal i • 1,2, ••• ,n, that all the real eigenvalues of it follows from Lemma 2.1 C are positive, and since C is 31. real, its complex eigenvalues occur in conjugate pairs. Hence, the product of the eigenvalues of B = P C , we C is positive, and since must have det B • (det P 1 ) (det C) > 0 det B < 0 if det P • det P as det P • det P < 0 • I Since P if det p'>o I and is a permutation matrix, we have • + l , and we conclude that Let ~ !!l det B has the same sign I Corollary~·~· A n x n ~-negative regular matrix ~ normal ~' ~ let B .. (bij) ~ ~ ~ matrix ~ ~(A) ~ bkk > 0 Corollary~·.£· normal form. for k • 1,2, .•• ,n. Let B a (bij) ,!! bkk > 0 ~ .such !.h!m det B >0. ~ ~ ~ symmetric regular k • 1,2, •.• ,n , then B matrix in ~positive definite . Proof: of It follows from Theorem 5 that the principal submatrices B of all orders are regular matrices in normal form. diagonal elements of Since the B are all positive, it follows from Corollary6.l that the determinant of each such principal submatrix must be positive. Therefore, B is positive definite, as desired. I 32. III. NORMAL GAPS IN THE EIGENVAI.UE SET OF A GENERAL COMPLEX MATRIX In Section II, we established a natural means of associating each regular matrix with a permutation matrix, and we shall use this result to show that each gap between .components of the eigenvalue set of a general complex matrix may be associated with a permutation matrix in a meaningful fashion. In this section we shall be mainly interested in gaps which are associated with the identity matrix; such gaps will be called normal gaps. We shall prove that the unbounded gap of every eigenvalue set is normal, and we shall show that certain interior gaps in the eigenvalue sets of special types of matrices are normal. also prove that if normal form and lbkk I "' akk A • (aij) B • (bij) for We is a non-negative regular matrix in is a matrix in c)}(A) k .. 1,2, ..• ,n, such that then the eigenvalue set of B is contained in that of A • For several of the following results, ·i t will be convenient to have a simple means of referring to the gaps in the eigenvalue set of a matrix. Definition 5. Let B be an n x n complex matrix, and let A any non-negative number which is not in .c;?.(B) • by G(B, 'A) the entire gap in unbounded gap in G{(B) be Then we shall denote a (B) which contains 'A • The will always be denoted by G( B,oo) If B is regular, the gap which contains the origin will always be denoted 33. by G(B,O) • If. /\ 1 ~ 0 is in one gap of c;?. (B) is in another, .then we say that two gaps and that G(B, /\ 2 ) G(B, A ) 1 and A. 2 > /\ 1 is the more interior of the is the more exterior. The .following diagram illustrates how Definition 5 is used in both the regular and non-regular cases: Regular Case G(A,oO) Non-Regular Case 34. Our first goal in this section is to show that each gap in the eigenvalue set of a general complex matrix may be associated with a permutation matrix. To obtain this result, we consider the following ·set of matrices, which is closely related to a certain gap in the eigenvalue set of a given matrix. Definition 6. Let B be a complex n x n non-negative number not in C{.(B) • set of all matrices of the form ,S (B) matrix, and let /\ be a Then we denote by }(' (B, ?\ ) C- 15 I , where the C is a matrix in and er is a non-negative number in the gap G(B, I\) • We shall show in Theorem 7 that all the matrices in 'J1 (B,?..) are regular and are associated with the same permutation matrix in the sense of Definition 4 , matrix but first we must show that a non-regular B is equimodular with a singular matrix which has the same diagonal elements as Let Lemma 7~1. regular. B • B • (bij) .£! ! complex nxn Then there exists ! singular matrix such that Proof: ckk - Since bkk -- matrix which is not c • (cij) in JCB) , -for k = 1,2, ••• ,n B is not regular, there exists a singular matrix For k • 1,2, ••• the arguments of the complex numbers ,n, let ek and ock be ~k and consider the unitary diagonal matrix : and bkk , respectively, 35. Then the matrix C • UD is singular, and we have for k • 1,2, •.• , n • b · Since D is unitary, it follows that C is in kk t.8(B) , and this completes the proof of the lemma. Theorem 7. Let B ~.!complex I\ let ~ ! regular ~ ~ associated with ~ ~ permutation matrix. Proof: C matrix,~ ~ _!!! ~ matrices~ }f (B, I\) positive number not in 9.(B) • ~ n x n Let Suppose C- o- I U = ( u1 j) in is not regular. J (C- er I) , ukk ""ckk-crI,. in ~ (B) , and since eigenvalue of n~t in G{ (B) , C- er I be an arbitrary matrix in d1 (B, I\) , where J (B) and er is a non-negative number in the gap G(B, I\) is in that C- a I V • Then there exists a singular matrix and because of Lemma 7 .1 , k = 1,2, •.. ,n. V = U +err. U is singular, it follows that was chosen arbitrarily from matrix in <S V is is an C- cs I must be regular. · Since df (B, /..) , it follows that every ls regular. Now we shall show that every matrix in '}{ ( B, I\ ) pivotal positions as Then However, this contradicts the fact that <J is and we conclude that matrix in }f (B, I\) Let we may assume Once again let B- ?-. I df (B, A) . Let k C- er I has the same be an arbitrary be an arbitrary index and l et be the pivotal position in the kth row of Fkt (B- /\.I) '? 0 and Fkt(C-O"I) ~ 0. B-A.I • (k, l) Suppose we have 36. Since n2 '}f' (B, J\) is a connected set in complex E tains both B- '/\I and C- d"I , matrix T in '}f (B, 'J...) it follows that there exists a such that Fkt (T) • 0 • dicts the fact that every matrix in l-f (B, '}...) clude that Fk.£ (c .. 6 I)> 0 • C- <SI df (B, A.) , and since k Since However, this contra- is regular, and we con- was chosen arbitrarily from was an arbitrary (row) index, it follows 'H (B, I\) that every matrix in space which con- has the same pivotal positions as and hence is associated with the same permutation matrix as B-~I B- ;i\I , and this completes the proof of the theorem. I The value of Theorem 1 lies in the fact that if we know . .· is not in the eigenvalue set of a given matrix B know that one matrix in d{(B,I\) permutation matrix associated with Definition 7. P , P • Let A~ 0 and if we also is associated with a certain then every matrix in 'd1' (B, :A) must be Therefore, we make the following definition: B be an n x n complex matrix, and let 71. be a non-negative number not in C<(B) Then the pivotal positions shared d1 (B,?..) will be called the pivotal positions · by all the matrices in of the gap G(B, I\ ) • If P . .is the permutation matrix associated with every matrix in '}( (B, I\ ) , is associated with P then we say that the gap G(B, I\) A gap which is associated with the identity matrix will be called a normal E.!!E· It will be seen that normal gaps play an important part in our investigations. One reason for the iroportance of such gaps is found in the following result, which states that the unbounded gap of any 37. eigenvalue set is normal. ·. Theorem 8. B be an. n x n · complex matrix. Let Then G(B, oo) is ! normal~· Proof: Let C be the matrix in . J. (B) which has all non- negative off-diagonal elements and all non-positive diagonal elements, and let ex. max a I ~ I< ' n ~~ j 7 K • If /\ is any positive number greater kj than both C< and the largest non-negative boundary point of Cl (B) , then C- I\ I is diagonally dominant, and it follows from Corollary 2. 2 that C-~I is a regular matrix in normal form. G(B, oo) , we conclude that G(B, 00 ) Since /\ is in is a normal gap. Theorem 8 guarantees that at least one gap in every eigenvalue set is normal. In Theorem 9, we show that if a certain gap in an eigenvalue set is normal, then every gap exterior to this normal gap is also normal. In particular, every gap in the eigenvalue set of a regular matrix in normal form is normal. . Theorem 9. Let B be an n x n complex matrix, ~ let I\ ~-negative number~! normal gap in C{(B) . in .Q(B) , Proof: ~ gap Let G(B,p) c ... ( c 1J .. ) Then g ~ ! J° >:A is ~ must be normal. ----be that matrix in ~ ( B) which has all non-negative off-diagonal elements and all non-positive diagonal elements. that C-~I Since G(B,?i,) is a normal gap, it follows from Theorem 7 is a regular matrix in normal form. Furthermore, C-;<> I 38. is in .A/CC-/\ I) since we have for k • 1,2, ••. ,n : I ckk - f I = Ibkk I +,P >I ~k J + A • Ickk - Jtj • . Therefore, it follows from Lemma 1.5 that C-.f>I is a regular matrix in normal form, and we conclude from Theorem 7 that the gap is normal. G(B,,,o) I Corollary ~·!· Let every~~ C{(B) Proof: B ~ ! regular matrix in normal form. Then is normal. Since the gap from Theorem 8. G(B,O) is normal, the corollary follows I The following result is perhaps the most interesting in this section, for it shows, in particular, that if A • (aij) is an n x n non-negative essentially diagonal:cy- dominant matrix and B • (bij) a non-negative matrix such that k = 1,2, •.• ,n, is A ~ B and akk = ~k for then the eigenvalue set of B is contained in that of A . Theorem 10. Let ~ every gap ~ A = (a .. ) _1J be an -- n x n _non-negative matrix such a (A) ~ normal, ~ ~ B (bij) be a complex IS matrix whose elements satisfy ~ following conditions for k • 1,2, ••• ,n I bkj I ~ akj Then we have C{(A) ~ .G{(B) . j • 1, 2, ••• , n j rk (3.1) 39. Proof: and let Let 7'. be any non-negative number which is not in ,C{.(A) , C m (cij) inequalities tions, for be an arbitrary matrix in ;..J (B) • (3.1) the elements of Because of C satisfy the following condi- k • 1,2, ••. ,n: I ckj I~ akj j • 1,2, ••• ,n j rk I akk - Al ~ I 0 kk - I\ I Since every gap in Q (A) is normal, it follows that regular matrix in normal form. Therefore, and we conclude from Lemma 1. 5 that cannot be an eigenvalue of from and since is a is in .Al (A- I\ I) is regular. Hence, I\ C was chosen arbitrarily J (B) , '/\ cannot be in Q(B) • Since /\ was any non-negative number not in C{(A) , {;(.(A) C , C- I\ I C- ?-. I A-/\ I we conclude that every number which is not ih also cannot be in .Q.(B) , Corollary 10.~. Let B a (bij) normal ~' and ~ C be a Q(B) .:=J Q.(c) Proof: and this means that Q.(A) ~ ~ k x k n x n =:J Q(B) . regular matrix in principal submatrix of B • Then . Let /\ be a positive number not in .G{(B) , be any matrix in ~(C) . To simplify notation, suppose and let T B can be partitioned as follows: (3. 2) 40. Let S be the following n x n S• partitioned matrix: TI B2 ~ Then S is in j (B) , and it follows from Theorem 10 that is a regular matrix in normal form. that T-/\I not in Q(B) , and since 7i. was any positive number we conclude that Q(B) ,:).Q(c) • If B is not in then we proceed exactly as in Theorem 5. (3.2) , Corollary 1f!. _g_. form. Hence, it follows from Theorem 5 is a regular matrix in normal form, and since T was chosen arbitrarily from .J'(c) , form S- I\ I Let be an ~ ~ diagonal element of n x n regular matrix ,!!! normal B is contained in G{(B) • Actually, using a continuity argument similar to that used in Theorem 0 , c./f/(B) we can show that the eigenvalue set of any matrix in whose diagonal elements equal those of · many components as c;((B) • component of ;;::((B) B must have at least as This fact can be used to show that each must contain at least one diagonal element of Clearly, this result is not necessarily true unless B • B is a regular matrix in normal form. If a non-negative matrix A has en isolated Gerschgorin disk, then it follows from the Gerschgorin Disk Theorem that the annulus formed by rotating this disk about the origin must contain at least one component of _c:;(_(A) • In Theorem 11, we obtain another fact about the eigenvalue set of a matrix with an isolated Gerschgorin disk. 41. Theorem ~l. kth ~ A • (aij) Gerschgorin ~ of A ~!~-negative If the ------------ which contains numbers greater ~ ~every gap~ ,C{(A) akk , ~ ~ normal. akk Let?-. > akk be in a gap in .c:{(A) • that matrix in ;,J (A) matrix. is isolated and at least one of the diagonal elements of A ~ ~ ~ Proof: n x n Let B • (bij) be which has all non-negative off-diagonal elements and all non-positive diagonal elements. We shall show that B-;;\ I is diagonal~ dominant. Let r be any index such that arr > akk and th Since the k Gerschgorin disk of A s, such that is isolated, we have I I:' > akk + [akj drarj arr Hk I and I J :t I< (3.3) j -:/:S Therefore, we must have I I brr - /\.I •arr+ J\>?: d-T' I 8 rj Ibss - AI .. L asj > 8 es + akk - [akj • Lbrj j:;tr and 8 ass +A > ss + 8 kk > , L I 8 sj = j;tS Lbsj jr#S Finally, since at least one diagonal element of A is less than it follows from inequality (3.)) that I I I bkk -?I • akk +A > ['akj + fi. > [akj J:i!K Therefore, Corollary 2. 2 B-/\I that (3.4) j~ K is diagonally dominant, and it follows from B- A.I Theorem 1 that the gap akk , is in normal form. G(B, /..) Hence, we conclude from must be normal, and since A was 42. any positive number not in ..G<_(A) pletes the proof of the theorem. ·. and greater than akk , this com- I In Theorem 11, the condition that at least one diagonal element of A be less than akk may be removed if we require that ~ be in a gap in Q (A) . which includes numbers greater than the larger of the and two numbers I L ak. , HK inequality (3.4) for this is enough to guarantee that J will hold. On the other hand, if smallest diagonal element of A , greater than akk akk is the then it is possible for numbers to lie in a gap in G{(A) For example, consider the following 2 x 2 which is not normal. matrix: Clearly A is a regular matrix associated with the permutation matrix , but both Gerschgorin disks of A are isolated, and one component of C{(A) must ·be contained in the disk exist .. numbers greater than in C{(A) j·zl ~ 1 . Therefore, there a • 0 which lie in the non-normal gap 22 which is associated with P . However, we can obtain a result similar to Theorem 11 even if element of A • akk is the smallest diagonal 43. Theorem 12. the kth A = (aij) Let ~!~-negative Gerschgorin ~ ~ A ~ isolated, where smallest diagonal element of A • ~ every gap in Q(A) normal. n x n If .!.£ which contains numbers greater~ akk ~~!gap:!.!! Q(A) , Since the akk !.::! in ~ 1:!! ~ ! component of Q.(A) , akk which!.::! exterior~~~ G(A,akk) Proof: matrix, ~ ~ kth akk ~ ~every gap~ Q(A) ~ normal. Gerschgorin disk of A is isolated, it follows that elements of only one component of .c;{(A) can be contained in the annulus (or disk) formed by rotating the disk I Iz - akk I ~ l:# k J· 9 j K about the origin. Therefore, if lies in a component of akk that any gap in Q(A) Q (A) , it follows which contains numbers greater than akk must I also contain numbers greater than positive boundary point of the akk + kth ~ akj , for the greatest J" K Gerschgorin disk of A must lie in the more exterior of the gaps which bound the component of c;:l(A) If A is greater than akk + I L: akj , then containing akk • inequality (J.4) holds, and the proof that G(A,A) is normal J #1( follows exactly as in Theorem 11. Similarly, if akk is in a gap in C?..(A) , then the "next" gap I contains akk + ~ akj , and it follows as before that this gap and j ;/:" every other gap exterior to G(A,akk) must be normal. I We conclude this section with a result which concerns the eigenvalue set of a positive definite matrix. Although this result is 44. interesting, it is included mainly to illustrate the method by which the technique which we developed in Section II may be used to obtain results which are basically combinatorial in nature. Let Theorem 13. matrix. B be an n x n positive definite ~ symmetric Then every ~ !!! C{(B) Proof: B = (bij) is normal. We shall use induction on n . Let b11 > 0 ; is positive definite, we must have b11 b 22 > b12 b 21 = (b12 ) 2 . Therefore, n s 2 • Since b22 > 0 ; and B must actually be a regular matrix in normal form, and it follows from Theorem 9 every gap in Q (B) matrix number which is not in ~(B) , J (B) . matrix. Let that is normal. Now, for a general n x n in 2 x 2 and let B , let A be a positive A be the non-negative matrix It follows from Theorem 7 that -A-/\ I S .. A +I\ I • We shall prove that Consider the non-negative matrix C • (c 1 j) S is a regular is in normal form. whose elements satisfy the following conditions: if skL is the pivotal element in the kth row of S otherwise Then C is in cA/(S) and it follows from Lemma 1.5 regular with the same pivotal positions as that C is reducible. S that C is We shall now show 45. A matrix is irreducible if and only if its graph is strongly connected. However, since arrl furthermore, · If is symmetric, C has at most C has less than reducible. S n n C must be symmetric, non-zero off-diagonal elements. non-zero off-diagonal elements, it is clearly On the other hand, if C has exactly n diagonal elements, it follows from the symmetry of be even, and the graph of two. n > 2 , Thus, for Since G consists of n/2 non-zero offC that n must closed paths of length C must be reducible. C is reducible, there exists a permutation matrix P such that ' where for some integer block of zeroes; c4 are c2 m x m and m with is an l~ m < n, m x (n-m) (n-m) x (n-m) 0 is an submatrix of submatrices of Now consider the matrix U = PBP'. (n-m) x m C C , and c1 and respectively. Partition U conformally with PCP'-- i.e. regard U as the partitioned matrix ' have the same dimensions as respectively . Since B is positive definite, it follows that positive definite, and the principal submatrices also be positive definite. /\ is not in Q (B) , U is u1 and U4 must Moreover, since .G((B) • G\(U) , and since it follows from Corollary 10.l that "A is not 46. ,, in either ..Qcu1 ) hypothesis, /\. Therefore, by the inductive or .Q.(U4) must be in · a normal gap in both Q (U1 ) and · Qcu ) 4 and u1 + A I and U4 + I\ I must be regular matrices in normal form. · Let V be the following block diagonal n x n matrix: Since the matrix V + :;>.. I cAJ (PSP 1 ) , is in 1 it follows that However, since both u1 +A I has the same pivotal positions as PSP • and U4 + /\I it follows that are in normal form, normal form, and this in turn implies that Therefore, we conclude that Theorem 7 that the gap S G(B, I\) V + :A I is in PSP' is in normal form. is in normal form, and it follows from is normal. arbitrary positive number not in Q (B) , in V + I\ I a (B) is normal, as desired. I Since 'A was an we conclude that every gap 47 • . IV. THE ANALOGUE OF A CONJECTURE OF VARGA AND I.EVINGER. In their characterization of the eigenvalue set, Varga and Levinger proved that at most (n+l) permutations are needed to char- acterize the eigenvalue set of a general n x n matrix A in terms of the minimal Gerschgorin sets of matrices related to mutations. A by these per- Furthermore, they conjectured that actually only n permutations . are needed to characterize ~(A) • such Although we do not actually obtain an analytic characterization of c,;((A) , we can still show that ..c;.:{(A) permutations may be associated with at most (n+l) in a meaningful fashion, for it follows from Theorem 0 exist at most (n+l) gaps in ~(A) , that there and each of these gaps is associated with a permutation matrix in the sense of Definition 7. Therefore, motivated by the analagous conjecture of Varga and Levinger, we make the following conjecture: . Conjecture 4.1. Let can exist at most n A be a non-negative n x n matrix. Then there different permutation matrices associated with gaps in Q(A) • In this section, we shall verify this conjecture, and in addition, we shall develop a new means of classifying gaps which is more refined than the one provided by Definition 7. It will be seen that this new gap classification system actually yields a certain amount of information about the components of ~(A) • 48. In constructing a proof of Conject\lre 4.1 , we shall depend mainly on a comparison technique which utilizes the results of Theorem 3 and Theorem 7. The following example illustrates this ·t echnique: Example 4.1. Let A • (aij) 4 x 4 non-negative matrix. be a general that a certain gap in ~(A) -- say Suppose G(A, I\ ) -- is associated with the permutation matrix P• (~gg~) 0 l 0 0 0 0 1 0 Then the non-negative matrix A- 'A I must be a regular matrix whose pivotal positions are (1,1); (2,3); (3,4); and (4,2) , and it follows from Theorem 3 that, among others, the following inequalities hold: Iall - Al 8 23 8 34 8 42>-la22 - /\la13 8 34 a41 1°11 - 7',1 8 23 8 34 8 42>1 8 11 -:Alla22 -.Al 8 34 a43 Consider the following matrix: al2 al3 8 a21 - 0 22 a23 a24 all B 14 IC 8 31 a32 - 8 33 a41 a42 8 8 34 43 -a44 (4.1) 49. Then B is in . J (A) , and we conclude from Theorem 7 that B- 'AI . is a regular matrix associated with inequalities (4.1) , P • Therefore, in addition to it follows from Theorem 3 that, among others, we have the following inequalities: I 11 - ~ I 23 a34 42 >l- 22 - A I 13 34 41 8 8 8 8 8 8 8 Iall - A Ia23 a34 a42> Iall - A 11- 22 - A I 34 43 8 Inequalities such as (4.1) and (4.2) 8 8 occur for .each and every gap in Q(A) • Thus, if there exists a second gap in (;{(A) is not associated with G(A,?.) P , (4.2) which the "difference" between this gap and must be due to a fundamental change in the above inequalities. However, suppose;° positions are i~ in a second gap in .G{(A) (1,1); (2,4); (3,2); · an.d whose pivotal (4,3) . Then we have the These two inequalities are clearly incompatible. We shall now show following pair of inequalities: and that this dilemma results from the fact that two gaps can be associated with different permutation matrices onlJr if they do not have the same diagonal pivotal positions. 50. Theorem 14. Let ~ P • (pij) A be an n x n non-negative matrix and let Q • (qij) · ~permutation matrices which~ associated ~~different~~ .Q(A) • .!,! pkk • ~k for k • 1,2, ••• ,n , then P • Q • Proof: Let /\, and /\ 2 be any positive numbers in the gaps which are associated with P Let A1 .• ·-A - ~J. I that and Q , respectively, and assume · ?\ 1 > 7'. 2. • A2 • -A - AzI • It follows from Theorem 7 are regular matrices in norrnal form, and it is and let PA and QA 1 2 clear that A and A have the same diagonal pivotal positions, 2 1 since Pkk • qkk for k • 1,2, ••• ,n • Let C • (c j) be the non-negative matrix whose elements satisfy 1 the following conditions, for k • 1,2, ••• ,n ckk •akk +A . 1 if pkk • qkk • 1 ckk • 0 if Pkk • qkk - 0 cks • a ks if (k,s) in the kth ckj • 0 is a pivotal position row of either A or 1 A2 otherwise C is in A/(A ) • Since Ai ) .A 2 and since A 1 2 has the same diagonal pivotal positions as A , it follows that C 1 also. Therefore, both PC and QC are regular is in cA'CA ) 2 matrices in normal form, and we conclude from Theorem 1 that P • Q It is clear that It is not hard to see that we could prove Conjecture 4.1 .I at this 51. point i f we could only show that any two gaps with the same number of diagonal pivotal positions must be associated With the same permutation matrix, for no positions. n x n matrix can have exactly (n-1) diagonal pivotal However, this is not the case, ·as 1;he following example illustrates: Example ~·~· Consider the following A• Then, using Theo.rem 2, 3 x 3 matrix: 0 l 0 1 0 1 0 5 1 it is easy to see that A is e regular matrix . associated with p - Furthermore, the number 1 0 1 0 1 0 0 0 0 1 • lies in a gap in c:{(A) which is associated with the permutation matrix Q - Therefore, both G(A,O) but P 1 0 0 0 0 1 0 1 0 and G(A,l) have one diagonal pivotal position, and Q are not identical. One feature of the preceding example merits further investigation. Namely, in the gap G(A,O) , the (3,3) position is pivotal, and we 52. 833 - 0 • 1 > 0 ; have however, in the gap G(A,l) , where (1,1) - 1 • -1 < 0 • 11 Furthermore, if A · is a general n x n non-negative matrix, and is the diagonal pivotal position, we have ·1:r (k,k) a is a pivotal position for a certain gap G(A, I\) , follows from Theorem 7 that akk then it cannot lie in the gap G(A, .I\) , . for cannot be a pivotal position of A - a I . Therefore, we conkk elude that every positive number in G{A, I\) must either be strictly (k,k) greater than, or strictly less than akk • This observation enables us to make the following definition: Definition 8. Let A be an n x n non-negative matrix, and let be a non-negative number not in Q(A) • Let position for the gap G(A, J..) • (k,k) Then the (k,k) be a pivotal position will be called subordinate if every non-negative number in G(A, /\) greater than akk • strictly less than Furthermore, the gap if it has r is strictly If every non-negative number in G(A, .A) akk , then ~ is {k,k) · will be called !!.2!1-subordinate. is said to be of ~ <r,s> G(A, J..) diagonal pivotal positions, exactly s of which are subordinate. For example, if A is the matrix in Example 4.2 , G(A,O) is of type <1,0) , since A has no negative diagonal pivotal elements, and the gap G(A,l) the the gap is of type (1,1) . position is pivotal in this gap and we have since 1 >a • O• 11 Thus, at least in the precedtiig .example, we see that this new method of classifying gaps enables us to distinguish between two gaps 53. which have the same number of diagonal pivotal positions but are associated with dif'ferent permutation matrices. Actually, this phenomenon is quite general, for we shall show in Theorem 15 A is a non-negative matrix suoh that two gaps in C{(A) that if have the same number of subordinate diagonal pivotal positions, then these gaps must be associated with the same permutation matrix. However, we shall first prove a lemma which will enable us to use an inductive technique in the proof of Theorem l~. Lemma 15._!. ~!~-negative Let · A ! ~ _!!! C{(A) ~~ position. Ak Let El deleting ~ <r,s) n x n which has matrix, ~~there~ (k,k) denote ~ (n-1) x (n-1) ~ ! pivotal submatrix formed from kth ~ ~ kth column. ~ if (k,k) subordinate, there exists ! gap 1!! Q. (Ak) ~~ <r-1, ~ !!, (k,k) is subordinate, there exists ! gap.!,!! Q(Ak) A ,:!! ~­ , and of~ <r-1,s-l>: Proof: First of all, we note that it is impossible to have . in the first case or s • 0 r • s in the second case because of the way the lemma is.worded. We shall assume that k • n • It will be seen that this involves no real loss of generality but merely facilitates the construction used in the proof. Let /.\ be any positive number in the given gap in U(A) • We shall show that /\ is in a ·gap in Q (An) (n,n) is non-subordinate. and of type subordinate. of type cQ--1,s-t> <z'-1, s> · if if (n,n) is 54. Let B • (bij) be the following n x n o2 end are respectively. · Since it follows that Therefore, of B. C- I\ I Since 1 x (n-1) (n,n) A- I\ I C , ~ o1 and let block diagonal partitioned matrixs c-~ where ~(An) , be an arbitrary matrix in and (n-1) x 1 blocks of zeroes, G(A, ~) , is a pivotal position for the gap is regular and that C- /\I is in J\/(A- I\ I) • is non-singular, and ?. cannot be an eigenvalue . B was chosen arbitrarily from ,](An) , we conclude is in a gap in C{(~) • that I\ Furthermore, C-.A I has the same pivotal positions as and from this we conclude that except for the (n,n) A-71 I , position, which G(~,?I.) is excluded, the diagonal pivotal position of the gap are either subordinate or non-subordinate according to their status in G(A, 'A) , G(A, /\) • If G(~, 1') has the same number of subordinate positions as the gap G(A, 'A) , but it has one less diagonal pivotal position than since (n,n) is of type G(An, A) (n,n) is non-subordinate in is not included. <r-1,s> then the gap Hence, in this case, the gap Similarly, if (n,n) and one less diagonal pivotal position than the gap G(A , 7') n is of type G(A , I\) n is subordinate, then contains one less subordinate position -- namely, in this case, G(A, "./\) , <z--1,s-t> Now we are in a position to prove Theorem 15. (n,n) -- G(A, I\) • Hence; 55. Theorem 15. Let A be~ n x n ~-negative matrix. ~ ~ ~ gaps~ Q(A) which~ the~ number of subordinate diagonal p ivotal positions ~ be associated ~ ~ ~ permutation matrix. Proof: For We shall proceed by induction on n "" 1 , n • the theorem is obviously true. Now assume the theorem holds for all matrices of order not greater than Suppose there exist two gaps in .(;{,(A) of subordinate diagonal pivotal positions. ?t 1 > 0 Let be in the /I. type <t,s) G (A, ?1 ) 1 • Naturally, we must have wise, and s,r which have the same number > I\ be in the other. 2 1 is of type <r,s) and that G (A, .A ) is of more interior of these gaps and let Suppose that n-1 • t 0 ~ s ~ r,t :;:;. n , are completely arbitrary. 2 but other- Before proceeding to the main part of the proof, we shall make a few simplifying observations and assumptions. First, suppose there exists an index non-subordinate for both gaps . such that It follows from Lemma 15.1 are in gaps in Q(A _t ) of types <r-1, s> and 1 respectively. By the inductive hypothesis, we conclude G(A,el' A ) and G(A,e , ,/l. ) are both associated with the same 1 1 2 permutation matrix, say Q • Then it follows that G (A, .A ) and 1 that G (A, 11 2 ) where are both associated with the permutation matrix P .e .l. ""' 1 "" Q • A similar argument shows that the 1 theorem holds if a diagonal pivotal position is subordinate for both I) gaps . and P • (pij) , P1 I Furthermore, if it is subordinate for (k ,k) is subordinate for G (A, A 2 ) , since /\l > G (A, .?l ) , 1 akk implies then :A2 > a kk. Therefore, it suffices to consider the case in which the only diagonal positions which a re pivotal for both gaps are non-subordinate for the gap G (A, /\. 1 ) and subordinate for G (A, /\. ) • 2 Suppose there 56. are precisely p we must also have such diagonal positions, where 0 ~ p ~ s • Clearly r +t - p ~n • In the proof that follows, we shell need to be able to index the diagonal pivotal positions of both gaps, and in order to avoid confusing the proof with a complicated, albeit completely general indexing scheme, we shall make a few assumptions concerning the location of these diagonal pivotal positions. Since the calculations used in the proof involve only arithmetic inequalities among products of elements along certain generalized diagonals, it will be seen that this assumption involves no real loss of generality. the p Accordingly, we will assume that common diagonal pivotal positions for the two gaps are (1,1); (2,2); ••• ; (p,p) ; that the and s are (p+l,p+l); ••• : (r-s,r-s) , subordinate diagonal pivotal positions for the gap respectively; (t-s) (r-s)-p other non-subordinate and and finally that the (r+t-p,r+t-p) , and 1 (r-s+l,r-s+l); ••• ; (r,r) , other subordinate and (s-p) non-subordinate diagonal pivotal positions for (r+l,r+l); ••• ; (r+s-p,r+s-p) G(A, 7' ) (r+s-p+l,r+s-p+l); G(A, ~ 2 ) are ...., and respectively. Moreover, let CX denote the product of the off-diagonal pivotal elements of the gap G(A, /\ ) , 1 and let (3 off-diagonal pivotal elements of the gap normal, then let we take O< denote the product of the equal one, and similarly, if f3 equal one. If G(A, ~ ) G(A, /i\ ) 2 Clearly O< and f3 gaps and depend in no way on the choice of 1 G(A, /\ ) 2 is is normal, are invariants of the two /\1 and Finally, 57. we shall need the following two matrices B • (b1 j) and C • (c j) 1 whose elements satisfy the following conditions: i,j • 1,2, ••• ,n i bii • -aii • i" j 1,2, ••• ,r i • r+l,r+2, ••• ,n and i,~ • 1,2, ••• ,n i ,i' j c 1 i • aii i • 1,2, ••• ,p; r+l, ••• , r+t-p cii • ...;aii i • p+l,p+2, ••• ,r; r+t-p+l, ••• ,n Clearly 9oth · B and C are in rJ(A) • Furthermore, the product of the pivotal elements of the matrix B is such that I B- /\ 1I I is no greater than the product of the pivotal elements of any other matrix , where R is in ;J(A) • The matrix C has an analagous connection with the gap G(A, A ) • 2 Now suppose the two gaps are not associated with the same permuta.tion matrix. If we apply Theorem 3 to the regular matrix j B- AlI I , we obtain the following inequality, since the terms on the right lie on a generalized diagonal of r I B- A.1I I : P -r+t.,.p <Dai1 - A1l>0< ><TI1aii -J\i.1><Til-si1 -l'-11> (3 i=I In the gap i=I (4.3) i..:'t+I G(A, A ) , the positions (1,1); (2,2); ••• ; (r-s,r-s) 1 are non-subord'inate, and th~ positions (r-s+l,r-s+l); ••• ; (r,r) are subordinate. Therefore, we conclude from Definition 8 that we have 58. the following: i • 1,2, ••• , r-s and i Thus, we may rewrite inequality • r-s+l, ••• , r (4.3) as follows: [C! <•u-/\1~[fJ.~·u- 7'1>Jll.)~.~1-•u>1O< ·> [Tl<•u-?>)[ft<:ii+ iat 'J l•f'+I 8 11+ "1~f3· A1~[.rt1T 'J ~ l•f-tS-.f•I As it stands, this inequality gives us little information, but we may weaken it to obtain the following useful inequality: (4.4) If we apply similar arguments to the matrix j C- /\2I j , we obtain the following inequality: Following exactly the same procedure as before, we obtain the weaker inequality: (4.6) 59. Combining inequalities (4.4) and (4.6) , we obtain the inequality r-s (4. 7) {fTaii)CX 1l i = f+I Since all the quantities in inequality -p we conclude that /\1 (4.7) are positive numbers, .,, )>A; . However, /\ 2 > 1'1 by assumption, and since this contradiction is a logical result of the existence of inequalities (4.3) and (4.5) , we conclude that at least one of these two inequalities cannot hold. This means that the gaps must have (4.3) and exactly the same pivotal position so that the two sides of (4.5) are identical, and this is equivalent to the statement that the two gaps correspond to the same pennutation matrix. With the results of Theorem 1, we are now in a position to prove Conjecture 4.1. Theorem 16. Let there exist (n+l) A ~ ~ regular n x n ~-negative matrix ~ which ~ ,:!!! Q(A) • ~ ~ least~~ these gap~ are associated ~ ~ ~ permutation matrix. Proof: Suppose that no two gaps in ..c;:2(A) the same permutation matrix. are associated with It follows from Theorem 15 exists one and only one gap with exactly s that there subordinate diagonal pivotal positions for each a• O, 1,2, ••• ,n • However, ifs • (n-1) for a certain gap, then that gap must have either (n-1) or pivotal positions, and since no non-zero diagonal elements, n n x n n diagonal permutation matrix has (n-1) it follows that any gap with (n-1) or subordinate diagonal pivotal positions must be associated with the 60. identity. . ·. - ., . . Thus, in any case at least two gaps in .G{(A) associated with the same permutation matrix. .Corollary 16._!. Let can exist at most n A ~ .!.!! · n x n must be I ~-negative matri.X. Then there different permutation matrices associated with gaps~ Q(A) • Proof: It is clear that may be needed only if there are (n+l) different permutation matrices (n+l) gaps in C{(A) , and in this case, it follows from Theorem 16 that at least two of the gaps in G{(A) must be associated with the same permutation matrix. The results of Theorem 15 and I 16 seem to indicate that gaps may be distinguished from one another by the number of subordinate diagonal pivotal positions which they determine. However, there is still the possibility that two gaps may have the same number of subordinate positions if they are associated with the same permutation matrix, and . we would like to remove this qualification if possible. We shall prove in Theorem 17 that two gaps which are associated with the same permuta- tion matrix cannot have the same number of subordinate diagonal pivotal positions. It will be seen that the proof of this result for a general non-negative matrix A depends almost entirely on the fact that the result holds for a non~negative generalized permutation matrix. · Before we proceed to the proof of Theorem 17, let us analyze the eigenvalue set of a specific generalized permutation matrix. 61. Example 4.2. Consider the following matrix: A .. Suppose we have three circles a 11 > (a all 0 0 0 0 a22 0 0 0 0 0 8 0 0 8 0 1 a ) 2 > a22 • 34 43 I zl = a11 ; I z I a a22 ; Clearly the gap G(A,O) 43 34 Then Q (A) consists of the 1 and I z I • (a34 a43)2 • is associated with (HH) 0 0 1 0 and is of type <2,o) . Then the gap G(A, A. ) 1 Let /\ , satisfy 1 is associated with ( 822 < 7'1 1- < Cs34 a43) 2 • ~~gg) 0 0 0 1 0 0 1 0 and is of type <2,1) Let ;\ 2 · Then ?l 22 > a a , and the gap 34 43 identity and is of type <(4,3). • > /\.2 > (a34 a4) 1 2 satisfy all G(A, A. 2 ) is associated with the The gap G(A,()(J) associated with the identity and is of type • is clearly <(4,4) . The reasoning used in this example may be applied to any generalized permutation matrix A to show tha~ if two gaps in C( (A) are associated with the same permutation matrix, then these gaps cannot have the same number of subordinate diagonal pivotal positions. · 62. However, before we prove this result, we shall need to define the concept of a cyclic matrix and to show that every generalized permutation matrix can be combinatorially decomposed into a direct sum of cyclic submatrices. Definition 9. For k ? 2 , ized permutation matrix. let A be a k x k non-negative general- Then A will be called cyclic .£! order if the permutation related to A is cyclic of length k • ively, A is cyclic of order k if Ak Alternat- is a positive diagonal matrix but any smaller power of A has positive off-diagonal elements. A is cyclic of order k , the positive kth If root of the product of the positive elements of A will be called the radius we shall denote this number by !: of A , and (rad A) • If A is cyclic of order k , the significance of the radius of A lies in the fact that .l2CA) consists entirely of the circle I z I • (rad A) • Lemma 17.1. matrix. Let .A .!:!! ~ n x n ~-negative generalized permutation Then there exists ! permutation matrix Q such that QAQ' - (4. 8) 63. diagonal submatrix .£! A and A1 ,A , ••• , Am 2 !.!!. .!,!! cyclic submatrices of A of various orders. where A0 ~!positive Proofs This resu1t is well known and is an immediate consequence of the fact that a permutation may be writ.t en as the composition of · disjoint orbital cycles. The cycles of length one correspond to non- zero diagonal elements of A , to k x k and the cycles of length k correspond submatrices of A which are cyclic of order k • A is a generalized permutation matrix, it follows Therefore, if ~ from Lemma 17.1 that c:2CA) a l)G:{(A1) , and it is easi]Jr seen that l "0 G2(A) consists of a set ·or circles. These circles fall into two fundamental]Jr different categories. Definition 10. tion matrix. Let If A be an n x n akk non-negative generalized permuta- r 0 ~ then the circle called a ;e~imary com;eonent of Q(A) • of the standard decomposition (4.8) then the circle I z I • (rad A..t) Let A be an n x n Lemma 17.2. matrix, ~ ~ .!:.!£ tion matrix. I z I • akk will be If AJ, is a cyclic submatrix of A given in Lemma 17.l , will be called a cyclic component ~-negative generalized permutation rn _!.!! Q. (A) ~ associated ~ ~ ~ permuta- ~ these gaps ~ E,! separated by onzy primary compon- ~ ,!!! Q(A)°. Furthermore, ~two~ cannot!!!!!~~ number of subordinate diagonal ;eivotal ;eositions. 64. Proofs We shall assume that A is in the block diagonal form of Lemma 17 .l. (4.8) ?i. 1 be a positive number in the more Let ?1 2 > /1. 1 be in the oth,er. interior of the gaps in question, and let Suppose the gaps are separated by a cyclic component of c;{(A) • say Al , there is a cyclic submatrix of A , ?-. 2 > (rad Al.) Since G(A, ?.. 1 ) and G(A, 1'2 ) such that > .A1 are both associated with the same permutation matrix, it follows from Theorem 7 that -A- A2I -A- fl. 1r are regular and have the same pivotal positions. block diagonal form of A , Then -Al. - A1 I it follows that and From the and -Ai, - .?I 2I are also regular and have the same pivotal positions -- namely, the pivotal positions of G(A, .?t1 ) matrix A1 -A~ - A2I • Since Al G(A, A ) 2 and which lie in the sub- is cyclic, it follows that -AL - 1'1 I and have non-zero elements along only the main diagonal and one other generalized diagonal, which includes no diagonal positions. Since Al · - /\ 1 , and each diagonal element of is cyclic, each diagonal element of Suppose that A is cyclic of order diagonal elements of -A/, - I\ 1 I -A.l - /\ 2 I k • -A£ - "1_I is equal to is equal to - /\. 2 ~ Then the product of the is equal to and the pro- duct of the elements along the only other generalized diagonal of -A.t - 1\ I 1 k is equal to _:!:(rad Ai ) (rad Al ) • Since we have k > 'A 1k , it follows from Theorem 3 that the pivotal elements of . the off-diagonal elements of -AL - .1'-1 I -A_t - t..1 I • On the other hand, since k . ?.. 2 :>(rad A,i) k , are 65. -A - ~ I are the diagonal 1 2 ·and, this contradicts the statement that we conclude that the pivotal elements of elements of - A£ - A1 I -AJ. - ?1.2I ' and -AJ., - /\ I 2 have the same pivotal positions. Hence, we conclude that no cyclic component of (;{(A) separate G(A, ~\) and G(~, 7' ) , . and since 2 can these two gaps were assumed to be distinct, they must be separated by a primary component of C{(A) • Thus, there exists a diagonal element of A, say arr , which satisfies row and Since ·arr is the only non-zero element in the column of A , it follows that (r,r) must be a pivotal position for both gaps, and it is clearly subordinate for G(A, A2 ) and non- G(A, /\ ) • Hence, the two gaps cannot have the same 1 number of · subordinate diagonal pivotal positions, and in fact, if the . subordinate for gaps are separated by exactly ·the gap G(A, /\.. 2 ) has exactly s primary components of (;{(A) , s then more subordinate positions than G(A, ?1. ) • 1 This result, coupled with Theorem 15, allows us to conclude that no two gaps in the eigenvalue set of a generalized permutation matrix can have the same number of subordinate diagonal pivotal positions. In order to prove that this result can be extended to the general case, we shall now establish a connection between the gaps in the eigenvalue set of a general matrix A and gaps in the eigenvalue sets of certain generalized permutation matrices which are closely related 66. to A • Definition 11. P = (pij) A be an n x n Let non-negative matrix, and let be a permutation matrix. n x n the set of all fomrna 17·1.· P "' (p .. ) 1.J matrix in Let whose elements k • 1,2, ••• ,n ck.ti .. akt if P,tk "" l I ckj I :;::; akj if p A be an n x n ~-negative jk =0 matrix, ~ ~ ~associated~! certain gap~ .Q(A) • ~~~in Q(A) j(P,A) • Proof: which is associated with P • ~ be any positive number in the given gap in .{;{(A) Let R .,, ( rij) C ~ ~ Let which is ~ associated with P is contained :!.::, ! gap in _c::{(c) Let c m (c ij ) complex matrices satisfy the following conditions, for J f(p ,A) Then we shall denote by be any matrix in J (C) • Let B • (bij) be the matrix whose entries satisfy the following conditions, fork• 1,2, ••• ,n Then B bkk ""akk if pkk = l bkk "" -akk if pkk ""0 bkj "' akj j ""1,2, ••• ,n belongs to J (A) , and it follows from Theorem 7 is a regular matrix associated with to cN(B-/\ I) , j ~ k P • Furthermore, that R- I\. I since we have the following inequalities B-?i I belongs for k ""1,2, ••• ,n Therefore, +/\ ... Jb if pkk - 0 Iakk-i\ I •jbkk-/\I ~ lrkk-A I if pkk .. l kk R- :A I kk kk is a regular matrix ass ociated with was chosen arbitrarily from follows that - 71J~lr 7 -J..I a G (A, I\ ) 0'Cc) and A, from is contained in a gap in P • Since G (A, I\) , Q (C) , it and we R conclude from The orem 7 that this gap , with P , s ince The orem 11.· gaps in Q(A) bel ongs to 'J-{(c ,~) R- ?II Let A G(C ,:;\. ) , must be a.ssociated • be a n n x n TIQ!!_-negative matrix: . T~e n no t wo can have the same number of subordinate diagonal pivotal positions. Proof: Be cause of Theor em 1 5 , it suffices to prove tha t any two gaps in Q(A) which a re associated with the same pe rmutation matrix cannot have the same number of subordinate diagonal p ivotal positions. Suppose that two ga ps in Q.(A.) permuta tion matrix Le t /\1 >O be in the more inte rior of these P • two gaps , and l e t A ;~ > /\1 G(A , ?t 2 ) are associated i1ith the s ame b e in the othe r. Since G(:\ ,/\ 1 ) ar e d i s joint gaps , at l east one compone nt of Q.( A) between t he circles z = ::\1 and = l\;z . z Le t i. e . for be ~ ( P , A) - - k = 1, 2 , ••• , n , we have bkt = a1a b kj = 0 Let lX be an eigenvalue of A G(A,1-.1) which separ a tes the gaps , B , ther e exists a 11 path" in if Ptk = 1 if Pjk = 0 contained in a compone nt of Q(A) G(A , /\ 2 ) . and a closed , connected subset of compl ex A and must lie B = ( b ij) the n x n non-ne e;.:i.tiv e generalized permutation ma trix in and En 2 ~( P ,A) Since :f"(P , A) is space which contains both which conne cts A to B, and . the e i genva lues of the matrices on this pat h form continuous paths in t he compl ex pl an e . e i genvalue of 3 . in §( P , A) One of these paths contains ex a nd at l east one Moreover, s ince Lemma 17. J informs u s t hat no matrix ca n have a compl ex number with modulus equa l t o /\1 or /\2 68. as an eigenvalue, we conclude that there must exist at least one com- Q (B) ponent of between the circles Iz I• A1 and that and Furthermore, it follows from Lemma 17 .3 in gaps in C{(B) Lemma 17 .2 which are associated with P , 1 that G(B, ~ ) and G(B, ~ ) 2 /l, 2 both lie and we conclude from cannot have the same number of subordinate diagonal pivotal positions. and G(A, ~2 ) ~l I z I • /\ 2 • Consequently, G(A, /\. ) 1 also cannot have the same number of subordinate positions, and the proof of the theorem is complete. We can also use Lemma 17.3 to obtain a certain amount of information about the comj'.lonents of {;{(A) , but this information is useful only if we know which permutation matrices are associated with the . gaps in Q(A) • Theorem 18. Let A ~ ~ n x n ~-negative matrix, ~ ,!!!:; ! ~ ~onent .£! Q {A) ~ bounded ~ ~ which ~ associated ~ ~ permutation matrices P · every matrix _!!! ~ ~ given component of Proof: G(A, 'A) · .G{(A) ~ t'.f{P,A) ~~least~ eigenvalue.£! n 8(Q,A) Let B be any matrix in be the gap in Q (A) J'.CP,A) and let G(A,f) be the gap It follows from Lemma 17.3 G(A, /\) is contained in the gap is associated with n j{Q,A) • Let which bounds the given component of and which is associated with P , G(B, I\) must be contained in the C<CA) • which is associated with Q • gap Q ~ P • G(B, /\) in .Q.(B) that the and that Similarly, the gap G(A,f') tained in the gap G(B,;o) , which is associated with Q • is con- Therefore, 0 since . 61{P,A) c3{Q,A) is a closed, connected subset of complex n2 E space which contains both A and B , it follows that G(B, ~) and G(B,f') must be separated by at least one component of ,.C((B) • Therefore, G(A, I\) and G(A,;O) must also be separated by at least one component of ~(B) , · and this means that at least one eigenvalue . of B must be contained in the given component of Q(A) • We conclude this . section with two results which illustrate how Theorem 17 may be used to determine the number and nature of the components of certain eigenvalue sets. Lemma 19.1; ~ A ~ !!! n x n regular, ~ ~ gap ,!.!! (;{(A) ~-negative matrix. If A is not must have at least one diagonal ----- - ------ pivotal position. l!, A !:! regular, ~ only. ~ gap G(A,O) ~ ~ diagonal Proof: ~ pivotal positions. Suppose A is not regular. Let I\ be a positive number in a gap in c;:?. (A) which has no diagonal pivotal positions. is in cJ\/(-A- i I) , and this contradicts the fact that · A . is not Then A · regular. Similarly, if A is regular, then i f G(A,O) has no diagonal pivotal positions, it follows from Theorem 17 that every other gap in Q(A) G(A,O) must have at least one diagonal pivotal position. If has at least one diagonal pivotal position, we conclude from a simple application of Theorem 3 that it is impossible for any gap ~ Q(A) to have no diagonal pivotal positions. 70. Theor em 19. be an Let that akk::: 0 for (n-1) components. Proof: k :::i 1,2, .... ,n. n x n ~-negative Then {)_(A) Since all the diagonal elements of matrix such can have at most A are equal to zero, it follows that all the diagonal pivotal positions of each gap in Q (A) are subordinate. If A is regular, then G(A,O) has no diagonal pivotal posi- tions, and it follows from Theorem 17 that no two gaps in (;{(A) have the same number of subordinate diagonal pivotal positions. can There- fore, in the worst possible case, there can exist one and only one gap of type '('s,s)> , exactly (n-1) for s u 0,1,2, ••• ,(n-2),n , diagonal pivotal positions. there can be at most n gaps in ..G{(A) , the statement that {;2(A) has at most since no gap can have Hence, if A is regular, and this is equivalent to (n-1) components . If A is not regular, then it follows from Lemma 19.1 that each gap in {;{(A) must have at least one diagonal pivotal position. t here can only be gaps of type it follows that J;;2(A) A Proof: n can have at most is not regular, .(;{_(A) Lemma 20.1. Let A Since <s, s) for Hence, s • 1, 2, ••• , (n-2), n , and (n-1) gaps. Therefore, since can have no more than (n-1) components. be an n x n G(A,oo) ~-ne gat ive matrix . I Then G(A, O<J) is associated with the identity, it has diagonal pivotal positions, all of which must be subordinate, since G(A,oo) is unbounded. Hence, G(A,OO) is of type <n,n) 71. Theorem 20. Let nxn matrix all of whose entries are ----- is the disk Proof: lzl::;n. Let /\ be a positive number which is not in Q(Jn) Then we conclude from Theorem 7 and the symmetry of must be in normal form. Furthermore, Jn - /\I that -Jn -/\I n must also be a regular J matrix in normal form, and it foll~as from Theorem 3 that since the product of the elements of Jn-~I /\ > 1 ' which lie along any generalized diagonal that includes no diagonal positions is equal to one. Since all the diagonal elements of Jn are equal to one, follows that all the diagonal pivotal positions of G(A, /\) ordinate, and G(A, I\) must be of type <n,n) n are sub- We conclude from Lemma 20.1 and Theorem 17 that the only gap in Q(A) Furthermore, it is clear that it is is an eigenvalue of G(A,oo) Jn , and if o- is any number greater than n , then -J - er I is diagonally n dominant and hence, a regular matrix in normal form. Consequently, n must be the only positive boundary point of r:;;{_(Jn) , I z l:::; n • and we conclude 72~ V. BOUNDARY PROPERI'IES OF NORMAL GAPS. It follows from the Perron-Frobenius Theorem that the largest non. negative boundary point of the eigenvalue set of a non-negative matrix A is actually an eigenvalue of A • to have as many as Since it is possible for ~(A) 2n non-negative boundary points, it is unrealistic to expect that every non-negative boundary point of ,G<.(A) eigenvalue of A • will be an However, we shall prove in this section that the positive boundary points of a normal gap are actually eigenvalues of certain ~ matrices equimodular with A • In particular, i f A is a regular matrix in normal form, then every real boundary point of C{(A) is an eigenvalue of a real matrix equimodular with A • We shall also show that i f A is an irreducible regular matrix in normal form, then the diagonal elements · of A are all interior points of G{(A) , and it will be seen that this in turn implies that no compon- ent of U(A) can be a circle. In order to prove that the real boundary· points of a normal gap in Q.(A) are actually eigenvalues of real matrices in ~(A) , we proceed along lines which are basically analagous to the method used in the proof of Theorem 1. However, certain continuity arguments must be altered to take into account the fact that the set of all real matrices equimodular with A is not a connected subset of real En space. We begin with a definition. 2 73. Definition 12. J10 (B) Let B • (bij) be an n x n real matrix. we shall denote the set of all real matrices Then by C • (c 1 j) in J'(B) whose diagonal elements satisfy c 11 • bii , for i • 1,2, ••• ,n. We shall call B ~-regular if every matrix in ~ 0 (B) is non- singular. We say that .J'0 (B) we have Lemma 21.1. index k then B B is in norma.l ~ if for every matrix Fkk(C) > 0 , Let for k • 1,2, ••• ,n • B be an n x n real matrix. such that C in If there exists an for every matrix C in - . _J 0 (B) , ~ ~-regular. is a singular matrix, then Fkk(C) ~ 0 • Hence, contains no singular matrices, and it follows that . ;.J 0 (B) Proof: If C is semi-regular. Lemma 21.2. matrix B Let B be an C in n x n real matrix. If there exists a and an index then ~ ~ ~-regular. Proof: Let C be a matrix in ..J'0 (B) such that Fkk(C) • 0 • Then we have I l ckk I I (,;kl< I • L I kj I I C kj I • ~ ckk (: kk 0 j :F k As in Lemma 1.3 we can use this equality to construct a singular matrix T • (tij) which is in ;J'0 (B) in the off-diagonal elements of the and which differs from kth row. Since .,)0 (B) C only contains 74. a singular matrix, it follows that Definition 13. Let B • (bij) shall denote by ~(B) B cannot be semi-regular. be an n x n real matrix. the set· of all real matrices elements satisfy the following conditions for k • C • (cij) whose 1,2, ••• ,n : j • 1,2, • •• ,n In the proof of Theorem 21, Then we j " k we shall show that s boundary point of a normal gap in the eigenvalue set of s non-negative matrix A must actually be an eigenvalue of a matrix in ~(A) • We shall now prove two lemmas which will enable us to use this fact to prove that such a boundary point must be an eigenvalue of a matrix in Lemma 21.3. Let B be an n x n Then every matrix .!!: ~ (B) Proof: ~-regular .;.J0 (A) • matrix in normal form. ~ ~ ~-regular ~ _!!: normal ~· The proof of this lemma is entirely analagous to the .proof of Lemma 1.5. Therefore, we shall demonstrate the validity of the lemma for those matrices in ~(B) the elements of a single row. which differ from B only in The general result is obtained by using a recursive argument analagous to that employed in Lemma 1.5. Accordingly, for an index the proof, we denote by cAtlk(B) U • (uij) k , which will remain fixed throughout the set of all real matrices whose elements satisfy the following inequalities: ~ - bkk I ukj I ~ Ibkj I uij • bij j •1,2, ••• ,n l,j •1,2, ••• ,n j rk i " k (5.1) 75. C be any element of ~(B) • We shall show that Let semi-regular matrix in normal form. and let tkj for and i rk • (/ kj • ~j 0 V is in J (B) ; that j • 1,2, ••• ,n ; and that vij • tij Fkk(V) > 0 , Then for since 0 B Fkk(T) > 0 , also. vkj has the same sign for 1,j .. 1,2, ••• ,n is in normal form. Since we have the fact that is in ,J (C) j .. 1,2, ••• ,n , together with inequalities be any matrix in be the corresponding matrix in .J (B) • V • (v1 j) By this we mean that as Let T "' (t1 ) C is a T 0 (5.1) allow us to conclude that xf0(c) , Since T was chosen arbitrarily from it follows from Lemma 21.1 that C is semi-regular, and since C was chosen arbitrarily from ~(B) we conclude that every matrix in~k(B) is semi-regular. Now, suppose for some index cfaf,k(V) m r k , we have Fmm (T) denote the set of all real matrices ~ 0 • Let R • (rij) whose elements satisfy the following conditions: j • 1,2, ••• ,n r ij • v ij i,j • 1,2, ••• ,n j " k i" k B is in normal form, it follows that F (V) > 0 , and since mm 2 c/11,k(V) is a connected subset of real En space which contains both Since V and T , that we conclude that there exists a matrix Fmm(R) • 0 • However, it follows from Lemma 21.2 not be semi-regular, and since vt\,k(B) , R in ~(V) that such R can- R is equimodular with a matrix in this contradicts the already established fact that every 76. matrix in ~(B) for is semi-regular. m • 1,2, ••• ,n, Hence, we conclude that and since T was chosen arbitrarily from it follows that C is in normal form. Lemma 21.4. A Let Fmm(T) > 0 ~ !!! n x n ,,J 0 (c), I ~-negative matrix, ~ ~ ! ~-negative boundary point .£!!normal gap~ Q(A) • Cf be If A- 11 I is semi-regular, then it is in normal form. ---Proof: We shall assume that <J is a non-negative right boundary point of a normal gap in .C2(A) • slightly smaller than <S By this, we mean that points Q (A) • are not in The proof for non- negative left boundary points is entirely analagous to the one given here. Let .A be a positive number in the gap for which o- is a boundary point, and let where ;J 0 (A) • C is a matrix in interval ( /I, o-) Theorem 7 that G(A, ~) Then p A-;or Let p is in a continuous function of f' , k , Furthermore, since Therefore, Fkk(A-j> I) > 0 , Fkk(A-j'I) for is a continuous A-fI, it follows that it is and we conclude that regular, it follows from Lemma 21.2 for each index k be any number in the open Hence, we must have Since for each fixed k • 1,2, ••• ,n • B r: C- er' I , G(A, I\) , and it follows from function of the elements of its argument, for Then is a regular matrix in normal form, since is a normal gap. k • 1,2, ••• ,n • xf0 (A- <J' I) • B be any matrix in A- <J'I Fkk(A- er I) ~ 0 , is assumed to be semi- that we must have strict inequality A- tr I is in normal form, as desired. I 77. Theorem 21. Let ~ ~ A n x n ~-negative matrix, ~ ~ (5 be ! ~-negative boundary point ~ .! normal gap . ~ Q.(A) • Then i:7" is ,J0 (A) • ~ eigenvalue ~ .! matrix ~ First we shall show that the matrix A- rs I Proof: regular. Suppose thet A- er I is regular. Then is a ·regular matrix in normal form. .J (A) , then can have (J" B- ~ I If B is any matrix in Hence, no lll8trix in J (A) as an eigenvalue, and this contradicts the fact that er is in .cl (A) • Since ~(A- ~ I) • is in is certainly and Theorem 7 that semi-regular, and it follows from Lemme 21.u A- O" I A- CT I cannot be A- Consequently, we conclude that err A- u I is not regular, it follows that of a matrix C • (c .. ) non-negative. Let 1.J .r.J(A) in is not regular• er is an eigenvalue whose diagonal elements are all y · be the eigenvector associated with <r , where ... , I Yn I e i0n ) ' say • Let D • diag ( d 1 , d 2 , ••• , ~ ) be the unitary diagonal matrix whose diagonal elements satisfy the following conditions: Then x • D -1 y r0 cik ... ei0.k if ~ if yk .. 0 • • l yk is a real vector, and since n-1cnx • C1x • Let T ... n-l C D • al elements of T satisfy Then T tkk • akk , for Cy ""f1' y ' is in we have ,J (A) ; the diagon- k • 1,2, ••• ,n ; has er as an eigenvalue associated with the real eigenvector Let T • T l + iT· 2 ' where T 1 and T 2 are real matrices. and T x • 78. Then we have and since O' x is real, we must have - er. I 1 has the same diagonal elements as Therefore, the matrix T since T T x • er x and T x • 0 • 1 2 is not semi-regular • . Furthermore is in ~(A) , A , normal form, and we conclude from Lemma 21.4 be semi-regular~ that A- a I cannot even Therefore, there must be a singular matrix in and this is equivalent to the statement that 6 is an J (A) • I eigenvalue of a matrix in Corollary 3.!·1: T 1 and T - 5 I is in ~(A- <JI) • Hence, it follows 1 that A- <r I cannot be a semi-regular matrix in from Lemma 21.3 ,00 (A- CT I) , we conclude that 0 .£ B is .! regular matrix in normal form, ~ every ~ boundary point 2! .c;((B) .!!!, .!!! eigenvalue ~ .! ~ matrix equimodular ~ B Corollary ~·3.· ~· B ~ .! positive definite, ~ symmetric matrix. ~every~ boundary point .2£ Q(B) ~.!!!eigenvalue.£!.!~ matrix equimodular ~ Using Theorem 21, B • we can also obtain· a result which is similar to the Perron-Frobenius Theorem, but considerab1y weaker. Theorem 22. Let A ~ ~ n x n ~-negative largest ~-negative boundary point .£! Q (A) matrix~ that ;J0 (A) • B? A , matrix. ~ ~ ,!! .!.!! eigenvalue .2£ .! Furthermore, .!!, B ~!~-negative matrix~ ~ .!.!:! largest ~-negative boundary point .£! Q. (B) 79. is at least as large as that of C((A) • _...... --Proof: Since G(A,oo) is a normal gap, it follows from Theorem 21 that the non-negative boundary point of G(A, oo ) eigenvalue of a matrix in Now, let ;J0 (A) • A be any positive number in G(B, 00) • Since G(B, oo) <n,n > and since B ~A , is a gap of type it follows that all the diagonal elements of both A and B are less than J C .,. (c j) be any matrix in (A) • 1 inequalities, for k • 1,2, ••• ,n : C- ~ I Therefore, and Therefore, and since }.. was chosen arbitrarily from is conta.i ned in G(B, 00) , Unfortunate~, ?.. • Let Then we have the following is in cA/(B- /\ I) , regular matrix in normal form. G(A, oo) is an C - /.. I must be a A is in a gap in Q (A) , G(B,00) , as desired. it follows that I the method used to prove Theorem 21 is non- constructive, and even though we can · say that the largest non-negative boundary point of the eigenvalue set of a non-negative matrix A is an eigenvalue of a matrix in an eigenvalue of A • prove that ;J0 (A) , we cannot prove that this point is Furthermore, if A is irreducible, we cannot B ~ A implies that the spectral radius of than that of A , B is greater and although it is possible to show that the eigen- vector which is associated with the largest non-negative boundary point of G{.(A) is non-negative, we cannot prove that i f A is irreducible, then this eigenvector is positive. 80. In fact, the concept of irreducibility rarely fits into our investigations, for if A is a reducible matrix, then there exists an irreducible matrix B such that the boundary points of Q (B) . arbitrarily close to those of Q_ (A) and the gaps in the same type as the corresponding gaps in kf (A) • Q (B) are are of Thus, the eigen- value sets of A and B are practically indistinguishable by the methods we employ. However, our final result shows that this is not altogether true, for we are able to prove that the diagonal elements of an irreducible regular matrix in normal form are actually interior points of its eigenvalue set. Theorem 23. Let A ~ ~ matrix in normal form. n x n ~-negative, irreducible, regular Then every diagonal element of A ~ .!ill inter- .!££ point £! Q. (A) • Proof: element of It follows from Corollary 10.2 A is in. C<(A) • We shell prove that no diagonal element C2 (A) • To simplify the proof, we ·of A can be a boundary point of shall show that, in particular, all C{.(A) • . We shall use induction on For n = 2 , a12 a 21 that every diagonal F 0 • Theorem 21 that cannot be a boundary point of n • the fact that A is irreducible means that Hence, a r must be regular, and it follows from . 11 cannot be a boundary point of _G( (A) • . A-a 11 Now, in the general case, since A . is irreducible, the graph of A must be strongly connected. in the graph of A which includes Hence, there must be a closed path node #1 • By paring off super- Bi. fluous circuits of this closed .path, it is possible to obtain a closed subpath which includes than once. node #1 and which passes through no node more This means there exists a sequence of, say, m Q n no.n - ·zero off-diagonal terms in A which lie along a generalized diagonal of an m x m principal submatrix of m< n , A that contains • If 11 it follows that there exists an irreducible principal sub- matrix of A which contains a the inductive hypothesis that a 11 • In this case, we conclude from a 11 is an interior point of the eigen- value set of this principal submatrix, and the theorem follows from Corollary 10.1 • If m• n , then the n non-zero off-diagonal elements must lie along a generalized diagonal which is cyclic of order n • Hence, there is no loss of generality in assuming that these elements are a12 ;a23 ; ••• ; an-l,n; anl • Let C • (c 1 j) elements satisfy the following conditions: be the matrix whose ckk • akk k • 1,2, ••• , n ck,k+l • 8 k,k+l k • 1,2, ••• , n-1 otherwise Then C is in )J(A) , a 11 is in ..G'<Cc) • Let and it follows from Corollary 10.2 B be an arbitrary matrix in Then we have 11r) • n-1 det B • + anl "f"-r ak k+l k•l It follows that ..r.J0 (c-a that C-a I 11 • ' is semi~regular, and we conclude from Theorem 21 82. . Therefore, a cannot be a boundary point of Qcc) 11 11 must be an interior point of _.C:((c) , and it follows from Theorem 10 that that 8 all must also be an interior point of ,C{(A) • Corollary 23.l. Let A be an n x n regular matrix in normal form. ~-negative, irreducible, ~ ~ component £! {).(A) can be a --- circle. Proof: G{(A) Let D • diag (a , a , ••• , ann) • Since every gap in 11 22 is normal, it follows from Theorem 18 that an eigenvalue of D is contained in every component of .c;?(A) • that a circular component of .kf2(A) element of A , would have to contain a diagonal and this is impossible since every diagonal element of A is an interior point of .(;2(A) • be a circle. In particular, this means Hence, no component of ~(A) can 83. VI. SUMMARY. In this section, we shall summarize the results of the preceding sections and make a few conjectures about possible future developments. Now that we have completed our investigations, we can say the following about the structure of the eigenvalue set of a general n x n non-negative matrix A : 1. The set .(;{(A) consists of k ~ n which is centered at the origin. ;cf (A) disk if 2. closed annuli, each of One of these annuli is a contains a singular matrix. Each gap in Q(A) (Theorem 0) • may be regarded as a class of regular matrices, each of which is associated with the same permutation matrix. Thus, each gap in Q(A) wi.th a permutation in a natural fashion. 3. The unbounded gap, G(A,oo) identity permutation. 4. may be associated (Theorem 7) • is always associated with the (Theorem 8) • permutations, ~l' cp , ••• , <pm, 2 such that each gap in {;{(A) is associated with one of There exist cp 1 'f.2 ' gaps. , m~ n ••• , Cf m • This is true even if Q(A) Hence, we say that .G{(A) permutations <f>i, f 2 , ••• , <f'm • has (n+l) is associated wi.th the (Theorem 16) • 84. 5. Let Pk denote the permutation matrix related to for k c 1,2, ••• , n • Then (;{(A) can be characterized as the complement of the set of all complex numbers that for each matrix tion, say <pk , that the matrix (Theorem 2 B in sJ(A) , z such there exists a permuta- and a positive diagonal matrix D such Pk(B- I z I I)D is diagonally dominant. and Theorem 7) • It is clearly not feasible to compute .G{(A) characterization. cpk , from the above Instead, we use tools such as Theorem 3 in conjunc- tion with Theorem 7 to determine key points in the gaps in .G{(A) , and once we have determined the number of gaps and the permutation matrix with which each is associated, we can use Theorem 18 struct points in the components of {;;(. (A) • to con- To illustrate this tech- nique, we shall analyze the eigenvalue set of a specific matrix. Example ~·.!· Consider the following matrix t A .. 16 0 1/16 0 0 0 . .1 0 1/32 0 0 1 0 l 9 2 Because of the structure of A , it follows from Theorem l that any 85. gap in ,C{(A) must be associated with one of the following permutation matrices : p. 1 1 000) 0001 0 1 0 0 ( 0 0 l 0 Since 1/16 and we eliminate P in Q (A) I 1 0 0 0 1/32 are small relative to the other numbers in A , A must be regular since the sub- A by deleting the Since 1st row and 1st coluTllil is position is zero for all matrices no product of elements of A which lie along generalized diagonal exceeds 16 , <1,0) , l 000) 0 l 0 0 0 0 1 0 0 0 0 l regular, and the minor of the (1,3) G(A,O) • from consideration and we shall assume that any gap 3 is associated with P1 ,P2 , or I • matrix formed from . gap 0 0 0 1 ( 0 0 0 l First of all, we observe that in sJ(A) • -(~~gg) 0 0 1 0 0 0 l 0 0100 p. 3 P2 it follows from Theorem 3 that the is associated with P • Since G(A,O) is of type 1 any other gap in Q.(A) must have at least one subordinate diagonal pivotal position. then this gap must have If C{(A) (1,1) has a gap of type ('1,1) , as a pivotal position, since any gap which includes numbers greater than 16 is clearly normal. (l,l) Since is the sole diagonal pivotal position of only P , it follows 1 that any gap of type <:1,1")- must be associated with P • If a 1 gap is associated with P , then every gap in {;{(A) which is more 2 exterior than this gap must be normal, since any such gap must have at least two subordinate diagonal pivotal positions. 86. Now we shall determine whether each diagonal element of in Q. (A) or in a gap in . Q.(A) • of A are in the gap ·which G(A,O) • i~ pivotal. (2,2) The number 2 cannot be in a gap in is not in Q.(A) , 2 it must P or P • We observe that the product 2 1 which lie along the generalized diagonal A-2I (1,1); (2,2); (3,4); (4,3) is greater than the product of elements (1,1); (2,3); (3,4); (4,2) • Hence, if 2 is in a gap, it along follows from Theorem 3 2 • Let iated with P any matrix in xJ (A) , and Theorem 7 that this gap must be assocD • diag gap in _c{(A) <2,1) gap in .GtCA) (1, 9/16, 1, 33/16) • Then i f the matrix Hence, it follows from Theorem 2 type Clearly, the zero diagonal elements Hence, if be in a gap associated with of the elements of A is is is diagonally dominant. P (B-2I)D 2 and Theorem 7 that which is associated with B P2 , 2 is in a and this gap must be of • On the other hand, the number 16 cannot be in a since (1,1) must be a pivotal position of every gap in Q(A) • Moreover, if B is any matrix in · clear that B-11.JT is diagonally dominant. is in a normal gap in C{(A) of type 0 (A) , then it is Hence, it follows that <4,3) 14 Thus, we conclude that there are four gaps in Q(A) : G(A,O) ' G(A,2) , which is associated with pl and is of type <1,0) ; which is associated with p2 and is of type <2,1) ; G(A,14) , which is associated with I and is of type <4,3) ; G(A,00) , which is associated with I and is of type <4,4) Now we shall determine a few key points in Q(A) • it follo'Ws from Theorem 18 that the component of ..G<(A) First of all, which is 87. bo.u nded by G(A,O) and G(A,2) contains at least one component of C{(c1 ) , where c1 is the following matrix 16 0 0 0 cl • 0 0 0 1 0 1 0 0 0 1 9 0 Thus, this first component contains only one eigenvalue of every matrix in sJ(A) , since this property holds for matrices in the smallest boundary point of Q(A) ~(c ) , 1 is no greater than arid 1/8 • Similarly, the largest positive boundary point of this component is somewhat less than by G(A,2) 1/2 • The second component of .Q.(A) is bounded and contains at least one component of and G(A,14) , Qcc2) ' where c2 - 16 0 0 0 0 0 1 0 0 0 0 0 1 -9 1 2 The characteristic polynomial of c2 is (x-16)(x3-2x2 +9x-l) • This polynomial has a pair of complex roots whose modulus is approximately 3 • Therefore, the second component of c;{(A) values of every matrix in small as 3. sJ (A) , contains two eigen- and contains numbers at least as In addition· to a component of .G{(c 2 ) , component of .Q(A) this second must . contain a component of .Q(c ) , 3 CJ • 16 0 0 0 0 0 0 0 0 0 0 1 0 0 9 2 where 88. Since the only two eigenvalues of component of in (A) are c3 which can be in the second 1 + ./iO and 1 - -fiO , and since 2 is G(A,2), we conclude that the smallest positive boundary point of ,C2(A) must be slightly larger than 2 • Further examination shows that the largest positive boundary point of this gap is slightly less than 5 • Finally, the last component of Q(A) contains 16, and its two positive boundary points are both approxiroa.tely equal to Hence, ~(A) 16. is closely approximated by the union of the following three annuli: 31 /2 ~I z \ < JJ/2 The results we have obtained answer only part of the questions raised in the introductory section. more can be said about Q(A). Actually, we believe that much In fact, we conjecture that the Perron-Frobenius Theorem is a special case of a more general property of the set Q(A) which may be stated as :follows: Conjecture 6.1. Let A be fill irreducible, !!Q!l-negative, n x n matrix, and let er> 0 be g_ boundary point of G{(A) • eigenvalue of §!. certain real matrix B in J (A) , and @:.matrix C eguimodular with A has fil!. eigenvalue of modulus C = eieDBD-1 , where Then <:r is fill <J' if and only if D is §!. unitary diagonal matrix. We also conjecture that it is possible to describe the matrix B of Conjecture 6.1 explicitly, in terms of the pivotal positions of the gap for which it is a boundary point. 89. Conjecture 6.2. Let G(A,/\) be §:.!@Qin Q(A). of Con,jecture 6.1 may be described ~follows, for ~) blCJ. £) = akj j B = 1,2, ••• ,n G(A, 71.), then = 1,2, ••• ,n i2. a non-subordinate pivotal position in (k1k) If k is a subordinate pivotal position in (k,k) If Then the matrix G(A,/\), bkk = akk bkj £) If (k, l ) .!:Qli ID = •akj with ,l :f k = 1,2, ••• ,n j j :/: k is ~pivotal :12osition in the kt.h !:h.fil!. G(A • /\ ) ' bk.t = ak.l = 1 , 2, ••• ,n j bkj = -akj j :/:L Moreover, we further conjecture that Theorem 17 may be ex tended in the following sense : Conjecture 6.3. Let G(A,7\) fA > /\ > 0 • suooose that pivotal oositions than and Then G(A,µ) G(A, f') be K,Cll2.2.in (A) §.ill!. has ~ subordinate dia gonal G(A, ?t) • It appears that a more systematic approach to the study of {;'{(A) is possible if we regard this study as a s pecial case of a more general problem. Before we can be more specific, we shall require the following definition: Definition: Let pair is said to be bi-regular if (A,B) in J(A) and S A and in B be non-negative, n x n matrices. J (B) • Then the det(R+S) :f 0 for all matrices R 90. The motivation for this definition is provided by Theorem ?, for if ?. is not in Q(A) , then the pair (A, /\I) is bi-regular. By regarding the set c;{(A) in terms of bi-regularity, it is possible to construct a unified theory in which the intrinsic properties of Q(A) are made evident. Specifically, it can be shown that the open set of all n x n regular matrices has a permutation matriX. nl components, each of which contains A similar result holds for the set of all bi- regular matrices of a given order. In particular, it can be shOim that each component of this set contains a bi-regular "splitting" P~ of the form (P, Q), where then is bi-regular if and only if A is regular, and in this (A, B) is a permutation matrix. If B = O, case, the corresponding splitting has Q = 0, and P is a permutation matrix. This is equivalent to Theorem 1. I.f B =/\I , where 71. i s not inc:{.(A) , then the corresponding splitting is closely related to the subordinate and non-s ubordinate diagonal pivotal positions of the gap G(A,/\) • This technique not only promises to yield interesting results concerning C{(A), but also suggests that the study of what could be called multi-regular sets o.f matrice s might be profitable. 91·. Bibliography Paul Camion and A. J. Hoffman, 11 0n the Nonaingularity of Complex Ma'trices," to appear. Olga Taussky, "On the Variation of the Characteristic Roots of a Finite Matrix Under Various Changes of its Elements," Recent Advances in Matrix Theory, ed. H. Schneider, University of Wisconsin Press, 1964: 125-138. [3] ~· ~· [4] Richard s. Varga, "Minimal Gerschgorin Sets," to appear. [5] ~· ~· [6] Levinger and R. s. Varga, "On a Problem of o. Taussky," to appear. Levinger and ~· ~· Varga, "Minimal Gerschgorin Sets II," to appear. John Todd, "On Smallest Gerschgorin Disks for Eigenvalues," Numer. 171-175. NatJi.----;; 1965: A. M. Ostrowski, "Solution of F.quations and Systems of Equations," Academic Press, New York: .192-194. S. Varga, "Matrix Iterative Analysis," Prentice-Hall, Inc., [a] Richard 1962. -