M-matrix

<h2 id="characterizations">Characterizations</h2>
An M-matrix is commonly defined as follows:
Definition: Let A be a n × n real <a href="/facts/Z-matrix_(mathematics)/csw92uKY">Z-matrix</a>. That is, A = (aij) where aij ≤ 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 = (bij) with bij ≥ 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 <a href="/facts/Non-singularity/8nvkrkE9">non-singularity</a> of A, according to the <a href="/facts/Perron%25E2%2580%2593Frobenius_theorem/K9nDY7DL">Perron–Frobenius theorem</a>, it must be the case that s > ρ(B). Also, for a non-singular M-matrix, the diagonal elements aii 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.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> For example, Plemmons lists 40 such equivalences.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> 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.

<h2 id="properties">Properties</h2>
Below, ≥ denotes the element-wise order (not the usual <a href="/facts/Positive_semidefinite_matrix/Hbr6AuPS">positive semidefinite</a> order on matrices). That is, for any real matrices A, B of size m × n, we write A ≥ B (or A > B) if aij ≥ bij (or aij > bij) for all i, j.
Let A be a n × n real <a href="/facts/Z-matrix_(mathematics)/csw92uKY">Z-matrix</a>, then the following statements are equivalent to A being a <a href="/facts/Algebraic_curve/LnWsPmDP">non-singular</a> M-matrix:
Positivity of principal minors

<ul><li>All the <a href="/facts/Minor_(linear_algebra)/CMudF5Eh">principal minors</a> 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.</li>
<li>A + D is non-singular for each nonnegative diagonal matrix D.</li>
<li>Every real eigenvalue of A is positive.</li>
<li>All the leading principal minors of A are positive.</li>
<li>There exist lower and <a href="/facts/Triangular_matrix/qjXSFMM3">upper triangular</a> matrices L and U respectively, with positive diagonals, such that A = LU.</li></ul>
Inverse-positivity and splittings

<ul><li>A is inverse-positive. That is, A−1 exists and A−1 ≥ 0.</li>
<li>A is monotone. That is, Ax ≥ 0 implies x ≥ 0.</li>
<li>A has a convergent regular splitting. That is, A has a representation A = M − N, where M−1 ≥ 0, N ≥ 0 with M−1N convergent. That is, ρ(M−1N) < 1.</li>
<li>There exist inverse-positive matrices M1 and M2 with M1 ≤ A ≤ M2.</li>
<li>Every regular splitting of A is convergent.</li></ul>
Stability

<ul><li>There exists a positive diagonal matrix D such that AD + DAT is positive definite.</li>
<li>A is positive stable. That is, the real part of each eigenvalue of A is positive.</li>
<li>There exists a symmetric <a href="/facts/Positive_definite_matrix/Hbr6AuPS">positive definite matrix</a> W such that AW + WAT is positive definite.</li>
<li>A + I is non-singular, and G = (A + I)−1(A − I) is convergent.</li>
<li>A + I is non-singular, and for G = (A + I)−1(A − I), there exists a positive definite symmetric matrix W such that W − GTWG is positive definite.</li></ul>
Semipositivity and diagonal dominance

