19.9 M-Matrices

Every section of this chapter so far has studied a non-negative matrix $\mathbf{B}$ through its spectral radius. This last section looks at the matrices $s\mathbf{I} - \mathbf{B}$ built from one, which turn up wherever a quantity is balanced against what flows into it from its neighbors: a discretized differential equation, an economy that consumes part of its own output, the fundamental matrix of an absorbing Markov chain. The question is always the same. When is $s\mathbf{I} - \mathbf{B}$ invertible with a non-negative inverse, so that a non-negative right-hand side is guaranteed a non-negative solution? The answer is a single inequality, $s > \rho(\mathbf{B})$ , and the section’s main theorem shows that six other conditions, several of which can be checked by hand, say the same thing. The chapter’s summary closes the section.

Throughout, matrices have real entries, the spectrum $\operatorname{spec}(\mathbf{A})$ of $\mathbf{A} \in M_n(\mathbb{R})$ is taken in $\mathbb{C}$ , as in the definition of the spectral radius (Definition 16.4.1), and $\ge$ , $>$ between matrices or vectors are entrywise.

19.9.1. Z-matrices and M-matrices

A matrix of the form $s\mathbf{I} - \mathbf{B}$ with $\mathbf{B} \ge 0$ has an unmistakable sign pattern: the diagonal entries $s - b_{ii}$ can be anything, and every entry off the diagonal is $-b_{ij} \le 0$ . The pattern comes first, because it is what one sees on the page.

Definition 19.9.1 (Z-Matrix)

A matrix $\mathbf{A} = (a_{ij}) \in M_n(\mathbb{R})$ , $n \ge 1$ , is a Z-matrix if $a_{ij} \le 0$ for every pair $i \ne j$ .

The diagonal is unrestricted. The identity is a Z-matrix, and so is $-\mathbf{I}$ ; every $1 \times 1$ matrix is one, since there is no off-diagonal entry to check. The matrix $\begin{psmallmatrix} 2 & -1 \\ -1 & 2 \end{psmallmatrix}$ is one; $\begin{psmallmatrix} 2 & 1 \\ -1 & 2 \end{psmallmatrix}$ is not, because of the single entry $a_{12} = 1 > 0$ .

Lemma 19.9.1 (Z-Matrices Are Shifts of Non-negative Matrices)

A matrix $\mathbf{A} \in M_n(\mathbb{R})$ is a Z-matrix if and only if $\mathbf{A} = s\mathbf{I} - \mathbf{B}$ for some real $s$ and some $\mathbf{B} \in M_n(\mathbb{R})$ with $\mathbf{B} \ge 0$ . For a Z-matrix, every $s \ge \max_i a_{ii}$ gives such a representation, with $\mathbf{B} = s\mathbf{I} - \mathbf{A}$ .

Proof. If $\mathbf{A} = s\mathbf{I} - \mathbf{B}$ with $\mathbf{B} \ge 0$ , then $a_{ij} = -b_{ij} \le 0$ for $i \ne j$ . Conversely, let $\mathbf{A}$ be a Z-matrix, let $s \ge \max_i a_{ii}$ and put $\mathbf{B} = s\mathbf{I} - \mathbf{A}$ . Its diagonal entries are $s - a_{ii} \ge 0$ by the choice of $s$ , and its off-diagonal entries are $-a_{ij} \ge 0$ because $\mathbf{A}$ is a Z-matrix. So $\mathbf{B} \ge 0$ and $\mathbf{A} = s\mathbf{I} - \mathbf{B}$ .

The representation is far from unique: raising $s$ by $t$ raises every diagonal entry of $\mathbf{B}$ by $t$ . A definition built on it must therefore not depend on which representation is used, and that is the first thing to check below.

Now the goal. For a Z-matrix $\mathbf{A} = s\mathbf{I} - \mathbf{B}$ with $s > 0$ , write $\mathbf{A} = s(\mathbf{I} - s^{-1}\mathbf{B})$ . If $\rho(\mathbf{B}) < s$ , the Neumann series of Chapter 10 (Theorem 10.10.6) inverts the second factor as $\sum_k (s^{-1}\mathbf{B})^k$ , a sum of non-negative matrices. So a comparison between $s$ and $\rho(\mathbf{B})$ is exactly what decides whether the inverse is non-negative, and it deserves a name.

An M-matrix is a non-negative matrix subtracted from a multiple of the identity large enough to dominate its spectral radius.

Definition 19.9.2 (M-Matrix)

A matrix $\mathbf{A} \in M_n(\mathbb{R})$ , $n \ge 1$ , is an M-matrix if it can be written as $\mathbf{A} = s\mathbf{I} - \mathbf{B} \qquad \text{with } s \in \mathbb{R},\ \mathbf{B} \in M_n(\mathbb{R}),\ \mathbf{B} \ge 0 \text{ and } s \ge \rho(\mathbf{B}) .$ An M-matrix that is invertible is a non-singular M-matrix.

In words: the first clause asks that $\mathbf{A}$ be a Z-matrix (by Lemma 19.9.1, that is what “ $s\mathbf{I} - \mathbf{B}$ with $\mathbf{B} \ge 0$ ” means), and the second asks that the shift $s$ be at least the spectral radius of what is subtracted. The definition says “can be written”, so a single good representation suffices. The next lemma shows that one representation is as good as any other, and also identifies the singular case.

Lemma 19.9.2 (The Smallest Real Eigenvalue of a Z-Matrix)

Let $\mathbf{A} \in M_n(\mathbb{R})$ be a Z-matrix, and let $\mathbf{A} = s\mathbf{I} - \mathbf{B}$ with $\mathbf{B} \ge 0$ be any representation as in Lemma 19.9.1.

(a) $s - \rho(\mathbf{B})$ is an eigenvalue of $\mathbf{A}$ , and every $\lambda \in \operatorname{spec}(\mathbf{A})$ satisfies $\operatorname{Re}\lambda \ge s - \rho(\mathbf{B})$ . In particular $s - \rho(\mathbf{B})$ is the smallest real eigenvalue of $\mathbf{A}$ , and so it is the same number for every representation.
(b) $\mathbf{A}$ is an M-matrix if and only if $s \ge \rho(\mathbf{B})$ , and a non-singular M-matrix if and only if $s > \rho(\mathbf{B})$ .

Idea. Shifting by $s\mathbf{I}$ moves the spectrum rigidly: the eigenvalues of $\mathbf{A}$ are $s - \mu$ for the eigenvalues $\mu$ of $\mathbf{B}$ . All of those $\mu$ lie in the disc of radius $\rho(\mathbf{B})$ , and the point of that disc farthest to the right, $\rho(\mathbf{B})$ itself, is an eigenvalue because $\mathbf{B} \ge 0$ . Reflected through $s$ , that point becomes the leftmost point of the spectrum of $\mathbf{A}$ , and it is real.

Proof.

