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 kth 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 kth 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:

gersh1.jpg 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

gersh2.jpg 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:

gersh1a.jpg

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

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular

Recent Comments