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 eigenvalues of an matrix can be found in a
region in the complex plane consisting of disks. We explore the theorem
for the case 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
matrix . 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 matrix. The
eigenvalues are contained in the Gershgorin region, which consists of three
disks.
In general, for an matrix , the Gershgorin region consists of disks in the complex
plane:
The centers of the disks are given by the diagonal entries of .
We get the radius of the disk with center by adding the absolute values
of each of the other elements in row .
We state this all formally in the following theorem.
Gershgorin Let be an complex matrix. Then for , we define the absolute deleted row
sum to be
Now we can define the th Gershgorin disk of to be
The Gershgorin region of is defined to be the union of the Gershgorin disks,
i.e.,
Then the eigenvalues of are contained in the Gershgorin region .
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.
(a)
(b)
(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 , are both contained in
(with 2 being on the boundary).
(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 is upper triangular, its eigenvalues are its diagonal entries. These
are the centers of the Gershgorin disks, which proves that the eigenvalues
of are contained in . consists of four disks. The first is centered at with
a radius of , since the absolute value of is 1. The second is centered at 4
with a radius of . The third disk is centered at 2 with a radius of 1. The
fourth disk is centered at with a radius of zero, so in fact, consists only
of the eigenvalue .
Proof of Gershgorin’s Theorem
Let be an eigenvalue of with
corresponding eigenvector so that . Let be an entry of such that is greater
than or equal to the absolute value of every other entry in . Then considering
row of the equation
gives us
Subtracting yields
Taking the absolute value of both sides, we have
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 in inequality eqn:pr4 by .
These inequalties show that , so , and hence , 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.
(a)
(b)
(c)
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 , we see that the zero vector is
not contained in it. It follows that zero cannot be an eigenvalue of matrix
, and we conclude that is nonsingular.
(b)
The Gershgorin region of matrix contains the zero vector, so there we
cannot determine from the Gershgorin region whether or not is singular.
Instead, if we perform Gaussian elimination on matrix , we will see it is
not of full rank, and so is singular.
(c)
The Gershgorin region of matrix contains the zero vector, so again we
cannot determine from the Gershgorin region whether or not is singular.
Observe that is an upper triangular matrix with non-zero entries along
the diagonal. Therefore . We conclude that is non-singular.
Practice Problems
Problems prob:Gersh1-prob:Gersh5 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.
contains does not contain . The test is conclusiveinconclusive.
Matrix is singularnonsingular.
contains does not contain . The test is conclusiveinconclusive.
Matrix is singularnonsingular.
contains does not contain . The test is conclusiveinconclusive.
Matrix is singularnonsingular.
contains does not contain . The test is conclusiveinconclusive.
Matrix is singularnonsingular.
contains does not contain . The test is conclusiveinconclusive.
Matrix is singularnonsingular.
Let be an matrix, and let
denote the sum of the absolute values of the non-diagonal entries in row . We say
that is strictly diagonally dominant if
for .
Prove that if a matrix is strictly diagonally dominant then it is nonsingular.
Show that the Gershgorin region cannot contain zero.