Thursday, February 11, 2016

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

No comments: