Gershgorin circle theorem

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

In mathematics, the Gershgorin circle theorem may be used to bound the spectrum of a square matrix. It was first published by the Soviet mathematician Semyon Aronovich Gershgorin in 1931. Gershgorin's name has been transliterated in several different ways, including Geršgorin, Gerschgorin, Gershgorin, Hershhorn, and Hirschhorn.

Statement and proof[edit]

Let be a complex matrix, with entries . For let be the sum of the absolute values of the non-diagonal entries in the -th row. Let be a closed disc centered at with radius . Such a disc is called a Gershgorin disc.

Theorem: Every eigenvalue of lies within at least one of the Gershgorin discs

Proof: Let be an eigenvalue of . Choose a corresponding eigenvector so that one component is equal to and the others are of absolute value less than or equal to : and for . There always is such an , which can be obtained simply by dividing any eigenvector by its component with largest modulus. Since , in particular

So, splitting the sum and taking into account once again that , we get

Therefore, applying the triangle inequality,

Corollary: The eigenvalues of A must also lie within the Gershgorin discs Cj corresponding to the columns of A.

Proof: Apply the Theorem to AT.

Example For a diagonal matrix, the Gershgorin discs coincide with the spectrum. Conversely, if the Gershgorin discs coincide with the spectrum, the matrix is diagonal.

Discussion[edit]

One way to interpret this theorem is that if the off-diagonal entries of a square matrix over the complex numbers have small norms, the eigenvalues of the matrix cannot be "far from" the diagonal entries of the matrix. Therefore, by reducing the norms of off-diagonal entries one can attempt to approximate the eigenvalues of the matrix. Of course, diagonal entries may change in the process of minimizing off-diagonal entries.

The theorem does not claim that there is one disc for each eigenvalue; if anything, the discs rather correspond to the axes in , and each expresses a bound on precisely those eigenvalues whose eigenspaces are closest to one particular axis. In the matrix

— which by construction has eigenvalues , , and with eigenvectors , , and — it is easy to see that the disc for row 2 covers and while the disc for row 3 covers and . This is however just a happy coincidence; if working through the steps of the proof one finds that it in each eigenvector is the first element that is the largest (every eigenspace is closer to the first axis than to any other axis), so the theorem only promises that the disc for row 1 (whose radius can be twice the sum of the other two radii) covers all three eigenvalues.

Strengthening of the theorem[edit]

If one of the discs is disjoint from the others then it contains exactly one eigenvalue. If however it meets another disc it is possible that it contains no eigenvalue (for example, or ). In the general case the theorem can be strengthened as follows:

Theorem: If the union of k discs is disjoint from the union of the other n − k discs then the former union contains exactly k and the latter n − k eigenvalues of A.

Proof: Let D be the diagonal matrix with entries equal to the diagonal entries of A and let

We will use the fact that the eigenvalues are continuous in , and show that if any eigenvalue moves from one of the unions to the other, then it must be outside all the discs for some , which is a contradiction.

The statement is true for . The diagonal entries of are equal to that of A, thus the centers of the Gershgorin circles are the same, however their radii are t times that of A. Therefore the union of the corresponding k discs of is disjoint from the union of the remaining n-k for all . The discs are closed, so the distance of the two unions for A is . The distance for is a decreasing function of t, so it is always at least d. Since the eigenvalues of are a continuous function of t, for any eigenvalue of in the union of the k discs its distance from the union of the other n-k discs is also continuous. Obviously , and assume lies in the union of the n-k discs. Then , so there exists such that . But this means lies outside the Gershgorin discs, which is impossible. Therefore lies in the union of the k discs, and the theorem is proven.

Remarks:

  • The continuity of should be understand in the sense of topology. It is sufficient to show that the roots (as a point in space ) is continuous function of its coefficients. Note that the inverse map that maps roots to coefficients is described by Vieta's formulas (note for Characteristic polynomial ) which can be proved a open map. This proves the roots as a whole is a continuous function of its coefficients. Since composition of continuous functions is again continuous, the as a composition of roots solver and is also continuous.
  • Individual eigenvalue could merge with other eigenvalue(s) or appeared from a splitting of previous eigenvalue. This may confuse people and questioning the concept of continuous. However, when viewing from the space of eigenvalue set , the trajectory is still a continuous curve although not necessarily smooth everywhere.

Note: There are two types of continuity concerning eigenvalues: the one in the above Proof is "each individual eigenvalue as a usual continuous function", while the one in the above Remark is a topological one - the continuity from a domain of t to the quotient space of C^n (unordered sets). (See Bhatia's Matrix Analysis, Springer). A proof using complex analysis (Argument Principle) is clear and mathematically sound. (See Horn and Johnson, Matrix Analysis, 2nd edition, Cambridge U Press.)

Application[edit]

The Gershgorin circle theorem is useful in solving matrix equations of the form Ax = b for x where b is a vector and A is a matrix with a large condition number.

In this kind of problem, the error in the final result is usually of the same order of magnitude as the error in the initial data multiplied by the condition number of A. For instance, if b is known to six decimal places and the condition number of A is 1000 then we can only be confident that x is accurate to three decimal places. For very high condition numbers, even very small errors due to rounding can be magnified to such an extent that the result is meaningless.

It would be good to reduce the condition number of A. This can be done by preconditioning: A matrix P such that PA−1 is constructed, and then the equation PAx = Pb is solved for x. Using the exact inverse of A would be nice but finding the inverse of a matrix is something we want to avoid because of the computational expense.

Now, since PAI where I is the identity matrix, the eigenvalues of PA should all be close to 1. By the Gershgorin circle theorem, every eigenvalue of PA lies within a known area and so we can form a rough estimate of how good our choice of P was.

Example[edit]

Use the Gershgorin circle theorem to estimate the eigenvalues of:

This diagram shows the discs in yellow derived for the eigenvalues. The first two disks overlap and their union contains two eigenvalues. The third and fourth disks are disjoint from the others and contain one eigenvalue each.

Starting with row one, we take the element on the diagonal, aii as the center for the disc. We then take the remaining elements in the row and apply the formula:

to obtain the following four discs:

Note that we can improve the accuracy of the last two discs by applying the formula to the corresponding columns of the matrix, obtaining and .

The eigenvalues are 9.8218, 8.1478, 1.8995, -10.86

See also[edit]

References[edit]

  • Gerschgorin, S. (1931), "Über die Abgrenzung der Eigenwerte einer Matrix", Izv. Akad. Nauk. USSR Otd. Fiz.-Mat. Nauk (in German), 6: 749–754.
  • Varga, Richard S. (2004), Geršgorin and His Circles, Berlin: Springer-Verlag, ISBN 3-540-21100-4. (Errata).
  • Varga, Richard S. (2002), Matrix Iterative Analysis (2nd ed.), Springer-Verlag. 1st ed., Prentice Hall, 1962.
  • Golub, G. H.; Van Loan, C. F. (1996), Matrix Computations, Baltimore: Johns Hopkins University Press, p. 320, ISBN 0-8018-5413-X.

External links[edit]