Testing the nullspace property using semidefinite programming

Recent results in compressed sensing show that, under certain conditions, the sparsest solution to an underdetermined set of linear equations can be recovered by solving a linear program. These results either rely on computing sparse eigenvalues of the design matrix or on properties of its nullspace. So far, no tractable algorithm is known to test these conditions and most current results rely on asymptotic properties of random matrices. Given a matrix A, we use semidefinite relaxation techniques to test the nullspace property on A and show on some numerical examples that these relaxation bounds can prove perfect recovery of sparse solutions with relatively high cardinality.     

A disjoint idempotent decomposition for linear combinations produced from two commutative tripotent matrices and its applications

A square matrix A of order n is said to be tripotent if A ³?=?A. In this note, we give a nine-term disjoint idempotent decomposition for the linear combination of two commutative tripotent matrices and their products. Using the decomposition, we derive some closed-form formulae for the eigenvalues, determinant, rank, trace, power, inverse and group inverse of the linear combinations. In particular, we show that the linear combinations of two commutative tripotent elements and their products can produce 3⁹?=?19,683 tripotent elements.     

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.     

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.     

Numerical enclosure for multiple eigenvalues of an Hermitian matrix whose graph is a tree

In this paper we consider a numerical enclosure method for multiple eigenvalues of an Hermitian matrix whose graph is a tree. If an Hermitian matrix A whose graph is a tree has multiple eigenvalues, it has the property that matrices which are associated with some branches in the undirected graph of A have the same eigenvalues. By using this property and interlacing inequalities for Hermitian matrices, we show an enclosure method for multiple eigenvalues of an Hermitian matrix whose graph is a tree. Since we do not generally know whether a given matrix has exactly a multiple eigenvalue from approximate computations, we use the property of interlacing inequalities to enclose some eigenvalues including multiplicities.In this process, we only use the enclosure of simple eigenvalues to enclose a multiple eigenvalue by using a computer and interval arithmetic.     

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.     

On the roots of the orthogonal polynomials and residual polynomials associated with a conjugate gradient method

In this paper we explore two sets of polynomials, the orthogonal polynomials and the residual polynomials, associated with a preconditioned conjugate gradient iteration for the solution of the linear system Ax = b. In the context of preconditioning by the matrix C, we show that the roots of the orthogonal polynomials, also known as generalized Ritz values, are the eigenvalues of an orthogonal section of the matrix C A while the roots of the residual polynomials, also known as pseudo-Ritz values (or roots of kernel polynomials), are the reciprocals of the eigenvalues of an orthogonal section of the matrix (C A)^?1. When C A is selfadjoint positive definite, this distinction is minimal, but for the indefinite or nonselfadjoint case this distinction becomes important. We use these two sets of roots to form possibly nonconvex regions in the complex plane that describe the spectrum of C A.     

On the eigenvalue distribution of a class of preconditioning methods

Summary A class of preconditioning methods depending on a relaxation parameter is presented for the solution of large linear systems of equationAx=b, whereA is a symmetric positive definite matrix. The methods are based on an incomplete factorization of the matrixA and include both pointwise and blockwise factorization. We study the dependence of the rate of convergence of the preconditioned conjugate gradient method on the distribution of eigenvalues ofC ^–1 A, whereC is the preconditioning matrix. We also show graphic representations of the eigenvalues and present numerical tests of the methods.     

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.     

Canonical Moments and Random Spectral Measures

We study some connections between the random moment problem and random matrix theory. A uniform draw in a space of moments can be lifted into the spectral probability measure of the pair (A,e), where A is a random matrix from a classical ensemble, and e is a fixed unit vector. This random measure is a weighted sampling among the eigenvalues of A. We also study the large deviations properties of this random measure when the dimension of the matrix increases. The rate function for these large deviations involves the reversed Kullback information.     

Function of a square matrix with repeated eigenvalues

