M-Matrices

Stanislaw H. Żak ^{∗}

June 8, 2001

In this write-up, we summarize some basic properties of the so called M-matrices that are useful in the design of neural associative memories. For more information on the subject, we refer to Berman and Plemmons [1].

Definition 1 A real n × n matrix A is an M-matrix if all its off-diagonal elements are non-positive, that is, a_{ij} ≤ 0, i ≠ j, and all its principal minors are positive.

Note that if A is an M-matrix, then its diagonal elements are positive because its principal minors are positive.

In establishing the needed properties of the M-matrices, we use the following technical lemma due to Fiedler and Pták [2].

Lemma 1 The following properties of an arbitrary matrix A ∈ ℝ^{n×n} are equivalent:

(i) The leading principal minors of A are positive,

(ii) There exists a lower triangular matrix L ∈ ℝ^{n×n} and an upper triangular matrix U ∈ ℝ^{n×n} both with positive diagonal elements such that A = LU

Proof We first prove the implication (i)⇒(ii). The proof is by induction. Obviously the implication holds for n = 1. Suppose the statement holds for all real matrices of order n − 1.

∗School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN 47907

Represent A as:

A = [ \begin{matrix}A_{n−1} & a \\ b^{T} & a_{nn} \end{matrix} ] ,

where A_{n−1} ∈ ℝ^{(n−1)×(n−1)}, a ∈ ℝ^{(n−1)×1}, b^{T} ∈ ℝ^{1×(n−1)}, and a_{nn} ∈ ℝ. From the inductive hypothesis, the matrix A_{n−1} has positive leading principal minors, A_{n−1} = L_{n−1}U_{n−1}, where L_{n−1} ∈ ℝ^{(n−1)×(n−1)} is a lower triangular matrix with positive diagonal elements, and U_{n−1} ∈ ℝ^{(n−1)×(n−1)} is an upper triangular matrix with positive diagonal elements. Observe that

[ \begin{matrix}I_{n−1} & 0 \\ −b^{T} A_{n−1}^{−1} & 1 \end{matrix} ] A = [ \begin{matrix}A_{n−1} & a \\ 0 & a_{nn} − b^{T} A_{n−1}^{−1}a \end{matrix} ] ,

where it follows from the assumptions that det A_{n−1} > 0, and det A > 0. Hence,

0 < det A = (a_{nn} − b^{T} A_{n−1}^{−1}a) det A_{n−1}.

Thus, we have

a_{nn} − b^{T} A_{n−1}^{−1}a > 0.

Let

L = [ \begin{matrix}L_{n−1} & 0 \\ b^{T} U_{n−1}^{−1} & 1 \end{matrix} ] ,

and

U = [ \begin{matrix}U_{n−1} & L_{n−1}^{−1}a \\ 0 & a_{nn} − b^{T} A_{n−1}^{−1}a \end{matrix} ] .

One can check that

A = LU,

and that the matrices L and U satisfy (ii).

We now prove the implication (i)⇐(ii). From the generalized Cauchy’s theorem it follows that the leading principal minors of A = LU are just the products of the corresponding leading principal minors of L and U. This is because the matrix L is lower triangular while the matrix U is upper triangular. Because the diagonal elements of L and U are positive, the principal minors of A must be positive. This completes our proof of the lemma.

□

The following theorem, also due to Fiedler and Pták [2], establishes some properties of the M-matrices in terms of their LU-decomposition.

Theorem 1 Let A ∈ ℝ^{n×n} be an M-matrix. Then, there is a lower triangular matrix L ∈ ℝ^{n×n} and an upper triangular matrix U ∈ ℝ^{n×n} both with positive diagonal elements. Their off-diagonal elements are non-positive. Furthermore, both L^{−1} and U^{−1} are nonnegative which implies that A^{−1} = U^{−1}L^{−1} is non-negative.

Proof We prove this theorem by induction. The theorem holds for n = 1. Suppose the theorem holds for matrices of order n − 1. Consider the factorization from the proof of Lemma 1,

A = LU = [ \begin{matrix}L_{n−1} & 0 \\ b^{T} U_{n−1}^{−1} & 1 \end{matrix} ] [ \begin{matrix}U_{n−1} & L_{n−1}^{−1}a \\ 0 & a_{nn} − b^{T} A_{n−1}^{−1}a \end{matrix} ] ,

