Gershgorin circle theorem

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.
Let formula_1 be a complex formula_2 matrix, with entries formula_3. For formula_4 let formula_5 be the sum of the absolute values of the non-diagonal entries in the formula_6-th row: 
Let formula_8 be a closed disc centered at formula_9 with radius formula_5. Such a disc is called a Gershgorin disc.
"Proof." Let formula_13 be an eigenvalue of formula_1. Choose a corresponding eigenvector formula_15 so that one component formula_16 is equal to formula_17 and the others are of absolute value less than or equal to formula_17: formula_19 and formula_20 for formula_21. There is always such an formula_22, which can be obtained simply by dividing any eigenvector by its component with largest modulus. Since formula_23, in particular
So, splitting the sum and taking into account once again that formula_19, we get
Therefore, applying the triangle inequality,
"Proof." Apply the Theorem to "A"T.
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.
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 formula_28, 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 formula_30, formula_31, and formula_32 with eigenvectors formula_33, formula_34, and formula_35 — it is easy to see that the disc for row 2 covers formula_30 and formula_31 while the disc for row 3 covers formula_30 and formula_32. 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.
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, formula_40 or formula_41). 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 formula_43, 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 formula_43, which is a contradiction.
The statement is true for formula_45. The diagonal entries of formula_46 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 formula_46 is disjoint from the union of the remaining "n-k" for all formula_48. The discs are closed, so the distance of the two unions for "A" is formula_49. The distance for formula_46 is a decreasing function of "t", so it is always at least "d". "Since the eigenvalues of formula_46 are a continuous function of "t", for any eigenvalue formula_52 of formula_46 in the union of the "k" discs its distance formula_54 from the union of the other "n-k" discs is also continuous." Obviously formula_55, and assume formula_56 lies in the union of the "n-k" discs. Then formula_57, so there exists formula_58 such that formula_59. But this means formula_60 lies outside the Gershgorin discs, which is impossible. Therefore formula_56 lies in the union of the "k" discs, and the theorem is proven.
Remarks:
Added Remark:
Application.
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 "P" ≈ "A"−1 is constructed, and then the equation "PAx" = "Pb" is solved for "x". Using the "exact" [[matrix inverse|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 "PA" ≈ "I" where "I" is the identity matrix, the [[eigenvalue]]s 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.
Use the Gershgorin circle theorem to estimate the eigenvalues of:
[[File:Gershgorin Disk Theorem Example.svg|thumb|400px|right|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, "a""ii" 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 formula_72 and formula_73.
The eigenvalues are 9.8218, 8.1478, 1.8995, −10.86. Note that this is a (column) [[diagonally dominant matrix]]: formula_74. This means that most of the matrix is in the diagonal, which explains why the eigenvalues are so close to the centers of the circles, and the estimates are very good. For a random matrix, we would expect the eigenvalues to be substantially further from the centers of the circles.
External links.
[[Category:Theorems in algebra]]
[[Category:Linear algebra]]
[[Category:Matrix theory]]
[[Category:Articles containing proofs]]