An estimate from one coordinate
A characteristic polynomial can be difficult to solve explicitly. Gershgorin's theorem instead gives regions that contain every eigenvalue, using only the entries of the matrix.
Definition 8.1.1
(Row radius and Gershgorin disc)
Let with . The row radius and the closed row disc of the th row are
The column discs are defined in the same way from the columns of : the column disc centered at has radius .
The discs may overlap, and a radius can be zero. For the only radius is , so is exactly the eigenvalue.
The row-disc theorem
Theorem 8.1.2
(Gershgorin row-disc theorem)
Every complex eigenvalue of lies in .
Proof
(A largest coordinate selects the disc)
If with , choose with . The th coordinate gives
Taking absolute values and using yields
Division by the nonzero proves .
Proof X-ray
Where the largest coordinate is used
The proof has one hypothesis on the vector and one choice. The hypothesis is what makes the maximum positive, so the final division is legal. The choice is the index of a largest coordinate: it is an index for which every other coordinate satisfies , which is the inequality that converts the sum into the row radius times . With any other index the same step would leave a factor that may exceed . The identity is just the th row of with the diagonal term moved to the left, so the eigenvalue equation is used once and only in that row. The argument closes after one division, and it never uses the other eigenvalues or any property of beyond its entries. Because the index depends on the eigenvector, the proof does not say in advance which disc will contain a given eigenvalue.
For a real matrix the discs still lie in , since eigenvalues need not be real. The theorem locates eigenvalues inside the union; it does not say that each disc contains one.
Counterexample mode
Every disc contains an eigenvalue
A tempting strengthening is that each of the discs must contain at least one eigenvalue. Take
Then and , so and . The characteristic polynomial is , so the eigenvalues are , both of modulus . Since , neither lies in , although both lie in . The claim fails, and the eigenvalues are not real even though is real. The correct statement is the one proved above: all eigenvalues lie in the union, with no promise about individual discs.
Corollary 8.1.3
(Column-disc theorem)
Every complex eigenvalue of also lies in the union of the column discs of .
Proof
(Apply the row theorem to the transpose)
The matrix has the same characteristic polynomial as , hence the same eigenvalues. The row discs of are the column discs of , so the row theorem applied to gives the claim.
Therefore every eigenvalue belongs to both unions, though not necessarily to a row disc and a column disc with the same index.
Strict diagonal dominance
Definition 8.1.4
(Strict diagonal dominance)
A matrix is strictly diagonally dominant (by rows) if for every .
Theorem 8.1.5
(Strictly dominant matrices are invertible)
If is strictly diagonally dominant by rows, or by columns, then is invertible.
Proof
(A nonzero kernel vector contradicts dominance)
Suppose with , and choose with . The th equation says , so and hence , contradicting strict dominance in row . So the kernel is and is invertible. Equivalently, the origin lies outside every row disc, so is not an eigenvalue. If the columns are dominant, apply the result to , which is invertible exactly when is.
Concept lensGeometric
Dominance fails exactly on the discs
For a complex number , the matrix has the same off-diagonal entries as and diagonal entries . Hence is strictly diagonally dominant by rows if and only if for every , that is, if and only if . The union of the discs is therefore the set of shifts at which the dominance test is silent, and the invertibility criterion at is the statement that the origin lies outside that union.
The inequalities are sufficient, not necessary.
Common mistake
(A disc containing the origin does not force a zero eigenvalue)
For , the first disc is and contains , and the first row is not strictly dominant, but . The criterion only proves invertibility; when it fails it says nothing. Nor does the basic theorem say that each disc contains an eigenvalue; it only locates eigenvalues in their union.
Worked examples
Worked example 8.1.6
(Row discs of a nonsymmetric matrix)
Consider the real, nonsymmetric matrix
The row discs are
All three exclude zero, so is invertible. Their horizontal ranges show that every eigenvalue has real part in . The theorem alone does not establish that the eigenvalues are real or count how many occur in each disc. As a separate check, direct expansion gives .
Worked example 8.1.7
(Rows fail but columns succeed)
Let . The row radii are and . Row has , so is not strictly dominant by rows. The column radii are for column and for column , and , , so is strictly dominant by columns. Hence is invertible; indeed . The eigenvalues are the roots of , namely and . The column discs are and : the point lies in both, and lies in the first.
Worked example 8.1.8
(Shifting the test to a point other than zero)
Use the matrix of the first example and ask whether is invertible. The distances from to the centers are , , , against the radii , , . Each distance exceeds its radius, so and is strictly dominant, hence invertible. For the distance to the second center is , so and the test is silent: it neither proves nor excludes that is an eigenvalue. For , and , the test is exact, because .
The explorer below draws the row and column discs of A and the computed eigenvalues, and lets you edit the matrix to see when strict dominance proves invertibility and when it is silent.
Exercises with solutions
Quick check
(What are the discs for ?)
Solution · Answer
Both radii are zero; the discs are the singleton sets and .
Quick check
(For the matrix of the first worked example, what is the radius of the first column disc?)
Solution · Answer
The radius is , so that disc is centered at with radius .
Quick check
(Is invertible?)
Solution · Answer
No. Each row is only weakly diagonally dominant and the rows coincide; its determinant is zero.
Quick check
(If a disc contains , must the matrix be singular?)
Solution · Answer
No. The triangular matrix above is an explicit invertible counterexample.