The inverse M-matrix problem

One aspect of the inverse M-matrix problem can be posed as follows. Given a positive n × n matrix A=(a_ij) which has been scaled to have unit diagonal elements and off-diagonal elements which satisfy 0 < y ? a_ij ? x < 1, what additional element conditions will guarantee that the inverse of A exists and is an M-matrix? That is, if A^?1=B=(b_ij), then b_ii> 0 and b_ij ? 0 for i≠_j. If n=2 or x=y no further conditions are needed, but if n ? 3 and y < x, then the following is a tight sufficient condition. Define an interpolation parameter s via x²=sy+(1?s)y²; then B is an M-matrix if s^?1 ? n?2. Moreover, if all off-diagonal elements of A have the value y except for a_ij=a_jj=x when i=n?1, n and 1 ? _j ? n?2, then the condition on both necessary and sufficient for B to be an M-matrix.     

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.     

An index classification of M-matrices

An M-matrix as defined by Ostrowski [5] is a matrix that can be split into A = sI ? B, where s > 0, B ? 0, with s ? r(B), the spectral radius of B. Following Plemmons [6], we develop a classification of all M-matrices. We consider v, the index of zero for A, i.e., the smallest nonnegative integer n such that the null spaces of Aⁿ and Aⁿ⁺¹ coincide. We characterize this index in terms of convergence properties of powers of s^?1B. We develop additional characterizations in terms of nonnegativity of the Drazin inverse of A on the range of A^v, extending (as conjectured by Poole and Boullion [7]) the well-known property that A^?1?0 whenever A is nonsingular.     

The level polynomials of the free distributive lattices

We show that there exist a set of polynomials {L_k?k = 0, 1?} such that L_k(n) is the number of elements of rank k in the free distributive lattice on n generators. L₀(n) = L₁(n) = 1 for all n and the degree of L_k is k?1 for k?1. We show that the coefficients of the L_k can be calculated using another family of polynomials, P_j. We show how to calculate L_k for k = 1,…,16 and P_j for j = 0,…,10. These calculations are enough to determine the number of elements of each rank in the free distributive lattice on 5 generators a result first obtained by Church [2]. We also calculate the asymptotic behavior of the L_k's and P_j's.     

On the inverse mean first passage matrix problem and the inverse M-matrix problem

The inverse mean first passage time problem is given a positive matrix M∈R^n,n, then when does there exist an n-state discrete-time homogeneous ergodic Markov chain C, whose mean first passage matrix is M? The inverse M-matrix problem is given a nonnegative matrix A, then when is A an inverse of an M-matrix. The main thrust of this paper is to show that the existence of a solution to one of the problems can be characterized by the existence of a solution to the other. In so doing we extend earlier results of Tetali and Fiedler.     

On a characterization of tridiagonal matrices by M. Fiedler

In this note two new proofs are given of the following characterization theorem of M. Fiedler: Let C_n, n?2, be the class of all symmetric, real matrices A of order n with the property that rank (A + D) ? n - 1 for any diagonal real matrix D. Then for any A ε C_n there exists a permutation matrix P such that PAP^T is tridiagonal and irreducible.     

A note on factorizations of singular M-matrices

Supposing that M is a singular M-matrix, we show that there exists a permutation matrix P such that PMP^T = LU, where L is a lower triangular M-matrix and U is an upper triangular singular M-matrix. An example is given to illustrate that the above result is the best possible one.     

The inverse of a matrix polynomial

An explicit representation is obtained for P(z)^?1 when P(z) is a complex n×n matrix polynomial in z whose coefficient of the highest power of z is the identity matrix. The representation is a sum of terms involving negative powers of z?λ for each λ such that P(λ) is singular. The coefficients of these terms are generated by sequences u_k, v_k of 1×n and n×1 vectors, respectively, which satisfy u₁≠0, v₁≠0, ∑^k?1_h=0(1?h!)u_k?hP^(h)(λ)=0, ∑^k?1_h=0(1?h!)P^(h)(λ)v_k?h=0, and certain orthogonality relations. In more general cases, including that when P(z) is analytic at λ but not necessarily a polynomial, the terms in the representation involving negative powers of z?λ provide the principal part of the Laurent expansion for P(z)^?1 in a punctured neighborhood of z=λ.     

A perturbation analysis of the intrinsic conditioning of an approximate null vector computed with a SVD

Let A be an m ×n real matrix with singular values σ₁ ? ··· ? σ_n?1 ? σ_n ? 0. In cases where σ_n ? 0, the corresponding right singular vector υ_n is a natural choice to use for an approximate null vector ofA. Using an elementary perturbation analysis, we show that κ = σ₁/(σ_n?1 ? σ_n) provides a quantitative measure of the intrinsic conditioning of the computation of υ_n from A.     

Strong linear preservers of rank reverse permutability on triangular matrices

Let F be a field with ∣F∣ > 2 and T_n(F) be the set of all n × n upper triangular matrices, where n ? 2. Let k ? 2 be a given integer. A k-tuple of matrices A₁, …, A_k ∈ T_n(F) is called rank reverse permutable if rank(A₁ A₂ ? A_k) = rank(A_k A_k−1 ? A₁). We characterize the linear maps on T_n(F) that strongly preserve the set of rank reverse permutable matrix k-tuples.     

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.     

Subdirect sums of P(P0)-matrices and totally nonnegative matrices

