Computing eigenspaces with specified eigenvalues of a regular matrix pair (A,B) and condition estimation: theory,algorithms and software

Theory, algorithms and LAPACK-style software for computing a pair of deflating subspaces with specified eigenvalues of a regular matrix pair (A, B) and error bounds for computed quantities (eigenvalues and eigenspaces) are presented. Thereordering of specified eigenvalues is performed with a direct orthogonal transformation method with guaranteed numerical stability. Each swap of two adjacent diagonal blocks in the real generalized Schur form, where at least one of them corresponds to a complex conjugate pair of eigenvalues, involves solving a generalized Sylvester equation and the construction of two orthogonal transformation matrices from certain eigenspaces associated with the diagonal blocks. The swapping of two 1×1 blocks is performed using orthogonal (unitary) Givens rotations. Theerror bounds are based on estimates of condition numbers for eigenvalues and eigenspaces. The software computes reciprocal values of a condition number for an individual eigenvalue (or a cluster of eigenvalues), a condition number for an eigenvector (or eigenspace), and spectral projectors onto a selected cluster. By computing reciprocal values we avoid overflow. Changes in eigenvectors and eigenspaces are measured by their change in angle. The condition numbers yield bothasymptotic andglobal error bounds. The asymptotic bounds are only accurate for small perturbations (E, F) of (A, B), while the global bounds work for all (E, F.) up to a certain bound, whose size is determined by the conditioning of the problem. It is also shown how these upper bounds can be estimated. Fortran 77software that implements our algorithms for reordering eigenvalues, computing (left and right) deflating subspaces with specified eigenvalues and condition number estimation are presented. Computational experiments that illustrate the accuracy, efficiency and reliability of our software are also described.     

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.     

On generalized stable rings

In this paper, we introduce the class of generalized stable rings and investigate equivalent characterizations of such rings. We show that End_R R is a generalized stable ring if and only if any right H-module decompositions M = A ₁ + B ₁ = A ₂ + B ₂ with A ₁ ? A ? A ₂ implies that there exist C,D,E ≤ M such that M = C + D B ₁ = c + E + B ₂ with.C ? A. Also we show that every generalized stable ring is a GE-ring and matrices over generalized stable regular ring can be diagonalized by some weakly invertible matrices.     

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}.     

The principal eigenvalue of a space–time periodic parabolic operator

This paper deals with the generalized principal eigenvalue of the parabolic operator , where the coefficients are periodic in t and x. We give the definition of this eigenvalue and we prove that it can be approximated by a sequence of principal eigenvalues associated to the same operator in a bounded domain, with periodicity in time and Dirichlet boundary conditions in space. Next, we define a family of periodic principal eigenvalues associated with the operator and use it to give a characterization of the generalized principal eigenvalue. Finally, we study the dependence of all these eigenvalues with respect to the coefficients.      

Perturbation bounds for the periodic Schur decomposition

This paper is devoted to the perturbation analysis for periodic regular matrix pairs. We present perturbation bounds for the periodic Schur decomposition of periodic regular matrix pairs with distinct eigenvalues, which extend the main result of Sun (SIAM J. Matrix Anal. Appl. 16:1328–1340, 1995). The results are illustrated by a numerical example.     

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.     

A binary powering Schur algorithm for computing primary matrix roots

An algorithm for computing primary roots of a nonsingular matrix A is presented. In particular, it computes the principal root of a real matrix having no nonpositive real eigenvalues, using real arithmetic. The algorithm is based on the Schur decomposition of A and has an order of complexity lower than the customary Schur based algorithm, namely the Smith algorithm.     

Computing the nearest stable matrix pairs

In this paper, we study the nearest stable matrix pair problem: given a square matrix pair (E,A), minimize the Frobenius norm of (Δ_E,Δ_A) such that (E+Δ_E,A+Δ_A) is a stable matrix pair. We propose a reformulation of the problem with a simpler feasible set by introducing dissipative Hamiltonian matrix pairs: A matrix pair (E,A) is dissipative Hamiltonian if A=(J−R)Q with skew‐symmetric J, positive semidefinite R, and an invertible Q such that Q^TE is positive semidefinite. This reformulation has a convex feasible domain onto which it is easy to project. This allows us to employ a fast gradient method to obtain a nearby stable approximation of a given matrix pair.     

