Diagonally dominant matrices

A diagonally dominant matrix is a complex matrix $B$ with the property that we have $\vert b_{ii}\vert \ge \sum_{j \ne i} \vert b_{ij}\vert$ for all $i$. When all these inequalities are strict, the matrix is called strictly diagonally dominant.

Lemma 1.13.2 (i)   A strictly diagonally dominant complex matrix is nonsingular.

(ii) A symmetric diagonally dominant real matrix with nonnegative diagonal entries is positive semidefinite.

(iii) The multiplicity of the eigenvalue 0 of a symmetric real matrix $B$ with zero row sums and nonpositive off-diagonal entries equals the number of connected components of the graph $\Gamma$ defined on the index set of the rows and columns of $B$, where two distinct indices $i,j$ are adjacent when $b_{i,j} \ne 0$.

Proof:     Let $B = (b_{ij})$ be diagonally dominant, and let $u$ be an eigenvector, say, with $Bu = bu$. Let $\vert u_i\vert$ be maximal among the $\vert u_j\vert$. Then $(b_{ii} - b) u_i = - \sum_{j \ne i} b_{ij} u_j$. In all cases the result follows by comparing the absolute values of both sides.

In order to prove (i), assume that $B$ is singular, and that $Bu = 0$. Take absolute values on both sides. We find $\vert b_{ii}\vert.\vert u_i\vert \le \sum_{j \ne i} \vert b_{ij}\vert.\vert u_j... ...m_{j \ne i} \vert b_{ij}\vert \vert u_i\vert < \vert b_{ii}\vert.\vert u_i\vert$. Contradiction.

For (ii), assume that $B$ has a negative eigenvalue $b$. Then $(b_{ii} - b).\vert u_i\vert \le \vert b_{ii}\vert.\vert u_i\vert$. Contradiction.

For (iii), take $b = 0$ again, and see how equality could hold everywhere in $b_{ii}.\vert u_i\vert \le \sum_{j \ne i} \vert b_{ij}\vert.\vert u_j\vert \le \sum_{j \ne i} \vert b_{ij}\vert \vert u_i\vert = b_{ii}.\vert u_i\vert$. We see that $u$ must be constant on the connected components of $\Gamma$. $\Box$