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.     

Computing the matrix sign and absolute value functions

We present two algorithms for the computation of the matrix sign and absolute value functions. Both algorithms avoid a complete diagonalisation of the matrix, but they however require some informations regarding the eigenvalues location. The first algorithm consists in a sequence of polynomial iterations based on appropriate estimates of the eigenvalues, and converging to the matrix sign if all the eigenvalues are real. Convergence is obtained within a finite number of steps when the eigenvalues are exactly known. Nevertheless, we present a second approach for the computation of the matrix sign and absolute value functions, when the eigenvalues are exactly known. This approach is based on the resolution of an interpolation problem, can handle the case of complex eigenvalues and appears to be faster than the iterative approach. To cite this article: M. Ndjinga, C. R. Acad. Sci. Paris, Ser. I 346 (2008).     

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.     

Eigenvalue bifurcation in multiparameter families of non-self-adjoint operator matrices

We consider two-point non-self-adjoint boundary eigenvalue problems for linear matrix differential operators. The coefficient matrices in the differential expressions and the matrix boundary conditions are assumed to depend analytically on the complex spectral parameter λ and on the vector of real physical parameters p. We study perturbations of semi-simple multiple eigenvalues as well as perturbations of non-derogatory eigenvalues under small variations of p. Explicit formulae describing the bifurcation of the eigenvalues are derived. Application to the problem of excitation of unstable modes in rotating continua such as spherically symmetric MHD α ²-dynamo and circular string demonstrates the efficiency and applicability of the approach.     

Arbitrary perturbations of hermitian matrices

Kahan's results on the perturbation of the eigenvalues of a hermitian matrix A affected by an arbitrary perturbation A+X are improved in two ways. Better constants are given, and it is shown that the estimates do not depend on the size of A, but only on the size of the clusters of eigenvalues of A, relative to the euclidean norm of X.     

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.     

A New Algorithm for the Symmetric Tridiagonal Eigenvalue Problem

We apply a novel approach to approximate within ϵ to all the eigenvalues of an n × n symmetric tridiagonal matrix A using at most n²([3 log₂(625n⁶)] + (83n − 34)[log₂ (log₂((λ₁ − λ_n)/(2ϵ))/log₂(25_n))]) arithmetic operations where λ₁ and λ_n denote the extremal eigenvalues of A. The algorithm can be modified to compute any fixed numbers of the largest and the smallest eigenvalues of A and may also be applied to the band symmetric matrices without their reduction to the tridiagonal form.     

The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices

We consider the eigenvalues and eigenvectors of finite, low rank perturbations of random matrices. Specifically, we prove almost sure convergence of the extreme eigenvalues and appropriate projections of the corresponding eigenvectors of the perturbed matrix for additive and multiplicative perturbation models.The limiting non-random value is shown to depend explicitly on the limiting eigenvalue distribution of the unperturbed random matrix and the assumed perturbation model via integral transforms that correspond to very well-known objects in free probability theory that linearize non-commutative free additive and multiplicative convolution. Furthermore, we uncover a phase transition phenomenon whereby the large matrix limit of the extreme eigenvalues of the perturbed matrix differs from that of the original matrix if and only if the eigenvalues of the perturbing matrix are above a certain critical threshold. Square root decay of the eigenvalue density at the edge is sufficient to ensure that this threshold is finite. This critical threshold is intimately related to the same aforementioned integral transforms and our proof techniques bring this connection and the origin of the phase transition into focus. Consequently, our results extend the class of ‘spiked’ random matrix models about which such predictions (called the BBP phase transition) can be made well beyond the Wigner, Wishart and Jacobi random ensembles found in the literature. We examine the impact of this eigenvalue phase transition on the associated eigenvectors and observe an analogous phase transition in the eigenvectors. Various extensions of our results to the problem of non-extreme eigenvalues are discussed.     

Perturbation Analysis for the Eigenvalue Problem of a Formal Product of Matrices

We study the perturbation theory for the eigenvalue problem of a formal matrix product A ₁ ^{s 1} ··· A _p ^{s p}, where all A _k are square and s _k {–1, 1}. We generalize the classical perturbation results for matrices and matrix pencils to perturbation results for generalized deflating subspaces and eigenvalues of such formal matrix products. As an application we then extend the structured perturbation theory for the eigenvalue problem of Hamiltonian matrices to Hamiltonian/skew-Hamiltonian pencils.     

Extreme value analysis for the sample autocovariance matrices of heavy-tailed multivariate time series