(a) For $\mathbf{v} \in \mathbb{C}^n$ and $\lambda \in \mathbb{C}$ , $\mathbf{A}\mathbf{v} = \lambda\mathbf{v}$ if and only if $\mathbf{B}\mathbf{v} = (s - \lambda)\mathbf{v}$ . Hence $\operatorname{spec}(\mathbf{A}) = \{s - \mu : \mu \in \operatorname{spec}(\mathbf{B})\}$ . By Theorem 19.3.1, $\rho(\mathbf{B}) \in \operatorname{spec}(\mathbf{B})$ , so $s - \rho(\mathbf{B}) \in \operatorname{spec}(\mathbf{A})$ . Now let $\lambda \in \operatorname{spec}(\mathbf{A})$ and put $\mu = s - \lambda \in \operatorname{spec}(\mathbf{B})$ . By Definition 16.4.1, $\lvert\mu\rvert \le \rho(\mathbf{B})$ , so $\operatorname{Re}\lambda = s - \operatorname{Re}\mu \ge s - \lvert\mu\rvert \ge s - \rho(\mathbf{B}) .$ For real $\lambda$ this reads $\lambda \ge s - \rho(\mathbf{B})$ . So $s - \rho(\mathbf{B})$ is the smallest real eigenvalue of $\mathbf{A}$ , a number determined by $\mathbf{A}$ alone.
(b) If $s \ge \rho(\mathbf{B})$ , then $\mathbf{A}$ is an M-matrix by Definition 19.9.2. Conversely, if $\mathbf{A}$ is an M-matrix, there is a representation $\mathbf{A} = s'\mathbf{I} - \mathbf{B}'$ with $\mathbf{B}' \ge 0$ and $s' \ge \rho(\mathbf{B}')$ , and by (a) $s - \rho(\mathbf{B}) = s' - \rho(\mathbf{B}') \ge 0$ . For the second statement, $\mathbf{A}$ is invertible if and only if $0 \notin \operatorname{spec}(\mathbf{A})$ (Theorem 9.2.6). If $s > \rho(\mathbf{B})$ , every eigenvalue has real part at least $s - \rho(\mathbf{B}) > 0$ by (a), so $0 \notin \operatorname{spec}(\mathbf{A})$ . If $s = \rho(\mathbf{B})$ , then $0 = s - \rho(\mathbf{B}) \in \operatorname{spec}(\mathbf{A})$ by (a), and $\mathbf{A}$ is singular. This proves the lemma.

So the M-matrix test can be run with the most convenient representation, usually the smallest admissible shift $s = \max_i a_{ii}$ , and the verdict does not change.

Examples.

Size one. The $1 \times 1$ matrix $(a)$ is $s - (s - a)$ for any $s \ge a$ , and $\rho(s - a) = s - a$ . So $(a)$ is an M-matrix exactly when $s \ge s - a$ , that is, $a \ge 0$ , and non-singular exactly when $a > 0$ . This degenerate case is worth keeping in mind: an M-matrix is the matrix version of a non-negative number, and a non-singular one the version of a positive number, whose reciprocal is again positive.
A standard example. $\mathbf{A} = \begin{psmallmatrix} 2 & -1 \\ -1 & 2 \end{psmallmatrix} = 2\mathbf{I} - \mathbf{B}$ with $\mathbf{B} = \begin{psmallmatrix} 0 & 1 \\ 1 & 0 \end{psmallmatrix}$ . Here $p_{\mathbf{B}}(x) = x^2 - 1$ , so $\operatorname{spec}(\mathbf{B}) = \{1, -1\}$ and $\rho(\mathbf{B}) = 1 < 2$ . By Lemma 19.9.2, $\mathbf{A}$ is a non-singular M-matrix, and indeed $\mathbf{A}^{-1} = \tfrac13\begin{psmallmatrix} 2 & 1 \\ 1 & 2 \end{psmallmatrix} \ge 0$ .

Non-example by minimal change. Double the off-diagonal entries of the standard example: $\mathbf{A}' = \begin{psmallmatrix} 2 & -2 \\ -2 & 2 \end{psmallmatrix} = 2\mathbf{I} - 2\mathbf{B}$ , with $\rho(2\mathbf{B}) = 2$ . It is still a Z-matrix and still has the smallest shift $s = 2$ , but now $s = \rho(2\mathbf{B})$ : an M-matrix, and a singular one ( $\mathbf{A}'\mathbf{1} = \mathbf{0}$ ). Go one step further, to $\mathbf{A}'' = \begin{psmallmatrix} 1 & -2 \\ -2 & 1 \end{psmallmatrix} = \mathbf{I} - 2\mathbf{B}$ . The clause that fails is the comparison of the shift with the spectral radius: here $s = 1 < 2 = \rho(2\mathbf{B})$ . By Lemma 19.9.2 its smallest real eigenvalue is $1 - 2 = -1$ , and its inverse, $-\tfrac13\begin{psmallmatrix} 1 & 2 \\ 2 & 1 \end{psmallmatrix}$ , is entrywise negative.

Why this definition. Drop the clause $s \ge \rho(\mathbf{B})$ and the definition describes every Z-matrix, including $\mathbf{A}''$ , whose inverse has the wrong sign everywhere; the whole point is lost. Drop the sign pattern instead, and ask only that some shift of $\mathbf{A}$ have small spectral radius, and the non-negativity of the terms $(s^{-1}\mathbf{B})^k$ in the Neumann series disappears with it. The strict inequality $s > \rho(\mathbf{B})$ is what the series needs to converge, and the lemma shows that the boundary case $s = \rho(\mathbf{B})$ is exactly the singular one, which is why the definition admits it but names the non-singular case separately.

Warning. Positive diagonal and non-positive off-diagonal entries do not make an M-matrix. The matrix $\mathbf{A}'' = \begin{psmallmatrix} 1 & -2 \\ -2 & 1 \end{psmallmatrix}$ has both, yet $\det\mathbf{A}'' = -3 < 0$ and its inverse has no non-negative entry at all. The sign pattern is only half the definition; the size of the off-diagonal entries relative to the diagonal is the other half, and it is measured by $\rho(\mathbf{B})$ , not entry by entry.

Quick check. Is $\begin{psmallmatrix} 1 & -1 \\ -1 & 1 \end{psmallmatrix}$ an M-matrix? Is it a non-singular one?

Solution. Take $s = 1$ and $\mathbf{B} = \begin{psmallmatrix} 0 & 1 \\ 1 & 0 \end{psmallmatrix} \ge 0$ , whose spectrum is $\{1, -1\}$ , so $\rho(\mathbf{B}) = 1 = s$ . By Lemma 19.9.2 (b) the matrix is an M-matrix but not a non-singular one. Directly: it sends $\mathbf{1}$ to $\mathbf{0}$ .

The payoff of the lemma is already visible: for a Z-matrix, the leftmost point of the spectrum is a real eigenvalue, and being a (non-singular) M-matrix means precisely that this eigenvalue is non-negative (positive). The theorem below turns that into conditions that can be checked without finding any eigenvalue.

19.9.2. The characterization theorem

Deciding $s > \rho(\mathbf{B})$ directly means locating the eigenvalues of $\mathbf{B}$ , which is the one computation we would like to avoid. The theorem gives three kinds of substitute: a certificate (one positive vector), a sign condition on the inverse, and a finite list of determinants. Its proof needs one small observation about certificates.

Lemma 19.9.3 (Test Vectors Survive Deletion)

Let $\mathbf{A} \in M_n(\mathbb{R})$ be a Z-matrix, and let $\mathbf{x} \in \mathbb{R}^n$ satisfy $\mathbf{x} > \mathbf{0}$ and $\mathbf{A}\mathbf{x} > \mathbf{0}$ . Let $S \subseteq [n]$ be non-empty, let $\mathbf{A}_{S,S}$ be the principal submatrix on rows and columns $S$ (Definition 7.7.1), and let $\mathbf{x}_S$ be the vector of the entries $x_j$ , $j \in S$ , in increasing order of $j$ . Then $\mathbf{A}_{S,S}$ is a Z-matrix, $\mathbf{x}_S > \mathbf{0}$ and $\mathbf{A}_{S,S}\mathbf{x}_S > \mathbf{0}$ .

Idea. Deleting columns throws away only non-positive contributions to each row, so the surviving rows can only get more positive. That is the whole reason principal minors enter the story.

Proof. The off-diagonal entries of $\mathbf{A}_{S,S}$ are off-diagonal entries of $\mathbf{A}$ , so they are $\le 0$ , and $\mathbf{x}_S > \mathbf{0}$ because $\mathbf{x} > \mathbf{0}$ . Let $i \in S$ . The entry of $\mathbf{A}_{S,S}\mathbf{x}_S$ belonging to $i$ is $\sum_{j \in S} a_{ij}x_j = (\mathbf{A}\mathbf{x})_i - \sum_{j \notin S} a_{ij}x_j \ge (\mathbf{A}\mathbf{x})_i > 0 ,$ because each $j \notin S$ differs from $i \in S$ , so $a_{ij} \le 0$ , while $x_j > 0$ ; every subtracted term is therefore $\le 0$ . This proves the lemma.

Write $\mathbf{A}_k$ for the leading principal submatrix $\mathbf{A}_{[k],[k]}$ , the top-left $k \times k$ corner, as in Sylvester’s criterion (Theorem 13.1.5).

Theorem 19.9.4 (Characterizations of Non-singular M-Matrices)

Let $\mathbf{A} \in M_n(\mathbb{R})$ , $n \ge 1$ , be a Z-matrix. The following are equivalent.

(a) $\mathbf{A}$ is a non-singular M-matrix.
(b) $\mathbf{A}$ is invertible and $\mathbf{A}^{-1} \ge 0$ .
(c) There is $\mathbf{x} \in \mathbb{R}^n$ with $\mathbf{x} > \mathbf{0}$ and $\mathbf{A}\mathbf{x} > \mathbf{0}$ .
(d) Every eigenvalue of $\mathbf{A}$ in $\mathbb{C}$ has positive real part.
(e) Every real eigenvalue of $\mathbf{A}$ is positive.
(f) Every principal minor of $\mathbf{A}$ is positive: $\det\mathbf{A}_{S,S} > 0$ for every non-empty $S \subseteq [n]$ .
(g) Every leading principal minor of $\mathbf{A}$ is positive: $\det\mathbf{A}_k > 0$ for $k = 1, \dots, n$ .

Idea. Three loops, all passing through (a), (b) or (c).

① (a) $\Rightarrow$ (b) $\Rightarrow$ (c) $\Rightarrow$ (a). The Neumann series writes $\mathbf{A}^{-1}$ as a sum of non-negative matrices. The vector $\mathbf{A}^{-1}\mathbf{1}$ is then a certificate for (c). And a certificate $\mathbf{x}$ bounds $\rho(\mathbf{B})$ : rescaling the coordinates by $\mathbf{x}$ turns $\mathbf{B}\mathbf{x} < s\mathbf{x}$ into “every row sum is less than $s$ ”, and Chapter 16 bounds a spectral radius by row sums.

② (a) $\Rightarrow$ (d) $\Rightarrow$ (e) $\Rightarrow$ (a). This is Lemma 19.9.2 read three ways.

③ (c) $\Rightarrow$ (f) $\Rightarrow$ (g) $\Rightarrow$ (b). A certificate survives deletion (Lemma 19.9.3), so every principal submatrix has a non-negative inverse by ①, and one cofactor of that inverse compares two nested minors. The way back from (g) is the induction of Sylvester’s criterion: peel off the last row and column, and read the sign of every block of the inverse from Chapter 8’s block inverse formula.

Proof. (a) $\Rightarrow$ (b). By Lemma 19.9.2 (b), $\mathbf{A} = s\mathbf{I} - \mathbf{B}$ with $\mathbf{B} \ge 0$ and $s > \rho(\mathbf{B}) \ge 0$ ; in particular $s > 0$ . Put $\mathbf{C} = s^{-1}\mathbf{B} \ge 0$ . Its eigenvalues are the numbers $\mu/s$ , $\mu \in \operatorname{spec}(\mathbf{B})$ , so $\rho(\mathbf{C}) = \rho(\mathbf{B})/s < 1$ . By Theorem 10.10.6, $\mathbf{I} - \mathbf{C}$ is invertible and $(\mathbf{I} - \mathbf{C})^{-1} = \sum_{k \ge 0}\mathbf{C}^k$ . Every partial sum $\sum_{k=0}^{K}\mathbf{C}^k$ is $\ge 0$ , since sums and products of non-negative matrices are non-negative; a non-strict inequality survives a limit (the algebra of limits quoted in Chapter 16’s introduction), so $(\mathbf{I} - \mathbf{C})^{-1} \ge 0$ . Hence $\mathbf{A} = s(\mathbf{I} - \mathbf{C})$ is invertible with $\mathbf{A}^{-1} = s^{-1}(\mathbf{I} - \mathbf{C})^{-1} \ge 0$ .

(b) $\Rightarrow$ (c). Put $\mathbf{x} = \mathbf{A}^{-1}\mathbf{1}$ , so that $\mathbf{A}\mathbf{x} = \mathbf{1} > \mathbf{0}$ . Each $x_i = \sum_j (\mathbf{A}^{-1})_{ij}$ is a sum of non-negative numbers, and it is $0$ only if row $i$ of $\mathbf{A}^{-1}$ is zero. That cannot happen: row $i$ of $\mathbf{A}^{-1}\mathbf{A} = \mathbf{I}$ is $\mathbf{e}_i^{\top} \ne \mathbf{0}$ . Hence $\mathbf{x} > \mathbf{0}$ .

(c) $\Rightarrow$ (a). Let $\mathbf{x} > \mathbf{0}$ with $\mathbf{A}\mathbf{x} > \mathbf{0}$ . Choose $s \ge \max_i a_{ii}$ , so that $\mathbf{B} = s\mathbf{I} - \mathbf{A} \ge 0$ by Lemma 19.9.1. Then $\mathbf{B}\mathbf{x} = s\mathbf{x} - \mathbf{A}\mathbf{x}$ , so $(\mathbf{B}\mathbf{x})_i < sx_i$ for every $i$ . Let $\mathbf{D} = \operatorname{diag}(x_1, \dots, x_n)$ , invertible because every $x_i > 0$ . The matrix $\mathbf{D}^{-1}\mathbf{B}\mathbf{D}$ has entries $b_{ij}x_j/x_i \ge 0$ , and its $i$ -th row sum is $(\mathbf{B}\mathbf{x})_i/x_i < s$ . By Corollary 16.4.2, $\rho(\mathbf{D}^{-1}\mathbf{B}\mathbf{D})$ is at most the largest of these row sums, so $\rho(\mathbf{D}^{-1}\mathbf{B}\mathbf{D}) < s$ . Similar matrices have the same characteristic polynomial (Theorem 7.10.3), hence the same eigenvalues, so $\rho(\mathbf{B}) < s$ . By Lemma 19.9.2 (b), $\mathbf{A}$ is a non-singular M-matrix.

(a) $\Rightarrow$ (d). Write $\mathbf{A} = s\mathbf{I} - \mathbf{B}$ with $\mathbf{B} \ge 0$ and $s > \rho(\mathbf{B})$ , by Lemma 19.9.2 (b). By part (a) of the same lemma, every $\lambda \in \operatorname{spec}(\mathbf{A})$ has $\operatorname{Re}\lambda \ge s - \rho(\mathbf{B}) > 0$ .

(d) $\Rightarrow$ (e). A real eigenvalue is its own real part.

(e) $\Rightarrow$ (a). Write $\mathbf{A} = s\mathbf{I} - \mathbf{B}$ with $\mathbf{B} \ge 0$ (Lemma 19.9.1). By Lemma 19.9.2 (a), $s - \rho(\mathbf{B})$ is a real eigenvalue of $\mathbf{A}$ , so it is positive by (e). Hence $s > \rho(\mathbf{B})$ , and $\mathbf{A}$ is a non-singular M-matrix by part (b) of the lemma.

(c) $\Rightarrow$ (f). Let $\mathbf{x} > \mathbf{0}$ with $\mathbf{A}\mathbf{x} > \mathbf{0}$ . We show $\det\mathbf{A}_{S,S} > 0$ by induction on $k = \lvert S\rvert$ . If $k = 1$ , say $S = \{i\}$ , then $a_{ii}x_i > 0$ by Lemma 19.9.3, so $\det\mathbf{A}_{S,S} = a_{ii} > 0$ . Let $k \ge 2$ , and suppose every principal minor of size $k - 1$ is positive. Put $\mathbf{N} = \mathbf{A}_{S,S} \in M_k(\mathbb{R})$ . By Lemma 19.9.3, $\mathbf{N}$ is a Z-matrix satisfying (c), so the implications (c) $\Rightarrow$ (a) $\Rightarrow$ (b), already proved for Z-matrices of every size, show that $\mathbf{N}$ is invertible with $\mathbf{N}^{-1} \ge 0$ . In particular $\det\mathbf{N} \ne 0$ (Theorem 7.5.2). Deleting the last row and column of $\mathbf{N}$ leaves $\mathbf{A}_{S',S'}$ , where $S'$ is $S$ without its largest element; so the $(k,k)$ cofactor of $\mathbf{N}$ is $\det\mathbf{A}_{S',S'}$ , which is positive by the induction hypothesis. By Corollary 7.6.3, $\mathbf{N}^{-1} = (\det\mathbf{N})^{-1}\operatorname{adj}\mathbf{N}$ , whose $(k,k)$ -entry is therefore $(\mathbf{N}^{-1})_{kk} = \frac{\det\mathbf{A}_{S',S'}}{\det\mathbf{N}} .$ This number is $\ge 0$ because $\mathbf{N}^{-1} \ge 0$ , and non-zero because its numerator is. So it is positive, and $\det\mathbf{N} = \det\mathbf{A}_{S',S'}/(\mathbf{N}^{-1})_{kk} > 0$ .

(f) $\Rightarrow$ (g). A leading principal minor is the principal minor with $S = [k]$ .

(g) $\Rightarrow$ (b). By induction on $n$ . If $n = 1$ , then $\mathbf{A} = (a_{11})$ with $a_{11} = \det\mathbf{A}_1 > 0$ , and $\mathbf{A}^{-1} = (1/a_{11}) \ge 0$ . Let $n \ge 2$ , and assume the implication for Z-matrices of size $n - 1$ . Partition $\mathbf{A} = \begin{pmatrix} \mathbf{A}_{n-1} & \mathbf{b} \\ \mathbf{c}^{\top} & a_{nn} \end{pmatrix}, \qquad \mathbf{b}, \mathbf{c} \in \mathbb{R}^{n-1} .$ The corner $\mathbf{A}_{n-1}$ is a Z-matrix whose leading principal minors $\det\mathbf{A}_1, \dots, \det\mathbf{A}_{n-1}$ are positive, so by the induction hypothesis it is invertible with $\mathbf{A}_{n-1}^{-1} \ge 0$ . The entries of $\mathbf{b}$ and $\mathbf{c}$ are off-diagonal entries of $\mathbf{A}$ , so $\mathbf{b} \le \mathbf{0}$ and $\mathbf{c} \le \mathbf{0}$ . By Theorem 8.3.2 (a), $\det\mathbf{A} = \det\mathbf{A}_{n-1}\cdot\sigma$ , where $\sigma = a_{nn} - \mathbf{c}^{\top}\mathbf{A}_{n-1}^{-1}\mathbf{b}$ is the Schur complement of $\mathbf{A}_{n-1}$ ; since $\det\mathbf{A} > 0$ and $\det\mathbf{A}_{n-1} > 0$ , $\sigma > 0$ . By Theorem 8.3.4 (a), $\mathbf{A}$ is invertible and $\mathbf{A}^{-1} = \begin{pmatrix} \mathbf{A}_{n-1}^{-1} + \sigma^{-1}\mathbf{u}\mathbf{w}^{\top} & -\sigma^{-1}\mathbf{u} \\ -\sigma^{-1}\mathbf{w}^{\top} & \sigma^{-1} \end{pmatrix}, \qquad \mathbf{u} = \mathbf{A}_{n-1}^{-1}\mathbf{b},\ \ \mathbf{w}^{\top} = \mathbf{c}^{\top}\mathbf{A}_{n-1}^{-1} .$ Now $\mathbf{u} \le \mathbf{0}$ , being a non-negative matrix times a non-positive vector, and likewise $\mathbf{w} \le \mathbf{0}$ . Hence $\mathbf{u}\mathbf{w}^{\top} \ge 0$ , each of its entries being a product of two non-positive numbers, and $-\sigma^{-1}\mathbf{u} \ge \mathbf{0}$ , $-\sigma^{-1}\mathbf{w} \ge \mathbf{0}$ , $\sigma^{-1} > 0$ . Every block of $\mathbf{A}^{-1}$ is therefore non-negative, so $\mathbf{A}^{-1} \ge 0$ .

The three loops connect all seven conditions, which proves the theorem.

Each condition has its use. Condition (c) is a certificate: to prove that a given Z-matrix is a non-singular M-matrix, exhibit one positive vector and multiply. Condition (g) is a finite test of $n$ determinants, the counterpart for Z-matrices of Sylvester’s criterion for Hermitian matrices, and condition (b) is the payoff: $\mathbf{A}\mathbf{x} = \mathbf{b}$ with $\mathbf{b} \ge \mathbf{0}$ has exactly one solution, and it is $\ge \mathbf{0}$ . Condition (d) links the theorem to differential equations: $-\mathbf{A}$ is stable, so the solutions of $\mathbf{x}' = -\mathbf{A}\mathbf{x}$ decay (exercise C3).

Remark. The two determinant conditions need the Z-hypothesis, and they need strict positivity. The matrix $\begin{psmallmatrix} 1 & 2 \\ 0 & 1 \end{psmallmatrix}$ has all three principal minors equal to $1$ , but it is not a Z-matrix and its inverse $\begin{psmallmatrix} 1 & -2 \\ 0 & 1 \end{psmallmatrix}$ has a negative entry. And the Z-matrix $\begin{psmallmatrix} 0 & -1 \\ 0 & -1 \end{psmallmatrix}$ has leading principal minors $0$ and $0$ , both non-negative, but its eigenvalue $-1$ shows it is not an M-matrix of any kind (exercise C2).

Remark. Stated, not proved. There is a companion statement for M-matrices that may be singular: a Z-matrix is an M-matrix if and only if every principal minor is non-negative. Exercise C2 proves the forward direction by a limiting argument; the converse is not proved in this book and is used nowhere. Longer lists of equivalent conditions exist in the literature; the seven above are the ones proved here.

Warning. A non-negative inverse does not make a matrix a Z-matrix, and so does not make it an M-matrix. Condition (b) characterizes non-singular M-matrices only among Z-matrices. Take $\mathbf{W} = \begin{pmatrix} 1 & -1 & 1 \\ 1 & 1 & -1 \\ -1 & 1 & 1 \end{pmatrix}, \qquad \mathbf{W}^{-1} = \frac12\begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{pmatrix} \ge 0 .$ Multiplying out confirms $\mathbf{W}\mathbf{W}^{-1} = \mathbf{I}$ : for instance row $1$ of $\mathbf{W}$ against the columns of $2\mathbf{W}^{-1}$ gives $1 - 0 + 1 = 2$ , $1 - 1 + 0 = 0$ and $0 - 1 + 1 = 0$ . The diagonal of $\mathbf{W}$ is positive, its principal minors are $1, 1, 1, 2, 2, 2, 4$ , $\mathbf{W}\mathbf{1} = \mathbf{1} > \mathbf{0}$ , and its eigenvalues $1$ and $1 \pm i\sqrt3$ have positive real parts. So $\mathbf{W}$ satisfies every one of (b)–(g), yet $w_{13} = 1 > 0$ : it is not a Z-matrix, and not an M-matrix.

Quick check. Let $\mathbf{A} = \begin{psmallmatrix} a & -b \\ -c & d \end{psmallmatrix}$ with $b, c \ge 0$ . Use the theorem to write down exactly when $\mathbf{A}$ is a non-singular M-matrix, and explain why the condition $d > 0$ need not be listed.

Solution. $\mathbf{A}$ is a Z-matrix, so by (g) it is a non-singular M-matrix if and only if $a > 0$ and $ad - bc > 0$ . Then $ad > bc \ge 0$ and $a > 0$ force $d > 0$ ; so condition (f), which also asks for $d > 0$ , adds nothing, as the theorem says it cannot.

A symmetric Z-matrix has one more characterization, because condition (g) is Sylvester’s criterion word for word.

Corollary 19.9.5 (Symmetric M-Matrices Are Positive Definite)

A symmetric Z-matrix $\mathbf{A} \in M_n(\mathbb{R})$ is a non-singular M-matrix if and only if $\mathbf{A} \succ 0$ .

Proof. By Theorem 19.9.4, $\mathbf{A}$ is a non-singular M-matrix if and only if $\det\mathbf{A}_k > 0$ for every $k$ . By Sylvester’s criterion, Theorem 13.1.5 (d), a real symmetric matrix satisfies this if and only if $\mathbf{A} \succ 0$ .

The Z-hypothesis cannot be dropped here either: $\begin{psmallmatrix} 2 & 1 \\ 1 & 2 \end{psmallmatrix} \succ 0$ , but its inverse $\tfrac13\begin{psmallmatrix} 2 & -1 \\ -1 & 2 \end{psmallmatrix}$ has negative entries. Entrywise order and the Loewner order answer different questions, and the corollary is a place where they meet.

19.9.3. The second-difference matrix

The first application is the one that gave M-matrices their importance. To solve $-u''(t) = f(t)$ on $[0, 1]$ with $u(0) = u(1) = 0$ , choose $n$ , put $h = 1/(n+1)$ and $t_i = ih$ , and replace $u(t_i)$ by an unknown $u_i$ and $-u''(t_i)$ by the second difference $(2u_i - u_{i-1} - u_{i+1})/h^2$ , with $u_0 = u_{n+1} = 0$ . The equations become $\frac{1}{h^2}\mathbf{K}_n\mathbf{u} = \mathbf{f}, \qquad \mathbf{K}_n = \begin{pmatrix} 2 & -1 & & \\ -1 & 2 & \ddots & \\ & \ddots & \ddots & -1 \\ & & -1 & 2 \end{pmatrix} \in M_n(\mathbb{R}),$ where $\mathbf{f} = (f(t_1), \dots, f(t_n))$ . Physically $u$ is the sag of a string under the load $f$ , and a load pushing everywhere in one direction should never make any part of the string move the other way. In matrix language: $\mathbf{K}_n^{-1}$ should be non-negative.

$\mathbf{K}_n$ is a Z-matrix, but the obvious certificate fails. Its rows sum to $1, 0, \dots, 0, 1$ , so $\mathbf{K}_n\mathbf{1}$ has zero entries once $n \ge 3$ : the matrix is diagonally dominant, but only weakly. The continuous problem suggests a better test vector. The function $u(t) = t(1 - t)$ solves $-u'' = 2$ with zero boundary values, so try its samples, scaled to be integers.

Proposition 19.9.6 (The Second-Difference Matrix)

Let $n \ge 1$ . Then $\mathbf{K}_n$ is a non-singular M-matrix, and its inverse is the matrix with entries $(\mathbf{K}_n^{-1})_{ij} = \frac{\min(i,j)\,\bigl(n + 1 - \max(i,j)\bigr)}{n + 1}, \qquad 1 \le i, j \le n .$ In particular every entry of $\mathbf{K}_n^{-1}$ is positive.

Idea. For the M-matrix property, feed $\mathbf{K}_n$ the vector $x_i = i(n + 1 - i)$ , a sampled parabola: second differences of a quadratic are constant, so $\mathbf{K}_n\mathbf{x} = 2\mathbf{1}$ . For the inverse, guess column $j$ from the continuous picture: the response to a point load at $t_j$ is a tent, linear on each side of $j$ and zero at both ends. The second difference of a function that is linear on each side of $j$ vanishes except at the kink, and there it equals the change in slope.

Proof. The certificate. Put $x_i = i(n + 1 - i)$ for $0 \le i \le n + 1$ , so that $x_0 = x_{n+1} = 0$ and $x_i > 0$ for $1 \le i \le n$ . For $1 \le i \le n$ , the $i$ -th entry of $\mathbf{K}_n\mathbf{x}$ is $2x_i - x_{i-1} - x_{i+1}$ , where the terms $x_0$ and $x_{n+1}$ , which do not occur in rows $1$ and $n$ , are zero anyway. Writing $x_i = (n+1)i - i^2$ , the linear part contributes $(n+1)(2i - (i - 1) - (i + 1)) = 0$ , and the quadratic part contributes $-2i^2 + (i-1)^2 + (i+1)^2 = 2 .$ So $\mathbf{K}_n\mathbf{x} = 2\mathbf{1} > \mathbf{0}$ with $\mathbf{x} > \mathbf{0}$ , and Theorem 19.9.4, (c) $\Rightarrow$ (a), shows that $\mathbf{K}_n$ is a non-singular M-matrix.

The inverse. Let $\mathbf{G}$ be the matrix given by the formula, fix a column $j$ , and put $g_i = \min(i,j)(n + 1 - \max(i,j))/(n+1)$ for $0 \le i \le n + 1$ . Then $g_i = \begin{cases} i\,\dfrac{n + 1 - j}{n + 1} & (0 \le i \le j), \\ j\,\dfrac{n + 1 - i}{n + 1} & (j \le i \le n + 1), \end{cases}$ the two lines agreeing at $i = j$ . So $g_0 = g_{n+1} = 0$ , and $(g_i)$ is an affine function of $i$ on $0 \le i \le j$ , with slope $(n+1-j)/(n+1)$ , and on $j \le i \le n+1$ , with slope $-j/(n+1)$ . For $1 \le i \le n$ , entry $i$ of $\mathbf{K}_n$ times column $j$ of $\mathbf{G}$ is $2g_i - g_{i-1} - g_{i+1} = (g_i - g_{i-1}) - (g_{i+1} - g_i)$ . If $i < j$ or $i > j$ , the three points $i - 1, i, i + 1$ lie on one side of $j$ , both differences are the same slope, and the entry is $0$ . If $i = j$ , it is $\frac{n + 1 - j}{n + 1} - \Bigl(-\frac{j}{n + 1}\Bigr) = 1 .$ Hence $\mathbf{K}_n\mathbf{G} = \mathbf{I}$ , so $\mathbf{G} = \mathbf{K}_n^{-1}$ . Finally $\min(i,j) \ge 1$ and $n + 1 - \max(i,j) \ge 1$ , so every entry is at least $1/(n+1) > 0$ .

The matrix $\mathbf{K}_n^{-1}$ is a discrete Green’s function: column $j$ is the sag produced by a unit load at the single point $t_j$ , and positivity of every entry says that a load at one point moves every point of the string, in the same direction. The non-negativity of $\mathbf{K}_n^{-1}$ is the discrete maximum principle: if $\mathbf{K}_n\mathbf{u} \ge \mathbf{0}$ then $\mathbf{u} \ge \mathbf{0}$ . Since $\mathbf{K}_n$ is symmetric, Corollary 19.9.5 also shows $\mathbf{K}_n \succ 0$ , which Chapter 7 foreshadowed by computing $\det\mathbf{K}_n = n + 1$ in Exercise (B2: The second-difference matrix).

Example (The Case n = 4)

Write down $\mathbf{K}_4^{-1}$ , check one column against $\mathbf{K}_4$ , and recover the certificate $\mathbf{x}$ from it.

Solution. With $n + 1 = 5$ , Proposition 19.9.6 gives $\mathbf{K}_4^{-1} = \frac15\begin{pmatrix} 4 & 3 & 2 & 1 \\ 3 & 6 & 4 & 2 \\ 2 & 4 & 6 & 3 \\ 1 & 2 & 3 & 4 \end{pmatrix} .$ Check of column 2. $\mathbf{K}_4$ applied to $(3, 6, 4, 2)$ gives $(6 - 6,\ -3 + 12 - 4,\ -6 + 8 - 2,\ -4 + 4) = (0, 5, 0, 0)$ , and dividing by $5$ gives $\mathbf{e}_2$ , as it must. Each column is a tent: column 2 rises by $3$ per step up to row $2$ and then falls by $2$ per step towards the zero at the fictitious row $5$ .

The certificate. The row sums of $5\mathbf{K}_4^{-1}$ are $10, 15, 15, 10$ , so $\mathbf{K}_4^{-1}\mathbf{1} = (2, 3, 3, 2)$ , which is $\tfrac12(1\cdot4, 2\cdot3, 3\cdot2, 4\cdot1) = \tfrac12\mathbf{x}$ . This is the proof of (b) $\Rightarrow$ (c) run backwards: the vector $\mathbf{A}^{-1}\mathbf{1}$ is always a certificate, and here it is the sampled parabola.

19.9.4. The Leontief input–output model

The second application comes from economics. An economy has $n$ sectors, each producing one good. To produce one unit of good $j$ , sector $j$ consumes $c_{ij} \ge 0$ units of good $i$ , so column $j$ of the consumption matrix $\mathbf{C} = (c_{ij}) \ge 0$ is sector $j$ ’s recipe. A production plan $\mathbf{x} \ge \mathbf{0}$ uses up $\mathbf{C}\mathbf{x}$ as inputs and leaves the net output $\mathbf{x} - \mathbf{C}\mathbf{x}$ for outside use. Given a final demand $\mathbf{d} \ge \mathbf{0}$ , the planner needs $(\mathbf{I} - \mathbf{C})\mathbf{x} = \mathbf{d}, \qquad \mathbf{x} \ge \mathbf{0} .$ The economy is productive if this has a solution for every $\mathbf{d} \ge \mathbf{0}$ . The matrix $\mathbf{I} - \mathbf{C}$ is a Z-matrix, and the theorem answers the question completely.

Corollary 19.9.7 (Productive Economies)

Let $\mathbf{C} \in M_n(\mathbb{R})$ with $\mathbf{C} \ge 0$ . The following are equivalent.

(i) For every $\mathbf{d} \ge \mathbf{0}$ there is $\mathbf{x} \ge \mathbf{0}$ with $(\mathbf{I} - \mathbf{C})\mathbf{x} = \mathbf{d}$ .
(ii) There is $\mathbf{x} \ge \mathbf{0}$ with $\mathbf{x} - \mathbf{C}\mathbf{x} > \mathbf{0}$ : some plan leaves a surplus of every good.
(iii) $\rho(\mathbf{C}) < 1$ .
(iv) $\mathbf{I} - \mathbf{C}$ is invertible and $(\mathbf{I} - \mathbf{C})^{-1} \ge 0$ .
(v) Every leading principal minor of $\mathbf{I} - \mathbf{C}$ is positive.

When they hold, the solution in (i) is unique, and $(\mathbf{I} - \mathbf{C})^{-1} = \mathbf{I} + \mathbf{C} + \mathbf{C}^2 + \cdots$ . They hold in particular when every column sum of $\mathbf{C}$ is less than $1$ .

Idea. The matrix $\mathbf{I} - \mathbf{C}$ is a Z-matrix, so this is the main theorem read in economic terms: (iii) is (a) with $s = 1$ ; (ii), (iv) and (v) are (c), (b) and (g), where in (ii) a plan $\mathbf{x} \ge \mathbf{0}$ with a surplus is automatically positive, since $\mathbf{x} > \mathbf{C}\mathbf{x} \ge \mathbf{0}$ ; and (i) sits between (iv) and (ii).

Proof. $\mathbf{I} - \mathbf{C}$ is a Z-matrix with the representation $s = 1$ , $\mathbf{B} = \mathbf{C}$ , so (iii) says, by Lemma 19.9.2 (b), that $\mathbf{I} - \mathbf{C}$ is a non-singular M-matrix. By Theorem 19.9.4, (iii) is therefore equivalent to (iv) (condition (b) there) and to (v) (condition (g)). It is also equivalent to (ii): if $\mathbf{x} \ge \mathbf{0}$ and $\mathbf{x} - \mathbf{C}\mathbf{x} > \mathbf{0}$ , then $\mathbf{x} > \mathbf{C}\mathbf{x} \ge \mathbf{0}$ , so $\mathbf{x} > \mathbf{0}$ and condition (c) of the theorem holds; conversely (c) supplies such an $\mathbf{x}$ .

(iv) $\Rightarrow$ (i): given $\mathbf{d} \ge \mathbf{0}$ , the vector $\mathbf{x} = (\mathbf{I} - \mathbf{C})^{-1}\mathbf{d}$ is a product of non-negative factors, hence $\ge \mathbf{0}$ , and it solves the system. (i) $\Rightarrow$ (ii): take $\mathbf{d} = \mathbf{1}$ .

When they hold, $\mathbf{I} - \mathbf{C}$ is invertible, so the solution is unique, and $\rho(\mathbf{C}) < 1$ gives the series by Theorem 10.10.6. Finally, if every column sum of $\mathbf{C}$ is less than $1$ , then $\rho(\mathbf{C}) \le \left\| \mathbf{C} \right\|_1 < 1$ by Corollary 16.4.2, which is (iii).

Condition (v) is known to economists as the Hawkins–Simon condition, and the series has a direct reading. To deliver $\mathbf{d}$ , the economy must first produce $\mathbf{d}$ ; that production consumes $\mathbf{C}\mathbf{d}$ , which must also be produced; that consumes $\mathbf{C}^2\mathbf{d}$ ; and so on. The Leontief inverse $(\mathbf{I} - \mathbf{C})^{-1}$ adds up all the rounds, and its $(i, j)$ -entry is the total amount of good $i$ that the economy must produce, directly and indirectly, to deliver one unit of good $j$ .

Example (Three Sectors)

An economy has three sectors, agriculture, manufacturing and services, with consumption matrix $\mathbf{C} = \frac15\begin{pmatrix} 1 & 1 & 1 \\ 2 & 0 & 1 \\ 0 & 2 & 1 \end{pmatrix} .$ Show that it is productive, find $\rho(\mathbf{C})$ exactly, compute the Leontief inverse, and find the production plan meeting the demand $\mathbf{d} = (12, 6, 6)$ .

Solution. Productive. Every column of $5\mathbf{C}$ sums to $3$ , so every column sum of $\mathbf{C}$ is $\tfrac35 < 1$ , and Corollary 19.9.7 applies.

The spectral radius. Expanding $\det(x\mathbf{I} - \mathbf{C})$ along the first row gives $p_{\mathbf{C}}(x) = x^3 - \tfrac25x^2 - \tfrac{3}{25}x = x\bigl(x - \tfrac35\bigr)\bigl(x + \tfrac15\bigr),$ so $\operatorname{spec}(\mathbf{C}) = \{0, \tfrac35, -\tfrac15\}$ and $\rho(\mathbf{C}) = \tfrac35$ , equal to the column-sum bound $\left\| \mathbf{C} \right\|_1$ of Corollary 16.4.2. The bound is attained because all column sums are equal: $\mathbf{C}^{\top}\mathbf{1} = \tfrac35\mathbf{1}$ .

The Leontief inverse. Here $\mathbf{I} - \mathbf{C} = \tfrac15\begin{psmallmatrix} 4 & -1 & -1 \\ -2 & 5 & -1 \\ 0 & -2 & 4 \end{psmallmatrix}$ , and $(\mathbf{I} - \mathbf{C})^{-1} = \frac16\begin{pmatrix} 9 & 3 & 3 \\ 4 & 8 & 3 \\ 2 & 4 & 9 \end{pmatrix} .$ To check, multiply $\begin{psmallmatrix} 4 & -1 & -1 \\ -2 & 5 & -1 \\ 0 & -2 & 4 \end{psmallmatrix}$ by $\begin{psmallmatrix} 9 & 3 & 3 \\ 4 & 8 & 3 \\ 2 & 4 & 9 \end{psmallmatrix}$ : the first row gives $36 - 4 - 2 = 30$ , $12 - 8 - 4 = 0$ , $12 - 3 - 9 = 0$ ; the second $-18 + 20 - 2 = 0$ , $-6 + 40 - 4 = 30$ , $-6 + 15 - 9 = 0$ ; the third $-8 + 8 = 0$ , $-16 + 16 = 0$ , $-6 + 36 = 30$ . The product is $30\mathbf{I}$ , and $\tfrac15\cdot\tfrac16\cdot 30 = 1$ . Every entry of the inverse is positive: extra demand for any one good raises the output of every sector. For instance, one extra unit of services requires $\tfrac12$ unit of agricultural output in total, although services consume only $\tfrac15$ unit of it directly.

The plan. $\mathbf{x} = (\mathbf{I} - \mathbf{C})^{-1}\mathbf{d} = \frac16\begin{pmatrix} 108 + 18 + 18 \\ 48 + 48 + 18 \\ 24 + 24 + 54 \end{pmatrix} = \begin{pmatrix} 24 \\ 19 \\ 17 \end{pmatrix} .$ Check: $\mathbf{C}\mathbf{x} = \tfrac15(24 + 19 + 17,\ 48 + 17,\ 38 + 17) = (12, 13, 11)$ , and $\mathbf{x} - \mathbf{C}\mathbf{x} = (12, 6, 6) = \mathbf{d}$ . Delivering this demand takes $24$ units of agricultural output, twice the $12$ that leave the economy.

Quick check. A two-sector economy has $\mathbf{C} = \begin{psmallmatrix} 1/2 & 1 \\ 1/2 & 0 \end{psmallmatrix}$ . Is it productive?

Solution. No. The leading principal minors of $\mathbf{I} - \mathbf{C} = \begin{psmallmatrix} 1/2 & -1 \\ -1/2 & 1 \end{psmallmatrix}$ are $\tfrac12$ and $\tfrac12 - \tfrac12 = 0$ , so (v) of Corollary 19.9.7 fails. Indeed $\mathbf{C}\begin{psmallmatrix} 2 \\ 1 \end{psmallmatrix} = \begin{psmallmatrix} 2 \\ 1 \end{psmallmatrix}$ : running the sectors in the ratio $2 : 1$ exactly reproduces its own inputs and leaves nothing over, and $\rho(\mathbf{C}) = 1$ .

19.9.5. Summary and transfer

The chapter set out to explain what the sign of the entries alone forces on the spectrum. For a positive matrix the answer is Perron’s theorem (§01, Positive matrices and Perron’s theorem): the spectral radius is a simple eigenvalue with a positive eigenvector, and it strictly dominates every other eigenvalue in modulus. Irreducibility, a property of the zero pattern read off a directed graph (§02, Irreducibility and graphs), is what keeps most of that conclusion alive when zeros are allowed (§03, The Perron–Frobenius theorem), and without it one still has $\rho(\mathbf{B})$ as an eigenvalue with a non-negative eigenvector. From there the chapter drew the long-run behavior of powers (§05, Primitive matrices), Markov chains (§06, Markov chains), the extreme points of the doubly stochastic matrices (§07, Birkhoff’s theorem), a ranking of web pages (§08, PageRank), and in this section the matrices $s\mathbf{I} - \mathbf{B}$ . Six moves did the work.

Compare entrywise, then take the spectral radius. Non-negativity makes the spectral radius monotone and lets $\lvert\mathbf{A}\mathbf{x}\rvert \le \lvert\mathbf{A}\rvert\lvert\mathbf{x}\rvert$ replace cancellation by an inequality (§01, Positive matrices and Perron’s theorem). Transfer: to bound the spectral radius of a matrix you do not understand, dominate it entrywise by one you do.
A positive test vector bounds $\rho$ from both sides. The ratios $(\mathbf{A}\mathbf{x})_i/x_i$ for a single $\mathbf{x} > \mathbf{0}$ trap $\rho(\mathbf{A})$ between their minimum and maximum (§04, The Collatz–Wielandt formula), and in this section one $\mathbf{x} > \mathbf{0}$ with $\mathbf{A}\mathbf{x} > \mathbf{0}$ certified a non-singular M-matrix. The mechanism used here is the rescaling $\mathbf{D}^{-1}\mathbf{B}\mathbf{D}$ with $\mathbf{D} = \operatorname{diag}(\mathbf{x})$ , which turns $\mathbf{B}\mathbf{x}$ into row sums. Transfer: guess a positive vector from the structure of the problem, the parabola for $\mathbf{K}_n$ , and verify it by one multiplication.
Read the zero pattern as a graph. Which entries of $\mathbf{A}^k$ are positive depends only on which entries of $\mathbf{A}$ are, and that is a question about paths (§02, Irreducibility and graphs; §05, Primitive matrices). Transfer: when only signs matter, draw the graph and count paths.
Prove it for positive matrices, then reach the boundary. Perron’s theorem is proved where every entry is positive, and the non-negative and irreducible cases are reached from it through positive matrices built from $\mathbf{A}$ (§03, The Perron–Frobenius theorem). Transfer: when a hypothesis is an inequality that may hold with equality, prove the strict case and ask what survives the passage to the boundary; $s > \rho(\mathbf{B})$ versus $s \ge \rho(\mathbf{B})$ in this section is the same division.
Divide by the Perron root, then use Chapter 10. Once $\rho(\mathbf{A})$ is known to be a simple eigenvalue dominating the others, $\mathbf{A}/\rho(\mathbf{A})$ meets the hypotheses of the convergence theorems of Chapter 10 §10, and no diagonalizability is ever needed (§05, Primitive matrices; §06, Markov chains). Transfer: normalize the dominant eigenvalue to $1$ before asking about limits.
Invert with a series of non-negative terms. If $\mathbf{B} \ge 0$ and $\rho(\mathbf{B}) < 1$ , then $(\mathbf{I} - \mathbf{B})^{-1} = \sum_k \mathbf{B}^k \ge 0$ . This is the fundamental matrix of an absorbing chain (§06, Markov chains), the Leontief inverse, and the non-negativity of the inverse of every non-singular M-matrix. Transfer: to prove that an inverse is non-negative, or to interpret its entries, expand it as the sum of the rounds of a process.

The chapter also paid promises made in earlier chapters.

The promise	Made in	Paid by
“Chapter 19 proves the Perron–Frobenius theorem, which gives the conclusions of Theorem 9.11.4 for every stochastic matrix with some power having all entries positive, without assuming diagonalizability and without computing eigenvalues”	Chapter 9 §11	§06 (Stochastic matrices and Markov chains), resting on §03 (The Perron–Frobenius theorem) and §05 (Primitive matrices and the limit theorem)
“We do not prove Birkhoff’s theorem here; Chapter 19 does”	Chapter 18 §08, and again in its summary, §11	§07 (Doubly stochastic matrices and Birkhoff’s theorem)

Some things the chapter did not do. The characterization of possibly singular M-matrices by non-negative principal minors was stated here and proved in one direction only. The theorem of Hardy, Littlewood and Pólya, that $\mathbf{x} \prec \mathbf{y}$ exactly when $\mathbf{x} = \mathbf{D}\mathbf{y}$ for a doubly stochastic $\mathbf{D}$ , belongs to Chapter 21. And the power method, the algorithm that computes a Perron vector at the size of the web, belongs to Chapter 24.

19.9.6. Exercises

A. Check your understanding

Exercise (A1)

(a) Define a Z-matrix and a non-singular M-matrix.
(b) True or false: every Z-matrix with positive diagonal entries is a non-singular M-matrix. Justify your answer.
(c) True or false: every principal submatrix of a non-singular M-matrix is a non-singular M-matrix. Justify your answer.
(d) True or false: if $\mathbf{A}$ is invertible and $\mathbf{A}^{-1} \ge 0$ , then $\mathbf{A}$ is an M-matrix. Justify your answer.
(e) True or false: the inverse of a non-singular M-matrix has every entry positive. Justify your answer.
(f) Name a vector $\mathbf{x} > \mathbf{0}$ with $\mathbf{K}_n\mathbf{x} > \mathbf{0}$ , and explain why $\mathbf{x} = \mathbf{1}$ does not work when $n \ge 3$ .

Solution.

(a) $\mathbf{A} \in M_n(\mathbb{R})$ is a Z-matrix if $a_{ij} \le 0$ for all $i \ne j$ (Definition 19.9.1). It is a non-singular M-matrix if $\mathbf{A} = s\mathbf{I} - \mathbf{B}$ with $\mathbf{B} \ge 0$ and $s \ge \rho(\mathbf{B})$ , and $\mathbf{A}$ is invertible; equivalently, $s > \rho(\mathbf{B})$ (Definition 19.9.2, Lemma 19.9.2 (b)).
(b) False. $\begin{psmallmatrix} 1 & -2 \\ -2 & 1 \end{psmallmatrix}$ is a Z-matrix with positive diagonal, but its determinant is $1 - 4 = -3$ , so condition (g) of Theorem 19.9.4 fails.
(c) True. Let $\mathbf{A}$ be a non-singular M-matrix. By Theorem 19.9.4 there is $\mathbf{x} > \mathbf{0}$ with $\mathbf{A}\mathbf{x} > \mathbf{0}$ . By Lemma 19.9.3, $\mathbf{A}_{S,S}$ is a Z-matrix with $\mathbf{A}_{S,S}\mathbf{x}_S > \mathbf{0}$ and $\mathbf{x}_S > \mathbf{0}$ , so it is a non-singular M-matrix by (c) $\Rightarrow$ (a) of the theorem.
(d) False. The swap $\mathbf{P} = \begin{psmallmatrix} 0 & 1 \\ 1 & 0 \end{psmallmatrix}$ satisfies $\mathbf{P}^{-1} = \mathbf{P} \ge 0$ , but $p_{12} = 1 > 0$ , so $\mathbf{P}$ is not a Z-matrix, and every M-matrix is one.
(e) False. $\mathbf{I}_2$ is a non-singular M-matrix, and $\mathbf{I}_2^{-1} = \mathbf{I}_2$ has zero off-diagonal entries.
(f) $x_i = i(n + 1 - i)$ , for which $\mathbf{K}_n\mathbf{x} = 2\mathbf{1}$ (Proposition 19.9.6). For $\mathbf{x} = \mathbf{1}$ , row $i$ of $\mathbf{K}_n\mathbf{1}$ is $2 - 1 - 1 = 0$ for every $2 \le i \le n - 1$ , and such rows exist when $n \ge 3$ .

B. Practice

Exercise (B1: Which are non-singular M-matrices?)

Determine which of the following are non-singular M-matrices. Justify your answer.

(a) $\begin{pmatrix} 3 & -1 & -1 \\ -1 & 3 & -1 \\ -1 & -1 & 3 \end{pmatrix}$
(b) $\begin{pmatrix} 1 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 1 \end{pmatrix}$
(c) $\begin{pmatrix} 2 & -3 \\ -1 & 2 \end{pmatrix}$
(d) $\begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}$
(e) $\begin{pmatrix} 1 & -2 & 0 \\ 0 & 1 & -2 \\ -2 & 0 & 1 \end{pmatrix}$

