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? ;)