Strictly diagonally dominant matrices are non singular

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.