I want to prove that a strictly (row) diagonally dominant matrix $A$ is invertible. Im using the Gershgorin circle theorem. This is my approach:

Gershgorin circle theorem says that every eigenvalue of $A$ satisfies :

$|\lambda - a_{ii}|\leq \sum_{i \neq j} |a_{ij}|$ for some $i $.

Strict dominance implies :

$\sum_{i \neq j} |a_{ij}|< |a_{ii}| $

Putting both together we get the following:

$|\lambda - a_{ii}| < |a_{ii}|$, which implies that $\lambda \neq 0 $. This shows that matrix $A$ is invertible because any matrix $A$ is invertible if and only if $\lambda_{i} \neq 0$.

Is this proof valid?

  • 1
    $\begingroup$ Valid, but you should be more precise about "if and only if $\lambda \ne 0$": what are the quantifiers on $i$? Also, it's overkill to use Gershgorin's theorem when this can be proved by a more direct elementary argument, but that doesn't make the proof invalid. $\endgroup$ – Erick Wong Sep 26 '17 at 23:05

It is valid but as noted the Gershgorin theorem is quite an overkill. A more elementary approach follows.

Let $A=D-B$, where $D$ is the diagonal part of $A$. Let $A$ be row diagonally dominant, that is, $$\tag{1} |a_{ii}|>\sum_{j\neq i}|a_{ij}|\;\iff\; 1>\frac{1}{|a_{ii}|}\sum_{j\neq i}|a_{ij}|, \quad i=1,\ldots,n. $$ The latter inequality is equivalent to $$\tag{2}1>\|D^{-1}B\|_\infty.$$

If $A$ was singular, $Ax=0$ and hence $x=D^{-1}Bx$ for some nonzero $x$. We would have $$ \|x\|_\infty=\|D^{-1}Bx\|_\infty\leq\|D^{-1}B\|_\infty\|x\|_\infty $$ and, dividing by $\|x\|_\infty$, $$ 1\leq\|D^{-1}B\|_\infty, $$ which contradicts (2).


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.