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