You are about to erase your work on this activity. Are you sure you want to do this?
Updated Version Available
There is an updated version of this activity. If you update to the most recent version of this activity, then your current progress on this activity will be erased. Regardless, your record of completion will remain. How would you like to proceed?
Mathematical Expression Editor
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.
(a)
Is it always true that each disk contains an eigenvalue? YesNo
(b)
What is the center of each disk?
(c)
What is the radius of each disk?
(d)
Are there some matrices for which one of the disks does not intersect the
others? Where none of the disks intersect?
(e)
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.
Gershgorin Let \(A=[a_{ij}]\) be an \(n\times n\) complex matrix. Then for \(1<i<n\), we define the absolute deleted row
sum to be
\[ r_i(A):= \sum _{i \ne j} |a_{ij}|. \]
Now we can define the \(i\)th Gershgorin disk of \(A\) to be
Then the eigenvalues of \(A\) are contained in the Gershgorin region \(\Gamma (A)\).
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.
Plot the eigenvalues and the Gershgorin region of each of the following
matrices.
\(\Gamma (A)\) consists of two disks. The first is centered at 1 with a radius of 1. The
second is centered at 0 with a radius of 2, so we see that the first disk is
contained in the second. The eigenvalues, 2 and \(-1\), are both contained in \(\Gamma (A)\)
(with 2 being on the boundary).
(b)
\(B\) is a matrix with complex entries, which makes for a more interesting
Gershgorin region. See Complex Matrices for more on matrices like this
one.
Since \(B\) is upper triangular, its eigenvalues are its diagonal entries. These
are the centers of the Gershgorin disks, which proves that the eigenvalues
of \(B\) are contained in \(\Gamma (B)\). \(\Gamma (B)\) consists of four disks. The first is centered at \(1+i\) with
a radius of \(2\), since the absolute value of \(i\) is 1. The second is centered at 4
with a radius of \(\sqrt {2}\). The third disk is centered at 2 with a radius of 1. The
fourth disk is centered at \(-1\) with a radius of zero, so in fact, consists only
of the eigenvalue \(-1\).
Proof of Gershgorin’s Theorem 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
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.
Sketch the Gershgorin region for each matrix and, if possible, use it as an aid for
determining whether or not the matrix is singular.
We can check our sketches of the Gershgorin regions using the GeoGebra interactive
in Exploration init:GershDisks3x3.
(a)
If we sketch the Gershgorin region of matrix \(A\), we see that the zero vector is
not contained in it. It follows that zero cannot be an eigenvalue of matrix
\(A\), and we conclude that \(A\) is nonsingular.
(b)
The Gershgorin region of matrix \(B\) contains the zero vector, so there we
cannot determine from the Gershgorin region whether or not \(B\) is singular.
Instead, if we perform Gaussian elimination on matrix \(B\), we will see it is
not of full rank, and so \(B\) is singular.
(c)
The Gershgorin region of matrix \(C\) contains the zero vector, so again we
cannot determine from the Gershgorin region whether or not \(C\) is singular.
Observe that \(C\) is an upper triangular matrix with non-zero entries along
the diagonal. Therefore \(\det {C}\neq 0\). We conclude that \(C\) is non-singular.
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.