Branch duplication for the construction of multiple eigenvalues in an Hermitian matrix whose graph is a tree

Suppose that the eigenvalues of an Hermitian matrix A whose graph is a tree T are known, as well as the eigenvalues of the principal submatrix of A corresponding to a certain branch of T. A method for constructing a larger tree T?', in which the branch is ‘`duplicated’', and an Hermitian matrix A′ whose graph is T?' is described. The eigenvalues of A' are all of those of A, together with those corresponding to the branch, including multiplicities. This idea is applied (1) to give a solution to the inverse eigenvalue problem for stars, (2) to prove that the known diameter lower bound, for the minimum number of distinct eigenvalues among Hermitian matrices with a given graph, is best possible for trees of bounded diameter, and (3) to increase the list of trees for which all possible lists for the possible spectra are know. A generalization of the basic branch duplication method is presented.     

A generalization of weyl’s inequalities with implications

This paper suggests a generalization of the additive Weyl inequalities to the case of two square matrices of different orders. As a consequence of the generalized Weyl inequalities, a theorem describing the location of eigenvalues of a Hermitian matrix in terms of the eigenvalues of an arbitrary Hermitian matrix of smaller order is derived. It is demonstrated that the latter theorem provides a generalization of Kahan’s theorem on clustered eigenvalues. It is also shown that the theorem on extended interlacing intervals is another consequence of the generalized additive Weyl inequalities suggested. Bibliography: 7 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 248, 1998, pp. 49–59. Translated by L. Yu. Kolotilina.     

Distributions of eigenvalues and inertias of some block Hermitian matrices consisting of orthogonal projectors

A complex square matrix A is called an orthogonal projector if A ²?=?A?=?A*, where A* is the conjugate transpose of A. In this article, we first give some formulas for calculating the distributions of real eigenvalues of a linear combination of two orthogonal projectors. Then, we establish various expansion formulas for calculating the inertias, ranks and signatures of some 2?×?2 and 3?×?3, as well as k?×?k block Hermitian matrices consisting of two orthogonal projectors. Many applications of the formulas are presented in characterizing interval distributions of numbers of eigenvalues, and nonsingularity of these block Hermitian matrices. In addition, necessary and sufficient conditions are given for various equalities and inequalities of these block Hermitian matrices to hold.     

Eigenvalue inequalities and equalities

We consider cases of equality in three basic inequalities for eigenvalues of Hermitian matrices: Cauchy's interlacing inequalities for principal submatrices, Weyl's inequalities for sums, and the residual theorem. Several applications generalize and sharpen known results for eigenvalues of irreducible tridiagonal Hermitian matrices.     

When is a matrix unitary or Hermitian plus low rank?

Hermitian and unitary matrices are two representatives of the class of normal matrices whose full eigenvalue decomposition can be stably computed in quadratic computing complexity once the matrix has been reduced, for instance, to tridiagonal or Hessenberg form. Recently, fast and reliable eigensolvers dealing with low‐rank perturbations of unitary and Hermitian matrices have been proposed. These structured eigenvalue problems appear naturally when computing roots, via confederate linearizations, of polynomials expressed in, for example, the monomial or Chebyshev basis. Often, however, it is not known beforehand whether or not a matrix can be written as the sum of a Hermitian or unitary matrix plus a low‐rank perturbation. In this paper, we give necessary and sufficient conditions characterizing the class of Hermitian or unitary plus low‐rank matrices. The number of singular values deviating from 1 determines the rank of a perturbation to bring a matrix to unitary form. A similar condition holds for Hermitian matrices; the eigenvalues of the skew‐Hermitian part differing from 0 dictate the rank of the perturbation. We prove that these relations are linked via the Cayley transform. Then, based on these conditions, we identify the closest Hermitian or unitary plus rank k matrix to a given matrix A, in Frobenius and spectral norm, and give a formula for their distance from A. Finally, we present a practical iteration to detect the low‐rank perturbation. Numerical tests prove that this straightforward algorithm is effective.     

Equalities and inequalities for inertias of hermitian matrices with applications

The inertia of a Hermitian matrix is defined to be a triplet composed of the numbers of the positive, negative and zero eigenvalues of the matrix counted with multiplicities, respectively. In this paper, we show some basic formulas for inertias of 2×2 block Hermitian matrices. From these formulas, we derive various equalities and inequalities for inertias of sums, parallel sums, products of Hermitian matrices, submatrices in block Hermitian matrices, differences of outer inverses of Hermitian matrices. As applications, we derive the extremal inertias of the linear matrix expression A-BXB^∗ with respect to a variable Hermitian matrix X. In addition, we give some results on the extremal inertias of Hermitian solutions to the matrix equation AX=B, as well as the extremal inertias of a partial block Hermitian matrix.     

Eigenvalue Inequalities and Schubert Calculus

Using techniques from algebraic topology we derive linear inequalities which relate the spectrum of a set of Hermitian matrices A₁,…, A_r ? ¢^n×n with the spectrum of the sum A₁ + … + A_r. These extend eigenvalue inequalities due to Freede-Thompson and Horn for sums of eigenvalues of two Hermitian matrices.     

半正定Hermitian矩阵的广义Schur补的Lner偏序和特征值

首先得到了半正定 Hermitian矩阵的方幂的广义 Schur补的 L owner偏序的一些结果 ,然后改进了半正定 Hermitian矩阵的 Schur补的交错不等式 .     

Interlacing properties of the eigenvalues of some matrix classes

We establish the eigenvalue interlacing property (i.e. the smallest real eigenvalue of a matrix is less than the smallest real eigenvalue of any of its principal submatrices) for the class of matrices introduced by Kotelyansky (all principal and almost principal minors of these matrices are positive). We show that certain generalizations of Kotelyansky and totally positive matrices possess this property. We also prove some interlacing inequalities for the other eigenvalues of Kotelyansky matrices.     

