Variational Analysis of the Spectral Abscissa at a Matrix with a Nongeneric Multiple Eigenvalue

The spectral abscissa is a fundamental map from the set of complex matrices to the real numbers. Denoted α and defined as the maximum of the real parts of the eigenvalues of a matrix X, it has many applications in stability analysis of dynamical systems. The function α is nonconvex and is non-Lipschitz near matrices with multiple eigenvalues. Variational analysis of this function was presented in Burke and Overton (Math Program 90:317–352, 2001), including a complete characterization of its regular subgradients and necessary conditions which must be satisfied by all its subgradients. A complete characterization of all subgradients of α at a matrix X was also given for the case that all active eigenvalues of X (those whose real part equals α(X)) are nonderogatory (their geometric multiplicity is one) and also for the case that they are all nondefective (their geometric multiplicity equals their algebraic multiplicity). However, necessary and sufficient conditions for all subgradients in all cases remain unknown. In this paper we present necessary and sufficient conditions for the simplest example of a matrix X with a derogatory, defective multiple eigenvalue.     

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.     

Generalized qd algorithm for block band matrices

The generalized qd algorithm for block band matrices is an extension of the block qd algorithm applied to a block tridiagonal matrix. This algorithm is applied to a positive definite symmetric block band matrix. The result concerning the behavior of the eigenvalues of the first and the last diagonal block of the matrix containing the entries q ^(k) which was obtained in the tridiagonal case is still valid for positive definite symmetric block band matrices. The eigenvalues of the first block constitute strictly increasing sequences and those of the last block constitute strictly decreasing sequences. The theorem of convergence, given in Draux and Sadik (Appl Numer Math 60:1300?C1308, 2010), also remains valid in this more general case.     

On the reduction of the normal Hankel problem to two particular cases

The normal Hankel problem (NHP) is to describe complex matrices that are normal and Hankel at the same time. The available results related to the NHP can be combined into two groups. On the one hand, there are several known classes of normal Hankel matrices. On the other hand, the matrix classes that may contain normal Hankel matrices not belonging to the known classes were shown to admit a parametrization by real 2 × 2 matrices with determinant 1. We solve the NHP for the cases where the characteristic matrix W of the given class has: (a) complex conjugate eigenvalues; (b) distinct real eigenvalues. To obtain a complete solution of the NHP, it remains to analyze two situations: (1) W is the Jordan block of order two for the eigenvalue 1; (2) W is the Jordan block of order two for ?1.     

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.     

Author index to volume 20

This paper considers the conjecture that given a real nonsingular matrix A, there exist a real diagonal matrix Λ with $\text{¦λ}{}_{\mathrm{ii}}\text{λ = 1}$ and a permutation matrix P such that (ΛPA) is positive stable. The conjecture is shown to be true for matrices of order 3 or less and may not be true for higher order matrices. A counterexample is presented in terms of a matrix of order 65. In showing this, an interesting matrix M_l of order 2^l = 64, which satisfies the matrix equation 2^l-1(M_l + M^T_l), has been used. The stability analysis is done by first decomposing the nonsingular matrix into its polar form. Some interesting results are presented in the study of eigenvalues of a product of orthogonal matrices. A simple function is derived in terms of these orthogonal matrices, which traces a hysteresis loop.     

On the nonsingular symmetric factors of a real matrix

For a given real square matrix A this paper describes the following matrices: (¹) all nonsingular real symmetric (r.s.) matrices S such that A = S^?1T for some symmetric matrix T.All the signatures (defined as the absolute value of the difference of the number of positive eigenvalues and the number of negative eigenvalues) possible for feasible S in (¹) can be derived from the real Jordan normal form of A. In particular, for any A there is always a nonsingular r.s. matrix S with signature S ? 1 such that A = S^?1T.     

Exploiting Mixed Precision for Computing Eigenvalues of Symmetric Matrices and Singular Values

The use of higher precision preconditioning for the symmetric eigenvalue problem and the singular value problem of general non–structured non–graded matrices are discussed. The matrix Q from the QR–decomposition as a preconditioner, applied to A with higher precision, in combination with Jacobi's method seems to allow the computation of all eigenvalues of symmetric positive definite matrices rsp. all singular values of general matrices to nearly full accuracy. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Construction of Matrices with Prescribed Singular Values and Eigenvalues

