Illustrating Gershgorin disks with NumPy

Gershgorin’s theorem gives bounds on the locations of eigenvalues for an arbitrary square complex matrix.

The eigenvalues are contained in disks, known as Gershgorin disks, centered on the diagonal elements of the matrix. The radius of the disk centered on the kth diagonal element is the sum of the absolute values of the elements in the kth row, excluding the diagonal element itself.

To illustrate this theorem, we create a 5 by 5 diagonal matrix and add some random noise to it. The diagonal elements are

0, 3 + i, 4 + i, 1 + 5i, 9 + 2i.

The eigenvalues of the diagonal matrix would simply be the diagonal elements. The additional random values pull the eigenvalues away from the diagonal values, but by an amount no more than Gershgorin predicts.

Gershgorin disks and eigenvalues

Note that in this example, two of the eigenvalues land in the smallest disk. It’s possible that a disk may not contain any eigenvalues; what Gershgorin guarantees is that the union of all the disks contains the union of all the eigenvalues.

Here’s the Python code that created the graph above.

import numpy as np
import matplotlib.pyplot as plt

np.random.seed(202103014)

N = 5 # dimension of our square matrix

D = np.diag([0, 3 + 1j, 4 + 1j, 1 + 5j, 9 + 2j])
M = np.random.rand(N, N) + D

R = np.zeros(N) # disk radii
for i in range(N):
    R[i] = sum(abs(M[i,:])) - abs(M[i,i])

eigenvalues = np.linalg.eigvals(M)

# Plotting code
fig, ax = plt.subplots()
for k in range(N):
    x, y = M[k,k].real, M[k,k].imag
    ax.add_artist( plt.Circle((x, y), R[k], alpha=0.5) )
    plt.plot(eigenvalues[k].real, eigenvalues[k].imag, 'k+')

ax.axis([-4, 12.5, -4, 9])
ax.set_aspect(1)    
plt.xlabel("$x$")
plt.ylabel("$y$")
plt.title("Gershgorin disks and eigenvalues $x + iy$")

6 thoughts on “Illustrating Gershgorin disks with NumPy

  1. I apologize, got the seed wrong in the previous comment. For some random values I get the eigenvalue outside of all circles like for the seed: 3218413686. I use python3.8, hope they have the same random number generator but one can also reproduce by not specifying seed and running the script few dozen times.

  2. Thank you very much for sharing this code!
    And thanks a lot for all the interesting posts in your website!
    I am not used to writing codes in Python (I am trying to learn about it), so maybe I am missing something.
    Is it possible that the coefficients in the diagonal of the random matrix in M should be zero? If they are not zero, I think that the eigenvalues of M could not be centered at the D(k,k) coefficients.
    In addition, I don’t understand why you multiply the radius by alpha=0.5.

  3. Roberto: The disks should be centered at M[k,k], not D[k,k]. That was a typo in my code. Thanks for letting me know.

    The alpha value is the transparency level of the disks. That’s why the circles are darker where they intersect. If we didn’t set alpha, all the disks would be solid blue. We wouldn’t be able to tell that the smallest disk was even there.

  4. I haven’t seen Gershgorin disks since I took a new class called Matrix Analysis with Roger Horn in 1984, using mimeographed galleys of what would eventually become _Matrix Analysis_ by Horn and Johnson.
    https://www.cambridge.org/us/academic/subjects/mathematics/algebra/matrix-analysis-2nd-edition?format=PB&isbn=9780521548236

    It was a revelation. I’ve never had the algebraic temperament, and to see all of those impenetrable results of algebra proven using analysis techniques was liberating. Cauchy sequences of matrices! Power series of matrices! Beautiful.

Leave a Reply

Your email address will not be published.