1
$\begingroup$

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

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

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.