Gershgorin theorem

Gerschgorin theorem, Geršgorin theorem

Given a complex -matrix, , with , then finding the eigenvalues of is equivalent to finding the zeros of its associated characteristic polynomial

where is the identity -matrix (cf. also Matrix; Eigen value). But for large, finding these zeros can be a daunting problem. Is there an "easy" procedure which estimates these eigenvalues, without having to explicitly form the characteristic polynomial above and then to find its zeros? This was first considered in 1931 by the Russian mathematician S. Gershgorin, who established the following result [a1]. If denotes the closed complex disc having centre and radius , then Gershgorin showed that for each eigenvalue of the given complex -matrix there is a positive integer , with , such that , where

(a1)

with

( is called the th Gershgorin disc for .) As this is true for each eigenvalue of , it is evident that if denotes the set of all eigenvalues of , then

(a2)

Indeed, let be any eigenvalue of , so that there is a complex vector , with , such that . As , then , and there is an , with , such that . Taking the th component of gives , or equivalently

On taking absolute values in the above expression and using the triangle inequality, this gives

(a3)

the last inequality following from the definition of in (a1) and the fact that for all . Dividing through by in (a3) gives that .

In the same paper, Gershgorin also established the following interesting result: If the discs of (a2) consist of two non-empty disjoint sets and , where consists of the union of, say, discs and consists of the union of the remaining discs, then contains exactly eigenvalues (counting multiplicities) of , while contains exactly eigenvalues of . (The proof of this depends on the fact that the zeros of the characteristic polynomial vary continuously with the entries of .)

One of the most beautiful results in this area, having to do with the sharpness of the inclusion of (a2), is a result of O. Taussky [a2], which depends on the following use of directed graphs (cf. also Graph, oriented). Given a complex -matrix , with , let be distinct points, called vertices, in the plane. Then, for each , let denote an arc from vertex to vertex . The collection of all these arcs defines the directed graph of . Then the matrix , with , is said to be irreducible if, given any distinct vertices and , there is a sequence of abutting arcs from to , i.e.,

where .

Taussky's theorem is this. Let be any irreducible complex -matrix, with . If is an eigenvalue of which lies on the boundary of the union of the Gershgorin discs of (a2), then lies on the boundary of each Gershgorin circle, i.e., from (a1) it follows that

Next, there is related work of A. Brauer [a3] on estimating the eigenvalues of a complex -matrix (), which uses Cassini ovals instead of discs. For any integers and () with , the th Cassini oval is defined by (cf. also Cassini oval)

(a4)

Then Brauer's theorem is that, for any eigenvalue of , there exist and , with , such that , and this now gives the associated eigenvalue inclusion

(a5)

Note that there are now such Cassini ovals in (a5), as opposed to the Gershgorin discs in (a2). But it is equally important to note that the eigenvalue inclusions of (a2) and (a5) use the exact same data from the matrix , i.e., and . So, which of the eigenvalue inclusions of (a2) and (a5) is smaller and hence better? It turns out that

(a6)

for any complex -matrix , so that the Cassini ovals are always at least as good as the Gershgorin discs. (The result (a6) was known to Brauer, but was somehow neglected in the literature.)

Finally, as both eigenvalue inclusions (a2) and (a5) depend only on the row sums , it is evident that these inclusions apply not to just the single matrix , but to a whole class of -matrices, namely,

Thus,

for each in . Then, if denotes the set of all eigenvalues of all in , it follows that

(a7)

How sharp is the first inclusion of (a7)? It was shown in 1999 by R.S. Varga and A. Krautstengl [a4] that

(a8)

Thus, for , it can be said that the Cassini ovals give "perfect" results.

Gershgorin's discs and Brauer's Cassini ovals are mentioned in [a5], [a6]. A more detailed treatment of these topics can be found in [a7].

References

[a1]	S. Gerschgorin, "Ueber die Abgrenzung der Eigenwerte einer Matrix" Izv. Akad. Nauk. SSSR Ser. Mat. , 1 (1931) pp. 749–754
[a2]	O. Taussky, "Bounds for the characteristic roots of matrices" Duke Math. J. , 15 (1948) pp. 1043–1044
[a3]	A. Brauer, "Limits for the characteristic roots of a matrix" Duke Math. J. , 13 (1946) pp. 387–395
[a4]	R.S. Varga, A. Krautstengl, "On Geršgorin-type problems and ovals of Cassini" Electron. Trans. Numer. Anal. , 8 (1999) pp. 15–20
[a5]	R.S. Varga, "Matrix iterative analysis" , Springer (2000) (Edition: Second)
[a6]	R.A. Horn, C.R. Johnson, "Matrix analysis" , Cambridge Univ. Press (1985)
[a7]	R.S. Varga, "Geršgorin and his circles" , Springer (to appear)