The Cauchy-Poincaré interlacing theorems, and Ky Fan trace theorems are important tools for characterizing the eigenvalues of Hermitian matrices. These classical theorems are closely related and form the basis of several useful observations, e.g.,  -  . In this note, we extend these assertions to handle non-Hermitian matrices. The interest in such extensions arises in Rayleigh-Ritz methods for calculating a few exterior eigenvalues of a large sparse matrix, e.g.,    . Let us consider, for example, a restarted Krylov method that is applied to some matrix . Then each iteration builds a new matrix , , whose columns provide an orthonormal basis of the current Krylov subspace. The eigenvalues of the related Rayleigh-quotient matrix, are called Ritz values and used to approximate those of A. If A is Hermitian the interlacing theorems apply, the Ritz values interlace the eigenvalues of A, and it is possible to establish monotonic convergence toward the desired exterior eigenvalues, e.g.,   . However, if A happens to be non-Hermitian then the behavior of the Ritz values is not that straightforward    . This drawback raises the question of whether it is possible to extend the above theorems, and what meanings do the modified ones have.
The plan of the paper is as follows. The idea of replacing eigenvalues and diagonal entries with their moduli is illustrated in the next section, in which we derive the absolute trace theorem. This observation can be viewed as a robust extension of Ky Fan maximum principle, that holds for any normal matrix. Further extensions provide useful majorization relations between eigenvalues of a matrix and a principal submatrix. The third section provides some background material on existing extensions of the interlacing theorems. This includes the concepts of diagonal similarity, transformed-Hermitian matrices, normal embedding, and principally normal matrices. Then, in Section 4, we introduce the “bounding inequalities” and derive conditions that ensure their viability.
2. The Absolute Trace of a Matrix
We shall start by stating Ky Fan trace theorems     . Let be a given Hermitian matrix whose eigenvalues are sorted to satisfy
and let k be a positive integer that is smaller than n. Let the set
contain all the matrices that have orthonormal columns. Then Ky Fan maximum principle asserts that
That is, the optimal value of the above maximum problem equals the sum of the k largest eigenvalues of H. Moreover, the optimal value is obtained for a matrix Q whose columns are eigenvectors of the k largest eigenvalues.
Similarly, Ky Fan minimum principle says that
and the optimal value is obtained for a matrix Q whose columns are eigenvectors of the k smallest eigenvalues.
The modification of the maximum principle is achieved by introducing a new type of objective function. This change enables us to handle all types of normal matrices.
Definition 1 Let be some matrix from with singular values , .Then the scalar functions and are defined by the equalities
The function is called the absolute trace of A, while is called the singular trace of A. This pair of functions is known to satisfy
for any . A detailed proof of the last inequality can be found, for example, in (  : p. 1237) (  : p. 154), and (  : pp. 261-263).
Theorem 1 (The absolute trace theorem) Let be a normal matrix with eigenvalues , , that satisfy
and let be defined by (2.2). Then
and the optimal value is obtained for a matrix Q which is composed from eigenvectors of N that correspond to .
Proof. Since N is normal the singular values of N satisfy
Let Q be some matrix from and let
denote the singular values of . Then (2.7) implies that
On the other hand, the interlacing relations for singular values give the inequalities
See (3.8) in the next section. Hence by combining (2.11), (2.12), and (2.10) we see that the inequality
holds for all . Yet equality is obtained when Q is composed from orthonormal eigenvectors of N that correspond to . □
The inequality (2.7) is part of a more general observation by Ky Fan  . Let be an arbitrary complex matrix with singular values
It is also possible to assume that the diagonal entries of A are ordered to satisfy
Then Ky Fan  has shown that
The last observation can be modified by replacing the diagonal entries with eigenvalues. Let , , denote the eigenvalues of A and assume that
Then Schur’s triangularization theorem implies the existence of a unitary matrix such that is an upper triangular matrix, say , and for . Therefore, since T has the same singular values as A, applying (2.16) on T gives
See, for example (  : p. 176;  : p. 318;  : p. 262). The inequalities (2.16) and (2.18) describe majorization relations between the related vectors. For a detailed survey of majorization relations see  . See also    . The next theorem extends (2.18) to handle principal submatrices.
Theorem 2 Let be as above, satisfying (2.14) - (2.18). Let be a principal submatrix of A. That is, , and is obtained from A by deleting rows and the same columns. Let the singular values and the eigenvalues of be ordered to satisfy
Proof. The first inequality is obtained from (2.18) by replacing A with . The second one is concluded from the singular values inequality
See (3.8) in the next section. □
When handling a normal matrix the last results can be refined as follows.
Theorem 3 Let be a normal matrix with eigenvalues as in (2.8). Let be a principal submatrix of N with eigenvalues
and singular values
Proof. Since N is normal, the singular values of N are , . Therefore (2.24) is obtained from (2.21) by replacing A with N, and with P. □
Theorem 4 Let N be a normal matrix as above. Let the matrix has k orthonormal columns, and consider the matrix
Let the eigenvalues and the singular values of P satisfy (2.22) and (2.23), respectively. Then (2.24) holds.
Proof. Let the orthonormal matrix be obtained by completing the columns of V to be an orthornormal basis of . Then P is a principal submatrix of the normal matrix , which has the same eigenvalues and singular values as N. □
The next sections sharpen the relations between eigenvalues of a matrix and a principal submatrix.
3. The Interlacing Theorems of Cauchy and Poincaré
In this section, we briefly overview the interlacing theorems of Cauchy and Poincaré, e.g.,    , and consider some ways to extend these results. Let be a Hermitian matrix with eigenvalues
Let the Hermitian matrix be a principal submatrix of G with eigenvalues
Then Cauchy interlacing theorem asserts that
In particular, for we have the interlacing relations
The Cauchy interlace theorem can be used to derive analogous results for singular values. Let have the singular values
and let be a principal submatrix of A with singular values
See, for example,     .
Another related corollary is Poincaré separation theorem, in which H is defined as
where has orthonormal columns. Then, assuming that the eigenvalues of G and H satisfy (3.1) and (3.2), the inequalities (3.3)-(3.5) remain valid. The last statement is sometimes summarized by saying that the eigenvalues of H interlace those of G.
Let the matrix U be obtained by extending the columns of V to be an orthonormal basis of . Then Poincaré theorem is concluded from Cauchy theorem by comparing the eigenvalues of and . Conversely, if V is composed of some columns of the identity matrix then Poincaré theorem coincides with Cauchy theorem. Note that Ky Fan trace theorems are direct consequences of Poincaré theorem.
One way to extend Cauchy theorem is based on diagonal similarity. Let A and B be two matrices in . Then A is diagonally similar to B if there exists a nonsingular diagonal matrix such that . Clearly, if A is diagonally similar to B then every principal submatrix of A is diagonally similar to the corresponding principal submatrix of B. Therefore, since similarity transformations preserve eigenvalues, Cauchy interlacing theorem applies to any matrix which is diagonally similar to Hermitian matrix. Let us consider for example a tridiagonal matrix, , such that
Then it is easy to verify that T is diagonally similar to a tridiagonal symmetric matrix, which means that Cauchy theorem holds for T. However, in the general case, when given an arbitrary matrix, the question of whether this matrix is diagonally similar to some (unknown) Hermitian matrix is not easy to answer.
A second extension regards the following matrices.
Definition 2 A matrix is called Transformed-Hermitian, or T-H in brief, if it has the form
where and are complex numbers and H Hermitian.
An equivalent way to write (3.11) is
where is a real number, a complex number, and H Hermitian. Observe that the eigenvalues of a T-H matrix lie on some line in the complex plane. This shows that the Cauchy-Poincaré interlacing theorems can be extended to T-H matrices: In this case, the interlacing relations take place on the relevant line.
It is also easy to verify that any T-H matrix is normal, and that any normal matrix whose eigenvalues lie on a line in the complex plane is a T-H matrix. Another feature that characterizes T-H matrices is that they have the normal embedding property which is defined as follows.
Definition 3 A normal matrix has the normal embedding property if for any matrix with orthonormal columns the matrix is normal.
The relation between normal embedding and T-H matrices was noted by Ky Fan and Pall (  : p. 299): A normal matrix has the normal embedding property if and only if its eigenvalues lie on a line in the complex plane. In other words, a matrix has the normal embedding property if and only if it is a T-H matrix.
A larger set of matrices gained by moving from T-H matrices to block-diagonal matrices of this kind.
Definition 4 A matrix is called block-diagonal T-H matrix if it is block-diagonal and each block is a T-H matrix.
Note that a block-diagonal T-H matrix may include blocks, and it is always a normal matrix. Moreover, let be a block-diagonal T-H matrix, and let be a principal submatrix of N. Then, clearly, P is also a block-diagonal T-H matrix, which shows that P is normal. Recently Sherman and Smith  have connected these observations with the following useful concept.
Definition 5 A normal matrix N is called principally-normal, or P-N in brief, if every principal submatrix of N is a normal matrix.
It is shown in  that if N is a P-N irreducible matrix then N is a T-H matrix. Otherwise, when N is a reducible P-N matrix, there exists a permutation matrix S such that is a block-diagonal T-H matrix. That is, a matrix is P-N if and only if it can be permuted into a block-diagonal T-H matrix. The eigenvalues of such matrices lie on the union of finitely many lines and singletons. Therefore, although local interlacing relations hold on each line, it is not possible to extend these relations to eigenvalues that lie on different lines. Consider for example a diagonal matrix, D, whose diagonal entries are random complex numbers. Then D has the P-N property but it fails to satisfy the interlacing relations (or to have the normal embedding property). It is also worthwhile noting that although a unitary matrix is always normal, it is not necessarily a P-N matrix. For example consider the matrix
The fact that Cauchy interlace theorem holds for real diagonal matrices enables us to extend this theorem to upper triangular matrices that have real diagonal entries: Let be such a matrix, and let be a principal submatrix of T. Then is also an upper triangular matrix, and each diagonal entry (eigenvalue) of is also a diagonal entry (eigenvalue) of T. Let the diagonal matrices and be obtained from the diagonal entries of T and respectively. Then is a principal submatrix of D, and the eigenvalues of (the eigenvalues of ) interlace those of D (those of T ). Similar arguments show that the interlacing relations remain valid when the diagonal entries of T lie on a line in the complex plane. Note that lower triangular matrices have a similar property. This example shows that Cauchy interlacing may hold in non-normal matrices.
Summarizing the attempts to extend the interlacing theorems, we see that extension is possible only for certain types of matrices whose eigenvalues lie on a line in the complex plane. If, however, the eigenvalues of a matrix are not real or collinear, then the interlacing inequalities become meaningless. In the next section, we introduce a new kind of inequalities between eigenvalues of a matrix and a principal submatrix. The new inequalities have a clear meaning for any square matrix, and are valid on a larger range of matrices.
4. The Bounding Inequalities
In this section, we introduce the bounding inequalities and discuss their viability.
Definition 6 (The Bounding inequalities) Let the matrix have eigenvalues , , that satisfy
Let be a principal submatrix of N with eigenvalues , , that satisfy
If the eigenvalues of the two matrices satisfy
then we say that the bounding inequalities hold.
Definition 7 (The Bounding Property) Let N be as above. If the bounding inequalities hold for any principal submatrix of N, then we say that N has the bounding property.
Below we will show that the bounding property is shared by several types of matrices.
Theorem 5 Any P-N matrix has the bounding property.
Proof. Let N and P be as in Definition 6. Since N and P are normal matrices, , , are the singular values of N, and , , are the singular values of P. Hence the interlacing relations for singular values imply (4.3).
We have seen that unitary matrices may fail to be principally normal. Yet the next assertion resolves this difficulty.
Theorem 6 Any unitary matrix has the bounding property.
Proof. Let N and P be as in Definition 6 and assume that N is unitary. In this case, all the singular values of N equal 1. That is, for . Let denote the largest singular value of P. Then it is easy to verify that
Consequently, the j th eigenvalues of N and P satisfy
which are the bounding relations. □
Corollary 7 Any permutation matrix has the bounding property.
As with Cauchy interlacing, the range of matrices that share the bounding property can be extended by applying diagonal similarity.
Theorem 8 If A is diagonally similar to a matrix B that has the bounding property, then A has the bounding property.
Proof. Since A is similar to B both matrices have the same set of eigenvalues. Moreover, let be a principal submatrix of A and let denote the corresponding principal submatrix of B. Then is diagonally similar to , and the two submatrices have the same eigenvalues. Therefore, since B and satisfy the bounding inequalities, the same is true for A and . □
Similar arguments can be used to verify the following assertions.
Theorem 9 Let the matrix has the bounding property. Then the following matrices share this property.
• The matrices and .
• The matrix cA where c is a complex number.
• The matrix where is a permutation matrix.
We have proved that the interlacing relations hold for upper (or lower) triangular matrices whose diagonal entries are restricted to lie on the real axis (or another line). Now we will show that the bounding property holds for such matrices even if their diagonal entries are not real or collinear.
Theorem 10 Any upper (or lower) triangular matrix has the bounding property.
Proof. Let be an upper triangular matrix, and let be a principal submatrix of T. Then is also an upper triangular matrix. Let the diagonal matrices and be obtained from the diagonals of T and , respectively. Then has the same eigenvalues as . Therefore, since D is a P-N matrix and is a principal submatrix of D, the eigenvalues of T and satisfy the bounding inequalities. □
One corollary of the last theorem is that any matrix that has the Jordan form has the bounding property. Yet a Jordan block with order larger than one is not a normal matrix. This shows that the bounding property is not restricted to normal matrices. Another type of matrix that shares this property is revealed below.
Theorem 11 Let be a tridiagonal matrix that has real diagonal entries, and the off-diagonal entries satisfy
Then T has the bounding property.
Proof. Condition (4.6) allows that
This possibility prevents the use of diagonal similarity and the proof needs a different argument. Let be a principal submatrix of T. Then has the same form as T. Let the symmetric tridiagonal matrix be obtained from T in the following way: for , and for . Let be a principal submatrix of S that is obtained in the same way that is obtained from T. Recall that the principal minors of a tridiagonal matrix can be computed in a recursive way, e.g., (  , p.29). This determinantal expansion shows that T has the same eigenvalues as S, and that has the same eigenvalues as . Moreover, the symmetry of S implies that the eigenvalues of S and satisfy both the bounding inequalities and the interlacing relations. Hence the same is true for the eigenvalues of T and . □
A further extension is gained by moving to block-diagonal matrices. For this purpose, we need the following lemmas.
Lemma 12 Let and be two square matrices. Assume that B has the bounding property, and let be a principal submatrix of B. Let the matrices and be defined by the equalities
and let the eigenvalues of these matrices satisfy (4.1) and (4.2). Then P is a principal submatrix of N, and the bounding inequalities (4.3) hold.
Proof. Let the eigenvalues of , and be denoted as
respectively. Then from (4.7) we see that the eigenvalues of N are the union of the eigenvalues of A and B. That is,
Similarly, the eigenvalues of P are obtained from those of A and . That is
Let be some eigenvalue of A. Then there exist two indices, and say, such that
Moreover, the bounding inequalities
implies that when moving from N to P either stays in its place or it moves “forward”. That is
Now (4.1) gives
and from (4.11) we obtain
which shows that satisfies the related bounding inequality.
Next we show that an eigenvalue of P which is an eigenvalue of satisfies the related bounding inequality. Let be an eigenvalue of such that
Then (4.12) implies that when moving from N to P the related eigenvalue can’t move forward. That is,
If then (4.12) and (4.16) give
which is the related bounding inequality.
It is possible, therefore, to assume that
where r is a positive integer. The last equality means that r eigenvalues of A have modulus between and . Let be the smallest of them (the one that has the smallest modulus) and let and be as in (4.11). Then
which shows that
Lemma 13 Let the matrices and N be as in Lemma 12, and let be a principal submatrix of A. If, in addition, A has the bounding property then the matrices N and
satisfy the bounding inequalities.
Proof. From Lemma 12 we know that the eigenvalues of N bound those of P. Also, since is a principal submatrix of P, a second use of Lemma 12 shows that the eigenvalues of P bound those of . Hence by combining these relations, we obtain that the eigenvalues of N bound those of . □
Lemma 14 Let the matrices A, B and N be as in Lemma 12. If both A and B have the bounding property then N inherits this property.
Proof. This statement is a direct corollary of Lemma 13. □
Theorem 15 Let N be a square block-diagonal matrix. If each block has the bounding property then N inherits this property.
Proof. The proof is concluded from Lemma 14 by using induction on the number of blocks. □
The Poincaré versions of the bounding inequalities are derived below. The first assertion is using the normal embedding property.
Theorem 16 Let be a normal matrix that has the normal embedding property. Let be some matrix with orthonormal columns, and let the matrix P be defined by the equality
Let the eigenvalues of N and P satisfy (4.1) and (4.2), respectively. Then the bounding inequalities (4.3) hold.
Proof. Let be a unitary matrix whose first k columns are those of V. Then is a principal submatrix of , and both matrices are normal. From this point, the proof continues as in Theorem 5. □
Theorem 17 Let be a unitary matrix with eigenvalues , . Let the matrices V and P be as in Theorem 16, and let the eigenvalues of P satisfy (4.2). Then the bounding relations (4.3) hold.
Proof. Let the unitary matrix be obtained from V as above. Then is a principal submatrix of , while the last matrix is unitary. Hence the proof follows from Theorem 6. □
The question of whether it is possible to achieve further extensions is interesting and challenging. For example, the majorization results of Theorem 3 tempt to assume that any normal matrix has the bounding property. Indeed, it is difficult to find a normal matrix that violates this rule, but the validity of this conjecture remains an open question.
Similarly, Theorem 2 suggests that the bounding inequalities may hold in several non-normal matrices. In this context, it is worth mentioning the following empirical observation. Experiments that we have done indicate that the bounding inequalities are valid in several types of random matrices. For example, let be a random matrix whose entries are uniformly distributed in the interval . Then the bounding inequalities are likely to hold whenever and . A similar behaviour is observed in other types of random matrices. However, the explanation of this phenomenon is left to future research.
5. Concluding Remarks
The classical theorems that we discuss are restricted to Hermitian matrices. Yet by introducing minor modifications, the theorems become meaningful for non-Hermitian matrices. The current extensions are gained by replacing eigenvalues and diagonal entries with their moduli. This enables us to replace Ky Fan maximum principle with the absolute trace theorem, which is applicable to all normal matrices.
The bounding inequalities and the bounding property are entirely new concepts. The geometric interpretation of the new bounds is quite different from that of the interlacing relations, which makes them meaningful for any square matrix. We have shown that the range of matrices that satisfy these bounds is considerably larger than that of the interlacing relations. Yet the question whether it is possible to achieve further extensions remains open.
As noted in the introduction, the interlacing relations are used to establish monotonic convergence in restarted Krylov methods for Hermitian matrices. The current results pave the way for extending these properties to non-Hermitian matrices.
 Fan, K. (1949) On a Theorem of Weyl Concerning Eigenvalues of Linear Transformations I. Proceedings of the National Academy of Sciences of the United States, 35, 652-655.
 Fan, K. (1951) Maximum Properties and Inequalities for the Eigenvalues of Completely Continuous Operators. Proceedings of the National Academy of Sciences of the United States, 37, 760-766.
 Marshall, A.W., Olkin, I. and Arnold, B.C. (2011) Inequalities: Theory of Majorization and Its Applications. Springer Series in Statistics, 2nd Edition, Springer, New York.
 Noschese, S., Pasquini, L. and Reichel, L. (2013) Tridiagonal Toeplitz Matrices: Properties and Novel Applications. Numerical Linear Algebra with Applications, 20, 302-326.
 Thompson, R.C. (1972) Principal Submatrices IX: Interlacing Inequalities for Singular Values of Submatrices. Linear Algebra and Its Applications, 5, 1-12.