M-matrix

In mathematics, especially linear algebra, an M-matrix is a matrix whose off-diagonal entries are less than or equal to zero (i.e., it is a Z-matrix) and whose eigenvalues have nonnegative real parts. The set of non-singular M-matrices are a subset of the class of P-matrices, and also of the class of inverse-positive matrices (i.e. matrices with inverses belonging to the class of positive matrices).^[1] The name M-matrix was seemingly originally chosen by Alexander Ostrowski in reference to Hermann Minkowski, who proved that if a Z-matrix has all of its row sums positive, then the determinant of that matrix is positive.^[2]

Characterizations

An M-matrix is commonly defined as follows:

Definition: Let A be a n × n real Z-matrix. That is, A = (a_ij) where a_ij ≤ 0 for all i ≠ j, 1 ≤ i,j ≤ n. Then matrix A is also an M-matrix if it can be expressed in the form A = sI − B, where B = (b_ij) with b_ij ≥ 0, for all 1 ≤ i,j ≤ n, where s is at least as large as the maximum of the moduli of the eigenvalues of B, and I is an identity matrix.

For the non-singularity of A, according to the Perron–Frobenius theorem, it must be the case that s > ρ(B). Also, for a non-singular M-matrix, the diagonal elements a_ii of A must be positive. Here we will further characterize only the class of non-singular M-matrices.

Many statements that are equivalent to this definition of non-singular M-matrices are known, and any one of these statements can serve as a starting definition of a non-singular M-matrix.^[3] For example, Plemmons lists 40 such equivalences.^[4] These characterizations has been categorized by Plemmons in terms of their relations to the properties of: (1) positivity of principal minors, (2) inverse-positivity and splittings, (3) stability, and (4) semipositivity and diagonal dominance. It makes sense to categorize the properties in this way because the statements within a particular group are related to each other even when matrix A is an arbitrary matrix, and not necessarily a Z-matrix. Here we mention a few characterizations from each category.

Properties

Below, ≥ denotes the element-wise order (not the usual positive semidefinite order on matrices). That is, for any real matrices A, B of size m × n, we write A ≥ B (or A > B) if a_ij ≥ b_ij (or a_ij > b_ij) for all i, j.

Let A be a n × n real Z-matrix, then the following statements are equivalent to A being a non-singular M-matrix:

Positivity of principal minors

• All the principal minors of A are positive. That is, the determinant of each submatrix of A obtained by deleting a set, possibly empty, of corresponding rows and columns of A is positive.
• A + D is non-singular for each nonnegative diagonal matrix D.
• Every real eigenvalue of A is positive.
• All the leading principal minors of A are positive.
• There exist lower and upper triangular matrices L and U respectively, with positive diagonals, such that A = LU.

Inverse-positivity and splittings

• A is inverse-positive. That is, A⁻¹ exists and A⁻¹ ≥ 0.
• A is monotone. That is, Ax ≥ 0 implies x ≥ 0.
• A has a convergent regular splitting. That is, A has a representation A = M − N, where M⁻¹ ≥ 0, N ≥ 0 with M⁻¹N convergent. That is, ρ(M⁻¹N) < 1.
• There exist inverse-positive matrices M₁ and M₂ with M₁ ≤ A ≤ M₂.
• Every regular splitting of A is convergent.

Stability

• There exists a positive diagonal matrix D such that AD + DA^T is positive definite.
• A is positive stable. That is, the real part of each eigenvalue of A is positive.
• There exists a symmetric positive definite matrix W such that AW + WA^T is positive definite.
• A + I is non-singular, and G = (A + I)⁻¹(A − I) is convergent.
• A + I is non-singular, and for G = (A + I)⁻¹(A − I), there exists a positive definite symmetric matrix W such that W − G^TWG is positive definite.

Semipositivity and diagonal dominance

• A is semi-positive. That is, there exists x > 0 with Ax > 0.
• There exists x ≥ 0 with Ax > 0.
• There exists a positive diagonal matrix D such that AD has all positive row sums.
• A has all positive diagonal elements, and there exists a positive diagonal matrix D such that AD is strictly diagonally dominant.
• A has all positive diagonal elements, and there exists a positive diagonal matrix D such that D⁻¹AD is strictly diagonally dominant.

Applications

The primary contributions to M-matrix theory has mainly come from mathematicians and economists. M-matrices are used in mathematics to establish bounds on eigenvalues and on the establishment of convergence criteria for iterative methods for the solution of large sparse systems of linear equations. M-matrices arise naturally in some discretizations of differential operators, such as the Laplacian, and as such are well-studied in scientific computing. M-matrices also occur in the study of solutions to linear complementarity problem. Linear complementarity problems arise in linear and quadratic programming, computational mechanics, and in the problem of finding equilibrium point of a bimatrix game. Lastly, M-matrices occur in the study of finite Markov chains in the field of probability theory and operations research like queuing theory. Meanwhile, economists have studied M-matrices in connection with gross substitutability, stability of a general equilibrium and Leontief's input–output analysis in economic systems. The condition of positivity of all principal minors is also known as the Hawkins–Simon condition in economic literature.^[5] In engineering, M-matrices also occur in the problems of Lyapunov stability and feedback control in control theory and are related to Hurwitz matrices. In computational biology, M-matrices occur in the study of population dynamics.

See also

• A is a non-singular weakly diagonally dominant M-matrix if and only if it is a weakly chained diagonally dominant L-matrix.
• If A is an M-matrix, then −A is a Metzler matrix.
• A non-singular symmetric M-matrix is sometimes called a Stieltjes matrix.
• Hurwitz-stable matrix
• P-matrix
• Perron–Frobenius theorem
• Z-matrix
• H-matrix

References

1. Fujimoto, Takao & Ranade, Ravindra (2004), "Two Characterizations of Inverse-Positive Matrices: The Hawkins-Simon Condition and the Le Chatelier-Braun Principle" (PDF), Electronic Journal of Linear Algebra, 11: 59–65.
2. Bermon, Abraham; Plemmons, Robert J. (1994), Nonnegative Matrices in the Mathematical Sciences, Philadelphia: Society for Industrial and Applied Mathematics, p. 134,161 (Thm. 2.3 and Note 6.1 of chapter 6), ISBN 0-89871-321-8.
3. Fiedler, M; Ptak, V. (1962), "On matrices with non-positive off-diagonal elements and positive principal minors", Czechoslovak Mathematical Journal, 12 (3): 382–400, doi:10.21136/CMJ.1962.100526.
4. Plemmons, R.J. (1977), "M-Matrix Characterizations. I -- Nonsingular M-Matrices", Linear Algebra and its Applications, 18 (2): 175–188, doi:10.1016/0024-3795(77)90073-8.
5. Nikaido, H. (1970). Introduction to Sets and Mappings in Modern Economics. New York: Elsevier. pp. 13–19. ISBN 0-444-10038-5.