Two issues concerning the construction of square matrices with prescribe singular values an eigenvalues are addressed. First, a necessary and sufficient condition for the existence of an n × n complex matrix with n given nonnegative numbers as singular values an m ( n) given complex numbers to be m of the eigenvalues is determined. This extends the classical result of Weyl and Horn treating the case when m = n. Second, an algorithm is given to generate a triangular matrix with prescribe singular values an eigenvalues. Unlike earlier algorithms, the eigenvalues can be arranged in any prescribe order on the diagonal. A slight modification of this algorithm allows one to construct a real matrix with specified real an complex conjugate eigenvalues an specified singular values. The construction is done by multiplication by diagonal unitary matrices, permutation matrices and rotation matrices. It is numerically stable and may be useful in developing test software for numerical linear algebra packages.     

Subtotally positive and Monge matrices

A real matrix is called k-subtotally positive if the determinants of all its submatrices of order at most k are positive. We show that for an m × n matrix, only mn inequalities determine such class for every k, 1 ? k ? min(m,n). Spectral properties of square k-subtotally positive matrices are studied. Finally, completion problems for 2-subtotally positive matrices and their additive counterpart, the anti-Monge matrices, are investigated. Since totally positive matrices are 2-subtotally positive as well, the presented necessary conditions for this completion problem are also necessary conditions for totally positive matrices.     

The higher-order derivatives of spectral functions

We are interested in higher-order derivatives of functions of the eigenvalues of real symmetric matrices with respect to the matrix argument. We describe a formula for the k-th derivative of such functions in two general cases.The first case concerns the derivatives of the composition of an arbitrary (not necessarily symmetric) k-times differentiable function with the eigenvalues of symmetric matrices at a symmetric matrix with distinct eigenvalues.The second case describes the derivatives of the composition of a k-times differentiable separable symmetric function with the eigenvalues of symmetric matrices at an arbitrary symmetric matrix. We show that the formula significantly simplifies when the separable symmetric function is k-times continuously differentiable.As an application of the developed techniques, we re-derive the formula for the Hessian of a general spectral function at an arbitrary symmetric matrix. The new tools lead to a shorter, cleaner derivation than the original one.To make the exposition as self contained as possible, we have included the necessary background results and definitions. Proofs of the intermediate technical results are collected in the appendices.     

On the accuracy of the Gerschgorin circle theorem for bounding the spread of a real symmetric matrix

The spread of a matrix with real eigenvalues is the difference between its largest and smallest eigenvalues. The Gerschgorin circle theorem can be used to bound the extreme eigenvalues of the matrix and hence its spread. For nonsymmetric matrices the Gerschgorin bound on the spread may be larger by an arbitrary factor than the actual spread even if the matrix is symmetrizable. This is not true for real symmetric matrices. It is shown that for real symmetric matrices (or complex Hermitian matrices) the ratio between the bound and the spread is bounded by $\text{p+1}$, where p is the maximum number of off diagonal nonzeros in any row of the matrix. For full matrices this is just $\text{n}$. This bound is not quite sharp for n greater than 2, but examples with ratios of $\text{n?1}$ for all n are given. For banded matrices with m nonzero bands the maximum ratio is bounded by $\text{m}$ independent of the size of n. This bound is sharp provided only that n is at least 2m. For sparse matrices, p may be quite small and the Gerschgorin bound may be surprisingly accurate.     

On the Symplectic Eigenvalues of Positive Definite Matrices

A simple proof of Williamson’s theorem is given. This theorem states that a real symmetric positive definite matrix A of even order can be brought to diagonal form Λ by a symplectic congruence transformation. The diagonal entries of Λ are called symplectic eigenvalues of A. The problem of calculating these values is also discussed.     

Computation of roots of real and complex matrices

An algorithm is presented in this paper by which the rth root of real or complex matrices can be found without the computation of the eigenvalues and eigenvectors of the matrix. All required computations are in the real domain. The method is based on the Newton-Raphson algorithm and is capable of finding roots even when the matrix is defective. Computing the root of a matrix from eigenvalues and eigenvectors would be the preferred method if these data were available.     

