Linear recurrence relations in the algebra of matrices and applications

We study here some linear recurrence relations in the algebra of square matrices. With the aid of the Cayley–Hamilton Theorem, we derive some explicit formulas for Aⁿ (nr) and e^tA for every r×r matrix A, in terms of the coefficients of its characteristic polynomial and matrices A^j, where 0jr−1.     

Nonchordal positive semidefinite stochastic matrices

Let K_nbe the convex set of n×npositive semidefinite doubly stochastic matrices. If Aε k_n, the graph of A,G(A), is the graph on n vertices with (i,j) an edge if a_ij ≠ 0i≠ j. We are concerned with the extreme points in K_n. In many cases, the rank of Aand G(A) are enough to determine whether A is extreme in K_n. This is true, in particular, if G(A)is a special kind of nonchordal graph, i.e., if no two cycles in G(A)have a common edge.     

Direct fail-proof triangularization algorithms for AX + XB = C with Error-Free and parallel implementations

Two 0(mn³) inversion-free direct algorithms to compute a solution of the linear system AX +XB = C by triangularizing a Hessenberg matrix are presented. Without any loss of generality the matrix A is assumed upper Hessenberg and the order m of A the order n of B. The algorithms have an in-built consistency check, are capable of pruning redundant rows and converting the resulting matrix into a full row rank matrix, and permit A and —B to be any square matrices with common or distinct eigenvalues. In addition, these algorithms can also solve the homogeneous system AX +XB = 0 (null matrix C). An error-free implementation of the solution X using multiple modulus residue arithmetic as well as a parallelization of the algorithms is discussed.     

Doubly stochastic matrices whose powers eventually stop

In this note we characterize doubly stochastic matrices A whose powers A,A²,A³,… eventually stop, i.e., A^p=A^p+1= for some positive integer p. The characterization enables us to determine the set of all such matrices.     

Hypernormal matrices

An nxn matrix A is hypernormal if APA^*=A^*PA for all permutation matrices P. We shall explain how to construct hypernormal matrices.     

Conditions for the positivity of determinants

Consider a matrix with positive diagonal entries, which is similar via a positive diagonal matrix to a symmetric matrix, and whose signed directed graph has the property that if a cycle and its symmetrically placed complement have the same sign, then they are both positive. We provide sufficient conditions so that A be a P-matrix, that is , a matrix whose principal minors are all positive. We further provide sufficiet conditions for an arbitrary matrix A whose (undirected) graph is subordinate to a tree, to be a P-matrix. If, in additionA is sign symmetric and its undirected graph is a tree, we obtain necessary and sufficient conditions that it be a P-matrix. We go on to consider the positive semi-definiteness of symmetric matrices whose graphs are subordinate to a given tree and discuss the convexity of the set of all such matrices.     

A note on compact graphs

An undirected simple graph G is called compact iff its adjacency matrix A is such that the polytope S(A) of doubly stochastic matrices X which commute with A has integral-valued extremal points only. We show that the isomorphism problem for compact graphs is polynomial. Furthermore, we prove that if a graph G is compact, then a certain naive polynomial heuristic applied to G and any partner G′ decides correctly whether G and G′ are isomorphic or not. In the last section we discuss some compactness preserving operations on graphs.     

Convex sets of nonsingular and P:-Matrices