In this paper, the problem of when the sub-direct sum of two strictly diagonally dominant P-matrices is a strictly diagonally dominant P-matrix is studied. In particular, it is shown that the subdirect sum of overlapping principal submatrices of strictly diagonally dominant P-matrices is a strictly diagonally dominant P-matrix. It is also established that the 2-subdirect sum of two totally nonnegative matrices is a totally nonnegative matrix under some conditions. It is obtained that a partial totally nonnegative matrix, whose graph of the specified entries is a monotonically labeled 2-chordal graph, has a totally nonnegative completion. Finally, a positive answer to the question (IV) in Fallat and Johnson [Shaun M. Fallat, C.R. Johnson, J.R. Torregrosa, A.M. Urbano, P-matrix completions under weak symmetry assumptions, Linear Algebra Appl. 312 (2000) 73-91] is given for P₀-matrices.     

On Euclidean distance matrices

If A is a real symmetric matrix and P is an orthogonal projection onto a hyperplane, then we derive a formula for the Moore-Penrose inverse of PAP. As an application, we obtain a formula for the Moore-Penrose inverse of an Euclidean distance matrix (EDM) which generalizes formulae for the inverse of a EDM in the literature. To an invertible spherical EDM, we associate a Laplacian matrix (which we define as a positive semidefinite n × n matrix of rank n − 1 and with zero row sums) and prove some properties. Known results for distance matrices of trees are derived as special cases. In particular, we obtain a formula due to Graham and Lovász for the inverse of the distance matrix of a tree. It is shown that if D is a nonsingular EDM and L is the associated Laplacian, then D⁻¹ − L is nonsingular and has a nonnegative inverse. Finally, infinitely divisible matrices are constructed using EDMs.     

On the groups of unitriangular automorphisms of relatively free groups

We describe the structure of the group U _n of unitriangular automorphisms of the relatively free group G _n of finite rank n in an arbitrary variety C of groups. This enables us to introduce an effective concept of normal form for the elements and present U _n by using generators and defining relations. The cases n = 1, 2 are obvious: U ₁ is trivial, and U ₂ is cyclic. For n ?? 3 we prove the following: If G _n?1 is a nilpotent group then so is U _n . If G _n?1 is a nilpotent-by-finite group then U _n admits a faithful matrix representation. But if the variety C is different from the variety of all groups and G _n?1 is not nilpotent-by-finite then U _n admits no faithful matrix representation over any field. Thus, we exhaustively classify linearity for the groups of unitriangular automorphisms of finite rank relatively free groups in proper varieties of groups, which complements the results of Olshanskii on the linearity of the full automorphism groups AutG _n . Moreover, we introduce the concept of length of an automorphism of an arbitrary relatively free group G _n and estimate the length of the inverse automorphism in the case that it is unitriangular.     

Products of reflections in the general linear group over a division ring

Let F be a division ring and A?GL_n(F). We determine the smallest integer k such that A admits a factorization A=R₁R₂?R_k?1B, where R₁,…,R_k?1 are reflections and B is such that rank(B?I_n)=1. We find that, apart from two very special exceptional cases, k=rank(A?I_n). In the exceptional cases k is one larger than this rank. The first exceptional case is the matrices A of the form I_m⊕αI_n?m where n?m?2, α≠?1, and α belongs to the center of F. The second exceptional case is the matrices A satisfying (A?I_n)²=0, rank(A?I_n)?2 in the case when char F≠2 only. This result is used to determine, in the case when F is commutative, the length of a matrix A?GL_n(F) with detA=±1 with respect to the set of all reflections in GL_n(F).     

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.     

On Ochoa's special matrices in matrix classes

It is well known that the ideal classes of an order Z[μ], generated over Z by the integral algebraic number μ, are in a bijective correspondence with certain matrix classes, that is, classes of unimodularly equivalent matrices with rational integer coefficients. If the degree of μ is ?3, we construct explicitly a particularly simple ideal matrix for an ideal which is a product of different prime ideals of degree 1. We obtain the following special n×n matrix (c_ij) in the matrix class corresponding to the ideal class of our ideal: c_i+1,_i=1(i=1,…,n?2); c_ij=0(?i?n, 1?j?n? 2, and i≠j+1); c_nj=0(j)=2,…,n?1). The remaining coefficients are given as explicit polynomials in an integer z which depends on the ideal. It is shown that the matrix class of every regular ideal class of Z[μ] contains a special matrix of this kind.     

The codimension of singular matrix pairs

The singular pairs of n × n matrices [those satisfying det(A? λB)  0] form a closed set of codimension n + 1 inside the space of all matrix pairs. The same holds for singular symmetric pairs. For Hermitian pairs, the singular ones form a closed set of codimension n+ 1 orn + 2 according as n is odd or even. The irreducible components of these closed sets are determined by various basic singular summands.     

Lyapunov equations and Gram matrices

If p is a polynomial with all roots inside the unit disc and C its companion matrix, then the Lyapunov equation

$\text{X ? C}{}^1\text{XC = P}$

has a unique solution for every positive semidefinite matrix P. We characterize sets of vectors x₀,…,x_n?1 and y₀,…,y_n?1 such that X = G(x₀,…,x_n?1)= G(y₀,…, y_n?1)^-1. Geometrical connections between such bases and contractions with one- dimensional defect spaces are established.