Factorization of symmetric singular M-matrices

Suppose A is a symmetric, singular M-matrix. A sufficient condition for A to have a triangular, singular M-matrix factorization is given, and it is shown that PAP^T always has such a factorization for a particular permutation matrix P.     

LU decomposition of M-matrices by elimination without pivoting

It is shown that if A or ?A is a singular M-matrix satisfying the generalized diagonal dominance condition y^TA?0 for some vector y? 0, then A can be factored into A = LU by a certain elimination algorithm, where L is a lower triangular M-matrix with unit diagonal and U is an upper triangular M-matrix. The existence of LU decomposition of symmetric permutations of A and for irreducible M-matrices and symmetric M-matrices follow as colollaries. This work is motivated by applications to the solution of homogeneous systems of linear equations Ax = 0, where A or ?A is an M-matrix. These applications arise, e.g., in the analysis of Markov chains, input-output economic models, and compartmental systems. A converse of the theorem metioned above can be established by considering the reduced normal form of A.     

On algebraic Riccati equations associated with M-matrices

We consider the algebraic Riccati equation for which the four coefficient matrices form an M-matrix K. When K is a nonsingular M-matrix or an irreducible singular M-matrix, the Riccati equation is known to have a minimal nonnegative solution and several efficient methods are available to find this solution. In this paper we are mainly interested in the case where K is a reducible singular M-matrix. Under a regularity assumption on the M-matrix K, we show that the Riccati equation still has a minimal nonnegative solution. We also study the properties of this particular solution and explain how the solution can be found by existing methods.     

Theorems on M-splittings of a singular M-matrix which depend on graph structure

Let $\text{A=M?Nε}\text{R}{}^{\mathrm{n\; n}}$ be a splitting. We investigate the spectral properties of the iteration matrix M^-1N by considering the relationships of the graphs of A, M, N, and M^-1N. We call a splitting an M-splitting if M is a nonsingular M-matrix and N?0. For an M-splitting of an irreducible Z-matrix A we prove that the circuit index of M^-1N is the greatest common divisor of certain sets of integers associated with the circuits of A. For M-splittings of a reducible singular M-matrix we show that the spectral radius of the iteration matrix is 1 and that its multiplicity and index are independent of the splitting. These results hold under somewhat weaker assumptions.     

Two properties of M-matrices

If A is an M-matrix with the property that some power of A is lower triangular, then A is lower triangular. An analogue of the Minkowski determinant theorem is proved for a subclass of the M-matrices.     

Nonnegativity of principal minors of generalized inverses of P0-matrices

We derive a necessary and sufficient condition under which a reflexive generalized inverse of a singular P₀-matrix is again a P₀-matrix. Simpler conditions are obtained when the rank of the matrix is n?1, where n is the order of the matrix. We then consider the application of these results to singular M-matrices of order n and rank n?1. In particular, for this case we prove that the Moore-Penrose inverse is a P₀-matrix.     

Semiconvergence of extrapolated iterative methods for singular linear systems

In this paper, we discuss convergence of the extrapolated iterative methods for solving singular linear systems. A general principle of extrapolation is presented. The semiconvergence of an extrapolated method induced by a regular splitting and a nonnegative splitting is proved whenever the coefficient matrix A is a singular M-matrix with ‘property c’ and an irreducible singular M-matrix, respectively. Since the (generalized, block) JOR and AOR methods are respectively the extrapolated methods of the (generalized, block) Jacobi and SOR methods, so the semiconvergence of the (generalized, block) JOR and AOR methods for solving general singular systems are proved. Furthermore, the semiconvergence of the extrapolated power method, the (block) JOR, AOR and SOR methods for solving Markov chains are discussed.     

Classes of general H-matrices

Let M(A) denote the comparison matrix of a square H-matrix A, that is, M(A) is an M-matrix. H-matrices such that their comparison matrices are nonsingular are well studied in the literature. In this paper, we study characterizations of H-matrices with either singular or nonsingular comparison matrices. The spectral radius of the Jacobi matrix of M(A) and the generalized diagonal dominance property are used in the characterizations. Finally, a classification of the set of general H-matrices is obtained.     

The Schur complement and the inverse M-matrix problem

It is well known that if M is a nonnegative nonsingular inverse M-matrix and if A is a nonsingular block in the upper left hand corner, then the Schur complement of A in M, (M ? A), is an inverse M-matrix. The converse of this is generally false. In this paper we give added restrictions on M or A to insure the converse, and give some necessary and sufficient conditions for HMH^?1, where H = I⊕(?I), to be an M-matrix.     

Lower bounds for the minimum eigenvalue of Hadamard product of an M-matrix and its inverse

For the Hadamard product A ° A⁻¹ of an M-matrix A and its inverse A⁻¹, we give new lower bounds for the minimum eigenvalue of A ° A⁻¹. These bounds are strong enough to prove the conjecture of Fiedler and Markham [An inequality for the Hadamard product of an M-matrix and inverse M-matrix, Linear Algebra Appl. 101 (1988) 1-8].     

