The ovals of Cassini and Gershgorin's circles
|
This page presents an interactive introduction to some
ideas about the location of the eigenvalues of a matrix. You
should see a plot window with a few buttons below it to the
left. The figure to the left can display the eigenvalues,
Gershgorin circles, and
Cassini ovals for the 3x3 matrix above it. The
matrix can contain real or complex numbers. As we shall see, the
eigenvalues of a matrix will lie within regions bounded by both
the ovals of Cassini and Gershgorin's circles. The buttons immediately
below the figure work as follows:
- Example generates a random example matrix.
- Spectrum plots the eigenvalues
of the matrix. Depending on the
example, this can take a moment.
- Gershgorin plots the famous
Gershgorin circles.
- Cassini plots the boundary of the (not as) famous
ovals of Cassini.
These are somewhat difficult to draw, and so only an
approximation is presented to give you an idea of what these sets look
like. Even so, they can take a while to display.
After displaying a figure, some color-coded numbers will appear
near the matrix. They correspond to the sum of the magnitudes of
the off-diagonal elements, row-wise. For example, r(1)=5 indicates
that the off diagonal elements in row 1 add up to 5 in modulus. The
color corresponds to the Gershgorin circle
associated with that row.
|
You can enter or modify values of the matrix to see how this may affect
the plot. If you enter values too large in magnitude, the Cassini ovals
may not display properly. It is recommended that you start with the examples.
What is fascinating about the Gergorin circle theorem and its
Brauer Cassini oval variant is that, given any complex matrix
A = [ai,j] in Cn ×n, n > 1, one can very easily
determine a closed set in in C which is guaranteed to include
all eigenvalues of A; this closed set is either the union
of n disks in the Gergorin case, or (n choose 2) ovals of
Cassini in the Brauer case. All that is needed in either case are
the n diagonal entries {ai,i}ni = 1 and the n
modified row sums
{
|ai,1|
+
|ai,2|
+ ... +
|ai,i-1|
+
|ai,i+1|
+ ... +
|ai,n|
}ni = 1. The price to be paid, for this ease
of calculation of an eigenvalue inclusion for the given matrix A,
is that these inclusions sets necessarily can apply to many
matrices, not just A, i.e., these inclusion sets apply to any
matrix B in
Cn ×n in Omega defined in (1.3) of the accompanying paper.
This
is why there is interest in describing the set , sigma defined
by (1.4), of all eigenvalues of all B in Omega.
As a consequence of the inclusions of (3.1) and (3.2), it is stated
in Section 4 that the Brauer Cassini ovals are in general at least
as good as the Gergorin disks, in estimating the spectrum
of any given matrix A in Cn ×n. But
this can be verified by the reader for any 3 ×3 complex
matrix by using the interactive aspect of this paper. Specifically,
try the 3 ×3 matrix
These is more interesting history concerning Brauer's ovals of
Cassini. A famous result of Olga Taussky [6] states that if
A = [ai,j] in Cn ×n is irreducible (equivalently,
the directed graph of A is strongly connected) and if
s,
an eigenvalue of A, lies on the boundary of Gamma,
defined in (1.1) then all Gergorin circles pass through
s, i.e.,
| s- ai,i | = ri(A) ( all i in N). |
| (1) |
A similar result of Brauer [1] states, again assuming that
A = [ai,j] in Cn ×n is irreducible,
that if s, an
eigenvalue of A, lies on the boundary of K(A), defined in
(2.4), then all (n choose 2) Cassini ovals pass through
s,
i.e.,
| s- ai,i| ·|s-aj,j| = ri (A) ·rj(A)
(all i <> j in N). |
| (2) |
It is remarkable that Zhang and Gu [9] recently produced the following
counterexample of this long-standing result of Brauer's
from 1947. Consider the matrix
which is irreducible and has s = 0 as an eigenvalue. (On
selecting the above matrix, you can verify, with your mouse that the
Cassini oval |z-4| ·|z-2| = 2 fails to pass through z = 0).