# Are non-strictly diagonally dominant matrices nonsingular?

I am trying to find a proof that diagonally dominant matrices (not strictly) are non singular.

For strictly diagonal is proof is here: Strictly diagonally dominant matrices are non singular

• This is false for the matrix $\begin{bmatrix}1&-1\\-1&1\end{bmatrix}$. – LutzL Feb 25 '14 at 10:52
• You could actually post that as an answer. You have proven that the premise is false :) – Dylan Meeus Feb 25 '14 at 11:07

As LutzL stated this is false in general. Another (even more simple) example would be the zero-matrix. But for some kind of (non-strictly) diagonal-dominant matrices you can ensure they are non singular.

Take $A\in\mathbb C^{n\times n}$ with $n\ge2$ and $$\forall\, i,j :\quad\left|a_{i,i}\right|\cdot\left|a_{j,j}\right| \gt r_i(A)\cdot r_j(A)$$ (where $a_{k,k}$ is the $k$-row-diagonal-element and $r_k(A)$ the associated row-sum)

then $A$ is non-singular. The proof is similar to the proof of Gershgorins Theorem.

Note that all strictly diagonal-dominant matrices fullfil this conditions, but also those, where you have non-strictly dominance in exact one row.

This is wrong for the matrix $$\begin{bmatrix} 1&-1\\-1&1 \end{bmatrix}$$

However, there exist important matrices that have equality in more than one row, namely the matrices resulting from discretization of the Laplace operator, or in 1D the second derivative. $$\begin{bmatrix} 2&-1& 0&\dots& 0& 0 \\ -1& 2&-1&\dots& 0& 0 \\ 0&-1& 2&-1& 0& 0 \\ &\vdots& & \ddots & & \vdots\\ 0& 0& 0 & -1& 2&-1 \\ 0& 0& 0 & &-1& 2 \\ \end{bmatrix}$$ Here one needs to carefully compute the eigenvalues to find that they are all inside the unit interval and that Gauß-Seidel still converges, even if very, glacially, slowly.

A large family of matrices that are weakly diagonally dominant (i.e. $|a_{ii}| \geq \sum_{j\neq i} |a_{ij}|$) but are nonsingular are the weakly chained diagonally dominant (WCDD) matrices. In fact, this family includes the Laplace matrix in @LutzL's example.

A definition of WCDD is given below.

Definition: A square complex matrix $A=(a_{ij})$ is said to be WCDD if

• $A$ is weakly diagonally dominant;
• For each row $i$ with $|a_{ii}|=\sum_{j\neq i}|a_{ij}|$, there exists a path $i\rightarrow\cdots\rightarrow r$ in the graph of $A$ such that $|a_{rr}|>\sum_{j\neq r}|a_{rj}|$.

In the definition above, the graph of $A \in \mathbb{C}^{n \times n}$ is the digraph $G=(V,E)$ with $V=\{1,\ldots,n\}$ with an edge $i \rightarrow j$ if and only if $a_{ij} \neq 0$.

An elementary proof (using Gershgorin's theorem) of the nonsingularity of WCDD matrices appears as Lemma 3.2 of a paper I wrote (alternative proofs of this fact predate my work). The result is summarized below.

Theorem: A WCDD matrix is nonsingular.

As an example, consider the $n \times n$ Laplace matrix $$A=\left[\begin{array}{ccccc} 2 & -1\\ -1 & 2 & -1\\ & \ddots & \ddots & \ddots\\ & & -1 & 2 & -1\\ & & & -1 & 2 \end{array}\right].$$ Obviously, $A = (a_{ij})$ is weakly diagonally dominant. Moreover,

• $2 = |a_{11}| > \sum_{j\neq 1} |a_{1j}| = 1$;
• the graph of $A$ contains the path $n \rightarrow (n-1) \rightarrow \cdots \rightarrow 1$.

Therefore, $A$ is WCDD, and hence nonsingular.

It can also be shown that $A$ above is a (nonsingular) M-matrix; see Theorem 3.5 of the same paper.