# Show that the inverse of a strictly diagonally dominant matrix is monotone

I have been struggling with this problem for awhile. Given that $A$ is a strictly diagonally dominant matrix with positive diagonal entries and non-positive off-diagonal entries, show that $A$ is monotone, i.e. $A^{-1} \geq 0$, meaning $a^{-1}_{ij} \geq 0$ for all $i,j$.

I have looked extensively for some help on this problem but have not come up with anything. Any help or a link to the right resource would help me out immensely!

• What is a "strictly diagonally dominant" matrix? – Timbuc Oct 14 '14 at 3:19
• A strictly diagonally dominant matrix is defined as: $|a_{ii}| > \sum \limits_{j \neq i} |a_{ij}|$ For all rows $i$. – Adam O'Brien Oct 14 '14 at 3:27
• Sorry hit the enter key by accident, see the edited version now. – Adam O'Brien Oct 14 '14 at 3:30
• Ok, but then something's odd imo: in your question, you say the off-diagonal elements of $\;A\;$ are non-positive, which means $$i\neq j\implies a_{ij}\le 0\iff a_{ij}^{-1}\le 0$$ so how do you expect to prove that $\;a_{ij}^{-1}\ge 0\;$ ? – Timbuc Oct 14 '14 at 3:32
• The proof of $A^{-1}\ge 0$ can be found in [Berman, Plemmans - Nonnegative Matrices in the Mathematical Sciences]. The proof relies on several results scattered in the book, which makes it hard to reproduce here. – daw Oct 14 '14 at 7:08

Take the definition:

A real n-by-n matrix $A=[a_{ij}]$ with $a_{ij}\le 0$ for all $i\neq j$ is an M-matrix if $A$ is nonsingular and $A^{-l}\le0$ (this mean that we don't have nonnegative elements)

If $A$ is strictly diagonal dominant, $|a_{jj}|>\sum_{j\neq i, i=1}^n |a_{ij}|$ and $a_{ij}\le0$ $i\neq j$. And now... why $a_{ij}^{-1}$ is nonnegative! Well if you do the Gauss-Jordan procedure to inverse you will note that, you inverse will have all elements positive.

Its it, make the inverse of matrix using elementary rows operations.

• Well, the important part of the proof is missing. – daw Oct 14 '14 at 6:38

$$[A|I]=\left[\begin{array}{ccc|ccc} a_{11} & ... & a_{1n} & 1 & ... & 0 \\ \vdots & \ddots & \vdots & \vdots & \ddots & \vdots\\ a_{n1} & ... & a_{nn} & 0 & ... & 1\end{array}\right]$$

Lets take the augmented system. All rows operation that will do in $A$ you do $I$ in order to transform $A$ in $I$

Perform $L_i=a_{11}L$ and $L_i=L_i-\frac{L_i}{a_{11}}$ for $i=2, \ldots,n$. This will change the matrix, since all elements below the $a_{11}$ will be zero.

Now you want to create zeros below the therm $a_{22}$ of A.

Doing the same process, $L_i=\frac{L_i}{a_{22}}$ and $L_i=L_i-\frac{L_i}{a_{22}}$ for $i=3, \ldots, n$ you will zero below the $a_{22}$. If you continue this process you will have a upper matrix in right hand of aumentad matrix and the leaf is begin to start to show your $A^{-1}$.

I so much thing to write, after this you must create zeros above the diagonal. An finally you just divide by diagonal element. Its will create $[I|A^{-1}]$.

You will see, all elements are positive. You understand? if not, i can shown you by skype. Try see this.

Use induction. Start with $1\times 1$ matrix (can be shown trivially). Then, use the formula for the inverse of block matrix (you need to use the induction hypothesis and the diagonal dominance property for this step).

Step 1: [A is a M-matrix (https://en.wikipedia.org/wiki/M-matrix)] Since 1) A is a Z-matrix (off diagonal is non positive) 2) A's eigenvalues have positive real part (Gershgorin’s Circle theorem) by definition, A is a M-matrix.

Step 2: [inverse of a non-singular M-matrix is nonnegative. ] See (How to prove that an M-matrix is inverse-non-negative?)

Let $D$ be the diagonal part of $A$. We can write $$A=D(I-S)$$ where $S$ has positive elements, ($0$ on the diagonal) and the sum of elements in each row is $<1$. Let $s$ be the maximum row sum of $s$. One checks that for all $n\ge 1$ the maximum row sum of $S^n$ is $\le s^n$. Therefore we get $S^n\to 0$. That implies that the sum $I+S+\cdots +S^n$ converges to $I-S$. Since $S$ has positive entries, so do all the partial sums, and so the limit. Therefore, $(I-S)^{-1}$ has positive entries, and so does $A^{-1}$.

Obs: The proof involves an infinite process. One would like an algebraic proof. It is easy to show that all the leading minors of $A$ are $>0$. Therefore, $A$ has an $LU$ decomposition.Are the off diagonal entries of $L$, $U$ always $\le 0$ ?