Where are Eigenvalues?

Semyon Gershgorin
The diagonal entries of a diagonal matrix are its eigenvalues. For an arbitrary matrix it is possible to give quantitative bounds for how much each diagonal entry can differ from an eigenvalue. The corresponding statement is known as the Gershgorin circle theorem may be used to bound the spectrum of a square matrix. It was first published by the Soviet mathematician Semyon Aronovich Gershgorin in 1931. Gershgorin's name has been transliterated in several different ways, including Geršgorin, Gerschgorin, Gershgorin, Hershhorn, and Hirschhorn.

Theorem (Gershgorin): Let \( {\bf A} = \left[ a_{ij} \right] \) be a square n×n matrix, when n ≥ 2. Then the spectrum of matrix A is a subset of

\[ \sigma ({\bf A}) \subseteq G({\bf A}) = \cup_{k=1}^n G_k ({\bf A}) \]
in which
\[ G_k ({\bf A}) = \left\{ z \in \mathbb{C} \,:\, |z- a_{kk} | \le R_k ({\bf A}) \right\} \]
is a disk in the complex plane whose center is at the point akk and whose radius is the deleted absolute row sum:
\[ R_k ({\bf A}) = \sum_{j\ne k} \left\vert a_{kj} \right\vert . \]
Let λ be an eigenvalue of a square n×n matrix A, with n≥2. Then for the corresponding eigenvector x = [x1, x2, ... , xn]T , we have
\[ \lambda\,x_i = \sum_{j=1}^n a_{ij} x_j = a_{ii} + \sum_{j\ne i} a_{ij} x_j , \qquad i = 1,2,\ldots , n, \]
which we express as
\[ \left( \lambda - a_{ii} \right) x_i = \sum_{j\ne i} a_{ij} x_j , \qquad i = 1,2,\ldots , n. \]
Let k be any index such that
\[ |x_k | = \| {\bf x} \|_{\infty} = \max_j \left\{ |x_1 | , |x_2 | , \ldots , |x_n | \right\} , \]
which is nonzero because x0. Setting i to be that value of k, we get
\[ \left\vert \lambda - a_{kk} \right\vert = \left\vert \sum_{j\ne k} a_{ij} \, \frac{x_j}{\| {\bf x} \|_{\infty}} \right\vert . \]
The choice of k guarantees that each of the quotient in the above equation has modulus at most 1. The triangle inequality ensures that
\[ \left\vert \lambda - a_{kk} \right\vert \le \sum_{j\ne k} \left\vert a_{ij} \right\vert \left\vert \frac{x_j}{\| {\bf x} \|_{\infty}} \right\vert \le \sum_{j\ne k} \left\vert a_{ij} \right\vert = R_k ({\bf A}) , \]
and hence \( \lambda \in G_k ({\bf A}) \subseteq G({\bf A}) . \)
The disks \( G_k ({\bf A}) = \left\{ z \in \mathbb{C} \,:\, |z- a_{kk} | \le R_k ({\bf A}) \right\} \) are c alled the Gershgorin disks; their boundaries are referred to as the Gershgorin circles. The set \( G({\bf A}) = \cup_{k=1}^n G_k ({\bf A}) \) is the Gershgorin region of matrix A.