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) |
Gershgorin theorem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Gershgorin_theorem&oldid=14015