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.     

Relative perturbation results for eigenvalues and eigenvectors of diagonalisable matrices

Let and be a perturbed eigenpair of a diagonalisable matrixA. The problem is to bound the error in and . We present one absolute perturbation bound and two relative perturbation bounds. The absolute perturbation bound is an extension of Davis and Kahan's sin θ Theorem from Hermitian to diagonalisable matrices. The two relative perturbation bounds assume that and are an exact eigenpair of a perturbed matrixD ₁ AD ₂ , whereD ₁ andD ₂ are non-singular, butD ₁ AD ₂ is not necessarily diagonalisable. We derive a bound on the relative error in and a sin θ theorem based on a relative eigenvalue separation. The perturbation bounds contain both the deviation ofD ₁ andD ₂ from similarity and the deviation ofD ₂ from identity. This work was partially supported by NSF grant CCR-9400921.     

Relative perturbation bounds for the unitary polar factor

LetB be anm×n (m≥n) complex (or real) matrix. It is known that there is a uniquepolar decomposition B=QH, whereQ*Q=I, then×n identity matrix, andH is positive definite, providedB has full column rank. Existing perturbation bounds suggest that in the worst case, for complex matrices the change inQ be proportional to the reciprocal ofB's least singular value, or the reciprocal of the sum ofB's least and second least singular values if matrices are real. However, there are situations where this unitary polar factor is much more accurately determined by the data than the existing perturbation bounds would indicate. In this paper the following question is addressed: how much mayQ change ifB is perturbed to $\tilde B = D_1^* BD_2 $ , whereD ₁ andD ₂ are nonsingular and close to the identity matrices of suitable dimensions? It is shown that for a such kind of perturbation, the change inQ is bounded only by the distances fromD ₁ andD ₂ to identity matrices and thus is independent ofB's singular values. Such perturbation is restrictive, but not unrealistic. We show how a frequently used scaling technique yields such a perturbation and thus scaling may result in better-conditioned polar decompositions.     

On the eigenvalues of some tridiagonal matrices

A solution is given for a problem on eigenvalues of some symmetric tridiagonal matrices suggested by William Trench. The method presented can be generalizable to other problems.     

Componentwise perturbation bounds for some matrix decompositions

Componentwise perturbation bounds for the Cholesky,LDL ^H ,QR andLU decompositions are derived. The bounds improve known results of the same type and reveal the structural characteristics of the perturbations.This subject was supported by the Institute of Information Processing of the University of Umeå and the Swedish Natural Science Research Council.     

A harmonic restarted Arnoldi algorithm for calculating eigenvalues and determining multiplicity

A restarted Arnoldi algorithm is given that computes eigenvalues and eigenvectors. It is related to implicitly restarted Arnoldi, but has a simpler restarting approach. Harmonic and regular Rayleigh-Ritz versions are possible.For multiple eigenvalues, an approach is proposed that first computes eigenvalues with the new harmonic restarted Arnoldi algorithm, then uses random restarts to determine multiplicity. This avoids the need for a block method or for relying on roundoff error to produce the multiple copies.     

Some closer bounds of Perron root basing on generalized Perron complement

This paper is concerned with the bounds of the Perron root ρ(A) of a nonnegative irreducible matrix A. Two new methods utilizing the relationship between the Perron root of a nonnegative irreducible matrix and its generalized Perron complements are presented. The former method is efficient because it gives the bounds for ρ(A) only by calculating the row sums of the generalized Perron complement P_t(A/A[α]) or even the row sums of submatrices A[α],A[β],A[α,β] and A[β,α]. And the latter gives the closest bounds (just in this paper) of ρ(A). The results obtained by these methods largely improve the classical bounds. Numerical examples are given to illustrate the procedure and compare it with others, which shows that these methods are effective.     

On upper bounds for Laplacian graph eigenvalues

In this paper, we obtain the following upper bound for the largest Laplacian graph eigenvalue λ(G):

     

Some lower bounds for the spectral radius of matrices using traces

Let A be an n×n matrix with eigenvalues λ₁,λ₂,…,λ_n, and let m be an integer satisfying rank(A)?m?n. If A is real, the best possible lower bound for its spectral radius in terms of m, trA and trA² is obtained. If A is any complex matrix, two lower bounds for are compared, and furthermore a new lower bound for the spectral radius is given only in terms of trA,trA²,‖A‖,‖A^∗A-AA^∗‖,n and m.     

Pseudospectra, critical points and multiple eigenvalues of matrix polynomials

We develop a general framework for perturbation analysis of matrix polynomials. More specifically, we show that the normed linear space L_m(C^n×n) of n-by-n matrix polynomials of degree at most m provides a natural framework for perturbation analysis of matrix polynomials in L_m(C^n×n). We present a family of natural norms on the space L_m(C^n×n) and show that the norms on the spaces C^m+1 and C^n×n play a crucial role in the perturbation analysis of matrix polynomials. We define pseudospectra of matrix polynomials in the general framework of the normed space L_m(C^n×n) and show that the pseudospectra of matrix polynomials well known in the literature follow as special cases. We analyze various properties of pseudospectra in the unified framework of the normed space L_m(C^n×n). We analyze critical points of backward errors of approximate eigenvalues of matrix polynomials and show that each critical point is a multiple eigenvalue of an appropriately perturbed polynomial. We show that common boundary points of components of pseudospectra of matrix polynomials are critical points. As a consequence, we show that a solution of Wilkinson’s problem for matrix polynomials can be read off from the pseudospectra of matrix polynomials.     

