Volume 8 (1999)

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 \[ A = \left| {\begin{array}{cc} 0 & 1 & 0 \\ \frac{1}{2} & 1 & 0 \\ 0 & 0 & 0 \\ \end{array}} \right| \]

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 \[ A = \left| {\begin{array}{cc} 1 & 1 & 1 \\ 2 & 4 & 0 \\ 1 & 0 & 2 \\ \end{array}} \right| \]

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).

< Back