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!
$\endgroup$ 65 Answers
$\begingroup$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.
$\endgroup$ 1 $\begingroup$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$ ?
$\endgroup$ $\begingroup$$$[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.
$\endgroup$ $\begingroup$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).
$\endgroup$ $\begingroup$Step 1: [A is a 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?)
$\endgroup$