New perturbation bounds for denumerable Markov chains

This paper is devoted to perturbation analysis of denumerable Markov chains. Bounds are provided for the deviation between the stationary distribution of the perturbed and nominal chain, where the bounds are given by the weighted supremum norm. In addition, bounds for the perturbed stationary probabilities are established. Furthermore, bounds on the norm of the asymptotic decomposition of the perturbed stationary distribution are provided, where the bounds are expressed in terms of the norm of the ergodicity coefficient, or the norm of a special residual matrix. Refinements of our bounds for Doeblin Markov chains are considered as well. Our results are illustrated with a number of examples.     

Computing the optimal commuting matrix pairs

A matrix can be modified by an additive perturbation so that it commutes with any given matrix. In this paper, we discuss several algorithms for computing the smallest perturbation in the Frobenius norm for a given matrix pair. The algorithms have applications in 2-D direction-of-arrival finding in array signal processing. The work of first author was supported in part by NSF grant CCR-9308399. The work of the second author was supported in part by China State Major Key Project for Basic Researches.     

A generalized inverse eigenvalue problem in structural dynamic model updating

This paper is concerned with the problem of the best approximation for a given matrix pencil under a given spectral constraint and a submatrix pencil constraint. Such a problem arises in structural dynamic model updating. By using the Moore–Penrose generalized inverse and the singular value decomposition (SVD) matrices, the solvability condition and the expression for the solution of the problem are presented. A numerical algorithm for solving the problem is developed.     

First order spectral perturbation theory of square singular matrix polynomials

We develop first order eigenvalue expansions of one-parametric perturbations of square singular matrix polynomials. Although the eigenvalues of a singular matrix polynomial P(λ) are not continuous functions of the entries of the coefficients of the polynomial, we show that for most perturbations they are indeed continuous. Given an eigenvalue λ₀ of P(λ) we prove that, for generic perturbations M(λ) of degree at most the degree of P(λ), the eigenvalues of P(λ)+?M(λ) admit covergent series expansions near λ₀ and we describe the first order term of these expansions in terms of M(λ₀) and certain particular bases of the left and right null spaces of P(λ₀). In the important case of λ₀ being a semisimple eigenvalue of P(λ) any bases of the left and right null spaces of P(λ₀) can be used, and the first order term of the eigenvalue expansions takes a simple form. In this situation we also obtain the limit vector of the associated eigenvector expansions.     

Error bounds for computed eigenvalues and eigenvectors

Summary On the basis of an existence theorem for solutions of nonlinear systems, a method is given for finding rigorous error bounds for computed eigenvalues and eigenvectors of real matrices. It does not require the usual assumption that the true eigenvectors span the whole space. Further, a priori error estimates for eigenpairs corrected by an iterative method are given. Finally the results are illustrated with numerical examples.Dedicated to Professor Yoshikazu Nakai on his sixtieth birthday     

On approximately simultaneously diagonalizable matrices

A collection A₁, A₂, …, A_k of n × n matrices over the complex numbers C has the ASD property if the matrices can be perturbed by an arbitrarily small amount so that they become simultaneously diagonalizable. Such a collection must perforce be commuting. We show by a direct matrix proof that the ASD property holds for three commuting matrices when one of them is 2-regular (dimension of eigenspaces is at most 2). Corollaries include results of Gerstenhaber and Neubauer-Sethuraman on bounds for the dimension of the algebra generated by A₁, A₂, …, A_k. Even when the ASD property fails, our techniques can produce a good bound on the dimension of this subalgebra. For example, we establish for commuting matrices A₁, …, A_k when one of them is 2-regular. This bound is sharp. One offshoot of our work is the introduction of a new canonical form, the H-form, for matrices over an algebraically closed field. The H-form of a matrix is a sparse “Jordan like” upper triangular matrix which allows us to assume that any commuting matrices are also upper triangular. (The Jordan form itself does not accommodate this.)     

Perturbation bounds for polynomials

Using two different elementary approaches we derive a global and a local perturbation theorem on polynomial zeros that significantly improve the results of Ostrowski (Acta Math 72:99–257, 1940), Elsner et al. (Linear Algebra Appl 142:195–209, 1990). A comparison of different perturbation bounds shows that our results are better in many cases than the similar local result of Beauzamy (Can Math Bull 42(1):3–12, 1999). Using the matrix theoretical approach we also improve the backward stability result of Edelman and Murakami (Proceedings of the Fifth SIAM Conference on Applied Linear Algebra, SIAM, Philapdelphia, 1994; Math Comput 64:210–763, 1995).     

An inverse eigenvalue problem and an associated approximation problem for generalized K-centrohermitian matrices

A partially described inverse eigenvalue problem and an associated optimal approximation problem for generalized K-centrohermitian matrices are considered. It is shown under which conditions the inverse eigenproblem has a solution. An expression of its general solution is given. In case a solution of the inverse eigenproblem exists, the optimal approximation problem can be solved. The formula of its unique solution is given.     

On Hadamard diagonalizable graphs

Of interest here is a characterization of the undirected graphs G such that the Laplacian matrix associated with G can be diagonalized by some Hadamard matrix. Many interesting and fundamental properties are presented for such graphs along with a partial characterization of the cographs that have this property.