On the optimal convergence factor of the accelerated parameterized inexact Uzawa method with three parameters for augmented systems

Under the assumption that all eigenvalues of the preconditioned Schur complement are real, we present an analytical proof for obtaining the optimal convergence factor of the real accelerated parameterized inexact Uzawa (APIU) method when P=A. It is proved that the optimal convergence factor is the same as that of the generalized successive overrelaxation method, which was published at the same time, and that it can be attained only at the unique optimum point of parameters, regardless of whether m>n or m=n. In addition, we generalize the APIU method and analyze the relationship between the APIU method and 10 additional Uzawa‐like methods.     

Resonance spectrum for one-dimensional layered media

We consider the “weighted” operator P_k=????_x a(x)? _x on the real line with a step-like coefficient which appears when propagation of waves through a finite slab of a periodic medium is studied. The medium is transparent at certain resonant frequencies which are related to the complex resonance spectrum of P_k. If the coefficient is periodic on a finite interval (locally periodic) with k identical cells, then the resonance spectrum of P_k has band structure. In the article, we study a transition to semi-infinite medium by taking the limit k→?∞?. The bands of resonances in the complex lower half plane are localized below the band spectrum of the corresponding periodic problem (k=∞) with k???1 or k resonances in each band. We prove that as k→?∞?, the resonance spectrum converges to the real axis.     

Matlab code for sorting real Schur forms

In Matlab 6, there exists a command to generate a real Schur form, wheras another transforms a real Schur form into a complex one. There do not exist commands to prescribe the order in which the eigenvalues appear on the diagonal of the upper (quasi‐) triangular factor T. For the complex case, a routine is sketched in Golub and Van Loan (Matrix Computations (3rd edn). The John Hopkins University Press: Baltimore and London, 1996), that orders the diagonal of T according to their distance to a target value τ. In this technical note, we give a Matlab routine to sort real Schur forms in Matlab. It is based on a block‐swapping procedure by Bai and Demmel (Linear Algebra and Its Applications 1993; 186 : 73) We also describe how to compute a partial real Schur form (see Saad (Numerical methods for large eigenvalue problems. Manchester University Press: Manchester, 1992.)) in case the matrix A is very large. Sorting real Schur forms, both partially and completely, has important applications in the computation of real invariant subspaces. Copyright © 2002 by John Wiley & Sons, Ltd.     

The generalized quaternion matrix equation AXB+CX⋆D=E

In this paper, we discuss the generalized quaternion matrix equation AXB+CX^⋆D=E, where X^⋆ is one of X, X^*, the η-conjugate or the η-conjugate transpose of X with η∈{i,j,k}. Two new real representations of a generalized quaternion matrix are proposed. By using this method, the criteria for the existence and uniqueness of solutions to the mentioned matrix equation as well as the existence of X=± X^⋆ solutions to the generalized quaternion matrix equation AXB+CXD=E are derived in a unified way.     

The geometry of t‐spreads in k‐walk‐regular graphs

A graph is walk‐regular if the number of closed walks of length ? rooted at a given vertex is a constant through all the vertices for all ?. For a walk‐regular graph G with d+1 different eigenvalues and spectrally maximum diameter D=d, we study the geometry of its d‐spreads, that is, the sets of vertices which are mutually at distance d. When these vertices are projected onto an eigenspace of its adjacency matrix, we show that they form a simplex (or tetrahedron in a three‐dimensional case) and we compute its parameters. Moreover, the results are generalized to the case of k‐walk‐regular graphs, a family which includes both walk‐regular and distance‐regular graphs, and their t‐spreads or vertices at distance t from each other. © 2009 Wiley Periodicals, Inc. J Graph Theory 64:312–322, 2010     

Bounds on path connectivity

