Gershgorin Circle Theorem

The Gershgorin circle theorem tells us where a square matrix's eigenvalues can lie without having to calculate them. I first learned it in college, and it has been one of my favorite theorems since. Something reminded me of it today.

Theorem

For each row of a complex square matrix $A$, draw a closed disk in the complex plane centered at $a_{ii}$ with radius $R_i = \sum_{j \neq i} | a_{ij} |$, where $a_{ij}$ are the matrix entries. The radius is the sum of the absolute values of the other entries in that row. Every eigenvalue of $A$ lies in at least one of these Gershgorin circles.

Proof

Let $\lambda$ be an eigenvalue of $A$ and $\mathbf{x}$ its corresponding eigenvector. Choose the largest entry of the eigenvector in absolute value: $i = \arg \max_{k} | x_k |$. The definition of an eigenvalue gives $\sum_{j \neq i} a_{ij} x_j = (\lambda - a_{ii}) x_i$. Apply the triangle inequality and use $| x_j | / |x_i| \leq 1$:

$$|\lambda - a_{ii}| = \left| \sum_{j \neq i} \frac{a_{ij} x_j}{x_i} \right| \leq \sum_{j \neq i} \left| a_{ij} \right| \frac{\left| x_j \right|}{\left| x_i \right|} \leq \sum_{j \neq i} \left| a_{ij} \right|.$$

Visualization

Enter a matrix as an array of arrays of numbers. The visualization shows the circles, but does not calculate the eigenvalues themselves, which takes more work. You can still see the regions where the eigenvalues must lie.