An -matrix is a matrix of the form

Here, is the spectral radius of , that is, the largest modulus of any eigenvalue of , and denotes that has nonnegative entries. An -matrix clearly has nonpositive off-diagonal elements. It also has positive diagonal elements, which can be shown using the result that

for any consistent matrix norm:

Although the definition of an -matrix does not specify , we can set it to . Indeed let satisfy and set and . Then , since and for . Furthermore, for a nonnegative matrix the spectral radius is an eigenvalue, by the Perron–Frobenius theorem, so is an eigenvalue of and is an eigenvalue of . Hence .

The concept of -matrix was introduced by Ostrowski in 1937. -matrices arise in a variety of scientific settings, including in finite difference methods for PDEs, input-output analysis in economics, and Markov chains in stochastic processes.

An immediate consequence of the definition is that the eigenvalues of an -matrix lie in the open right-half plane, which means that -matrices are special cases of positive stable matrices. Hence an -matrix is nonsingular and the determinant, being the product of the eigenvalues, is positive. Moreover, since satisfies ,

In fact, nonnegativity of the inverse characterizes -matrices. Define

Theorem 1.A nonsingular matrix is an -matrix if and only if .

Sometimes an -matrix is *defined* to be a matrix with nonpositive off-diagonal elements and a nonnegative inverse. In fact, this condition is just one of a large number of conditions equivalent to a matrix with nonpositive off-diagonal elements being an -matrix, fifty of which are given in Berman and Plemmons (1994, Chap. 6).

It is easy to check from the definitions, or using Theorem 1, that a triangular matrix with positive diagonal and nonpositive off-diagonal is an -matrix. An example is

## Bounding the Norm of the Inverse

An -matrix can be constructed from any nonsingular triangular matrix by taking the comparison matrix. The comparison matrix associated with a general is the matrix

For a nonsingular triangular , is an -matrix, and it easy to show that

where the absolute value is taken componentwise. This bound, and weaker related bounds, can be useful for cheaply bounding the norm of the inverse of a triangular matrix. For example, with denoting the vector of ones, since is nonnegative we have

and can be computed in flops by solving a triangular system, whereas computing costs flops.

More generally, if we have an LU factorization of an -matrix then, since ,

Therefore the norm of the inverse can be computed in flops with two triangular solves, instead of the flops that would be required if were to be formed explicitly.

## Connections with Symmetric Positive Definite Matrices

There are many analogies between M-matrices and symmetric positive definite matrices. For example, every principal submatrix of a symmetric positive definite matrix is symmetric positive definite and every principal submatrix of an -matrix is an -matrix. Indeed if is a principal submatrix of a nonnegative then , which follows from for the -norm (for example). Hence on taking principal submatrices in we have with the same .

A symmetric -matrix is known as a *Stieltjes matrix*, and such a matrix is positive definite. An example of a Stieltjes matrix is minus the second difference matrix (the tridiagonal matrix arising from a central difference discretization of a second derivative), illustrated for by

## LU Factorization

Since the leading principal submatrices of an -matrix have positive determinant it follows that has an LU factorization with having positive diagonal elements. However, more is true, as the next result shows.

Theorem 2.An -matrix has an LU factorization in which and are -matrices.

Proof. We can write

The first stage of LU factorization is

where is the Schur complement of in . The first column of and the first row of are of the form required for a triangular -matrix. We have

Since it follows that . It is easy to see that , and hence Theorem shows that is an -matrix. The result follows by induction.

The question now arises of what can be said about the numerical stability of LU factorization of an -matrix. To answer it we use another characterization of -matrices, that is strictly diagonally dominant by columns for some diagonal matrix with for all , that is,

(This condition can also be written as because of the sign pattern of .) Matrices that are diagonally dominant by columns have the properties that an LU factorization without pivoting exists, the growth factor , and partial pivoting does not require row interchanges. The effect of row scaling on LU factorization is easy to see:

where is unit lower triangular, so that and are the LU factors of . It is easy to see that the growth factor bound of for a matrix diagonally dominant by columns translates into the bound

for an -matrix, which was obtained by Funderlic, Neumann, and Plemmons (1982). Unfortunately, this bound can be large. Consider the matrix

We have

so is an -matrix. The element of the LU factor of is , which means that

and this lower bound can be arbitrarily large. One can verify experimentally that numerical instability is possible when is large, in that the computed LU factors have a large relative residual. We conclude that pivoting is necessary for numerical stability in LU factorization of -matrices.

## Stationery Iterative Methods

A stationery iterative method for solving a linear system is based on a splitting with nonsingular, and has the form . This iteration converges for all starting vectors if . Much interest has focused on *regular splittings*, which are defined as ones for which and . An -matrix has the important property that for every regular splitting, and it follows that the Jacobi iteration, the Gauss-Seidel iteration, and the successive overrelaxation (SOR) iteration (with ) are all convergent for -matrices.

## Matrix Square Root

The principal square root of an -matrix is an -matrix, and it is the unique such square root. An expression for follows from :

This expression does not necessarily provide the best way to compute .

## Singular M-Matrices

The theory of -matrices extends to the case where the condition on is relaxed to in , though the theory is more complicated and extra conditions such as irreducibility are needed for some results. Singular -matrices occur in Markov chains (Berman and Plemmons, 1994, Chapter 8), for example. Let be the transition matrix of a Markov chain. Then is stochastic, that is, nonnegative with unit row sums, so . A nonnegative vector with such that is called a *stationary distribution vector* and is of interest for describing the properties of the Markov chain. To compute we can solve the singular system . Clearly, and , so is a singular -matrix.

## H-Matrices

A more general concept is that of -matrix: is an -matrix if the comparison matrix is an -matrix. Many results for -matrices extend to -matrices. For example, for an -matrix with positive diagonal elements the principal square root exists and is the unique square root that is an -matrix with positive diagonal elements. Also, the growth factor bound holds for any -matrix for which is diagonally dominant by columns.

## References

This is a minimal set of references, which contain further useful references within.

- Abraham Berman and Robert J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1994.
- R. E. Funderlic and M. Neumann and R. J. Plemmons Decompositions of Generalized Diagonally Dominant Matrices, Numer. Math. 40, 57–69, 1982.
- Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, second edition, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2002. (Chapter 8.)
- Nicholas J. Higham, Functions of Matrices: Theory and Computation, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2008. (Section 6.8.3.)

## Related Blog Posts

- What Is a Matrix Square Root? (2020)
- What Is a Symmetric Positive Definite Matrix? (2020)
- What is Numerical Stability? (2020)

This article is part of the “What Is” series, available from https://nhigham.com/category/what-is and in PDF form from the GitHub repository https://github.com/higham/what-is.

Excuse me, can you prove the inequalities for the inveres M-matrix bound, i.e |A^{-1}| \leq M(A)^{-1} ? Thanks in advance

For an M-matrix, M(A) = A so that bound is trivial. The bound always holds for triangular A, as noted above, but does not always hold in general.

Thankyou for the replies, Sir. First of all, i have already read an article about M-Matrices and H-Matrices (https://www.sciencedirect.com/science/article/abs/pii/S0024379519305087). In that article (pg 5), there is a statement :

A well known relationship between an invertible H-matrix and its comparison matrix due to Ostrowski [10] states that, for an invertible H-matrix A ∈ C^{n×n}, the inequality |A^{−1}| ≤ (M(A))^{−1} holds.

I am confused to prove this statement. Any advice?