View source for 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 (mathematics)|''Z''-matrix]]) and whose [[eigenvalue]]s have nonnegative [[Complex number#Notation|real parts]]. The set of non-singular ''M''-matrices are a subset of the class of [[P-matrix|''P''-matrices]], and also of the class of [[inverse-positive matrix|inverse-positive matrices]] (i.e. matrices with inverses belonging to the class of [[Nonnegative matrix|positive matrices]]).<ref>{{Citation |first=Takao |last=Fujimoto |name-list-style=amp |first2=Ravindra |last2=Ranade |title=Two Characterizations of Inverse-Positive Matrices: The Hawkins-Simon Condition and the Le Chatelier-Braun Principle |journal=Electronic Journal of Linear Algebra |volume=11 |pages=59–65 |year=2004 |url=http://www.emis.de/journals/ELA/ela-articles/articles/vol11_pp59-65.pdf }}.</ref> 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.<ref name="Berman">{{Citation |first=Abraham |last=Bermon |authorlink2=Robert J. Plemmons |first2=Robert J. |last2=Plemmons |title=Nonnegative Matrices in the Mathematical Sciences |location=Philadelphia |publisher=Society for Industrial and Applied Mathematics |year=1994 |page=134,161 (Thm. 2.3 and Note 6.1 of chapter 6) |isbn=0-89871-321-8 }}.</ref>

== Characterizations ==
An M-matrix is commonly defined as follows:

'''Definition:''' Let {{math|1=''A''}} be a {{math|''n'' × ''n''}} real [[Z-matrix (mathematics)|Z-matrix]]. That is, {{math|1=''A''&nbsp;=&nbsp;(''a<sub>ij</sub>'')}} where {{math|1=''a<sub>ij</sub>'' ≤ 0}} for all {{math|1=''i'' ≠ ''j'', 1 ≤ ''i,j'' ≤ ''n''}}. Then matrix ''A'' is also an ''M-matrix'' if it can be expressed in the form {{math|1=''A'' = ''sI'' − ''B''}}, where {{math|1=''B''&nbsp;=&nbsp;(''b<sub>ij</sub>'')}} with {{math|1=''b<sub>ij</sub>'' ≥ 0}}, for all {{math|1=1 ≤ ''i,j'' ≤ n}}, where {{math|1=''s''}} is at least as large as the maximum of the moduli of the eigenvalues of {{math|1=''B''}}, and {{math|1=''I''}} is an identity matrix.

For the [[non-singularity]] of {{math|1=''A''}}, according to the [[Perron–Frobenius theorem]], it must be the case that {{math|1=''s'' > ''ρ''(''B'')}}. Also, for a non-singular M-matrix, the diagonal elements {{math|1=''a<sub>ii</sub>''}} 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.<ref>{{Citation |first=M |last=Fiedler |first2=V. |last2=Ptak |title=On matrices with non-positive off-diagonal elements and positive principal minors |journal=Czechoslovak Mathematical Journal |volume=12 |issue=3 |pages=382–400 |year=1962 | doi = 10.21136/CMJ.1962.100526|doi-access=free }}.</ref> For example, Plemmons lists 40 such equivalences.<ref>{{Citation |first=R.J. |last=Plemmons |title=M-Matrix Characterizations. I -- Nonsingular M-Matrices |journal=Linear Algebra and its Applications |volume=18 |issue=2 |pages=175–188 |year=1977 |doi=10.1016/0024-3795(77)90073-8|doi-access=free }}.</ref> 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 {{math|1=''A''}} is an arbitrary matrix, and not necessarily a Z-matrix. Here we mention a few characterizations from each category.

==Equivalences==
Below, {{math|1= ≥ }} denotes the element-wise order (not the usual [[positive semidefinite matrix|positive semidefinite]] order on matrices). That is, for any real matrices ''A'', ''B'' of size {{math|1=''m'' × ''n''}}, we write {{math|1=''A'' ≥ ''B'' (or ''A'' > ''B'')}} if {{math|1= ''a''<sub>''ij''</sub> ≥ ''b''<sub>''ij''</sub> (or ''a''<sub>''ij''</sub> > ''b''<sub>''ij''</sub>) }} for all {{math|1=''i'', ''j''}}.

Let ''A'' be a {{math|1=''n'' × ''n''}} real [[Z-matrix (mathematics)|Z-matrix]], then the following statements are equivalent to ''A'' being a [[Algebraic curve#Singularities|non-singular]] M-matrix:

''Positivity of principal minors''
* All the [[minor (linear algebra)|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.
* {{math|1=''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 {{math|1=''A'' = ''LU''}}.

''Inverse-positivity and splittings''
* ''A'' is ''inverse-positive''. That is, {{math|1=''A''<sup>−1</sup>}} exists and {{math|1=''A''<sup>−1</sup> ≥ 0}}.
* ''A'' is ''monotone''. That is, {{math|1=''Ax'' ≥ 0}} implies {{math|1=''x'' ≥ 0}}.
* ''A'' has a ''convergent regular splitting''. That is, ''A'' has a representation {{math|1=''A'' = ''M'' − ''N''}}, where {{math|1=''M''<sup>−1</sup> ≥ 0, ''N'' ≥ 0}} with {{math|1=''M''<sup>−1</sup>''N''}} ''convergent''. That is, {{math|1=''ρ''(''M''<sup>−1</sup>''N'') < 1}}.
* There exist inverse-positive matrices {{math|1=''M''<sub>1</sub>}} and {{math|1=''M''<sub>2</sub>}} with {{math|1=''M''<sub>1</sub> ≤ ''A'' ≤ ''M''<sub>2</sub>}}.
* Every regular splitting of ''A'' is convergent.

''Stability''
* There exists a positive diagonal matrix ''D'' such that {{math|1=''AD'' + ''DA<sup>T</sup>''}} 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 {{math|1=''AW'' + ''WA<sup>T</sup>''}} is positive definite.
* {{math|1=''A'' + ''I''}} is non-singular, and {{math|1=''G'' = (''A'' + ''I'')<sup>−1</sup>(''A'' − ''I'')}} is convergent.
* {{math|1=''A'' + ''I''}} is non-singular, and for {{math|1=''G'' = (''A'' + ''I'')<sup>−1</sup>(''A'' − ''I'')}}, there exists a positive definite symmetric matrix ''W'' such that {{math|''W'' − ''G<sup>T</sup>WG''}} is positive definite.

''Semipositivity and diagonal dominance''
* ''A'' is ''semi-positive''. That is, there exists {{math|''x'' > 0}} with {{math|''Ax'' > 0}}.
* There exists {{math|''x'' ≥ 0}} with {{math|''Ax'' > 0}}.
* There exists a positive diagonal matrix ''D'' such that {{mvar|AD}} has all positive row sums.
* ''A'' has all positive diagonal elements, and there exists a positive diagonal matrix ''D'' such that {{mvar|AD}} is ''strictly [[diagonally dominant]]''.
* ''A'' has all positive diagonal elements, and there exists a positive diagonal matrix ''D'' such that {{math|''D''<sup>−1</sup>''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 matrix|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 programming|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 theory|general equilibrium]] and [[Input–output model|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.<ref>{{cite book |last=Nikaido |first=H. |title=Introduction to Sets and Mappings in Modern Economics |location=New York |publisher=Elsevier |year=1970 |isbn=0-444-10038-5 |pages=13–19 }}</ref> In engineering, M-matrices also occur in the problems of [[Lyapunov stability]] and [[feedback control]] in [[control theory]] and are related to [[Hurwitz matrix|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 {{math|1=−A}} is a [[Metzler matrix]].
* A non-singular symmetric ''M''-matrix is sometimes called a [[Stieltjes matrix]].
* [[Hurwitz matrix]]
* [[P-matrix]]
* [[Perron–Frobenius theorem]]
* [[Z-matrix (mathematics)|Z-matrix]]
* [[H-matrix (iterative method)|H-matrix]]

== References ==
<references/>

[[Category:Matrices]]