On the spread of a hermitian matrix and a conjecture of thompson

We prove some inequalities involving the eigenvalues of an nxn Hermitian matrix and the eigenvalues of the (n?1)x(n?1) principal submatrices. We apply this inequality to generalize a known result on the numerical range to the lth numerical range. The method used yields an elegant proof of the converse to the interlacing theorem, which we include. A counterexample to the quardratic spread inequality conjectured by R. C. Thompson is also given.     

Inertial properties of eigenvalues,II

Inequalities involving the eigenvalues of conjunctive Hermitian matrices are established, and shown to contain a recent result of Machover, the law of inertia, and the interlacing inequalities.     

Arc transitive covering digraphs and their eigenvalues

We prove that every finite regular digraph has an arc-transitive covering digraph (whose arcs are equivalent under automorphisms) and every finite regular graph has a 2-arc-transitive covering graph. As a corollary, we sharpen C. D. Godsil's results on eigenvalues and minimum polynomials of vertex-transitive graphs and digraphs. Using Godsil's results, we prove, that given an integral matrix A there exists an arc-transitive digraph X such that the minimum polynomial of A divides that of X. It follows that there exist arc-transitive digraphs with nondiagonalizable adjacency matrices, answering a problem by P. J. Cameron. For symmetric matrices A, we construct a 2-arc-transitive graphs X.     

Inertia possibilities for completions of partial hermitian matrices

A partial Hermitian matrix is one in which some entries are specified and others are considered to be free (complex) variables. Assuming the undirected graph of the specified entries is chordal, it is shown that, with certain mild restrictions, a partial Hermitian matrix may be completed to a Hermitian matrix with any inertia allowed by the specified principal submatrices through the interlacing inequalities. This generalizes earlier work dealing with the existence of positive definite completions, and. as before, the chordality assumption is, in general, necessary. Further related observations dealing with Toeplitz completions and the minimum eigenvalues of completions are also made, and these raise additional questions.     

Inertia possibilities for completions of partial hermitian matrices *

A partial Hermitian matrix is one in which some entries are specified and others are considered to be free (complex) variables. Assuming the undirected graph of the specified entries is chordal, it is shown that, with certain mild restrictions, a partial Hermitian matrix may be completed to a Hermitian matrix with any inertia allowed by the specified principal submatrices through the interlacing inequalities. This generalizes earlier work dealing with the existence of positive definite completions, and. as before, the chordality assumption is, in general, necessary. Further related observations dealing with Toeplitz completions and the minimum eigenvalues of completions are also made, and these raise additional questions.     

On the spread of a hermitian matrix and a conjecture of thompson

We prove some inequalities involving the eigenvalues of an nxn Hermitian matrix and the eigenvalues of the (n-1)x(n-1) principal submatrices. We apply this inequality to generalize a known result on the numerical range to the lth numerical range. The method used yields an elegant proof of the converse to the interlacing theorem, which we include. A counterexample to the quardratic spread inequality conjectured by R. C. Thompson is also given.     

点删除下的图的$A_\alpha$特征值的交错性

设$G$为具有顶点集$V$, 边集$E$的简单图, 本文给出了图$G$与其子图$G-U$的$A_\alpha$特征值的交错不等式, 其中$U\subset V$. 作为应用, 我们利用该交错不等式导出了一些关于图的独立数, 点覆盖数, 哈密尔顿性及支撑数的$A_\alpha$ 谱条件.     

The bounds of the eigenvalues for rank‐one modification of Hermitian matrix

In this paper, we present some new interlacing properties about the bounds of the eigenvalues for rank‐one modification of Hermitian matrix, whose eigenvalues are different and spectral decomposition also needs to be known. Numerical examples demonstrate the efficiency of the proposed method and support our theoretical results.Copyright © 2013 John Wiley & Sons, Ltd.     

H‐self‐adjoint matrices. Application to radiosity

In computer graphics, in the radiosity context, a linear system Φx=b must be solved and there exists a diagonal positive matrix H such that H Φ is symmetric. In this article, we extend this property to complex matrices: we are interested in matrices which lead to Hermitian matrices under premultiplication by a Hermitian positive‐definite matrix H. We shall prove that these matrices are self‐adjoint with respect to a particular innerproduct defined on ?ⁿ. As a result, like Hermitian matrices, they have real eigenvalues and they are diagonalizable. We shall also show how to extend the Courant–Fisher theorem to this class of matrices. Finally, we shall give a new preconditioning matrix which really improves the convergence speed of the conjugate gradient method used for solving the radiosity problem. Copyright © 2002 John Wiley & Sons, Ltd.     

Estimates for the Eigenvalues of Matrices

For matrices whose eigenvalues are real (such as Hermitian or real symmetric matrices), we derive simple explicit estimates for the maximal (λ_max) and the minimal (λ_min) eigenvalues in terms of determinants of order less than 3. For 3 × 3 matrices, we derive sharper estimates, which use det A but do not require to solve cubic equations.     

The computation of isotropic vectors

We describe algorithms to compute isotropic vectors for matrices with real or complex entries. These are unit vectors b satisfying b ^* Ab = 0. For real matrices the algorithm uses only the eigenvectors of the symmetric part corresponding to the extreme eigenvalues. For complex matrices, we first use the eigenvalues and eigenvectors of the Hermitian matrix K = (A − A ^*)/2i. This works in many cases. In case of failure we use the Hermitian part H or a combination of eigenvectors of H and K. We give some numerical experiments comparing our algorithms with those proposed by R. Carden and C. Chorianopoulos, P. Psarrakos and F. Uhlig.