The path-connectivity of a graph G is the maximal k for which between any k pairs of vertices there are k edge-disjoint paths (one between each pair). An upper bound for the path-connectivity of n^q(q<1) separable graphs [6] is shown to exist.If the edge-connectivity of a graph is K_E then between any two pairs of vertices and for every $\text{t?}\text{K}{}_{\mathrm{E}}$ there exists a t?t′?t+1 such that there are t′ paths between the first pair and $\text{K}{}_{\mathrm{E}}\text{?t′}$ between the second pair. All paths are edge-disjoint.     

Regular graphs constructed from the classical generalized quadrangle Q(4, q)

Let c_k be the smallest number of vertices in a regular graph with valency k and girth 8. It is known that c_{k + 1}?2(1 + k + k² + k³) with equality if and only if there exists a finite generalized quadrangle of order k. No such quadrangle is known when k is not a prime power. In this case, small regular graphs of valency k + 1 and girth 8 can be constructed from known generalized quadrangles of order q>k by removing a part of its structure. We investigate the case when q = k + 1 is a prime power, and try to determine the smallest graph under consideration that can be constructed from a generalized quadrangle of order q. This problem appears to be much more difficult than expected. We have general bounds and improve these for the classical generalized quadrangle Q(4, q), q even. © 2010 Wiley Periodicals, Inc. J Combin Designs 19:70‐83, 2010     

First‐order systems in on with periodic matrix potentials and vanishing instability intervals

First‐order systems in on with absolutely continuous real symmetric π‐periodic matrix potentials are considered. A thorough analysis of the discriminant is given. Interlacing of the eigenvalues of the periodic, antiperiodic and Dirichlet‐type boundary value problems on [0,π] is shown for a suitable indexing of the eigenvalues. The periodic and antiperiodic eigenvalues are characterized in terms of Dirichlet‐type eigenvalues. It is shown that all instability intervals vanish if and only if the potential is the product of an absolutely continuous real scalar valued function with the identity matrix. Copyright © 2014 John Wiley & Sons, Ltd.     

A rational Arnoldi process with applications

The rational Arnoldi process is a popular method for the computation of a few eigenvalues of a large non‐Hermitian matrix and for the approximation of matrix functions. The method is particularly attractive when the rational functions that determine the process have only few distinct poles , because then few factorizations of matrices of the form A ? z_jI have to be computed. We discuss recursion relations for orthogonal bases of rational Krylov subspaces determined by rational functions with few distinct poles. These recursion formulas yield a new implementation of the rational Arnoldi process. Applications of the rational Arnoldi process to the approximation of matrix functions as well as to the computation of eigenvalues and pseudospectra of A are described. The new implementation is compared to several available implementations.     

Bounds on the k-th generalized base of a primitive sign pattern matrix

You et al. [L. You, J. Shao, and H. Shan, Bounds on the bases of irreducible generalized sign pattern matrices, Lin. Alg. Appl. 427 (2007), pp. 285–300] extended the concept of the base of a powerful sign pattern matrix to the nonpowerful, irreducible sign pattern matrices. The key to their generalization was to view the relationship A ^l =A ^l?+?p as an equality of generalized sign patterns rather than of sign patterns. You, Shao and Shan showed that for primitive generalized sign patterns, the base is the smallest positive integer k such that all entries of A ^k are ambiguous. In this paper we study the k-th generalized base for nonpowerful primitive sign pattern matrices. For a primitive, nonpowerful sign pattern A, this is the smallest positive integer h such that A^k has h rows consisting entirely of ambiguous entries. Extending the work of You, Shao and Shan, we obtain sharp upper bounds on the k-th generalized base, together with a complete characterization of the equality cases for those bounds. We also show that there exist gaps in the k-th generalized base set of the classes of such matrices.     

Factorizations of complete multipartite graphs into generalized cubes

For a positive integer d, the usual d‐dimensional cube Q_d is defined to be the graph (K₂)^d, the Cartesian product of d copies of K₂. We define the generalized cube Q(K_k, d) to be the graph (K_k)^d for positive integers d and k. We investigate the decomposition of the complete multipartite graph K into factors that are vertex‐disjoint unions of generalized cubes Q(K_k, d_i), where k is a power of a prime, n and j are positive integers with j ≤ n, and the d_i may be different in different factors. We also use these results to partially settle a problem of Kotzig on Q_d‐factorizations of K_n. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 144–150, 2000