We provide some asymptotic theory for the largest eigenvalues of a sample covariance matrix of a p-dimensional time series where the dimension p = p _n converges to infinity when the sample size n increases. We give a short overview of the literature on the topic both in the light- and heavy-tailed cases when the data have finite (infinite) fourth moment, respectively. Our main focus is on the heavy-tailed case. In this case, one has a theory for the point process of the normalized eigenvalues of the sample covariance matrix in the iid case but also when rows and columns of the data are linearly dependent. We provide limit results for the weak convergence of these point processes to Poisson or cluster Poisson processes. Based on this convergence we can also derive the limit laws of various function als of the ordered eigenvalues such as the joint convergence of a finite number of the largest order statistics, the joint limit law of the largest eigenvalue and the trace, limit laws for successive ratios of ordered eigenvalues, etc. We also develop some limit theory for the singular values of the sample autocovariance matrices and their sums of squares. The theory is illustrated for simulated data and for the components of the S&P 500 stock index.     

Sharpness of generalized Gerschgorin disk

The generalized Gerschgorin disks of a partitioned matrix A, as introduced by D. G. Feingold and R. S. Varga (Pacif. J. Math.12 1241–1250 (1962)), are shown to give the smallest region covering all eigenvalues of all matrices from a certain class related to A.     

Applications of a theorem by Ky Fan in the theory of graph energy

The energy of a graph G is equal to the sum of the absolute values of the eigenvalues of G, which in turn is equal to the sum of the singular values of the adjacency matrix of G. Let X, Y, and Z be matrices, such that X+Y=Z. The Ky Fan theorem establishes an inequality between the sum of the singular values of Z and the sum of the sum of the singular values of X and Y. This theorem is applied in the theory of graph energy, resulting in several new inequalities, as well as new proofs of some earlier known inequalities.     

Towards a spectral theory of graphs based on the signless Laplacian, II

A spectral graph theory is a theory in which graphs are studied by means of eigenvalues of a matrix M which is in a prescribed way defined for any graph. This theory is called M-theory. We outline a spectral theory of graphs based on the signless Laplacians Q and compare it with other spectral theories, in particular to those based on the adjacency matrix A and the Laplacian L. As demonstrated in the first part, the Q-theory can be constructed in part using various connections to other theories: equivalency with A-theory and L-theory for regular graphs, common features with L-theory for bipartite graphs, general analogies with A-theory and analogies with A-theory via line graphs and subdivision graphs. In this part, we introduce notions of enriched and restricted spectral theories and present results on integral graphs, enumeration of spanning trees, characterizations by eigenvalues, cospectral graphs and graph angles.     

Determination of a matrix function using the divided difference method of Newton and the interpolation technique of Hermite

Computing a function f(A) of an n-by-n matrix A is a frequently occurring problem in control theory and other applications. In this paper we introduce an effective approach for the determination of matrix function f(A). We propose a new technique which is based on the extension of Newton divided difference and the interpolation technique of Hermite and using the eigenvalues of the given matrix A. The new algorithm is tested on several problems to show the efficiency of the presented method. Finally, the application of this method in control theory is highlighted.     

Matrices with prescribed Ritz values

On the way to establishing a commutative analog to the Gelfand-Kirillov theorem in Lie theory, Kostant and Wallach produced a decomposition of M(n) which we will describe in the language of linear algebra. The “Ritz values” of a matrix are the eigenvalues of its leading principal submatrices of order m=1,2,…,n. There is a unique unit upper Hessenberg matrix H with those eigenvalues. For real symmetric matrices with interlacing Ritz values, we extend their analysis to allow eigenvalues at successive levels to be equal. We also decide whether given Ritz values can come from a tridiagonal matrix.     

Computation of exact inertia and inclusions of eigenvalues (singular values) of tridiagonal (bidiagonal) matrices

