How to prove that an M-matrix is inverse-non-negative?

Question

Wikipedia says that

The inverse of any non-singular M-matrix is a non-negative matrix."

To be more precise, if $A$ is an M-matrix, then the entries of the inverse of $A$ are all non-negative, i.e. $A^{-1} \geq 0$.

How do I prove this result?

Answer 1

Let $A$ be a real matrix with entries $a_{ij}$ be an $M$ matrix. We have:

• $a_{ij} \leq 0$ when $i \neq j$
• the eigenvalues of $A$ have positive real part

Let $s$ be equal to the greatest diagonal entry of $A$ (which must be positive! otherwise, $A$ would have a negative eigenvalue). We can rewrite $A$ as $A = sI - B$, where $B$ is a non-negative matrix.

By the Perron-Frobenius theorem, $B$ must have a positive eigenvalue equal to $\rho(B)$.

Furthermore, for any eigenvalue $\lambda$ of $B$, $s - \lambda$ is an eigenvalue of $A$. Thus, $s - \rho(B)$ is an eigenvalue of $B$. Since the eigenvalues of $A$ all have positive real part, we note that $$ \text{Re}(s - \rho(B)) > 0 \implies \rho(B) < s $$ So, we have $\rho(B) < s$. Denote $B' = \frac 1s B$. We note that $\rho(B') = \rho(B)/|s| < 1$.

Let $A' = \frac 1s A = I - B'$. Since $\rho(B') < 1$, we can show that the infinite series $\sum_n (B')^n$ converges. More importantly, we note that (defining the zeroeth power to be the identity), $$ A' \sum_{n=0}^\infty (B')^n = (I - B') \sum_{n=0}^\infty (B')^n = \left(\sum_{n=0}^\infty (B')^n \right) - \left(\sum_{n=1}^\infty (B')^n \right) = (B')^0 = I $$ Thus, we have $$ A^{-1} = (sA')^{-1} = \frac 1s(A')^{-1} = \frac 1s \sum_{n=0}^\infty (B')^n. $$ Since $A^{-1}$ is a positive multiple of the sum of non-negative matrices, it must be non-negative.

Answer 2

Take home messages:

If $B$ is small ($\rho(B)<1$) then the inverse of $I-B$ is the sum of the convergent series $I + B + B^2 + \cdots$.

Moreover, if $B$ has all its entries $\ge 0$, then so does $B^k$ for all $k$. If the above series is convergent the same for its sum.

So it's all about in cases of interest that $B$ is small. For instance, if we use some norm on the space and $\|B\|<1$ for that norm.

Note: it may well be that $B$ has all entries positive, $I-B$ is invertible, yet $(I-B)^{-1}$ does not have entries positive. Note that the invertibility condition is $1 \ne \sigma(B)$ ($1$ is not in the spectrum of $B$), which is weaker than $\rho(B) <1$. The problem is that we cannot use the Neumann series to get the inverse of $I-B$. In fact, for any matrix $B$ the Neumann series converges if and only if $\rho(B)<1$.