An analytical function f(A) of an arbitrary n×n constant matrix A is determined and expressed by the “fundamental formula”, the linear combination of constituent matrices. The constituent matrices Z_kh, which depend on A but not on the function f(s), are computed from the given matrix A, that may have repeated eigenvalues. The associated companion matrix C and Jordan matrix J are then expressed when all the eigenvalues with multiplicities are known. Several other related matrices, such as Vandermonde matrix V, modal matrix W, Krylov matrix K and their inverses, are also derived and depicted as in a 2-D or 3-D mapping diagram. The constituent matrices Z_kh of A are thus obtained by these matrices through similarity matrix transformations. Alternatively, efficient and direct approaches for Z_kh can be found by the linear combination of matrices, that may be further simplified by writing them in “super column matrix” forms. Finally, a typical example is provided to show the merit of several approaches for the constituent matrices of a given matrix A.     

The Probability that a Random Real Gaussian Matrix haskReal Eigenvalues, Related Distributions, and the Circular Law

LetAbe annbynmatrix whose elements are independent random variables with standard normal distributions. Girko's (more general) circular law states that the distribution of appropriately normalized eigenvalues is asymptotically uniform in the unit disk in the complex plane. We derive the exact expected empirical spectral distribution of the complex eigenvalues for finiten, from which convergence in the expected distribution to the circular law for normally distributed matrices may be derived. Similar methodology allows us to derive a joint distribution formula for the real Schur decomposition ofA. Integration of this distribution yields the probability thatAhas exactlykreal eigenvalues. For example, we show that the probability thatAhas all real eigenvalues is exactly 2^{−n(n−1)/4}.     

A note on maximizing the permanent of a positive definite hermitian matrix,given the eigenvalues ∗

As a step toward understanding the unsolved problem of determining how large the permanent of a positive semi-definite matrix can be, given the eigenvalues, we note that a necessary condition for A to be a permanent maximizing matrix is that A commute with its permanental adjoint.     

Über Die Konvergenz Operatorwertiger Cosinusfunktionen mit Gestörtem Infinitesimalen Erzeuger

On convergence of operator cosine functions with perturbed infinitesimal generator. The question under what kind of perturbations a closed linear operatorA remains of the class of infinitesimal generators of operator cosine functions seems to be a rather difficult one and is unsolved in general. In this note we give bounds for the perturbation of operator cosine functions caused byA-bounded perturbationsT ofA under the assumption thatT + A is also a generator.

     

On a matrix associated to a matrix pair

For a c–stable matrix pair (E,A), i.e., all finite eigenvalues of (E,A) have negative real part, an associated c–stable matrix is provided. It has all finite eigenvalues of (E,A) as eigenvalues and an additional stable eigenvalue −α, where α may be chosen arbitrarily, which corresponds to the eigenvalue ∞ of (E,A). In the case of positive systems, this associated c–stable matrix is, in addition, shown to be a −M-matrix. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A sufficient condition that a matrix have eigenvalues with non-zero real parts

If A is a complex matrix let à be the real matrix obtained by replacing the diagonal elements of A by the moduli of their real parts and by replacing the off-diagonal elements by the negative of their moduli. Then we show that if à is an M-matrix the eigenvalues of A have nonzero real parts and, moreover, the moduli of the real parts are bounded below by the minimum of the real parts of the eigenvalues of Ã.     

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.     

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.     

Stability properties of superoptimal preconditioner from numerical range

A matrix is said to be stable if the real parts of all the eigenvalues are negative. In this paper, for any matrix A_n, we give some sufficient and necessary conditions for the stability of superoptimal preconditioner E_U(A_n) proposed by Tyrtyshnikov (SIAM J. Matrix Anal. Appl. 1992; 13 :459–473). Copyright © 2005 John Wiley & Sons, Ltd.     

Structured Backward Error and Condition Number for Linear Systems of the Type A* Ax = b

We present a formulation for the structured condition number and for the structured backward error for the linear system A* Ax = b, when the rectangular matrix A is subjected to normwise perturbations. Perturbations on the data A and the solution x are measured in the Frobenius norm. Numerical experiments are provided that show the relevance of this condition number in the prediction of the computing error when solving such systems.