Brauer's Cassini Ovals versus Gershgorin Circles

Initializing live version
Download to Desktop

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

This Demonstration gives different views of the neighborhood of the spectrum of a matrix acting in , with low dimension . It continues the ideas presented in the Demonstration "Enclosing the Spectrum by Gershgorin-Type Sets", offering extensions that go by the names of Brauer, Ostrowski, and others.

[more]

We are looking for the eigenvalues of ; we can offer some easily derivable ensembles of sets covering their location, consisting of members with a simple description and low computational cost.

To illustrate the ideas, a family of random complex matrices with dimensions from 2 to 15 is selected. You can choose whether the matrix is normal, diagonalizable, or deficient, each being built from (almost) the same spectrum.

First, to get an impression of the area in the complex plane where the matrix "lives", the location of the points, the hub, the convex hull, and its boundary fence can be shown, independently for all the entries of , for its diagonal entries, and for its eigenvalues.

What we call the "hub" of is the mean of the diagonal entries of , which is at the same time the mean of the eigenvalues of . In the literature this is usually expressed as , an invariant under similarity. We call it the hub of because, for all matrices similar to , it represents the center of gravity of their respective diagonal entries, which is common to them all, as well as the center of gravity of their common spectrum, so it is the natural pivot point for the whole similarity class of . Indeed, one could claim that the whole question of similarity of a matrix hinges on this point! Here it is marked as a yellow point with a red boundary.

The total energy of a matrix is defined as , its distribution between the diagonal and rest of the matrix can be popped up, too. For normal matrices the total energy is an invariant under unitary similarity, its distribution between diagonal and rest depends on how close the diagonal of approximates the spectrum. For non-normal matrices the total energy does not need to be constant within a similarity class.

In addition, you can experiment with a unitarily similarized version of via a parameter between 0 and 1, showing a possible passage from to its Schur similarity , thereby resembling a Jacobi tour. For every , has the same eigenvalues as , and carries them on its diagonal.

The ideas of Gershgorin, Brauer, Ostrowski, and others can be made explicit with the help of the next block of controls. Get familiar with some of their contributions and compare their respective benefits or drawbacks!

If you would like to focus your attention on even simpler regions, such as a single disk or a circular ring, you can find some circles that enclose or exclude the whole or parts of the spectrum of . Their centers might be chosen as the mean of the points (i.e. the hub), as the center of area of the convex hull, or as the "best" center with the smallest radius.

Last but not least, the "numerical range frame" gives a cover of the spectrum by a simple rectangle, at the expense of having to calculate four eigenvalues, two of the Hermitian part of and two of the skew-Hermitian part of .

To familiarize yourself with what is shown, start with the settings of a snapshot. Almost every item in the graphics is annotated, so mouseover the graphics to see explanations and click buttons one after the other. After any change, mouseover the graphic again. Although almost every item is explained, some annotations only show up when the respective items are not shadowed by other ones. Resize the graphics area. Look at the impact of loading the diagonal by using the "" slider. Look at the impact of changing the matrix type. Switch between Gershgorin and Brauer methods and between sum and Euclid norms. Look at the relation between the convex hull of the eigenvalues and the numerical range frame, especially for different matrix types.

[less]

Contributed by: Ludwig Weingarten (June 2011)
Open content licensed under CC BY-NC-SA


Snapshots


Details

This Demonstration carries on the ideas presented in "Enclosing the Spectrum by Gershgorin-Type Sets", so you are encouraged to read its caption and details.

We want to show 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 a lot more, to compare to its spectrum, which is what we are actually looking for, but which is usually a priori not available without huge effort. The significance or failure of the concepts for a specific matrix, presented here, 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 ; . If the matrix is not normal, this method will not lead to a diagonal similarity, even if the matrix were diagonizable. In this case you can click the "ordinary" button to go over to a version that uses the proper eigensystem to similarize : is the normalization of ; . In the case of a normal matrix both methods should lead to the same result.

Originally, Gershgorin used a family of disks to cover the spectrum of a matrix . These disks are derived using seminorms built by the off-diagonal entries of rows or columns. Brauer refined those ideas to come to what is called "Brauer’s Cassini ovals". These ovals combine two rows or columns at a time to yield a narrower cover than Gershgorin's, at the expense of more labor. Ostrowski showed that combinations of row and column radii could also give closer results. Using the sum of the squares instead of the absolute values within the seminorms can lead to further refinement, but the covering is not guaranteed to be complete, so it must be taken with care. Most of the ideas presented here are explained in [1], [2], and [3].

