next up previous contents
Next: Eigenvalues on the Up: Positive matrices Previous: Positive matrices

Gerschgorin's disks

The fundamental tool for estimating the size of eigenvalues is the eigenvalue equation itself, written out in terms of components of the eigenvectors. Thus, from the matrix equation there follows

Since the zero vector is never considered to be an eigenvector, there is at least one component which is not zero; let us select the largest among the non-zero components, move the corresponding diagonal element to the left hand side of the equation, and apply the triangle inequality. If there is any ambiguity in selecting the largest component, any one of them will do. Then

The purpose of selecting the largest component and ensuring that it was non-zero was to allow division of this equation by to obtain the factors which are all less than, or equal to, 1 (even when i=j). Thus

Since the inequality can only be enhanced by making the terms on the right hand side larger by dropping their small multipliers, we finally obtain the basic result

which applies even for complex matrices or for real matrices with complex eigenvalues. The complex setting allows a picturesque description of the results with respect to the geometry of the plane. Regarding the column sum excluding the diagonal element as a radius and the diagonal element as a center, we have found a circle which surely contains the eigenvalue.

In general, without having actually found an eigenvector, which would be its largest component would be rarely be evident; but if all the different disks were joined together, no eigenvalue could escape the collection. There is even some choice of the precise disks to be used, according to whether the diagonal element is taken as part of the radius or as part of the center; the procedure shown yields the smallest disks but, at times a common center might be preferable. Of course, the smallest disks are centered on the diagonal elements.

This estimate is due to Gerschgorin, whose name is associated with the disks. Generally the disks all intersect, and there is no correspondence between eigenvalues and disks because of the uncertainty as to which would be the largest component of any given eigenvector. Sometimes there will be disjoint clusters of disks for which continuity arguments give each cluster its quota of eigenvalues. That is, if the diagonal elements are retained and the remainder multiplied by a small parameter, continuity of the eigenvalues with respect to the coefficients of the matrix will locate the eigenvalues within small disks surrounding the diagonal elements. As the parameter is increased, eigenvalues can only wander amongst disks which overlap, but the number within a given cluster must remain constant.

Using the origin as a common center for the Gerschgorin disks leads to expressing the bounds directly in terms of row sums:

since the inequality must hold for at least one row, we could always select the worse case with full confidence that it expresses a valid bound.



next up previous contents
Next: Eigenvalues on the Up: Positive matrices Previous: Positive matrices



Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx