GERSHGORIN CIRCLE THEOREM

Gershgorin Circle Theorem is a pretty neat theorem in linear algebra that provides a simple yet powerful way to bound the eigenvalues of a square matrix. I was first introduced to this during college, and it has been one of my favorite theorems since then. Today I was reminded of this theorem.

Theorem

Define Gershgorin circle in a complex plane to be a closed disk centered at aiia_{ii} with radius Ri=∑j≠i∣aij∣R_i = \sum_{j \neq i} | a_{ij} |, where aija_{ij} are the elements of a complex square matrix AA. Then every eigenvalue of a square complex matrix AA lies within the union (or equivalently at least one) of the Gershgorin circles.

Proof

Let λ\lambda be an eigenvalue of AA and x\mathbf{x} be the corresponding eigenvector. Find ii such that i=arg⁡max⁡k∣xk∣i = \arg \max_{k} | x_k |. Then we have ∑j≠iaijxj=(λ−aii)xi\sum_{j \neq i} a_{ij} x_j = (\lambda - a_{ii}) x_i from the definition of eigenvalue. We can apply triangle inequality and let ∣xj∣/∣xi∣≤1| x_j | / |x_i| \leq 1 to get

∣λ−aii∣=∣∑j≠iaijxjxi∣≤∑j≠i∣aij∣∣xj∣∣xi∣≤∑j≠i∣aij∣.|\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

We can visualize the Gershgorin circles for the matrix A=[4−10−13−10−12]A = \begin{bmatrix} 4 & -1 & 0 \\ -1 & 3 & -1 \\ 0 & -1 & 2 \end{bmatrix}.

The eigenvalues are 3±33 \pm \sqrt{3} and 33, which all lie within the circles.