Gershgorin circle theorem

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.

Contents 1 Statement and proof 2 Discussion 3 Strengthening of the theorem 4 Application 5 Example 6 See also 7 References 8 External links Statement and proof Let {displaystyle A} be a complex {displaystyle ntimes n} matrix, with entries {displaystyle a_{ij}} . For {displaystyle iin {1,dots ,n}} let {displaystyle R_{i}} be the sum of the absolute values of the non-diagonal entries in the {displaystyle i} -th row: {displaystyle R_{i}=sum _{jneq {i}}left|a_{ij}right|.} Let {displaystyle D(a_{ii},R_{i})subseteq mathbb {C} } be a closed disc centered at {displaystyle a_{ii}} with radius {displaystyle R_{i}} . Such a disc is called a Gershgorin disc.

Theorem. Every eigenvalue of {displaystyle A} lies within at least one of the Gershgorin discs {displaystyle D(a_{ii},R_{i}).} Proof. Let {displaystyle lambda } be an eigenvalue of {displaystyle A} with corresponding eigenvector {displaystyle x=(x_{j})} . Find i such that the element of x with the largest absolute value is {displaystyle x_{i}} . Since {displaystyle Ax=lambda x} , in particular we take the ith component of that equation to get: {displaystyle sum _{j}a_{ij}x_{j}=lambda x_{i}.} Taking {displaystyle a_{ii}} to the other side: {displaystyle sum _{jneq i}a_{ij}x_{j}=(lambda -a_{ii})x_{i}.} Therefore, applying the triangle inequality and recalling that {displaystyle {frac {left|x_{j}right|}{left|x_{i}right|}}leq 1} based on how we picked i, {displaystyle left|lambda -a_{ii}right|=left|sum _{jneq i}{frac {a_{ij}x_{j}}{x_{i}}}right|leq sum _{jneq i}left|a_{ij}right|=R_{i}.} 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 while recognizing that the eigenvalues of the transpose are the same as those of the original matrix.

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 {displaystyle mathbb {C} ^{n}} , and each expresses a bound on precisely those eigenvalues whose eigenspaces are closest to one particular axis. In the matrix {displaystyle {begin{pmatrix}3&2&2\1&1&0\1&0&1end{pmatrix}}{begin{pmatrix}a&0&0\0&b&0\0&0&cend{pmatrix}}{begin{pmatrix}3&2&2\1&1&0\1&0&1end{pmatrix}}^{-1}={begin{pmatrix}-3a+2b+2c&6a-2b-4c&6a-4b-2c\b-a&a+(a-b)&2(a-b)\c-a&2(a-c)&a+(a-c)end{pmatrix}}} — which by construction has eigenvalues {displaystyle a} , {displaystyle b} , and {displaystyle c} with eigenvectors {displaystyle left({begin{smallmatrix}3\1\1end{smallmatrix}}right)} , {displaystyle left({begin{smallmatrix}2\1\0end{smallmatrix}}right)} , and {displaystyle left({begin{smallmatrix}2\0\1end{smallmatrix}}right)} — it is easy to see that the disc for row 2 covers {displaystyle a} and {displaystyle b} while the disc for row 3 covers {displaystyle a} and {displaystyle c} . 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, {displaystyle A=left({begin{smallmatrix}0&1\4&0end{smallmatrix}}right)} or {displaystyle A=left({begin{smallmatrix}1&-2\1&-1end{smallmatrix}}right)} ). 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 {displaystyle B(t)=(1-t)D+tA.} We will use the fact that the eigenvalues are continuous in {displaystyle t} , 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 {displaystyle t} , which is a contradiction.

The statement is true for {displaystyle D=B(0)} . The diagonal entries of {displaystyle B(t)} 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 {displaystyle B(t)} is disjoint from the union of the remaining n-k for all {displaystyle tin [0,1]} . The discs are closed, so the distance of the two unions for A is {displaystyle d>0} . The distance for {displaystyle B(t)} is a decreasing function of t, so it is always at least d. Since the eigenvalues of {displaystyle B(t)} are a continuous function of t, for any eigenvalue {displaystyle lambda (t)} of {displaystyle B(t)} in the union of the k discs its distance {displaystyle d(t)} from the union of the other n-k discs is also continuous. Obviously {displaystyle d(0)geq d} , and assume {displaystyle lambda (1)} lies in the union of the n-k discs. Then {displaystyle d(1)=0} , so there exists {displaystyle 0sum _{jneq i}|a_{ji}|} . 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.

See also For matrices with non-negative entries, see Perron–Frobenius theorem. Doubly stochastic matrix Hurwitz matrix Joel Lee Brenner Metzler matrix Muirhead's inequality Bendixson's inequality Schur–Horn theorem References ^ Roger A. Horn & Charles R. Johnson (2013), Matrix Analysis, second edition, Cambridge University Press ISBN 9780521548236 [https://www.cambridge.org/ca/academic/subjects/mathematics/algebra/matrix-analysis-2nd-edition ^ Chi-Kwong Li & Fuzhen Zhang (2019), Eigenvalue continuity and Gersgorin's theorem, Electronic Journal of Linear Algebra (ELA) {Vol.35, pp.619-625|2019} [DOI: https://doi.org/10.13001/ela.2019.5179] 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 "Gershgorin's circle theorem". PlanetMath. Eric W. Weisstein. "Gershgorin Circle Theorem." From MathWorld—A Wolfram Web Resource. Semyon Aranovich Gershgorin biography at MacTutor Categories: Theorems in algebraLinear algebraMatrix theory