What can matrix entries tell us?
Computing all eigenvalues can be expensive or sensitive to perturbations. Before running an eigensolver, simple bounds can show that a matrix is invertible, locate candidate eigenvalue regions, or check a computed answer. Gershgorin's theorem uses the diagonal entry in each row as a center and the sum of the magnitudes of the other entries as a radius.
Definition 5.1.1
(Gershgorin disks)
Let . The th row radius and the th Gershgorin (row) disk are
The disks are closed, so their boundary circles belong to them. Disks built from column sums are the row disks of .
Theorem 5.1.2
(Gershgorin theorem)
Every eigenvalue of lies in .
Proof
(Largest coordinate of an eigenvector)
Let with . Choose for which . The th equation yields
Divide by to obtain , that is, .
The proof identifies at least one disk containing the eigenvalue; it does not identify a predetermined disk for each eigenvalue. Applying the same theorem to , which has the same characteristic polynomial as , gives a second enclosure using column sums. Every eigenvalue lies in the intersection of the row-disk union and the column-disk union.
Common mistake
(An enclosure is not an error bound)
A Gershgorin disk says where exact eigenvalues can be; it does not say how far a value computed by an algorithm is from the nearest exact eigenvalue. To certify a numerical eigenvalue more tightly, one needs residual estimates, spectral separation or conditioning information. Nonnormal matrices can have eigenvalues that are sensitive even when every matrix entry changes only slightly.
Separated disks and eigenvalue counts
There is a stronger result when a group of disks is separated from the rest.
Theorem 5.1.3
(Separated-cluster theorem)
If the union of of the disks is disjoint from the union of the other disks, then the first union contains exactly eigenvalues, counted with algebraic multiplicity.
Proof
(Shrinking the off-diagonal part to zero)
Write , where is diagonal, and consider for . Its row disks have the same centers and radii , so the two designated unions remain disjoint and stay inside their disjoint original compact unions. At , the first union contains exactly the diagonal eigenvalues corresponding to its disks, counted with multiplicity; no diagonal entry from the other group can lie there.
The roots of the characteristic polynomial depend continuously on its coefficients as a multiset, and the coefficients depend continuously on . Since the two compact original unions are separated by a positive distance, no root can move from one to the other along this path without leaving their union. Gershgorin excludes that possibility. Hence the count is constant from to . This argument uses continuity of polynomial roots; it does not assert that individual eigenvalues can always be labeled by differentiable functions of .
Proof X-ray
A count needs more than containment
The first theorem puts each eigenvalue somewhere in the union. To count a separated cluster, shrink the off-diagonal part continuously to zero: at the diagonal matrix the count is obvious, and the gap prevents eigenvalues from crossing between the two unions. Algebraic multiplicity is essential when roots coincide.
The next example shows that the separation hypothesis cannot simply be dropped when one wants a count for a single disk.
Counterexample mode
A disk may contain no eigenvalue by itself
For , the row disks have centers and radii . The characteristic polynomial is , so both eigenvalues equal and the small disk around contains none. The disks overlap, so the separated-cluster theorem does not apply to the small disk alone.
Worked examples
Worked example 5.1.4
(Invertibility by strict diagonal dominance)
If in every row, then zero belongs to none of the disks. Gershgorin therefore rules out zero as an eigenvalue, so is invertible. This is sufficient, not necessary: is invertible although its first row is not strictly diagonally dominant.
Worked example 5.1.5
(A separated eigenvalue)
For
the row disks are centered at with radii . They are pairwise disjoint, so each contains exactly one eigenvalue. The matrix is real symmetric, so its eigenvalues are real; consequently they lie in the real intervals , , and . For any real matrix with pairwise disjoint disks, conjugation symmetry together with the one-eigenvalue count also forces each eigenvalue to be real. Without separation, real matrices can have nonreal eigenvalues.
Worked example 5.1.6
(Eigenvalues on the boundary of a disk)
Let . Both rows give center and radius , so . The characteristic polynomial is , so the eigenvalues are and . Both lie on the boundary circle, which is why the disks must be closed. The union of the two disks is a single disk, and it contains eigenvalues, in agreement with the separated-cluster theorem for (the other group is empty). In particular , so Gershgorin cannot exclude zero, and indeed is singular.
Common mistake
(Weak diagonal dominance does not give invertibility)
The condition in every row allows zero to sit on the boundary of a disk. The matrix above satisfies in both rows, yet . Strict inequality in every row is what removes zero from all the disks.
Practice and solutions
Quick check
(Locate the eigenvalues of in two real intervals, and count them.)
Compute the row radii first.
Solution · Answer
The row disks have centers and and both radii equal , so they are disjoint and the separated-cluster theorem gives exactly one eigenvalue in each. The matrix is real symmetric, so its eigenvalues are real, and therefore one lies in and one in .
Quick check
(Prove that a matrix satisfying strict row diagonal dominance, for every , is invertible.)
Where does zero sit relative to the disks?
Solution · Answer
If then , that is , which contradicts strict dominance. So zero lies outside every disk. By Gershgorin's theorem every eigenvalue lies in the union of the disks, so zero is not an eigenvalue, , and is invertible.
Quick check
(For , compare the row-disk and column-disk unions.)
Row gives a row disk; column gives a column disk.
Solution · Answer
The row disks have centers and radii ; the column disks have centers and radii . Both unions are valid enclosures, but they differ: the row union contains and the column union does not, so the intersection of the two unions is smaller than either one. The exact eigenvalues (the diagonal, since is triangular) are and , which lie in both unions.
Quick check
(If an approximate value lies outside every row disk of a matrix, can it be an exact eigenvalue?)
Recall what Gershgorin's theorem says about every exact eigenvalue.
Solution · Answer
No. Every exact eigenvalue lies in the union of the row disks, so a value outside all of them is not an eigenvalue. The converse direction is different: a value inside a disk need not be an eigenvalue, and the theorem does not by itself quantify the error of an approximation.