<ul><li>A is semi-positive. That is, there exists x > 0 with Ax > 0.</li>
<li>There exists x ≥ 0 with Ax > 0.</li>
<li>There exists a positive diagonal matrix D such that AD has all positive row sums.</li>
<li>A has all positive diagonal elements, and there exists a positive diagonal matrix D such that AD is strictly <a href="/facts/Diagonally_dominant/qbRQV7CV">diagonally dominant</a>.</li>
<li>A has all positive diagonal elements, and there exists a positive diagonal matrix D such that D−1AD is strictly diagonally dominant.</li></ul>
<h2 id="applications">Applications</h2>
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 <a href="/facts/Iterative_methods/uKMAJhEh">iterative methods</a> for the solution of large <a href="/facts/Sparse_matrix/FFtN0XjR">sparse</a> <a href="/facts/Systems_of_linear_equations/fk9CFdgp">systems of linear equations</a>. M-matrices arise naturally in some discretizations of <a href="/facts/Differential_operators/Nr15J0IE">differential operators</a>, such as the <a href="/facts/Laplacian/kov9u3PT">Laplacian</a>, and as such are well-studied in scientific computing. M-matrices also occur in the study of solutions to <a href="/facts/Linear_complementarity_problem/eSKsgl38">linear complementarity problem</a>. Linear complementarity problems arise in <a href="/facts/Linear_programming/GduXFQxT">linear</a> and <a href="/facts/Quadratic_programming/ct4RIUgs">quadratic programming</a>, <a href="/facts/Computational_mechanics/t8EAMTke">computational mechanics</a>, and in the problem of finding <a href="/facts/Equilibrium_point/DgbGMPkg">equilibrium point</a> of a <a href="/facts/Bimatrix_game/J0jHIycQ">bimatrix game</a>. Lastly, M-matrices occur in the study of finite <a href="/facts/Markov_chains/5oP5hntk">Markov chains</a> in the field of <a href="/facts/Probability_theory/mFBn51rE">probability theory</a> and <a href="/facts/Operations_research/H5yJkV5n">operations research</a> like <a href="/facts/Queuing_theory/8NDl56EM">queuing theory</a>. Meanwhile, economists have studied M-matrices in connection with gross substitutability, stability of a <a href="/facts/General_equilibrium_theory/WY0zX5UD">general equilibrium</a> and <a href="/facts/Input%25E2%2580%2593output_model/Wyxm5PXt">Leontief's input–output analysis</a> in economic systems. The condition of positivity of all principal minors is also known as the Hawkins–Simon condition in economic literature.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> In engineering, M-matrices also occur in the problems of <a href="/facts/Lyapunov_stability/r3je5zaQ">Lyapunov stability</a> and <a href="/facts/Feedback_control/XnuWH3zp">feedback control</a> in <a href="/facts/Control_theory/aIuERpn6">control theory</a> and are related to <a href="/facts/Hurwitz-stable_matrix/Jme6EsXz">Hurwitz matrices</a>. In <a href="/facts/Computational_biology/GxgNfwcX">computational biology</a>, M-matrices occur in the study of <a href="/facts/Population_dynamics/WXbtbncd">population dynamics</a>.

<h2 id="see-also">See also</h2>
<ul><li>A is a non-singular weakly <a href="/facts/Diagonally_dominant/qbRQV7CV">diagonally dominant</a> M-matrix if and only if it is a <a href="/facts/Weakly_chained_diagonally_dominant/hu0KdX4F">weakly chained diagonally dominant</a> <a href="/facts/L-matrix/tC6UBITU">L-matrix</a>.</li>
<li>If A is an M-matrix, then −A is a <a href="/facts/Metzler_matrix/H0no2J9b">Metzler matrix</a>.</li>
<li>A non-singular symmetric M-matrix is sometimes called a <a href="/facts/Stieltjes_matrix/fzD3ogn8">Stieltjes matrix</a>.</li>
<li><a href="/facts/Hurwitz-stable_matrix/Jme6EsXz">Hurwitz-stable matrix</a></li>
<li><a href="/facts/P-matrix/XVgLSEbf">P-matrix</a></li>
<li><a href="/facts/Perron%25E2%2580%2593Frobenius_theorem/K9nDY7DL">Perron–Frobenius theorem</a></li>
<li><a href="/facts/Z-matrix_(mathematics)/csw92uKY">Z-matrix</a></li>
<li><a href="/facts/H-matrix_(iterative_method)/pBngzcJf">H-matrix</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn: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. <a href="http://www.emis.de/journals/ELA/ela-articles/articles/vol11_pp59-65.pdf" target="_blank">http://www.emis.de/journals/ELA/ela-articles/articles/vol11_pp59-65.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn: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. <a href="0-89871-321-8" target="_blank">0-89871-321-8</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn: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. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn: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. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Nikaido, H. (1970). Introduction to Sets and Mappings in Modern Economics. New York: Elsevier. pp. 13–19. ISBN 0-444-10038-5. <a href="0-444-10038-5" target="_blank">0-444-10038-5</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
</ol>

M-matrix open-in-new

M-matrix