M-matrix asymptotics for Sturm–Liouville problems on graphs

We consider a system formulation for Sturm–Liouville operators with formally self-adjoint boundary conditions on a graph. An M-matrix associated with the boundary value problem is defined and related to the matrix Prüfer angle associated with the system boundary value problem, and consequently with the boundary value problem on the graph. Asymptotics for the M-matrix are obtained as the eigenparameter tends to negative infinity. We show that the boundary conditions may be recovered, up to a unitary equivalence, from the M-matrix and that the M-matrix is a Herglotz function. This is the first in a series of papers devoted to the reconstruction of the Sturm–Liouville problem on a graph from its M-matrix.     

Nonnegative matrices with power invariant zero patterns

If A is a nonsingular M-matrix, the elements of the sequence {A^?k} all have the same zero pattern. Using the Drazin inverse, we show that a similar zero pattern invariance property holds for a class of matrices which is larger than the generalized M-matrices.     

On square roots of M-matrices

The question of the existence and uniqueness of an M-matrix which is a square root of an M-matrix is discussed. The results are then used to derive some new necessary and sufficient conditions for a real matrix with nonpositive off diagonal elements to be an M-matrix.     

On the first and second order derivatives of the Perron vector

In a previous work [5] the authors developed formulas for the second order partial derivatives of the Perron root as a function of the matrix entries at an essentially nonnegative and irreducible matrix. These formulas, which involve the group generalized inverse of an associated M-matrix, were used to investigate the concavity and convexity of the Perron root as a function of the entries. The authors now combine the above results together with an approach taken in an earlier joint paper [6] of the second author with L. Elsner and C. Johnson, and they develop formulas for the second order derivatives of an appropriately normalized Perron vector with respect to the matrix entries, which again are given in terms the group generalized inverse of an associated M-matrix. Convexity properties of the Perron vector as a function of the entries of the matrix are then examined. In addition, formulas for the first derivative of the Perron vector resulting from different normalizations of this eigenvector are also given. A by-product of one of these formulas yields that the group generalized inverse of a singular and irreducible M-matrix can be diagonally scaled to a matrix which is entrywise column diagonally dominant.     

Recurrence relation for biorthogonal polynomials

We use a geometric approach to obtain a recurrence relation for two families of biorthogonal polynomials associated to a nonsingular, strongly regular matrix M. We propose a “look-ahead procedure” for computing the biorthogonal polynomials when M has singular or ill-conditioned leading principal submatrices. These polynomials lead to two recursive triangular factorizations for the inverse of a nonsingular matrix M which is not necessarily strongly regular.     

On zero-pattern invariant properties of structured matrices

It is interesting that inverse M-matrices are zero-pattern (power) invariant. The main contribution of the present work is that we characterize some structured matrices that are zero-pattern (power) invariant. Consequently, we provide necessary and sufficient conditions for these structured matrices to be inverse M-matrices. In particular, to check if a given circulant or symmetric Toeplitz matrix is an inverse M-matrix, we only need to consider its pattern structure and verify that one of its principal submatrices is an inverse M-matrix.     

On inadmissibility of Hotelling T-tests for restricted alternatives

For multinormal distributions, testing against a global shift alternative, the Hotelling T²-test is uniformly most powerful invariant, and hence admissible. For testing against restricted alternatives this feature may no longer be true. It is shown that whenever the dispersion matrix is an M-matrix, Hotelling's T²-test is inadmissible, though some union-intersection tests may not be so.     

A trace inequality for M-matrices and the symmetrizability of a real matrix by a positive diagonal matrix

The question of whether a real matrix is symmetrizable via multiplication by a diagonal matrix with positive diagonal entries is reduced to the corresponding question for M-matrices and related to Hadamard products. In the process, for a nonsingular M-matrix A, it is shown that tr(A^-1A^T) ? n, with equality if and only if A is symmetric, and that the minimum eigenvalue of A^-1 ° A is ? 1 with equality in the irreducible case if and only if A is positive diagonally symmetrizable.     

Monotone convergence of Newton-like methods for M-matrix algebraic Riccati equations

For the algebraic Riccati equation whose four coefficient matrices form a nonsingular M-matrix or an irreducible singular M-matrix K, the minimal nonnegative solution can be found by Newton’s method and the doubling algorithm. When the two diagonal blocks of the matrix K have both large and small diagonal entries, the doubling algorithm often requires many more iterations than Newton’s method. In those cases, Newton’s method may be more efficient than the doubling algorithm. This has motivated us to study Newton-like methods that have higher-order convergence and are not much more expensive each iteration. We find that the Chebyshev method of order three and a two-step modified Chebyshev method of order four can be more efficient than Newton’s method. For the Riccati equation, these two Newton-like methods are actually special cases of the Newton–Shamanskii method. We show that, starting with zero initial guess or some other suitable initial guess, the sequence generated by the Newton–Shamanskii method converges monotonically to the minimal nonnegative solution.We also explain that the Newton-like methods can be used to great advantage when solving some Riccati equations involving a parameter.