Monday, November 28, 2022
HomeMatlabWhat Is Gershgorin’s Theorem? – Nick Higham

What Is Gershgorin’s Theorem? – Nick Higham

For a given $ntimes n$ matrix, Gershgorin’s theorem defines $n$ discs within the advanced aircraft whose union accommodates the eigenvalues of the matrix. The theory can present approximations to eigenvalues. It will probably additionally present qualitative data, similar to that each one the eigenvalues lie in a selected half-plane.

Theorem 1 (Gershgorin’s theorem).

The eigenvalues of $Ainmathbb{C}^{ntimes n}$ lie within the union of the $n$ discs within the advanced aircraft

$notag D_i = Big{ zinmathbb{C}: |z-a_{ii}| le displaystylesum_{jne i} |a_{ij}|Big}, quad i=1colon n.$

Proof. Let $lambda$ be an eigenvalue of $A$ and $x$ a corresponding eigenvector and let $|x_k| = |x|_infty$. From the $k$th equation in $Ax=lambda x$ we’ve got

$notag sum_{j=1 atop jne k}^n a_{kj}x_j = (lambda-a_{kk}) x_k.$

Therefore

$notag |lambda-a_{kk}| le sum_{j=1 atop jne k}^n |a_{kj}||x_j|/|x_k|,$

and since $|x_j|/|x_k|le 1$ it follows that $lambda$ belongs to the $k$th disc, $D_k$.

The Gershgorin discs $D_i$ are outlined when it comes to a summation over the rows of $A$, however for the reason that eigenvalues of $A$ are the identical as these of $A^T$ the identical consequence holds with summation over the columns.

A consequence of the concept is that if $0$ doesn’t belong to any of the Gershgorin discs then $A$ is nonsingular. That is equal to the well-known consequence {that a} strictly diagonally dominant matrix is nonsingular.

One other consequence of the concept is that if $A$ is symmetric and all of the discs lie within the open proper half-plane then the eigenvalues are constructive and so $A$ is constructive particular. This situation is equal to $A$ having constructive diagonal components and being strictly diagonally dominant.

The Gershgorin discs for the $5times 5$ matrix

$notag left[begin{array}{ccccc} 5/4 & 1 & 3/4 & 1/2 & 1/4 1 & 0 & 0 & 0 & 0 -1 & 1 & 0 & 0 & 0 0 & 0 & 1 & 3 & 0 0 & 0 & 0 & 1/2 & 5 end{array}right]$

are proven right here:

The eigenvalues—three actual and one advanced conjugate pair—are the black dots. It occurs that every disc accommodates an eigenvalue, however this isn’t at all times the case. For the matrix

$notag left[begin{array}{cc} 2 & -1 2 & 0 end{array}right]$

the discs are

and the blue disc doesn’t include an eigenvalue. The subsequent consequence, which is proved by a continuity argument, offers further data that will increase the utility of Gershgorin’s theorem. Specifically it says that if a disc is disjoint from the opposite discs then it accommodates an eigenvalue.

Theorem 2.

If $k$ of the Gershgorin discs of $Ainmathbb{C}^{ntimes n}$ are disjoint from the opposite discs then their union accommodates $k$ eigenvalues of $A$.

Theorem 2 tells us that the rightmost disc in our $5times 5$ instance accommodates one eigenvalue, $lambda$, since it’s disjoint from the opposite discs, and the union of the opposite 4 discs accommodates 4 eigenvalues. Moreover, $lambda$ have to be actual, as a result of if not it happens in a fancy conjugate pair for the reason that matrix is actual, and because the disc is symmetric about the true axis $overline{lambda}$ would additionally lie within the disc, contradicting Theorem 2.

Gershgorin’s theorem is most helpful for matrices which might be near being diagonal. A way that may produce improved eigenvalue estimates is to use the concept to $D^{-1}AD$ for some nonsingular diagonal matrix $D$. This similarity transformation doesn’t change the eigenvalues however it does change the discs, and the goal is to decide on $D$ to cut back the radiuses of the discs. Take into account our $5times 5$ instance. We all know that there’s one eigenvalue $lambda$ within the rightmost disc and that it’s actual, so $4.5 le lambda le 5.5$. For $D = mathrm{diag}(1,1,1,1,1/4)$ the rightmost disc shrinks and stays distinct from the others and we acquire the sharper bounds $4.875 le lambda le 5.126$. The discs for $D^{-1}AD$ are proven right here:

Notes

Most books on matrix evaluation or numerical linear algebra embody Gershgorin’s theorem.

Eigenvalue inclusion areas have been developed with discs changed by extra sophisticated shapes, similar to Brauer’s ovals of Cassini.

Varga’s 2004 e-book is dedicated to Gershgorin’s theorem and associated outcomes. It reproduces Gershgorin’s 1931 paper in an appendix.

References

• S. Gerschgorin. Uber die Abgrenzung der Eigenwerte einer Matrix. Izv. Akad. Nauk. SSSR, 1:749–754, 1931.
• Richard S. Varga. Geršgorin and His Circles. Springer-Verlag, Berlin, Germany, 2004.
RELATED ARTICLES