Levy–Desplanques theorem

Remarks

Suppose $Ax = 0$ with $x \ne 0$, and choose $i$ with $\abs{x_i}$ maximal, so $\abs{x_i} > 0$. Row $i$ gives $a_{ii} x_i = -\sum_{j \ne i} a_{ij} x_j$, so $\abs{a_{ii}} \abs{x_i} \le \sum_{j \ne i} \abs{a_{ij}} \abs{x_i}$. This contradicts strict dominance in row $i$. Equivalently, $0$ lies in no disc of the Gershgorin circle theorem.

Example: $\begin{pmatrix} 3 & 1 & 1 \\ 0 & 2 & 1 \\ 1 & -1 & 4 \end{pmatrix}$ is strictly diagonally dominant, so it is invertible without any computation.

Strictness is necessary: $\begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}$ satisfies $\abs{a_{ii}} \ge \sum_{j \ne i} \abs{a_{ij}}$ with equality, and it is singular. The theorem also holds for strict dominance by columns, by applying it to $A^T$.

Going deeper

For a student

The theorem gives a cheap test for invertibility, used for the matrices that arise when differential equations are discretised. For strictly diagonally dominant matrices, the Jacobi and Gauss–Seidel iterations for $Ax = b$ converge. It is the special case "$0$ is not an eigenvalue" of the Gershgorin circle theorem.