Solution.

(a) Yes. It is a Z-matrix, and every row sums to $1$ , so $\mathbf{x} = \mathbf{1} > \mathbf{0}$ gives $\mathbf{A}\mathbf{x} = \mathbf{1} > \mathbf{0}$ . By Theorem 19.9.4, (c) $\Rightarrow$ (a), it is a non-singular M-matrix. (Its inverse is $\tfrac14\begin{psmallmatrix} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \end{psmallmatrix} \ge 0$ , as (b) predicts.)
(b) No. Every row sums to $0$ , so $\mathbf{A}\mathbf{1} = \mathbf{0}$ and $\mathbf{A}$ is singular. (It is a singular M-matrix: with $s = 2$ , $\mathbf{B} = 2\mathbf{I} - \mathbf{A}$ has every row sum equal to $2$ , so $\rho(\mathbf{B}) \le 2$ by Corollary 16.4.2, while $\mathbf{B}\mathbf{1} = 2\mathbf{1}$ gives $\rho(\mathbf{B}) \ge 2$ .)
(c) Yes. It is a Z-matrix with leading principal minors $2 > 0$ and $4 - 3 = 1 > 0$ , so (g) $\Rightarrow$ (a) applies. Check: $\mathbf{A}^{-1} = \begin{psmallmatrix} 2 & 3 \\ 1 & 2 \end{psmallmatrix} \ge 0$ .
(d) No. The off-diagonal entries are $1 > 0$ , so it is not a Z-matrix. (It is positive definite, and its inverse $\tfrac13\begin{psmallmatrix} 2 & -1 \\ -1 & 2 \end{psmallmatrix}$ has negative entries.)
(e) No. It is a Z-matrix, but expanding along the first row, $\det\mathbf{A} = 1\cdot(1 - 0) - (-2)\cdot(0 - 4) + 0 = 1 - 8 = -7 < 0 ,$ so condition (f) of Theorem 19.9.4 fails.

Exercise (B2: A string with a free end)

Let $\mathbf{A} = \begin{pmatrix} 2 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 1 \end{pmatrix} .$

(a) Show that $\mathbf{A}\mathbf{1}$ is not positive, and find $\mathbf{x} > \mathbf{0}$ with $\mathbf{A}\mathbf{x} > \mathbf{0}$ .
(b) Compute the leading principal minors of $\mathbf{A}$ , and check that they agree with (a).
(c) Compute $\mathbf{A}^{-1}$ and check that $\mathbf{A}^{-1} \ge 0$ . Hence solve $\mathbf{A}\mathbf{u} = \mathbf{e}_3$ , and say why the answer had to be non-negative.

Hint: try an increasing $\mathbf{x}$ whose increments decrease.

Solution.

(a) $\mathbf{A}\mathbf{1} = (1, 0, 0)$ , which is not positive. Take $\mathbf{x} = (3, 5, 6)$ : then $\mathbf{A}\mathbf{x} = (6 - 5,\ -3 + 10 - 6,\ -5 + 6) = (1, 1, 1) > \mathbf{0}$ . Since $\mathbf{A}$ is a Z-matrix, it is a non-singular M-matrix by Theorem 19.9.4, (c) $\Rightarrow$ (a).
(b) $\det\mathbf{A}_1 = 2$ , $\det\mathbf{A}_2 = 4 - 1 = 3$ , and, expanding along the first row, $\det\mathbf{A} = 2(2 - 1) - (-1)(-1 - 0) = 2 - 1 = 1$ . All three are positive, which is condition (g), as (a) and the theorem require.
(c) $\mathbf{A}^{-1} = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 2 & 2 \\ 1 & 2 & 3 \end{pmatrix},$ the matrix with entries $\min(i, j)$ . Check: row 1 of $\mathbf{A}$ against the columns gives $2 - 1 = 1$ , $2 - 2 = 0$ , $2 - 2 = 0$ ; row 2 gives $-1 + 2 - 1 = 0$ , $-1 + 4 - 2 = 1$ , $-1 + 4 - 3 = 0$ ; row 3 gives $-1 + 1 = 0$ , $-2 + 2 = 0$ , $-2 + 3 = 1$ . So $\mathbf{A}\mathbf{A}^{-1} = \mathbf{I}$ , and $\mathbf{A}^{-1} \ge 0$ . Hence $\mathbf{u} = \mathbf{A}^{-1}\mathbf{e}_3 = (1, 2, 3)$ . It had to be $\ge \mathbf{0}$ because $\mathbf{e}_3 \ge \mathbf{0}$ and $\mathbf{A}^{-1} \ge 0$ . Note that $\mathbf{A}^{-1}\mathbf{1} = (3, 5, 6)$ is the certificate of (a).

Exercise (B3: A two-sector economy)

Let $\mathbf{C} = \begin{pmatrix} 1/5 & 2/5 \\ 3/10 & 1/10 \end{pmatrix} .$

(a) Show that the economy with consumption matrix $\mathbf{C}$ is productive.
(b) Compute the Leontief inverse $(\mathbf{I} - \mathbf{C})^{-1}$ .
(c) Find the production plan meeting the demand $\mathbf{d} = (30, 60)$ , and check it.
(d) Find $\rho(\mathbf{C})$ exactly.

Solution.

(a) The column sums are $\tfrac15 + \tfrac{3}{10} = \tfrac12$ and $\tfrac25 + \tfrac{1}{10} = \tfrac12$ , both less than $1$ , so the economy is productive by Corollary 19.9.7.
(b) $\mathbf{I} - \mathbf{C} = \begin{psmallmatrix} 4/5 & -2/5 \\ -3/10 & 9/10 \end{psmallmatrix}$ , with determinant $\tfrac{36}{50} - \tfrac{6}{50} = \tfrac35$ . By Theorem 0.9.8, $(\mathbf{I} - \mathbf{C})^{-1} = \frac53\begin{pmatrix} 9/10 & 2/5 \\ 3/10 & 4/5 \end{pmatrix} = \begin{pmatrix} 3/2 & 2/3 \\ 1/2 & 4/3 \end{pmatrix} \ge 0 .$
(c) $\mathbf{x} = (\tfrac32\cdot30 + \tfrac23\cdot60,\ \tfrac12\cdot30 + \tfrac43\cdot60) = (85, 95)$ . Check: $\mathbf{C}\mathbf{x} = (17 + 38,\ \tfrac{51}{2} + \tfrac{19}{2}) = (55, 35)$ , and $\mathbf{x} - \mathbf{C}\mathbf{x} = (30, 60)$ .
(d) $p_{\mathbf{C}}(x) = x^2 - \tfrac{3}{10}x + \bigl(\tfrac{1}{50} - \tfrac{12}{100}\bigr) = x^2 - \tfrac{3}{10}x - \tfrac{1}{10} = (x - \tfrac12)(x + \tfrac15)$ . So $\operatorname{spec}(\mathbf{C}) = \{\tfrac12, -\tfrac15\}$ and $\rho(\mathbf{C}) = \tfrac12$ . Here the column-sum bound $\left\| \mathbf{C} \right\|_1 = \tfrac12$ is attained, as it must be when all column sums are equal.

