Backward errors for eigenvalues and eigenvectors of Hermitian,skew-Hermitian,H-even and H-odd matrix polynomials

We discuss the perturbation analysis for eigenvalues and eigenvectors of structured homogeneous matrix polynomials with Hermitian, skew-Hermitian, H-even and H-odd structure. We construct minimal structured perturbations (structured backward errors) such that an approximate eigenvalue and eigenvector pair (finite or infinite eigenvalues) is an exact eigenvalue eigenvector pair of an appropriately perturbed structured matrix polynomial. We present various comparisons with unstructured backward errors and previous backward errors constructed for the non-homogeneous case and show that our results generalize previous results.     

Additive/Multiplicative Free Subordination Property and Limiting Eigenvectors of Spiked Additive Deformations of Wigner Matrices and Spiked Sample Covariance Matrices

When some eigenvalues of a spiked additive deformation of a Wigner matrix or a spiked multiplicative deformation of a Wishart matrix separate from the bulk, we study how the corresponding eigenvectors project onto those of the perturbation. We point out that the subordination function relative to the free (additive or multiplicative) convolution plays an important part in the asymptotic behavior.     

On the eigenvalues of specially low-rank perturbed matrices

We study the eigenvalues of a matrix A perturbed by a few special low-rank matrices. The perturbation is constructed from certain basis vectors of an invariant subspace of A, such as eigenvectors, Jordan vectors, or Schur vectors. We show that most of the eigenvalues of the low-rank perturbed matrix stayed unchanged from the eigenvalues of A; the perturbation can only change the eigenvalues of A that are related to the invariant subspace. Existing results mostly studied using eigenvectors with full column rank for perturbations, we generalize the results to more general settings. Applications of our results to a few interesting problems including the Google’s second eigenvalue problem are presented.     

Large deviations of the extreme eigenvalues of random deformations of matrices

Consider a real diagonal deterministic matrix X _n of size n with spectral measure converging to a compactly supported probability measure. We perturb this matrix by adding a random finite rank matrix, with delocalized eigenvectors. We show that the joint law of the extreme eigenvalues of the perturbed model satisfies a large deviation principle in the scale n, with a good rate function given by a variational formula. We tackle both cases when the extreme eigenvalues of X _n converge to the edges of the support of the limiting measure and when we allow some eigenvalues of X _n , that we call outliers, to converge out of the bulk. We can also generalise our results to the case when X _n is random, with law proportional to e ^{?n Tr V(X)} dX, for V growing fast enough at infinity and any perturbation of finite rank.     

The Polynomial Method for Random Matrices

We define a class of “algebraic” random matrices. These are random matrices for which the Stieltjes transform of the limiting eigenvalue distribution function is algebraic, i.e., it satisfies a (bivariate) polynomial equation. The Wigner and Wishart matrices whose limiting eigenvalue distributions are given by the semicircle law and the Marčenko–Pastur law are special cases. Algebraicity of a random matrix sequence is shown to act as a certificate of the computability of the limiting eigenvalue density function. The limiting moments of algebraic random matrix sequences, when they exist, are shown to satisfy a finite depth linear recursion so that they may often be efficiently enumerated in closed form. In this article, we develop the mathematics of the polynomial method which allows us to describe the class of algebraic matrices by its generators and map the constructive approach we employ when proving algebraicity into a software implementation that is available for download in the form of the RMTool random matrix “calculator” package. Our characterization of the closure of algebraic probability distributions under free additive and multiplicative convolution operations allows us to simultaneously establish a framework for computational (noncommutative) “free probability” theory. We hope that the tools developed allow researchers to finally harness the power of infinite random matrix theory.     

Sharp estimates and saturation phenomena for a nonlocal eigenvalue problem

We determine the shape which minimizes, among domains with given measure, the first eigenvalue of a nonlocal operator consisting of a perturbation of the standard Dirichlet Laplacian by an integral of the unknown function. We show that this problem displays a saturation behaviour in that the corresponding value of the minimal eigenvalue increases with the weight affecting the average up to a (finite) critical value of this weight, and then remains constant. This critical point corresponds to a transition between optimal shapes, from one ball as in the Faber–Krahn inequality to two equal balls.     

