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.     

A Recursive Test for P-Matrices

The time complexity for testing whether an n-by-n real matrix is a P-matrix is reduced from O(2ⁿ n ³) to O(2 ⁿ ) by applying recursively a criterion for P-matrices based on Schur complementation. A Matlab program implementing the associated algorithm is provided.     

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 fast method to block-diagonalize a Hankel matrix

In this paper, we consider an approximate block diagonalization algorithm of an n×n real Hankel matrix in which the successive transformation matrices are upper triangular Toeplitz matrices, and propose a new fast approach to compute the factorization in O(n ²) operations. This method consists on using the revised Bini method (Lin et al., Theor Comp Sci 315: 511–523, 2004). To motivate our approach, we also propose an approximate factorization variant of the customary fast method based on Schur complementation adapted to the n×n real Hankel matrix. All algorithms have been implemented in Matlab and numerical results are included to illustrate the effectiveness of our approach.     

On Certain Positivity Classes of Operators

A real square matrix A is called a P-matrix if all its principal minors are positive. Such a matrix can be characterized by the sign non-reversal property. Taking a cue from this, the notion of a P-operator is extended to infinite dimensional spaces as the first objective. Relationships between invertibility of some subsets of intervals of operators and certain P-operators are then established. These generalize the corresponding results in the matrix case. The inheritance of the property of a P-operator by the Schur complement and the principal pivot transform is also proved. If A is an invertible M-matrix, then there is a positive vector whose image under A is also positive. As the second goal, this and another result on intervals of M-matrices are generalized to operators over Banach spaces. Towards the third objective, the concept of a Q-operator is proposed, generalizing the well known Q-matrix property. An important result, which establishes connections between Q-operators and invertible M-operators, is proved for Hilbert space operators.     

Lanczos,Householder transformations,and implicit deflation for fast and reliable dominant singular subspace computation

Many applications, such as subspace‐based models in information retrieval and signal processing, require the computation of singular subspaces associated with the k dominant, or largest, singular values of an m×n data matrix A, where k?min(m,n). Frequently, A is sparse or structured, which usually means matrix–vector multiplications involving A and its transpose can be done with much less than ??(mn) flops, and A and its transpose can be stored with much less than ??(mn) storage locations. Many Lanczos‐based algorithms have been proposed through the years because the underlying Lanczos method only accesses A and its transpose through matrix–vector multiplications. We implement a new algorithm, called KSVD, in the Matlab environment for computing approximations to the singular subspaces associated with the k dominant singular values of a real or complex matrix A. KSVD is based upon the Lanczos tridiagonalization method, the WY representation for storing products of Householder transformations, implicit deflation, and the QR factorization. Our Matlab simulations suggest it is a fast and reliable strategy for handling troublesome singular‐value spectra. Copyright © 2001 John Wiley & Sons, Ltd.     

The inverse problem of bisymmetric matrices with a submatrix constraint

An n×n real matrix A is called a bisymmetric matrix if A=A^T and A=S_nAS_n, where S_n is an n×n reverse unit matrix. This paper is mainly concerned with solving the following two problems: Problem I Given n×m real matrices X and B, and an r×r real symmetric matrix A₀, find an n×n bisymmetric matrix A such that where A([1: r]) is a r×r leading principal submatrix of the matrix A. Problem II Given an n×n real matrix A^*, find an n×n matrix  in S_E such that where ∥·∥ is Frobenius norm, and S_E is the solution set of Problem I. The necessary and sufficient conditions for the existence of and the expressions for the general solutions of Problem I are given. The explicit solution, a numerical algorithm and a numerical example to Problem II are provided. Copyright © 2003 John Wiley & Sons, Ltd.     

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

Finite criteria for conditional definiteness of quadratic forms

A real symmetric n × n matrix Q is A-conditionally positivesemidefinite, where A is a given m × n matrix, if x′Qx?0 whenever Ax?0, and is A-conditionally positive definite if strict inequality holds except when x=0. When A is the identity matrix these notions reduce to the well-studied notions of copositivity and strict copositivity respectively. This paper presents finite criteria, involving only the solution of sets of linear equations constructed from the matrices Q,A, for testing both types of conditional definiteness. These criteria generalize known facts about copositive matrices and, when Q is invertible and all row submatrices of A have maximal rank, can be very elegantly stated in terms of Schur complements of the matrix AQ^-1A′.     

Linear algorithms for testing the sign stability of a matrix and for findingZ-maximum matchings in acyclic graphs