C. Going deeper

Exercise (C1: Raising the diagonal)

(a) Let $\mathbf{A}$ be a non-singular M-matrix and $\mathbf{M}$ a Z-matrix of the same size with $\mathbf{M} \ge \mathbf{A}$ entrywise. Prove that $\mathbf{M}$ is a non-singular M-matrix and that $0 \le \mathbf{M}^{-1} \le \mathbf{A}^{-1}$ .
(b) Deduce that for every diagonal $\mathbf{D} \ge 0$ , $\mathbf{K}_n + \mathbf{D}$ is a non-singular M-matrix with $(\mathbf{K}_n + \mathbf{D})^{-1} \le \mathbf{K}_n^{-1}$ . Check this for $n = 2$ and $\mathbf{D} = \operatorname{diag}(1, 0)$ .

Hint: for the inequality, factor $\mathbf{A}^{-1} - \mathbf{M}^{-1}$ .

Solution.

(a) By Theorem 19.9.4 there is $\mathbf{x} > \mathbf{0}$ with $\mathbf{A}\mathbf{x} > \mathbf{0}$ . Since $\mathbf{M} - \mathbf{A} \ge 0$ and $\mathbf{x} > \mathbf{0}$ , $(\mathbf{M} - \mathbf{A})\mathbf{x} \ge \mathbf{0}$ , so $\mathbf{M}\mathbf{x} = \mathbf{A}\mathbf{x} + (\mathbf{M} - \mathbf{A})\mathbf{x} > \mathbf{0}$ . As $\mathbf{M}$ is a Z-matrix, (c) $\Rightarrow$ (a) of the theorem makes it a non-singular M-matrix, and (a) $\Rightarrow$ (b) gives $\mathbf{M}^{-1} \ge 0$ . Next, $\mathbf{A}^{-1} - \mathbf{M}^{-1} = \mathbf{A}^{-1}\mathbf{M}\mathbf{M}^{-1} - \mathbf{A}^{-1}\mathbf{A}\mathbf{M}^{-1} = \mathbf{A}^{-1}(\mathbf{M} - \mathbf{A})\mathbf{M}^{-1} ,$ a product of three non-negative matrices, hence $\ge 0$ . This proves $0 \le \mathbf{M}^{-1} \le \mathbf{A}^{-1}$ .
(b) $\mathbf{K}_n$ is a non-singular M-matrix by Proposition 19.9.6, and $\mathbf{K}_n + \mathbf{D}$ is a Z-matrix with $\mathbf{K}_n + \mathbf{D} \ge \mathbf{K}_n$ , since $\mathbf{D}$ only changes the diagonal and does so upwards. Part (a) gives the claim. For $n = 2$ : $\mathbf{K}_2^{-1} = \tfrac13\begin{psmallmatrix} 2 & 1 \\ 1 & 2 \end{psmallmatrix}$ , and $\mathbf{K}_2 + \mathbf{D} = \begin{psmallmatrix} 3 & -1 \\ -1 & 2 \end{psmallmatrix}$ has determinant $5$ and inverse $\tfrac15\begin{psmallmatrix} 2 & 1 \\ 1 & 3 \end{psmallmatrix}$ . The difference is $\frac13\begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix} - \frac15\begin{pmatrix} 2 & 1 \\ 1 & 3 \end{pmatrix} = \frac{1}{15}\begin{pmatrix} 4 & 2 \\ 2 & 1 \end{pmatrix} \ge 0 .$

