M-matrix

{{Short description|Matrix in mathematics}} 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 |first1=Takao |last1=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 |doi=10.13001/1081-3810.1122 |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 |first1=Abraham |last1=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_ij'')}} where {{math|1=''a_ij'' ≤ 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_ij'')}} with {{math|1=''b_ij'' ≥ 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_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.<ref>{{Citation |first1=M |last1=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 |hdl=10338.dmlcz/100526 |hdl-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.

==Properties== 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''_''ij'' ≥ ''b''_''ij'' (or ''a''_''ij'' > ''b''_''ij'') }} 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 [[Triangular matrix|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''⁻¹}} exists and {{math|1=''A''⁻¹ ≥ 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''⁻¹ ≥ 0, ''N'' ≥ 0}} with {{math|1=''M''⁻¹''N''}} ''convergent''. That is, {{math|1=''ρ''(''M''⁻¹''N'') < 1}}. * There exist inverse-positive matrices {{math|1=''M''₁}} and {{math|1=''M''₂}} with {{math|1=''M''₁ ≤ ''A'' ≤ ''M''₂}}. * Every regular splitting of ''A'' is convergent.

''Stability'' * There exists a positive diagonal matrix ''D'' such that {{math|1=''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 {{math|1=''AW'' + ''WA^T''}} is positive definite. * {{math|1=''A'' + ''I''}} is non-singular, and {{math|1=''G'' = (''A'' + ''I'')⁻¹(''A'' − ''I'')}} is convergent. * {{math|1=''A'' + ''I''}} is non-singular, and for {{math|1=''G'' = (''A'' + ''I'')⁻¹(''A'' − ''I'')}}, there exists a positive definite symmetric matrix ''W'' such that {{math|''W'' − ''G^TWG''}} 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''⁻¹''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-stable 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]]. * [[Translation_(geometry)#Matrix_representation|Translation matrix]] * [[Hurwitz-stable matrix]] * [[P-matrix]] * [[Perron–Frobenius theorem]] * [[Z-matrix (mathematics)|Z-matrix]] * [[H-matrix (iterative method)|H-matrix]]

== References == <references/>

[[Category:Matrices (mathematics)]]