On the "Gershgorin circle theorem": How to bound the eigenvalues beautifully!

Gershgorin circle theorem is really simple despite its fancy name. I got to know this theorem during my PhD, when I was working on the solvability of numerical methods, and I needed to show that the spectrum of the system I had to solve did not contain the origin. Here, I give a very brief introduction to this thereom.

.

---

Let's start from the end, the theorem! Gershgorin circle theorem says that, given a square matrix A, no eigenvalue can be located outsides a finite number of discs.

More precisely, for every row $i$, we consider the disc $D(a_{ii},R_i)$ with

• center $a_{ii}$ (the diagonal entry of $i$-th row)
• radius $R_i:=\sum_{j\neq i }|a_{ij}|$ (sum of off-diagonal entries)

Then, every eigenvalue lies within at least one of discs $D(a_{ii},R_i)$.

Consider a very simple case of a $3\times 3$ matrix: $$A = \begin{bmatrix} 2 & 0.5 & 0.5\\ 0 & 5 & 1\\ 1 & 1 & 8\\ \end{bmatrix}$$ We can easily see that there are three discs: $$D(2,1), \quad D(5,1), \quad D(8,2)$$ which contain the eigenvalues $1.95, 7.76, 5.3$: (you can find the jupyter notebook here)

The proof of this theorem is quite easy. One just needs to use the definition of the eigenvalue $Ax=\lambda x$ and the triangle inequality to show that $\boxed{|\lambda-a_{ii}|\leq R_i}$. The way that Semyon Aronovich Gershgorin proved it in 1931 is a bit different though, but similar.

He first started from another ansatz which was an extension of the work of Levy:

Then, based on this, he stated his own beautiful result:

Note that this bound gets better as the off-diagonal part gets smaller (so smaller radius). The limit case is a diagonal matrix!

Brainteaser:

Now, can you answer why diagonally dominant matrices are really desired in numerical analysis? ;)