where L_{n−1}, U_{n−1}, L_{n−1}^{−1}, U_{n−1}^{−1} and A_{n−1}^{−1} = U_{n−1}^{−1}L_{n−1}^{−1} satisfy the inductive hypotheses. We see that l_{ij} ≤ 0 for i > j and u_{kl} ≤ 0 for k < l which means that the off-diagonal elements of L and U are non-positive. Their diagonal elements are positive. The inverse of L is

L^{−1} = [ \begin{matrix}L_{n−1}^{−1} & 0 \\ −b^{T} L_{n−1}^{−1} & 1 \end{matrix} ] .

From the inductive assumption L_{n−1}^{−1} and A_{n−1}^{−1} are non-negative and hence L_{n−1}^{−1} is nonnegative. The inverse of U is

U^{−1} = [ \begin{matrix}U_{n−1}^{−1} & −A_{n−1}^{−1} \frac{a}{a_{nn}−b^{T}A_{n−1}^{−1}a} \\ 0 & (a_{nn} − b^{T} A_{n−1}^{−1}a)^{−1} \end{matrix} ] .

From the inductive assumptions and the fact that a_{nn} − b^{T} A_{n−1}^{−1}a > 0, the matrix U^{−1} is non-negative, and the proof is complete.

□

We now consider a more general class of matrices called Z-matrices.

Definition 2 A real n × n matrix whose off-diagonal elements are non-positive is called a Z-matrix.

Note that M-matrices are Z-matrices.

In the following, we use the notation B > 0, to mean that all the elements of B are positive, where B can be a matrix or a vector. Respectively, B ≥ 0 means that all the elements of B are non-negative. We are now ready to state and prove the following theorem concerning properties of Z-matrices. The theorem can be found in Fiedler and Pták [2].

Theorem 2 Let A ∈ ℝ^{n×n} be a Z-matrix. Then, the following conditions are equivalent:

(i) There exists a vector x ≥ 0 such that Ax > 0;

(ii) There exists a vector y > 0 such that Ay > 0;

(iii) There exists a diagonal matrix D with positive diagonal elements such that ADe > 0, where e = [ 1 ⋯ 1 ]^{T} ∈ ℝ^{n};

(iv) There exists a diagonal matrix D with positive diagonal elements such that the matrix W = AD has a dominant positive main diagonal, that is, for i = 1, 2, …, n, we have

w_{ii} > ∑n_{{j=1 \atop j≠i}} w_{ij}.

Proof We prove this theorem using the following scheme:

(i) ⇒ (ii) ⇒ (iii) ⇒ (iv) ⇒ (i).

We begin with the implication (i)⇒(ii). Thus suppose that there exists a vector x ≥ 0 such that Ax > 0. Let e = [ 1 ⋯ 1 ]^{T} ∈ ℝ^{n}, ϵ > 0, and y = x + ϵe > 0. Then,

Ay = A(x + ϵe) = Ax + ϵAe > 0

for a sufficiently small ϵ > 0.

We next prove that (ii)⇒(iii). For this let y = [ y_{1} ⋯ y_{n} ]^{T} > 0 be such that Ay > 0. Let

D = [ \begin{matrix}y_{1} & 0 & 0 & ⋯ & 0 \\ 0 & y_{2} & 0 & ⋯ & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & 0 & ⋯ & y_{n} \end{matrix} ] .

It then follows that ADe = Ay > 0.

To prove (iii)⇒(iv), let D > 0 be a diagonal matrix with positive diagonal elements such that ADe > 0. We denote

AD = W = [ \begin{matrix}w_{11} & −w_{12} & ⋯ & −w_{1n} \\ −w_{21} & w_{22} & ⋯ & −w_{2n} \\ ⋮ & ⋮ & ... & ⋮ \\ −w_{n1} & −w_{n2} & ⋯ & w_{nn} \end{matrix} ] ,

where w_{ij} ≥ 0 for i ≠ j. Note that ADe = W e > 0 which is equivalent to

w_{ii} > ∑_{{j=1 \atop j≠i}}^{n} w_{ij}, i = 1, 2, …, n.

Since w_{ij} ≥ 0, we have

w_{ii} > ∑_{{j=1 \atop j≠i}}^{n} |w_{ij}|.

The above means that W is a row diagonal dominant matrix with positive main diagonal. Note a_{ii} > 0 since 0 < w_{ii} = a_{ii}d_{i} and d_{i} > 0.

