Are non-strictly diagonally dominant matrices nonsingular?

Question

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

Answer 1

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 (wdd);
• 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$.

The nonsingularity of wcdd matrices was first proved in a paper by Shivakumar and Chew. A simple-to-follow proof is also available as Lemma 3.2 in a paper I wrote. Let's summarize:

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.

---

You can actually go further and establish that the Laplacian matrix is an M-matrix: a monotone matrix whose off-diagonals are nonpositive.

To do so, employ the following result:

$$\text{wcdd L-matrix} \iff \text{nonsingular wdd L-matrix} \iff \text{nonsingular wdd M-matrix}.$$

For details, see Theorem 2.24 of a paper I wrote. In the above, we have used the term L-matrix to refer to any matrix with positive diagonals and nonpositive off-diagonals.

Answer 2

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.

Answer 3

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.