Exercise (C2: The singular case)

(a) Show that the Z-matrix $\mathbf{Z} = \begin{psmallmatrix} 0 & -1 \\ 0 & -1 \end{psmallmatrix}$ has non-negative leading principal minors but is not an M-matrix.
(b) Let $\mathbf{A}$ be an M-matrix. Prove that $\mathbf{A} + \varepsilon\mathbf{I}$ is a non-singular M-matrix for every real $\varepsilon > 0$ .
(c) Deduce that every principal minor of an M-matrix is non-negative.
(d) Check (c) for $\begin{psmallmatrix} 1 & -1 \\ -1 & 1 \end{psmallmatrix}$ , and explain why (a) does not contradict the stated converse in the remark after Theorem 19.9.4.

Solution.

(a) $\det\mathbf{Z}_1 = 0$ and $\det\mathbf{Z} = 0\cdot(-1) - (-1)\cdot 0 = 0$ , both non-negative. $\mathbf{Z}$ is upper triangular, so its eigenvalues are its diagonal entries $0$ and $-1$ (Theorem 9.7.4). Its smallest real eigenvalue is $-1 < 0$ , so by Lemma 19.9.2 it is not an M-matrix: for any representation $\mathbf{Z} = s\mathbf{I} - \mathbf{B}$ , $s - \rho(\mathbf{B}) = -1$ .
(b) Write $\mathbf{A} = s\mathbf{I} - \mathbf{B}$ with $\mathbf{B} \ge 0$ and $s \ge \rho(\mathbf{B})$ . Then $\mathbf{A} + \varepsilon\mathbf{I} = (s + \varepsilon)\mathbf{I} - \mathbf{B}$ with $s + \varepsilon > \rho(\mathbf{B})$ , so it is a non-singular M-matrix by Lemma 19.9.2 (b).
(c) Fix a non-empty $S \subseteq [n]$ with $k$ elements. Then $(\mathbf{A} + \varepsilon\mathbf{I})_{S,S} = \mathbf{A}_{S,S} + \varepsilon\mathbf{I}_k$ . By (b) and condition (f) of Theorem 19.9.4, $q(\varepsilon) = \det(\mathbf{A}_{S,S} + \varepsilon\mathbf{I}_k) > 0$ for every $\varepsilon > 0$ . By the Leibniz formula, $q$ is a polynomial in $\varepsilon$ , hence continuous by the algebra of limits quoted in Chapter 16’s introduction, so $q(1/m) \to q(0)$ as $m \to \infty$ . A non-strict inequality survives a limit, so $\det\mathbf{A}_{S,S} = q(0) \ge 0$ .
(d) It is an M-matrix (see the Quick check after Lemma 19.9.2). Its principal minors are $1$ , $1$ and $1 - 1 = 0$ , all non-negative. The converse in the remark asks for all principal minors to be non-negative, and $\mathbf{Z}$ of (a) has the principal minor $\det\mathbf{Z}_{\{2\},\{2\}} = -1 < 0$ . Only its leading ones are non-negative, and for the non-strict inequality leading minors are not enough.