To complete the proof of the theorem, we show that (iv)⇒(i). For this let D be a diagonal matrix with positive diagonal elements such that W = AD has a positive dominant main diagonal. Then,

0 < W e = ADe = Ax,

where

x = [ \begin{matrix}d_{1} & ⋯ & 0 \\ ⋮ & ... & ⋮ \\ 0 & ⋯ & d_{n} \end{matrix} ] [ 1 ⋮ 1 ] = [ d_{1} ; ⋮ ; d_{n} ] > 0.

Hence (i) is satisfied.

□

To proceed further, we need the following two technical results.

Lemma 2 An n × n matrix A with complex coefficients such that

|a_{ii}| > ∑_{{j=1 \atop j≠i}}^{n} |a_{ij}| for i = 1, 2, …, n,

is nonsingular, that is, det A ≠ 0.

Proof We prove the above lemma by contraposition. Suppose that det A = 0. Then, there exists a nontrivial solution x ≠ 0 to Ax = 0, that is, for k = 1, 2, …, n,

∑_{j=1}^{n} a_{kj}x_{j} = 0.

Let

x_{i} = max_{1≤k≤n} |x_{k}|.

Rearranging ∑_{j=1}^{n} a_{ij}x_{j} = 0 yields

−a_{ii}x_{i} = a_{i1}x_{1} + ⋯ + a_{i,i−1}x_{i−1} + a_{i,i+1}x_{i+1} + ⋯ + a_{in}x_{n}.

Taking the absolute values of both sides of the above equation gives

|a_{ii}||x_{i}| = |a_{i1}x_{1} + ⋯ + a_{i,i−1}x_{i−1} + a_{i,i+1}x_{i+1} + ⋯ + a_{in}x_{n}| ≤ ∑_{{j=1 \atop j≠i}}^{n} |a_{ij}||x_{j}|.

Thus,

|a_{ii}| ≤ ∑_{{j=1 \atop j≠i}}^{n} |a_{ij}|\frac{|x_{j}|}{|x_{i}|} ≤ ∑_{{j=1 \atop j≠i}}^{n} |a_{ij}|

which contradicts the assumption that |a_{ii}| > ∑n_{{j=1 \atop j≠i}} |a_{ij}|.

□

The above lemma says that if a square matrix is row diagonal dominant then it is nonsingular. Following the arguments of the proof of the lemma, we can show that if a square, complex, matrix is column diagonal dominant then it is also nonsingular. We state this result in the following corollary.

Corollary 1 A complex n × n matrix A such that for j = 1, 2, …, n,

|a_{jj}| > ∑_{{k=1 \atop k≠j}}^{n} |a_{kj}|

is nonsingular.

We now use Lemma 2 to prove the following theorem due to Gershgorin. Theorem 3 Given a complex n × n matrix A. Let D_{i}, i = 1, 2, …, n, denote the i-th closed disk in the complex plane centered at a_{ii} whose radius is r_{i} = ∑n_{{j=1 \atop j≠i}} |a_{ij}|. Then the eigenvalues of A are located in the union ⋃_{i=1}^{n} D_{i}. Proof The eigenvalues of A are the roots of the characteristic equation

det[λI − A] = det [ \begin{matrix}λ − a_{11} & −a_{12} & ⋯ & −a_{1n} \\ −a_{21} & λ − a_{22} & ⋯ & −a_{2n} \\ ⋮ & ⋮ & ... & ⋮ \\ −a_{n1} & −a_{n2} & ⋯ & λ − a_{nn} \end{matrix} ] = 0.

By Lemma 2, the characteristic polynomial is nonzero if for all i = 1, 2, …, n,

|λ − a_{ii}| > ∑_{{j=1 \atop j≠i}}^{n} |a_{ij}|,

that is, for all i = 1, 2, …, n

|λ − a_{ii}| > r_{i}.

Thus the eigenvalues of A must be in the set ⋃_{i=1}^{n} D_{i}.

□

In the following theorem, due to Fiedler and Pták [2], we collect a number of equivalent conditions characterizing the M-matrices. Theorem 4 Let A be a Z-matrix. Then, the following conditions are: equivalent

(i) There exists a vector x ≥ 0 such that Ax > 0; (ii) There exists a diagonal matrix D with positive diagonal such that the matrix W = AD