Perturbation bounds for means of eigenvalues and invariant subspaces

When a matrix is close to a matrix with a multiple eigenvalue, the arithmetic mean of a group of eigenvalues is a good approximation to this multiple eigenvalue. A theorem of Gershgorin type for means of eigenvalues is proved and applied as a perturbation theorem for a degenerate matrix.For a multiple eigenvalue we derive bounds for computed bases of subspaces of eigenvectors and principal vectors, relating them to the spaces spanned by the last singular vectors of corresponding powers of the matrix. These bounds assure that, provided the dimensionalities are chosen appropriately, the angles of rotation of the subspaces are of the same order of magnitude as the perturbation of the matrix.A numerical example is given.     

Threshold properties of matrix-valued Schrödinger operators, II. Resonances

We present some results on the perturbation of eigenvalues embedded at a threshold for a matrix-valued Hamiltonian with three-dimensional dilation analytic Schrödinger operators as entries and with a small off-diagonal perturbation. The main result describes how a threshold eigenvalue generates resonances (that is, poles of the meromorphic continuation of the perturbed Hamiltonian).     

Eigenvalues and Eigenvectors of a Matrix Dependent on Several Parameters

This paper describes a method for investigating the analyticity and for obtaining perturbation expansions of eigenvalues and eigenvectors of a matrix dependent on several parameters. Some of results of this paper provide justification of the applications of the Newton method for inverse matrix eigenvalue problems.     

Sufficient conditions for the solubility of inverse eigenvalue problems

We define an inverse eigenvalue problem, which contains as special cases the classical additive and multiplicative inverse eigenvalue problems. Using some results on the distance of eigenvalues from matrix diagonal elements and Brouwer's fixed-point theorem, we give sufficient conditions for the solubility of the problem.     

On condition numbers of polynomial eigenvalue problems

In this paper, we investigate condition numbers of eigenvalue problems of matrix polynomials with nonsingular leading coefficients, generalizing classical results of matrix perturbation theory. We provide a relation between the condition numbers of eigenvalues and the pseudospectral growth rate. We obtain that if a simple eigenvalue of a matrix polynomial is ill-conditioned in some respects, then it is close to be multiple, and we construct an upper bound for this distance (measured in the euclidean norm). We also derive a new expression for the condition number of a simple eigenvalue, which does not involve eigenvectors. Moreover, an Elsner-like perturbation bound for matrix polynomials is presented.     

Perturbation theory of selfadjoint matrices and sign characteristics under generic structured rank one perturbations

For selfadjoint matrices in an indefinite inner product, possible canonical forms are identified that arise when the matrix is subjected to a selfadjoint generic rank one perturbation. Genericity is understood in the sense of algebraic geometry. Special attention is paid to the perturbation behavior of the sign characteristic. Typically, under such a perturbation, for every given eigenvalue, the largest Jordan block of the eigenvalue is destroyed and (in case the eigenvalue is real) all other Jordan blocks keep their sign characteristic. The new eigenvalues, i.e. those eigenvalues of the perturbed matrix that are not eigenvalues of the original matrix, are typically simple, and in some cases information is provided about their sign characteristic (if the new eigenvalue is real). The main results are proved by using the well known canonical forms of selfadjoint matrices in an indefinite inner product, a version of the Brunovsky canonical form and on general results concerning rank one perturbations obtained.     

Computable eigenvalue bounds for rank-k perturbations

We investigate lower bounds for the eigenvalues of perturbations of matrices. In the footsteps of Weyl and Ipsen & Nadler, we develop approximating matrices whose eigenvalues are lower bounds for the eigenvalues of the perturbed matrix. The number of available eigenvalues and eigenvectors of the original matrix determines how close those approximations can be, and, if the perturbation is of low rank, such bounds are relatively inexpensive to obtain. Moreover, because the process need not be restricted to the eigenvalues of perturbed matrices, lower bounds for eigenvalues of bordered diagonal matrices as well as for singular values of rank-k perturbations and other updates of n×m matrices are given.     

