# Strictly diagonally dominant matrices are non singular

I try to find a good proof for invertibility of strictly diagonally dominant matrices (defined by $|m_{ii}|>\sum_{j\ne i}|m_{ij}|$). There is a proof of this in this paper but I'm wondering whether there are are better proof such as using determinant, etc to show that the matrix is non singular.

• Use Gershgorin's theorem. Wiki has the proof. – TZakrevskiy Jul 31 '13 at 21:15
• The above can be generalized to the larger class of weakly chained diagonally dominant matrices. For an elementary proof of the nonsingularity, also using Gershgorin's theorem, see arxiv.org/pdf/1510.03928v2.pdf Definition 3.1 and Lemma 3.2 on page 5. Note that nonsingularity is not necessarily true for weakly diagonally dominant matrices (a simple counterexample is $\left(\begin{array}{cc} +1 & -1\\ -1 & +1 \end{array}\right)$) – parsiad Sep 2 '16 at 19:42

The proof in the PDF (Theorem 1.1) is very elementary. The crux of the argument is that if $M$ is strictly diagonally dominant and singular, then there exists a vector $u \neq 0$ with $$Mu = 0.$$

$u$ has some entry $u_i > 0$ of largest magnitude. Then

\begin{align*} \sum_j m_{ij} u_j &= 0\\ m_{ii} u_i &= -\sum_{j\neq i} m_{ij}u_j\\ m_{ii} &= -\sum_{j\neq i} \frac{u_j}{u_i}m_{ij}\\ |m_{ii}| &\leq \sum_{j\neq i} \left|\frac{u_j}{u_i}m_{ij}\right|\\ |m_{ii}| &\leq \sum_{j\neq i} |m_{ij}|, \end{align*} a contradiction.

I'm skeptical you will find a significantly more elementary proof. Incidentally, though, the Gershgorin circle theorem (also described in your PDF) is very beautiful and gives geometric intuition for why no eigenvalue can be zero.

I would probe it a bit tangentially. And not because it will be simpler, but because it gives an excuse to show an application. I would take an iterative method, like Jacobi's, and show that it converges in this case; and that it converges to a unique solution. This, incidentally implies the matrix is non-singular.

How does it work exactly?

For the system $Ax=b$, Jacobi's method consists in writing $A=D+R$, where $D$ is diagonal and $R$ has zeros in the diagonal. Then you define the recurrence

$$x_{n+1}=D^{-1}(b-Rx_{n}).$$

Now we can show that it converges.

We have

\begin{align}||x_m-x_n||&=||\sum_{k=n}^{m}(D^{-1}R)^kb-((D^{-1}R)^{m}-(D^{-1}R)^{n})x_0||\\ &\leq\sum_{k=n}^{m}||D^{-1}R||^k||b||+\left(||D^{-1}R||^m+||D^{-1}R||^n\right)||x_0|| \end{align}

For the norm $||\cdot||:=||\cdot||_{\infty}$, the matrix norm is bounded by the maximum of the sums of the absolute values of its entries in each row. Therefore $$||D^{-1}R||$$ is less than some number less than $1$. For this reason the sum above can be as small as you want for $n,m$ large. This shows the convergence of the sequence.

If it clear too that it has to converge to any solution of the system $Ax=b$. To see this we use the same argument above but placing a solution $x$ in place of $x_m$. We use that $Ax=b$, i.e. $x=D^{-1}(b-Rx)$ and we get it. So $x_n$ converges to any solution. Since it is a convergent sequence it converges to only one thing so there is only one solution to the system.

• Nice reversion of the usual teaching order :-) However, $\|D^{-1}\|$ seems not necessarily $<1$ to me (should not be required anyway), and I do not see the uniqueness from the mere convergence yet. – ccorn Jul 31 '13 at 21:31
• Oh, true. Let me correct it. – OR. Jul 31 '13 at 21:35
• The fact that every such sequence converges does not imply that all the sequences have the same limit. However, it would be sufficient to show that given any particular solution $x^*$, starting with any distance from that $x^*$ decreases that distance by a factor strictly less than $1$. – ccorn Jul 31 '13 at 22:06
• Yes, I am, if not saying, trying to say what you just said. When you put that $x^{*}$ instead of $x_m$ in the inequalities above, that is what you prove: That $x_n\rightarrow x^{*}$. Therefore it happens for any solution $x^{*}$ the system may have. Since the sequence converges and the limit is unique then there is a unique $x^{*}$. – OR. Jul 31 '13 at 22:08
• So it could be cleaned up to: $x_{n+1}-x^* = -D^{-1}R(x_n-x^*)$. No $\sum$ required. Then the norm estimate, and you are done. – ccorn Jul 31 '13 at 22:21

## protected by Zev ChonolesSep 12 '16 at 18:44

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).