has a positive main diagonal and is row diagonal dominant;

(iii) Eigenvalues of W have positive real parts and principal minors of W are positive;

(iv) All principal minors of A are positive, that is, A is an M-matrix;

(v) All leading principal minors of A are positive;

(vi) There exists a lower triangular matrix L and an upper triangular matrix U both with positive diagonals such that A = LU. Furthermore, l_{ij} ≤ 0 for i > j, and u_{kl} ≤ 0 for k < l;

(vii) A^{−1} exists and A^{−1} ≥ 0.

Proof The implication (i)⇒(ii) follows from Theorem 2. To prove (ii)⇒(iii), we represent the matrix W = AD as follows

W = AD = [ \begin{matrix}w_{11} & −w_{12} & ⋯ & −w_{1n} \\ −w_{21} & w_{22} & ⋯ & −w_{2n} \\ ⋮ & ⋮ & ... & ⋮ \\ −w_{n1} & −w_{n2} & ⋯ & w_{nn} \end{matrix} ] ,

where w_{ij} ≥ 0 for i ≠ j, and w_{ii} > 0, as follows from Theorem 2. Furthermore,

w_{ii} > ∑_{{j=1 \atop j≠i}}^{n} w_{ij} for i = 1, 2, …, n.

The above implies that each principal minor matrix of W is also row diagonal dominant. By the Theorem of Gershgorin, the eigenvalues of W as well as its principal minor matrices are located on the disks with centers at w_{ii} and radii r_{i} < w_{ii}. Hence they must have real positive parts.

We shall now show that (iii)⇒(iv) holds. First note that since the determinant of a square matrix is the product of its eigenvalues and the product of complex eigenvalues of a real matrix is positive, it follows that all principal minors of the matrix W are positive. Next, the matrix W has the form

W = AD = [ \begin{matrix}a_{11} & −a_{12} & ⋯ & −a_{1n} \\ −a_{21} & a_{22} & ⋯ & −a_{2n} \\ ⋮ & ⋮ & ... & ⋮ \\ −a_{n1} & −a_{n2} & ⋯ & a_{nn} \end{matrix} ] [ \begin{matrix}d_{11} & ⋯ & & 0 \\ & d_{22} \\ ⋮ & & ... & ⋮ \\ 0 & ⋯ & & d_{nn} \end{matrix} ] ,

where a_{ij} ≥ 0 for i ≠ j, a_{ii} > 0, and d_{ii} > 0. Thus if the principal minors of W are positive, the principal minors of A must be positive, and vice versa. This is because

W ( \begin{matrix}i_{1} & i_{2} & … & i_{k} \\ i_{1} & i_{2} & … & i_{k} \end{matrix} ) = A ( \begin{matrix}i_{1} & i_{2} & … & i_{k} \\ i_{1} & i_{2} & … & i_{k} \end{matrix} ) [ \begin{matrix}d_{i_{1}i_{1}} & … & & 0 \\ & d_{i_{2}i_{2}} \\ ⋮ & & ... & ⋮ \\ 0 & … & & d_{i_{k}i_{k}} \end{matrix} ] ,

where

W ( \begin{matrix}i_{1} & i_{2} & … & i_{k} \\ i_{1} & i_{2} & … & i_{k} \end{matrix} )

is a matrix formed using i_{1}, i_{2}, …, i_{k} columns and i_{1}, i_{2}, …, i_{k} rows of the matrix W.

The implication (iv)⇒(v) follows from the observation that the leading principal minors are also principal minors.

The implications (v)⇒ (vi) ⇒(vii) follow from Theorem 1.

Finally, to complete the proof, we show that (vii)⇒(i). For this note that if A^{−1} exists and A^{−1} ≥ 0, then

x = A^{−1}e ≥ 0,

where e = [ 1 1 ⋯ 1 ]^{T} ∈ ℝ^{n}. Hence

Ax = e > 0,

which implies that (i) is satisfied.

□

References

[1] A. Berman and R. J. Plemmons, Nonnegative Matrices in the Mathematical Sciences. Classics in Applied Mathematics Series, Philadelphia: SIAM, 1994.

[2] M. Fiedler and V. Pták, “On matrices with non-positive off-diagonal elements and positive principal minors,” Czechoslovak Journal of Mathematics, vol. 12, no. 87, pp. 382–400, 1962.