9814

Enclosing the Spectrum by Gershgorin-Type Sets

It is possible to cover the eigenvalues of a general matrix merely by using the entries of to derive some disks that will work in some combination. These disks are called Gershgorin disks after the Russian mathematician.
There are two families of disks; one based on the rows and the other on the columns of . These disks are centered at the diagonal entries of ; the radii are the sums of the absolute values of the off-diagonal elements in the corresponding row or column, so usually the disks will have different centers and different radii. The green-yellow filled area is built from unions or intersections of those disks and should cover the spectrum of , that is, the set of eigenvalues of .
You can choose three different types of Gershgorin regions. The first is based on the rows of , the second on the columns, and the third on the intersection of row and column disks. In any case, all corresponding circles are shown and the corresponding Gershgorin region is shown as the green-yellow filled area.
A yellow point with a red boundary marks the mean of the diagonal entries of , which is also the mean of the eigenvalues of . We call this point the hub of , because it is the natural pivot point for all matrices similar to . Indeed, one could claim that the whole question of similarity hinges on this point!
Choosing "Heinrich" shows a blue dashed circle centered at the hub of . Its diameter is derived from the Frobenius norm of , which overestimates the spectral norm of but can be calculated simply from the entries of directly, see [1], Teil 2, p. 237, where it is attributed to Heinrich.
For comparison, by choosing "eigenvalues" to show the hub circle, you can see the smallest circle (dashed red) around the hub of that covers the spectrum.
Moreover, for your convenience, you can see the convex hulls of the entries of (in blue) and of the diagonal entries of (in yellow). The convex hull of the eigenvalues of (in red) will let you judge which (combination of) disks will work.
A family of random complex matrices with dimensions from 2 to 15 is selected to illustrate the ideas. You can choose whether the matrix is diagonalizable or not.
In addition, you can experiment with a unitarily similarized version of via a parameter κ between 0 and 1, where 0 gives itself and 1 the Schur similarity of . Values in between show a possible passage from to its Schur similarity, as might occur when using an iterative method like the one named after Jacobi.
Almost every item in the graphics is annotated, so guide the mouse over them to see explanations!

THINGS TO TRY

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

DETAILS

Knowledge of the spectrum, the exact location of all or some of the eigenvalues, whether an eigenvalue is real, in the left half-plane, or not in a specified region, or anything else like that is of key importance.
The Russian mathematician Gershgorin became famous for his disks that cover the eigenvalues; they constitute a relatively crude enclosure that compensates by being easy to calculate. However, if all you need is to know if the spectrum is part of a region or not, this crude estimate might already suffice. And if you already have an approximation of the eigensystem, for instance during the course of an iterative procedure like the Jacobi method, the Gershgorin circles of the similarity shrink down until they finally consist of the points of the spectrum alone. This is certainly true only if the matrix is normal, for only then is the Schur similarity actually diagonal. In general the Schur similarity is upper triangular, which means that some of its row or column circles do not have zero diameter, although its diagonal and its spectrum and the spectrum of coincide. Nevertheless, the knowledge of an intermediate stage might already be sufficient.
A recent book of Varga [3] brought these seemingly old ideas back to our attention, providing general extensions of the ideas up to the present. [1] and [2], key books on matrix analysis, give some additional background to the original ideas and their immediate consequences.
Varga's book motivated this Demonstration, but the Demonstration "Gershgorin Circles" by Chris Maes triggered it. Some ideas therefrom were the starting points for this program, especially the use of RegionPlot with a predicate. That is really a good idea!
What we want to show is as much visual information as possible about the matrix and some easily derivable entities like its hub, its convex hull, the convex hull of its diagonal, its Gershgorin circles, and maybe more, to be visually compared with its spectrum, which a priori is usually not available. The significance or failure of the concepts for a specific matrix should leap to the eyes, especially when using the transition from the matrix to its Schur similarity via a unitarized convex combination of its eigenvectors and the identity , namely, , where the parameter varies between 0 and 1; is the orthogonalization of ; .
Snapshot 0: push buttons one after the other; after any change mouseover the graphics to see explanations
Snapshot 1: typical Gershgorin region based on rows and columns
Snapshot 2: the matrix is not diagonalizable, so the Gershgorin circles show up even for the Schur similarity of , that is,
Snapshot 3: Gershgorin region based on columns, intermediate similarity stage, that is, , spectral and Heinrich circle shown
Snapshot 4: higher dimension, 15, Gershgorin region based on columns, high similarity stage, that is, , Heinrich circle has a large radius, Gershgorin circles still have relatively large radii although all off-diagonal entries seem to be close to zero
This Demonstration does not deal with any of the extensions mentioned in Varga's book. This might be a future topic. Read Varga's book, it is really worthwhile!
[1] R. Zurmühl and S. Falk, Matrizen und ihre Anwendungen, Berlin, Heidelberg: Springer–Verlag, 1984, Teil 1 and Teil 2.
[2] R. A. Horn and C. R. Johnson, Matrix Analysis, New York: Cambridge University Press, 1985.
[3] R. S. Varga, Gershgorin and His Circles, Berlin, Heidelberg: Springer–Verlag, 2004.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.









 
RELATED RESOURCES
Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and
interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Step-by-step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
Powered by Wolfram Mathematica © 2014 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+