Gerschgorin's Circle Theorem

Let $\mathbf{A}$ be an $n \times n$ matrix.

Define the disks (i.e., circles) in the complex plane, for $i = 1, 2,...,n$, by
$$\mathcal{D}_i = \left\lbrace z : |a_{ii} - z | \leq \sum_{j \neq i} |a_{ij}| \right\rbrace$$ Then all the eigenvalues of $\mathbf{A}$ lie in the union of the disks
$$\bigcup_{i=1}^n \mathcal{D}_i$$ Moreover, if $k$ disks are disjoint then there are exactly $k$ eigenvalues lying in the union of these $k$ disks.

For a diagonal matrix, these discs coincide with the spectrum.

Example

The python program attached below can be used to visualize the Gerschgorin discs $\mathcal{D}_i$ and the actual eigenvalues on a complex plane.

A = np.matrix('5. 3. 2.;4., 6., 5.; -3., 1., 4.')
demoGerschgorin(A)

produces the plot:

The discs are centered around the diagonal elements (5,0), (6, 0), and (4, 0) with radius 5, 9, and 4 respectively. Since the matrix is real, the centers all line up on the real axis.

The eigenvalues of this matrix are approximately 0.92,  7.04+0.70j, and 7.04-0.70j, which are shown by the blue, green, and red dots respectively.

Python Program

	import numpy as np
	import matplotlib
	from matplotlib.patches import Circle
	from matplotlib.collections import PatchCollection
	import matplotlib.pyplot as plt
	from numpy import linalg as LA
	def demoGerschgorin(A):
	n = len(A)
	eval, evec = LA.eig(A)
	patches = []
	# draw discs
	for i in range(n):
	xi = np.real(A[i,i])
	yi = np.imag(A[i,i])
	ri = np.sum(np.abs(A[i,:])) - np.abs(A[i,i])
	circle = Circle((xi, yi), ri)
	patches.append(circle)
	fig, ax = plt.subplots()
	p = PatchCollection(patches, cmap=matplotlib.cm.jet, alpha=0.1)
	ax.add_collection(p)
	plt.axis('equal')
	for xi, yi in zip(np.real(eval), np.imag(eval)):
	plt.plot(xi, yi,'o')
	plt.show()

view raw Gerschgorin.py hosted with ❤ by GitHub