Summary Ann×n real matrixA=(a _ij ) isstable if each eigenvalue has negative real part, andsign stable (orqualitatively stable) if each matrix B with the same sign-pattern asA is stable, regardless of the magnitudes ofB's entries. Sign stability is of special interest whenA is associated with certain models from ecology or economics in which the actual magnitudes of thea _ij may be very difficult to determine. Using a characterization due to Quirk and Ruppert, and to Jeffries, an efficient algorithm is developed for testing the sign stability ofA. Its time-and-space-complexity are both 0(n ²), and whenA is properly presented that is reduced to 0(max{n, number of nonzero entries ofA}). Part of the algorithm involves maximum matchings, and that subject is treated for its own sake in two final sections.     

Error-free matrix symmetrizers and equivalent symmetric matrices

A symmetrizer of the matrix A is a symmetric solution X that satisfies the matrix equation XA=AX. An exact matrix symmetrizer is computed by obtaining a general algorithm and superimposing a modified multiple modulus residue arithmetic on this algorithm. A procedure based on computing a symmetrizer to obtain a symmetric matrix, called here an equivalent symmetric matrix, whose eigenvalues are the same as those of a given real nonsymmetric matrix is presented.Supported by CSIR.     

On latently real matrices and block quaternions

Let a complex n × n matrix A be unitarily similar to its entrywise conjugate matrix [`(A)] \bar{A} . If in the relation [`(A)] = P^*AP \bar{A} = {P^*}AP the unitary matrix P can be chosen symmetric (skew-symmetric), then A is called a latently real matrix (respectively, a generalized block quaternion). The differences in the systems of elementary divisors of these two matrix classes are found that explain why latently real matrices can be made real via unitary similarities, whereas, in general, block quaternions cannot. Bibliography: 5 titles.     

A fast solver for linear systems with displacement structure

We describe a fast solver for linear systems with reconstructible Cauchy-like structure, which requires O(rn ²) floating point operations and O(rn) memory locations, where n is the size of the matrix and r its displacement rank. The solver is based on the application of the generalized Schur algorithm to a suitable augmented matrix, under some assumptions on the knots of the Cauchy-like matrix. It includes various pivoting strategies, already discussed in the literature, and a new algorithm, which only requires reconstructibility. We have developed a software package, written in Matlab and C-MEX, which provides a robust implementation of the above method. Our package also includes solvers for Toeplitz(+Hankel)-like and Vandermonde-like linear systems, as these structures can be reduced to Cauchy-like by fast and stable transforms. Numerical experiments demonstrate the effectiveness of the software.     

On Some Properties of Convex Matrix Sets Characterized by P -Matrices and Block P -Matrices

In this paper, we consider convex sets of real matrices and establish criteria characterizing these sets with respect to certain matrix properties of their elements. In particular, we deal with convex sets of P-matrices, block P-matrices and M-matrices, nonsingular and full rank matrices, as well as stable and Schur stable matrices. Our results are essentially based on the notion of a block P-matrix and extend and generalize some recently published results on this topic.     

When does the inverse have the same sign pattern as the transpose?

By a sign pattern (matrix) we mean an array whose entries are from the set {+, –, 0}. The sign patterns A for which every real matrix with sign pattern A has the property that its inverse has sign pattern A ^T are characterized. Sign patterns A for which some real matrix with sign pattern A has that property are investigated. Some fundamental results as well as constructions concerning such sign pattern matrices are provided. The relation between these sign patterns and the sign patterns of orthogonal matrices is examined.     

Carathéodory - Fejér Problem for Pairs of Meromorphic Functions

We continue our study of families of pairs of matrix-valued meromorphic functions P(ρ,P) depending on two parameters p and P introduced in [2]. These include as special cases the projective Schur, Nevanlinna and Carathéodory classes. A two sided Carathéodory Fejér interpolation problem is defined and solved in P(ρ,P), using the fundamental matrix inequality method. A corresponding Schur algorithm is studied. Finally we also consider the case of functions (as opposed to pairs).     

On sufficient conditions for the existence of a unitary congruence transformation of a given complex matrix into a real one

A complex n × n matrix A is said to be nonderogatory if the degree of its minimal polynomial is equal to the degree of the characteristic polynomial. The aim of the paper is to prove the following assertion: Let A[`(A)] A\bar{A} be a nonderogatory matrix with real positive spectrum. Then A can be made real by a unitary congruence transformation if and only if A and [`(A)] \bar{A} are unitarily congruent. Bibliography: 5 titles.