Exercise (C3: Non-negative dynamics)

Let $\mathbf{A} \in M_n(\mathbb{R})$ be a Z-matrix, written as $\mathbf{A} = s\mathbf{I} - \mathbf{B}$ with $\mathbf{B} \ge 0$ .

(a) Prove that $e^{-t\mathbf{A}} \ge 0$ for every real $t \ge 0$ .
(b) Suppose $\mathbf{A}$ is a non-singular M-matrix, and let $\mathbf{x}$ be the solution of $\mathbf{x}' = -\mathbf{A}\mathbf{x}$ with $\mathbf{x}(0) = \mathbf{x}_0 \ge \mathbf{0}$ . Prove that $\mathbf{x}(t) \ge \mathbf{0}$ for every $t \ge 0$ and that $\mathbf{x}(t) \to \mathbf{0}$ as $t \to \infty$ .

Hint: split $-t\mathbf{A}$ into two commuting matrices.

Solution.

(a) $-t\mathbf{A} = t\mathbf{B} + (-ts)\mathbf{I}$ , and the two terms commute because every matrix commutes with a multiple of $\mathbf{I}$ . By Theorem 10.9.4 (d), $e^{-t\mathbf{A}} = e^{t\mathbf{B}}e^{-ts\mathbf{I}}$ . Every partial sum of the series for $e^{-ts\mathbf{I}}$ is $\bigl(\sum_{m=0}^{M}(-ts)^m/m!\bigr)\mathbf{I}$ , so $e^{-ts\mathbf{I}} = e^{-ts}\mathbf{I}$ . The series for $e^{t\mathbf{B}}$ converges by Theorem 10.9.3, and its partial sums $\sum_{m=0}^{M}t^m\mathbf{B}^m/m!$ are $\ge 0$ because $t \ge 0$ and $\mathbf{B} \ge 0$ ; a non-strict inequality survives a limit, so $e^{t\mathbf{B}} \ge 0$ . Hence $e^{-t\mathbf{A}} = e^{-ts}e^{t\mathbf{B}} \ge 0$ .
(b) By Theorem 10.9.6, $\mathbf{x}(t) = e^{-t\mathbf{A}}\mathbf{x}_0$ , which is $\ge \mathbf{0}$ for $t \ge 0$ by (a). By Theorem 19.9.4 (d), every eigenvalue of $\mathbf{A}$ has positive real part, so every eigenvalue of $-\mathbf{A}$ has negative real part: $-\mathbf{A}$ is stable. By Theorem 16.6.3, $\mathbf{x}(t) \to \mathbf{0}$ . Both conclusions matter in models of concentrations or populations, which must stay non-negative and, when $-\mathbf{A}$ is stable, die out.