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 Belarusian mathematician Semyon Aranovich Gershgorin in 1931. The spelling of S. A. Gershgorin's name has been transliterated in several different ways, including Geršgorin, Gerschgorin and Gershgorin.

Statement and proof

Let A be a complex n×n matrix, with entries (a_ij). For i ∈ {1, … n} write R_i = ∑_{j ≠ i} |a_ij| where |a_ij| denotes the absolute value of a_ij. Let D(a_ii, R_i) be the closed disc centered at a_ii with radius R_i. Such a disc is called a Gershgorin disc.

Theorem: Every eigenvalue of A lies within at least one of the Gershgorin discs D(a_ii, R_i).

Proof: Let λ be an eigenvalue of A and let x = (x_j) be a corresponding eigenvector. Let i ∈ {1, … n} be chosen so that |x_i| = max_j |x_j|. Then |x_i| > 0, otherwise x = 0. Since x is an eigenvector, Ax = λx or equivalent

$\sum _{j}a_{ij}x_{j}=\lambda x_{i}\quad \forall i\in 1\ldots n$

so, splitting the sum, we get

$\sum _{j\neq i}a_{ij}x_{j}=\lambda x_{i}-a_{ii}x_{i}$

We may then divide both sides by $x_{i}$ (choosing i as we explained we can be sure that $x_{i}\neq 0$ ) and take the absolute value to obtain

$|\lambda -a_{ii}|=\left|{\frac {\sum _{j\neq i}a_{ij}x_{j}}{x_{i}}}\right|\leq \sum _{j\neq i}|a_{ij}|=R_{i}.$

where the last inequality is valid because $\left|{\frac {x_{j}}{x_{i}}}\right|\leq 1\quad \forall j\neq i$

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

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.

Strengthening of the theorem

If one of the discs is disjoint form the others then it contains exactly one eigenvalue. If however it meets another disc it is possible that it contains no eigenvalue. In the general case the theorem can be strenghtened 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

$B(t)=(1-t)*D+t*A$.

Then the statement is true for D=B(0), and since B(t) is a continuous deformation in the sense that both the eigenvalues and the Gershgorin discs change continuously, it remains true for A=B(1) too.

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⁻¹ 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 generally very difficult.

Now, since PA ≈ I where I is the identity matrix, the eigenvalues of PA should all be close to 1. By the Gerschgorin 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.

References

• Gerschgorin, S. "Über die Abgrenzung der Eigenwerte einer Matrix." Izv. Akad. Nauk. USSR Otd. Fiz.-Mat. Nauk 7, 749-754, 1931
• Varga, R. S. Geršgorin and His Circles. Berlin: Springer-Verlag, 2004. ISBN 3-540-21100-4. Errata.

External links

• "Gershgorin's circle theorem". PlanetMath.
• Eric W. Weisstein. "Gershgorin Circle Theorem." From MathWorld--A Wolfram Web Resource.
• Semyon Aranovich Gershgorin biography at MacTutor