In looking for a proof to the Gerschgorin's Theorem, I stumbled across this paper: http://buzzard.ups.edu/courses/2007spring/projects/brakkenthal-paper.pdf

I don't quite buy the proof for Theorem 2.1 in that paper (yet).

Theorem 2.1: every eigenvalue $\lambda$ of a square matrix $A\in \mathbb{C}^{n\times n}$ satisfies $$ \vert \lambda - A_{ii}\vert \leq \sum_{j\neq i}\vert A_{i,j}\vert , i\in \{1,2,\ldots,n\} $$

And the proof offered:

If Theorem 2.1 is not satisfied, then $\lambda I-A$ is strictly diagonally dominant (SDD).

$\Rightarrow$ $\lambda I - A$ is non-singular

$\Rightarrow$ $\lambda$ is not an eigenvalue of $A$

My problem lies with

Theorem not satisfied $\Rightarrow$ $\lambda I - A$ is SDD


I mean, the author also states that

the matrix $\lambda I - A$ is SDD if $\vert \lambda - A_{ii}\vert > \sum_{j\neq i}\vert A_{i,j}\vert$ for every i

But the way I see it, the theorem is already not satisfied if $$\vert \lambda - A_{ii}\vert > \sum_{j\neq i}\vert A_{i,j}\vert$$ were to hold for some $i$ while $$\vert \lambda - A_{kk}\vert \leq \sum_{j\neq k}\vert A_{k,j}\vert$$ for some $k\neq i$, in which case $\lambda I - A$ would not be SDD.

What am I missing?

  • $\begingroup$ Not sure if I get the issue, but Gershgorin's disc theorem says all eigenvalues must lie is in the union of the discs. As far as I understand an eigenvalue can by continuity escape from the disc it's centered on by diagonal element when that disc starts overlapping other discs. $\endgroup$ – mathreadler Jan 18 '17 at 13:43
  • 1
    $\begingroup$ @mathreadler What you are saying is that if you reverse the quantifiers, i.e. if you say "for all $i$ there exists an eigenvalue $\lambda$ such that $|\lambda-A_{ii}| \leq \sum_{i \neq j} |A_{ij}|$ is not true. As I recall that is indeed correct. But that, and the refined version of the theorem that is true, is not what is at issue here. This is just about the basic version. $\endgroup$ – Ian Jan 18 '17 at 14:12

The issue is the quantifiers, which this proof has suppressed. The statement of the theorem is: for any eigenvalue $\lambda$ there exists $i$ such that $|\lambda - A_{ii}| \leq \sum_{j \neq i} |A_{ij}|$. The negation of that would be that there exists an eigenvalue $\lambda$ such that for all $i$ we have $|\lambda-A_{ii}| > \sum_{j \neq i} |A_{ij}|$. But this means $\lambda I - A$ is SDD, which means it is nonsingular, which contradicts the assumption that $\lambda$ is an eigenvalue.


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.