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

Question

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!

Answer 1

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)^{-1}$. 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$ ?

Answer 2

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?)

Answer 3

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.

Answer 4

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).

Answer 5

$$[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.