Gershgorin’s Theorem

We have seen that eigenvalues are the roots of the characteristic polynomial, and therefore may be complex numbers, even when a matrix has entries that are real. This section is devoted to a remarkable theorem proved by S.A. Gershgorin in 1931. Gershgorin’s theorem says that the \(n\) eigenvalues of an \(n \times n\) matrix can be found in a region in the complex plane consisting of \(n\) disks. We explore the theorem for the case \(n=3\) before proving the result. If you have never plotted complex numbers before, you may wish to try Exploration exp:geometry_complex_numbers in Complex Numbers before proceeding.

In the GeoGebra exploration below, you can adjust any of the entries of the \(3 \times 3\) matrix \(A\). The three eigenvalues are plotted as dots in the complex plane. The Gershgorin region is the union of three closed disks whose boundaries are plotted in red. Notice that the eigenvalues are always in the Gershgorin region.

As you experiment with the interactive, see if you can answer the following questions.

1.
Is it always true that each disk contains an eigenvalue? YesNo
2.
What is the center of each disk?
3.
What is the radius of each disk?
4.
Are there some matrices for which one of the disks does not intersect the others? Where none of the disks intersect?
5.
Try using a matrix with complex number entries. How is the visual pattern of eigenvalues for such a matrix different from a matrix whose entries are real numbers?

In the exploration above you were able to see the eigenvalues of a \(3 \times 3\) matrix. The eigenvalues are contained in the Gershgorin region, which consists of three disks.

In general, for an \(n \times n\) matrix \(A=[a_{ij}]\), the Gershgorin region consists of \(n\) disks in the complex plane:

  • The centers of the disks are given by the \(n\) diagonal entries of \(A\).
  • We get the radius of the disk with center \(a_{ii}\) by adding the absolute values of each of the other elements in row \(i\).

We state this all formally in the following theorem.

The fact that (eqn:Gersh_disk) represents a disk in the complex plane is a direct result of the complex distance formula (see Complex Numbers for more information). Before proving Gershgorin’s theorem, we provide an example and a video to aid in understanding exactly what the theorem says.

Let \(\lambda \) be an eigenvalue of \(A\) with corresponding eigenvector \(\vec {x}=\begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix}\) so that \(A\vec {x}=\lambda \vec {x}\). Let \(x_k\) be an entry of \(\vec {x}\) such that \(|x_k|\) is greater than or equal to the absolute value of every other entry in \(\vec {x}\). Then considering row \(k\) of the equation

\[A\begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix}=\lambda \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix}\]
gives us
\[\sum _{j=1}^n a_{kj} x_j = \lambda x_k.\]
Subtracting yields
\[\sum _{j\ne k} a_{kj} x_j = (\lambda - a_{kk}) x_k.\]
Taking the absolute value of both sides, we have
\begin{align} |(\lambda - a_{kk})x_k| &= |\lambda - a_{kk}| |x_k|\label {eqn:pr1} \\ &= \left |\sum _{j\ne k} a_{kj} x_j\right | \label {eqn:pr2} \\ &\le \sum _{j\ne k} |a_{kj} x_j| \label {eqn:pr3} \\ &= \sum _{j\ne k} |a_{kj}| |x_j| \label {eqn:pr4}\\ &\le \sum _{j\ne k} |a_{kj}| |x_k| \label {eqn:pr5} \end{align}

Here equations eqn:pr1 and eqn:pr4 follow from property C2 of Complex Numbers, inequality eqn:pr3 follows from the Triangle Inequality (C12 of Complex Numbers), and we arrive at inequality eqn:pr5 by replacing each \(\vec {x}_j\) in inequality eqn:pr4 by \(\vec {x}_k\).

These inequalties show that \(|\lambda - a_{kk}| \le \sum _{j\ne k} |a_{kj}|\), so \(\lambda \in \Gamma _k(A)\), and hence \(\lambda \in \Gamma (A)\), as desired.

Practice Problems

Problems -

Sketch the Gerhgorin region for each matrix. What, if anything, does the region tell us about the matrix being singular or nonsingular? If the test is inconclusive, test for singularity in some other way.

\(A = \left [ \begin{array}{rr} 1 & i\\ -i & 1 \end{array}\right ]\)

\(\Gamma (A)\) contains \(0\)does not contain \(0\). The test is conclusiveinconclusive.

Matrix \(A\) is singularnonsingular.
\(B = \left [ \begin{array}{cc} 4 & 3 - i \\ 3 + i & 1 \end{array}\right ]\)

\(\Gamma (A)\) contains \(0\)does not contain \(0\). The test is conclusiveinconclusive.

Matrix \(A\) is singularnonsingular.
\(C = \left [ \begin{array}{cc} 2 & 1 + i\\ 1 - i & 3 \end{array}\right ]\)

\(\Gamma (A)\) contains \(0\)does not contain \(0\). The test is conclusiveinconclusive.

Matrix \(A\) is singularnonsingular.
\(D = \left [ \begin{array}{ccc} 1 & 0 & 1 + i\\ 0 & 2 & 0 \\ 1 - i & 0 & 0 \end{array}\right ]\)

\(\Gamma (A)\) contains \(0\)does not contain \(0\). The test is conclusiveinconclusive.

Matrix \(A\) is singularnonsingular.
\(E = \left [ \begin{array}{ccc} 1 & 0 & 0\\ 0 & 1 & 1 + i\\ 0 & 1 - i & 2 \end{array}\right ]\)

\(\Gamma (A)\) contains \(0\)does not contain \(0\). The test is conclusiveinconclusive.

Matrix \(A\) is singularnonsingular.
Let \(A=[a_{ij}]\) be an \(n\times n\) matrix, and let
\[ r_i(A):= \sum _{j \ne i} |a_{ij}| \]
denote the sum of the absolute values of the non-diagonal entries in row \(i\). We say that \(A\) is strictly diagonally dominant if
\[|a_{ii}|>r_i(A)\]
for \(i=1,\dots , n\).

Prove that if a matrix is strictly diagonally dominant then it is nonsingular.

Show that the Gershgorin region cannot contain zero.