This report may be considered as a non-trivial extension of an unpublished report by William Kahan (Accurate Eigenvalues of a symmetric tri-diagonal matrix, Technical Report CS 41, Computer Science Department, Stanford University, 1966). His interplay between matrix theory and computer arithmetic led to the development of algorithms for computing accurate eigenvalues and singular values. His report is generally considered as the precursor for the development of IEEE standard 754 for binary arithmetic. This standard has been universally adopted by virtually all PC, workstation and midrange hardware manufactures and tens of billions of such machines have been produced. Now we use the features in this standard to improve the original algorithm.In this paper, we describe an algorithm in floating-point arithmetic to compute the exact inertia of a real symmetric (shifted) tridiagonal matrix. The inertia, denoted by the integer triplet (π, ν, ζ), is defined as the number of positive, negative and zero eigenvalues of a real symmetric (or complex Hermitian) matrix and the adjective exact refers to the eigenvalues computed in exact arithmetic. This requires the floating-point computation of the diagonal matrix D of the LDL^t factorization of the shifted tridiagonal matrix T − τI with +∞ and −∞ rounding modes defined in IEEE 754 standard. We are not aware of any other algorithm which gives the exact answer to a numerical problem when implemented in floating-point arithmetic in standard working precisions. The guaranteed intervals for eigenvalues are obtained by bisection or multisection with this exact inertia information. Similarly, using the Golub-Kahan form, guaranteed intervals for singular values of bidiagonal matrices can be computed. The diameter of the eigenvalue (singular value) intervals depends on the number of shifts with inconsistent inertia in two rounding modes. Our algorithm not only guarantees the accuracy of the solutions but is also consistent across different IEEE 754 standard compliant architectures. The unprecedented accuracy provided by our algorithms could be also used to debug and validate standard floating-point algorithms for computation of eigenvalues (singular values). Accurate eigenvalues (singular values) are also required by certain algorithms to compute accurate eigenvectors (singular vectors).We demonstrate the accuracy of our algorithms by using standard matrix examples. For the Wilkinson matrix, the eigenvalues (in IEEE double precision) are very accurate with an (open) interval diameter of 6 ulps (units of the last place held of the mantissa) for one of the eigenvalues and lesser (down to 2 ulps) for others. These results are consistent across many architectures including Intel, AMD, SGI and DEC Alpha. However, by enabling IEEE double extended precision arithmetic in Intel/AMD 32-bit architectures at no extra computational cost, the (open) interval diameters were reduced to one ulp, which is the best possible solution for this problem. We have also computed the eigenvalues of a tridiagonal matrix which manifests in Gauss-Laguerre quadrature and the results are extremely good in double extended precision but less so in double precision. To demonstrate the accuracy of computed singular values, we have also computed the eigenvalues of the Kac₃₀ matrix, which is the Golub-Kahan form of a bidiagonal matrix. The tridiagonal matrix has known integer eigenvalues. The bidiagonal Cholesky factor of the Gauss-Laguerre tridiagonal is also included in the singular value study.     

Remarks on Non-Linear Spectral Perturbation

We are interested in some aspects of the perturbation effects in the spectrum of a real nonnormal matrix A under linear perturbations. We discuss some known results and we use them to justify some recent experimental observations. Moreover, we demonstrate that the qualitative behavior of the eigenvalues of A under linear perturbations may be predicted by inspecting the spectral radius of a related matrix. Then, we show how this information can be used to analyze the quality of the approximation of a projection method and to justify the presence of unexpected approximate eigenvalues.     

A New Lower Bound for the Kirchhoff Index using a numerical procedure based on Majorization Techniques

In this note, we use a procedure, proposed in [Bianchi, M., and A. Torriero, Some localization theorems using a majorization technique, Journal of Inequalities and Applications 5 (2000), 433–446], based on a majorization technique, which localizes real eigenvalues of a matrix of order n. Through this information, we compute a lower bound for the Kirchhoff index (see [Bianchi M., A. Cornaro, J.L. Palacios and A. Torriero, Bounds for the Kirkhhoff index via majorization techniques, Journal of Mathematical Chemistry, (2012) online first]) that takes advantage of additional eigenvalues bounds. An algorithm has been developed with MATLAB software to evaluate the above mentioned bound. Finally, numerical examples are provided showing how tighter results can be obtained.     

Eigenvalue asymptotics of a modified Jaynes–Cummings model with periodic modulations

We analyze the influence of additive and multiplicative periodic modulations on the asymptotic behavior of eigenvalues of some Hermitian Jacobi Matrices related to the Jaynes–Cummings model using the so-called “successive diagonalization” method. This approach allows us to find the asymptotics of the nth eigenvalue λ_n as n→∞ stepwise with successively increasing precision. We bring to light the interplay of additive and multiplicative periodic modulations and their influence on the asymptotic behavior of eigenvalues. To cite this article: A. Boutet de Monvel et al., C. R. Acad. Sci. Paris, Ser. I 338 (2004).     

Fixing multiple eigenvalues by a minimal perturbation

Suppose we are given an n×n matrix, M, and a set of values, (m?n), and we wish to find the smallest perturbation in the 2-norm (i.e., spectral norm), ΔM, such that M-ΔM has the given eigenvalues λ_i. Some interesting results have been obtained for variants of this problem for fixing two distinct eigenvalues, fixing one double eigenvalue, and fixing a triple eigenvalue. This paper provides a geometric motivation for these results and also motivates their generalization. We also present numerical examples (both “successes” and “failures”) of fixing more than two eigenvalues by these generalizations.