We show that the set r(A,B) (resp. c(A,B) of square matrices whose rows (resp. columns) are the independent convex combinations of the rows (resp.columns) of real matrices A and B consists entirely of nonsingular matrices if and only if BA^-1(resp. B^-1A) is a P-matrix. This imrpoves a theorem on P-Matrices proven in [2] and [3], in the context of interval nonsingularity. We also show that every real P-matrix admits a representation BA^-1 with the above property. These reseults are only partially true for complex P-matrices. Based on them we obtain a characterizaiton of complex P-matrices in terms of block partitions.     

Alternative proofs of a theorem of Moyls and Marcus on the numerical range of a square matrix

Moyls and Marcus [4] showed that for n≤4,n×n an complex matrix A is normal if and only if the numerical range of A is the convex hull of the eigenvalues of A. When n≥5, there exist matrices which are not normal, but such that the numerical range is still the convex hull of the eigenvalues. Two alternative proofs of this fact are given. One proof uses the known structure of the numerical range of a 2×2 matrix. The other relies on a theorem of Motzkin and Taussky stating that a pair of Hermitian matrices with property L must commute.     

The numerical range of certain 0,1-matrices

Let A be a 0, 1-matrix with at most one 1 in each row and column. The authors prove that the numerical range of A is the convex hull of a polygon and a circular disk, both centered at the origin and contained in the unit disk. The proof uses a permutation similarity to reduce A to a direct sum of matrices whose numerical ranges can be determined. A computer program, developed by the authors, which plots the boundary of the numerical range of an arbitrary complex matrix is also discussed.     

Ranks of Solutions of the Matrix Equation AXB = C

The purpose of this article is to solve two problems related to solutions of a consistent complex matrix equation AXB = C : (I) the maximal and minimal ranks of solution to AXB = C , and (II) the maximal and minimal ranks of two real matrices X₀ and X₁ in solution X = X₀ + iX₁ to AXB = C . As applications, the maximal and minimal ranks of two real matrices C and D in generalized inverse (A + iB)^- = C + iD of a complex matrix A + iB are also examined.     

The growth of laguerre matrix polynomials on bounded intervals

Let A be a matrix in ^r×r such that Re(z) > −1/2 for all the eigenvalues of A and let {π_n^(A,1/2) (x)} be the normalized sequence of Laguerre matrix polynomials associated with A. In this paper, it is proved that π_n^(A,1/2) (x) = O(n^(A)/2ln^r−1(n)) and π_n+1^(A,1/2) (x) − π_n^(A,1/2) (x) = O(n^((A)−1)/2ln^r−1(n)) uniformly on bounded intervals, where (A) = max{Re(z); z eigenvalue of A}.     

Group inverse and group involutory Matrices

In this work we deal with group involutory matrices, i.e.A^#=A. We give necessary and sufficient conditions to characterize these matrices in terms of different representations of the group inverse. First, we give different expressions of the group inverse of a square matrix A. In addition, the special case of integer matrices is considered.     

Linear operators preserving unitary t-congruence (orthogonal similarity) on complex (real) matrices

Two complex (real) square matrices A and B are said io be unitarily t-congruent (orthogonally similar) it there exists a unitary (an orthogonal) matrix U such that A=UBU¹ We characterize those linear operators that preserve unitary t-congruence on complex matrices and those linear operators that preserve orthogonal similarity on real matrices. This answers a question raised in a paper by Y. P. Hong, R. A. Horn and the first author.     

On matrices stochastically similar to matrices with equal diagonal elements

A necessary and sufficient condition for a matrix to be stochastically similar to a matrix with equal diagonal elements is obtained Aand B are called Stochastically similar if B=SAS^{- 1} where S is quasi-stochastic i.e., all row sums of .S are I. An inverse elementary divisor problem for quasi-stochastic matrices is also considered.     

Complementarity forms of theorems of Lyapunov and Stein, and related results

The well-known Lyapunov's theorem in matrix theory / continuous dynamical systems asserts that a (complex) square matrix A is positive stable (i.e., all eigenvalues lie in the open right-half plane) if and only if there exists a positive definite matrix X such that AX+XA^* is positive definite. In this paper, we prove a complementarity form of this theorem: A is positive stable if and only if for any Hermitian matrix Q, there exists a positive semidefinite matrix X such that AX+XA^*+Q is positive semidefinite and X[AX+XA^*+Q]=0. By considering cone complementarity problems corresponding to linear transformations of the form I−S, we show that a (complex) matrix A has all eigenvalues in the open unit disk of the complex plane if and only if for every Hermitian matrix Q, there exists a positive semidefinite matrix X such that X−AXA^*+Q is positive semidefinite and X[X−AXA^*+Q]=0. By specializing Q (to −I), we deduce the well known Stein's theorem in discrete linear dynamical systems: A has all eigenvalues in the open unit disk if and only if there exists a positive definite matrix X such that X−AXA^* is positive definite.     

On the inertia of the Lyapunov transform AH+HA* for H >0

Given an arbitrary n×n matrix A with complex entries, we characterize all inertia triples (abc) that are attained by the Lyapunov transform AH+ HA^*, as H varies over the set of all n× n positive definite matrices.     

On poset similarity

Let P be a poset, and let A be an element of its strict incidence algebra. Saks (SIAM J. Algebraic Discrete Methods 1 (1980) 211–215; Discrete Math. 59 (1986) 135–166) and Gansner (SIAM J. Algebraic Discrete Methods 2 (1981) 429–440) proved that the kth Dilworth number of P is less than or equal to the dimension of the nullspace of A^k, and that there is some member of the strict incidence algebra of P for which equality is attained (for all k simultaneously). In this paper we focus attention on the question of when equality is attained with the strict zeta matrix, and proceed under a particular random poset model. We provide an invariant depending only on two measures of nonunimodality of the level structure for the poset that, with probability tending to 1 as the smallest level tends to infinity, takes on the same value as the inequality gap between the width of P and the dimension of the nullspace of its strict zeta matrix. In particular, we characterize the level structures for which the width of P is, with probability tending to 1, equal to the dimension of the nullspace of its strict zeta matrix. As a consequence, by the Kleitman–Rothschild Theorem 5, almost all posets in the Uniform random poset model have width equal to the dimension of the nullspace of their zeta matrices. We hope this is a first step toward a complete characterization of when equality holds in Saks’ and Gansner's inequality for the strict zeta matrix and for all k. New to this paper are also the canonical representatives of the poset similarity classes (where two posets are said to be similar if their strict zeta matrices are similar in the matrix-theoretic sense), and these form the setting for our work on Saks’ and Gansner's inequalities. (Also new are two functions that measure the nonunimodality of a sequence of real numbers.)