# 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. Commented Jul 31, 2013 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)$) Commented Sep 2, 2016 at 19:42

## 4 Answers

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.

• How do you go from the prior to last inequality to the last? $u_j/u_i$ could be a very large number thus taking it out of the absolute value can make it smaller, how do you know the inequality is preserved? Commented Jan 6, 2023 at 1:49
• @Makogan This is because $u_i>0$ was chosen to be the largest entry in the vector $u$ (this is mentioned in the answer just before the string of displayed equations). So, $|u_j/u_i|\leq 1$ for each $j\neq i$. Commented Jan 28, 2023 at 4:17

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. Commented Jul 31, 2013 at 21:31
• Oh, true. Let me correct it.
– OR.
Commented Jul 31, 2013 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$. Commented Jul 31, 2013 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.
Commented Jul 31, 2013 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. Commented Jul 31, 2013 at 22:21

As I couldn't think of focusing on the component of largest magnitude, below was my approach, as a variation of user7530's proof.

Assume that $$\boldsymbol{\mathrm{M}}\boldsymbol{\mathrm{x}} = \boldsymbol{\mathrm{0}}.$$

For each $$i = \overline{1, n},$$ \begin{aligned} \sum_{j = 1}^nx_jm_{ij} &= 0\Rightarrow -x_im_{ii} = \sum_{j = 1,j \neq i}^nx_jm_{ij}\\ \sum_{j = 1, j\neq i}^n|x_i||m_{ij}| \le |x_i||m_{ij}| = |x_im_{ii}| &= \left|\sum_{j = 1, j\neq i}^nx_jm_{ij}\right|\le\sum_{j = 1, j\neq i}^n|x_jm_{ij}| = \sum_{j = 1, j\neq i}^n|x_j||m_{ij}|\\ Q_i &:= \sum_{j = 1, j\neq i}^n(|x_i| - |x_j|)|m_{ij}| \le 0 \end{aligned}

Note that if $$x_i\neq 0,$$ the left most inequality is strictly smaller, then $$Q_i < 0.$$ Also, if $$Q_i = 0\Rightarrow x_i = 0.$$

• If there exists $$x_i \neq 0,$$ as $$Q_i < 0,$$ it must be that $$|x_i| < |x_k|,$$ for some $$k\neq i.$$

• Then comes $$x_k \neq 0,$$ it similarly must be that $$|x_k| < |x_l|,$$ for some $$l\notin \{ k, i\} := D_l,$$ so $$x_l \neq 0.$$

• By continuing this way, as any subsequent index differs from those coming before it, $$D_l$$ will reach a state in which it consists of all indices running from $$1$$ to $$n$$ but one, say $$m.$$

As $$x_l\neq 0,$$ to have $$Q_l < 0$$ valid, it must be that $$|x_l| < |x_m|.$$

So, $$x_m\neq 0.$$ But, as $$|x_m| > |x_k|,\,\forall k\in D_m,$$ which contains at least one index, it must be that $$Q_m > 0.$$ A contradiction because $$Q_m < 0.$$

Alternatively, if taking the idea of focusing on the component that has the largest magnitude, say $$x_m.$$

Therefore, as $$|x_m|\ge |x_i|,\,\forall i = \overline{1, n},$$ then $$Q_m\ge 0.$$ Nevertheless, $$Q_m\le 0,$$ then $$Q_m = 0.$$ This equality holds when all the components of $$\boldsymbol{\mathrm{x}}$$ have the same magnitude, and also $$x_m = 0.$$

So, $$\boldsymbol{\mathrm{M}}\boldsymbol{\mathrm{x}} = \boldsymbol{\mathrm{0}}\Rightarrow\boldsymbol{\mathrm{x}} = \boldsymbol{\mathrm{0}}.$$ This means that the columns of $$\boldsymbol{\mathrm{M}}$$ are linearly independent.

Thus, $$\boldsymbol{\mathrm{M}}$$ is non-singular.

• How do you have the left-most inequality? Commented Jan 1, 2023 at 12:49
• Basically, how do you get the inequality and then the equality $\sum_{j = 1, j\neq i}^n|x_i||m_{ij}| \le |x_i||m_{ij}| = |x_im_{ii}|$? Commented Jan 1, 2023 at 12:52

Let $$D$$ and $$F$$ be the diagonal and the off-diagonal parts of $$M$$ respectively. Let $$\mathbf1$$ be the vector of ones. Since $$M$$ is strictly diagonally dominant, $$(|D|-|F|)\mathbf1$$ is a positive vector, where the notation $$|\cdot|$$ means the entrywise absolute value of a matrix or a vector. Hence $$v^T(|D|-|F|)\mathbf1>0$$ for every nonnegative but nonzero vector $$v$$.

Now, if $$x^TM=0$$, then $$x^TD=-x^TF$$. Hence $$|x|^T|D|=|x^TD|=|x^TF|\le |x|^T|F|$$. In turn, $$|x|^T(|D|-|F|)\mathbf1\le0$$. Therefore $$|x|$$ must be zero, i.e., $$x$$ must be zero. Thus $$M$$ is nonsingular.