加法与乘法逆特征值问题的可解性

1.引言 本文讨论如下代数特征值反问题可解的充分条件: 问题A(加法逆特征值问题)。给定一Hermite矩阵A=(a_(ij))_(n×n)及n个实数λ_1,…,λ_n,求一实对角阵D=diag(c_1…,c_n),使得A+D的特征值为λ_1,…,λ_n。 问题M(乘法逆特征值问题)。给定一正定Hermite矩阵A=(a_(ij))_(n×n)和n个正实数     

A correction of approximations used in sensitivity study of principal component analysis

Principal component analysis is a method of dimensionality reduction based on the eigensystem of the covariance matrix of a set of multivariate observations. Analyzing the effects of some specific observations on this eigensystem is therefore of particular importance in the sensitivity study of the results. In this framework, approximations for the perturbed eigenvalues and eigenvectors when deleting one or several observations are useful from a computational standpoint. Indeed, they allow one to evaluate the effects of these observations without having to recompute the exact perturbed eigenvalues and eigenvectors. However, it turns out that some approximations which have been suggested are based on an incorrect application of matrix perturbation theory. The aim of this short note is to provide the correct formulations which are illustrated with a numerical study.     

Trimmed linearizations for structured matrix polynomials

We discuss the eigenvalue problem for general and structured matrix polynomials which may be singular and may have eigenvalues at infinity. We derive condensed forms that allow (partial) deflation of the infinite eigenvalue and singular structure of the matrix polynomial. The remaining reduced order staircase form leads to new types of linearizations which determine the finite eigenvalues and corresponding eigenvectors. The new linearizations also simplify the construction of structure preserving linearizations.     

On polynomial Schur's matrix

Classical Schur's matrix is a different evaluation, provided by Schur, of the quadratic Gaussian sum from Gauss. The advanced information was studied by L. Carlitz who determined its eigenvalues, and by P. Morton who determined its eigenvectors. In this paper, we generalize the classical Schur's matrix to the case in polynomial rings over finite fields, and what is more, we give explicit formulas for the determinant, inverse matrix, eigenvalues, multiplicity and eigenvectors with respect to each eigenvalue of the polynomial Schur's matrix.     

A Note on Random Perturbations of a Multiple Eigenvalue of a Hermitian Operator

The problem of a random Hermitian perturbation of a multiple isolated eigenvalue of a Hermitian operator is considered. It is shown that the combined multiplicities of the perturbed eigenvalues converge in probability to the multiplicity of the eigenvalue of the target operator. Also the asymptotic distribution of a certain average of these eigenvalues, centered at the target, is obtained. As a tool differentiation of analytic functions of operators is employed in conjunction with an ensuing “delta-method”. The result is of a probabilistic rather than statistical nature.     

A note on additive results for the Drazin inverse

For two square matrices that commute, we present some additive results for the Drazin inverse. We also give the application to relative perturbation of eigenvalues when the perturbed matrix commutes with the original matrix and perturbation bounds of the Drazin inverse.     

Singularities in Gaussian random fields

This paper studies a class of Gaussian random fields defined on lattices that arise in pattern analysis. Phase transitions are shown to exist at a critical temperature for these Gaussian random fields. These are established by showing discontinuous behavior for certain field random variables as the lattice size increases to infinity. The discontinuities in the statistical behavior of these random variables occur because the growth rates of the eigenvalues of the inverse of the variance-covariance matrix at the critical temperature are different from the growth rates at noncritical temperatures. It is also shown that the limiting specific heat has a phase transition with a power law behavior. The critical temperature occurs at the end point of the available values of temperature. Thus, although the critical behavior is not extreme, caution should be exercised when using such models near critical temperatures.Research supported by AFOSR Grant No. 91-0048 and by USARO Grant No. DAAL03-90-G-0103.