Skip to content
Tutorials Center
My learning

Topics

Lesson 37 of 62 ยท Eigenvalues and Decompositions

Gershgorin Circles and Eigenvalue Bounds

Use the Gershgorin circle theorem to locate eigenvalues from the rows of a matrix, test invertibility with diagonal dominance, and bound the spectral radius.

Finding eigenvalues exactly means solving a polynomial equation of degree n, which is hard by hand. Often you do not need exact values: you only want to know whether all eigenvalues are positive, whether they are all inside the unit circle, or whether the matrix is invertible. The Gershgorin circle theorem gives rough but rigorous answers from nothing more than the entries of the matrix, in a few lines of arithmetic.

It builds on eigenvalues and eigenvectors and is the reason behind a convergence guarantee for the iterative methods in Iterative Solvers.

The theorem

Take an n ร— n matrix A with entries a_ij (real or complex). For each row i, let the radius be the sum of the absolute values of the off-diagonal entries in that row:

TEXT
R_i = ฮฃ_{j โ‰  i} |a_ij|

The Gershgorin disc D_i is the set of complex numbers within distance R_i of the diagonal entry a_ii. Then:

Every eigenvalue of A lies in at least one Gershgorin disc.

Why it is true. Let Av = ฮปv and choose i where |v_i| is the largest component of v. Row i of the equation says ฮป v_i = a_ii v_i + ฮฃ_{jโ‰ i} a_ij v_j, so (ฮป - a_ii) v_i = ฮฃ_{jโ‰ i} a_ij v_j. Taking absolute values, |ฮป - a_ii| |v_i| โ‰ค ฮฃ |a_ij||v_j| โ‰ค R_i |v_i|. Dividing by |v_i| โ‰  0 gives |ฮป - a_ii| โ‰ค R_i. โˆŽ

Two refinements make the theorem sharper:

  • Columns work too. A and Aแต€ have the same eigenvalues, so you may use column sums for the radii instead, and then every eigenvalue is also in the union of those discs. Using the better of the two usually tightens the estimate.
  • Isolated groups. If a union of k discs does not overlap with the remaining discs, then exactly k eigenvalues (counted with multiplicity) lie in that union.

For a real matrix, the eigenvalues come in conjugate pairs and the discs are centered on the real axis, so a disc lying entirely in the right half plane (for example, in Re > 0) guarantees real part positive for the eigenvalues it contains.

Gershgorin in four steps

Center The diagonal entry a_ii.
Radius Sum of the other entries in row i.
Disc All points within the radius.
Conclusion Every eigenvalue lies in some disc.
1 / 2

Strict diagonal dominance

If every disc avoids the origin, then 0 is not an eigenvalue, and the matrix is invertible. A disc avoids the origin when |a_ii| > R_i. A matrix with this property in every row is called strictly diagonally dominant, and it is always invertible. Many matrices from applications (discretized differential equations, graph Laplacians plus a shift, well-conditioned covariance matrices) have this property, and then Gauss-Seidel and Jacobi iterations are guaranteed to converge.

If a symmetric matrix is also strictly diagonally dominant with positive diagonal, all discs sit in the positive half-line, so all eigenvalues are positive and the matrix is positive definite, which is a quick sufficient test before attempting a Cholesky factorization.

The theorem also bounds the spectral radius ฯ(A) (the largest eigenvalue modulus): ฯ(A) โ‰ค max_i (|a_ii| + R_i), which is the maximum absolute row sum. That is the same as the infinity norm of A.

Python Gershgorin discs, containment and diagonal dominance

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In matrix A every disc misses the origin, so A is invertible without computing a single eigenvalue. In B the discs overlap and the theorem only says where eigenvalues can be, not how many are in each disc. In the isolated example, the discs centered at 10, 5 and 1 are so far apart that each one contains exactly one eigenvalue, very near its center.

Using the theorem in practice

  • Quick invertibility check: |a_ii| > ฮฃ_{jโ‰ i} |a_ij| in every row (or column).
  • Stability of a system x' = Ax: if every disc lies in the left half-plane (a_ii + R_i < 0), all eigenvalues have negative real part and the system is stable.
  • Convergence of iteration x_{k+1} = Mx_k: if max_i(|m_ii| + R_i) < 1, then the spectral radius is below 1 and the iteration converges.
  • Scaling to improve bounds: similar matrices have the same eigenvalues, so forming Dโปยน A D with a diagonal D can shrink the discs, which gives a sharper estimate.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What are the center and radius of the Gershgorin disc for row i?

    The disc is centered at the diagonal entry and its radius is the sum of the absolute values of the other entries in that row.
  2. 2. A matrix is strictly diagonally dominant. What can you conclude?

    No Gershgorin disc contains 0, so 0 is not an eigenvalue and the matrix is invertible.
  3. 3. For A = [[5, 1], [2, 4]], which interval contains a real eigenvalue according to the row discs?

    Row 1 gives center 5 and radius 1, so [4, 6]. Row 2 gives center 4 and radius 2, so [2, 6]. The eigenvalues are 3 and 6, and 6 lies in [4, 6].
  4. 4. Can you use column sums instead of row sums for the radii?

    The transpose has the same eigenvalues, so the theorem applies to the columns as well.
  5. 5. Which bound on the spectral radius follows from the theorem?

    Every eigenvalue has modulus at most |a_ii| + R_i for some i, and that is at most the largest absolute row sum.

Summary

  • Each Gershgorin disc is centered at a diagonal entry a_ii with radius R_i = ฮฃ_{jโ‰ i} |a_ij|; every eigenvalue lies in at least one disc, and column discs work equally well.
  • A union of k discs disjoint from the others contains exactly k eigenvalues.
  • Strict diagonal dominance (|a_ii| > R_i for all i) implies invertibility, and for symmetric matrices with a positive diagonal it implies positive definiteness.
  • The spectral radius is at most the largest absolute row sum.

Next: Cayley-Hamilton Theorem, another way to learn about a matrix from its characteristic polynomial.