A single disk, centered at the origin of the complex plane, with a radius called the "spectral radius", will be the most prominent covering of the spectrum of . To show it, you need to know the eigenvalue of with the biggest modulus. What we show here as "spectral circles" are disks that cover the spectrum of , but whose centers might be taken as the mean of the eigenvalues, that is, the hub, or as the center of area of the convex hull of the eigenvalues, or as the "best" center of the eigenvalues with the smallest radius. Choosing "spectral 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], p. 237, where it is attributed to Heinrich). It serves as an a priori estimate of the spectral circle.

The next circles are all based on the location of the diagonal entries of : • The button "spectrum enclosure" shows a single disk enclosing the spectrum that is based on the Gershgorin circles that are actually chosen. • The button "diag boundary outer" shows the circle that encloses the whole diagonal of . • The button "diag boundary inner" shows the circle that excludes those diagonal entries of that are on the boundary of the convex hull of the diagonal. • The button "diagonal inner" shows the circle that excludes the whole diagonal of .

These four circles can all be determined for different centers. You may show them for the mean of the diagonal entries (the hub), the center of area of the convex hull of the diagonal entries, or the "best" center of the diagonal entries with the smallest radius. When changing from the matrix to its Schur similarity these four circles build a sandwich of circular rings that squeeze the spectrum.

The "numerical range frame" shows a simple framed rectangle that covers the spectrum. To determine it you have to calculate at least four eigenvalues, the minimum and maximum of the Hermitian part of and the minimum and maximum of the skew-Hermitian part of . This is possible, since each of these two parts is Hermitian, and so has only real eigenvalues. Clicking "points" positions all the eigenvalues of these two parts at appropriate locations on the frame, whereas "lines" gives a grid whose crossings are built from all possible pairs of eigenvalues of these two parts.

Note: A matrix is normal exactly when its Hermitian part and its skew-Hermitian part commute. In that case, the real part of its spectrum coincides with the spectrum of its Hermitian part and the imaginary part of its spectrum coincides with the spectrum of its skew-Hermitian part; so these two real spectra are just the projections of the spectrum of onto the real and imaginary axes. Or, conversely, the eigenvalues of can all be found under the crossings of the lines. If is not normal, you can only claim that the respective two real numerical ranges are just the projections of the numerical range of onto the real and imaginary axes; the eigenvalues of cannot, in general, be found within those crossings.

To learn more about the concept of the numerical range, see the Demonstration "Numerical Range for Some Complex Upper Triangular Matrices"and consult [4] or [5].

All matrices in the snapshots are normal.

Brauer's covering and Gershgorin's circles

Snapshot 1: all entries, diagonal entries plus eigenvalues of the original matrix , their means and their convex hull fences, the energy distribution between the diagonal and the rest, Gershgorin's circles, Brauer's covering

Snapshot 2: all entries, diagonal entries plus eigenvalues of the similarity of , for , their means and their convex hull fences, the energy distribution between the diagonal and the rest, Gershgorin's circles, Brauer's covering

Spectrum squeezing circles, centered at the hub

Snapshot 3: all entries, diagonal entries plus eigenvalues of the similarity of , for , their means and their convex hull fences, the energy distribution between the diagonal and the rest, Gershgorin's circles, spectrum squeezing circles, centered at the hub

Numerical range frame

Snapshot 4: all entries, diagonal entries plus eigenvalues of the original matrix , their means and their convex hull fences, the energy distribution between the diagonal and the rest, Gershgorin's circles, numerical range frame, plus eigenvalues of Hermitian and skew-Hermitian parts, plus their intersecting lines

References

[1] R. Zurmühl and S. Falk, Matrizen und ihre Anwendungen, Berlin/Heidelberg/New York: Springer–Verlag, 1984.

[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/New York: Springer–Verlag, 2004.

[4] R. A. Horn and C. R. Johnson, Topics in Matrix Analysis, New York: Cambridge University Press, 1991.

[5] L. N. Trefethen and M. Embree, Spectra and Pseudospectra: The Behavior of Nonnormal Matrices and Operators, Princeton, NJ: Princeton University Press, 2005.



Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send