On eigenvalues of random complexes

We consider higher-dimensional generalizations of the normalized Laplacian and the adjacency matrix of graphs and study their eigenvalues for the Linial–Meshulam model X^k(n, p) of random k-dimensional simplicial complexes on n vertices. We show that for p = Ω(logn/n), the eigenvalues of each of the matrices are a.a.s. concentrated around two values. The main tool, which goes back to the work of Garland, are arguments that relate the eigenvalues of these matrices to those of graphs that arise as links of (k - 2)-dimensional faces. Garland’s result concerns the Laplacian; we develop an analogous result for the adjacency matrix.     

Bounds for Eigenvalues of Matrix Polynomials Over Quaternion Division Algebra

Localization theorems are discussed for the left and right eigenvalues of block quaternionic matrices. Basic definitions of the left and right eigenvalues of quaternionic matrices are extended to quaternionic matrix polynomials. Furthermore, bounds on the absolute values of the left and right eigenvalues of quaternionic matrix polynomials are devised and illustrated for the matrix p norm, where \({p = 1, 2, \infty, F}\). The above generalizes the bounds on the absolute values of the eigenvalues of complex matrix polynomials, which give sharper bounds to the bounds developed in [LAA, 358, pp. 5–22 2003] for the case of 1, 2, and \({\infty}\) matrix norms.     

On the generalization of a retrocirculant

We study the properties of matrices of the form P(σ)A where σ is induced by an automorphism of an abelian group G and A is a group matrix. P(σ)A is a generalization of a retrocirculant. We also determine the eigenvalues of P(σ)A.     

A splitting preconditioner for saddle point problems

For large sparse systems of linear equations iterative techniques are attractive. In this paper, we study a splitting method for an important class of symmetric and indefinite system. Theoretical analyses show that this method converges to the unique solution of the system of linear equations for all t>0 (t is the parameter). Moreover, all the eigenvalues of the iteration matrix are real and nonnegative and the spectral radius of the iteration matrix is decreasing with respect to the parameter t. Besides, a preconditioning strategy based on the splitting of the symmetric and indefinite coefficient matrices is proposed. The eigensolution of the preconditioned matrix is described and an upper bound of the degree of the minimal polynomials for the preconditioned matrix is obtained. Numerical experiments of a model Stokes problem and a least‐squares problem with linear constraints presented to illustrate the effectiveness of the method. Copyright © 2011 John Wiley & Sons, Ltd.     

Extremal inverse eigenvalue problem for symmetric doubly arrow matrices

In this paper, we consider the following inverse eigenvalue problem: to construct a real symmetric doubly arrow matrix A from the minimal and maximal eigenvalues of all its leading principal submatrices. The necessary and sufficient condition for the solvability of the problem is derived. We also give a necessary and sufficient condition in order that the constructed matrices can be nonnegative. Our results are constructive and they generate algorithmic procedures to construct such matrices.     

Generating equations approach for quadratic matrix equations

We show how Van Loan's method for annulling the (2,1) block of skew‐Hamiltonian matrices by symplectic‐orthogonal similarity transformation generalizes to general matrices and provides a numerical algorithm for solving the general quadratic matrix equation: For skew‐Hamiltonian matrices we find their canonical form under a similarity transformation and find the class of all symplectic‐orthogonal similarity transformations for annulling the (2,1) block and simultaneously bringing the (1,1) block to Hessenberg form. We present a structure‐preserving algorithm for the solution of continuous‐time algebraic Riccati equation. Unlike other methods in the literature, the final transformed Hamiltonian matrix is not in Hamiltonian–Schur form. Three applications are presented: (a) for a special system of partial differential equations of second order for a single unknown function, we obtain the matrix of partial derivatives of second order of the unknown function by only algebraic operations and differentiation of functions; (b) for a similar transformation of a complex matrix into a symmetric (and three‐diagonal) one by applying only finite algebraic transformations; and (c) for finite‐step reduction of the eigenvalues–eigenvectors problem of a Hermitian matrix to the eigenvalues– eigenvectors problem of a real symmetric matrix of the same dimension. Copyright © 1999 John Wiley & Sons, Ltd.