Discs that fence in the eigenvalues

The eigenvalues of a matrix are the roots of a polynomial, and for anything larger than four by four there is no formula for them. They are found by iteration, the iteration takes time, and it answers a question much more precise than the one usually being asked. Very often what is wanted is not the eigenvalues but a fence round them: are they all to the left of zero, is none of them near one, could any of them be zero at all.

A fence can be read straight off the entries. Draw a disc in the complex plane for each row of the matrix. Centre it on that row’s diagonal entry. Give it a radius equal to the sum of the absolute values of the other entries in the row. Then every eigenvalue lies in at least one of the discs. And when the discs fall into separate clusters, a cluster made of $k$ discs holds exactly $k$ eigenvalues — so an isolated disc holds exactly one.

Semyon Gershgorin published it in 1931, in a paper of a few pages. It may be the most useful theorem about eigenvalues that requires no computation of eigenvalues, and it has two proofs worth drawing: one line for the containment and a continuity argument for the count.

Three rows and three discs #

The hero is a three-by-three matrix with modest entries off the diagonal:

$$A = \begin{pmatrix} 4 & 1 & 0.5 \\ 0.6 & -1 & 0.8 \\ 0.3 & 0.4 & -5 \end{pmatrix}.$$

Row one says: a disc centred at $4$, of radius $1 + 0.5 = 1.5$. Row two: centred at $-1$, radius $0.6 + 0.8 = 1.4$. Row three: centred at $-5$, radius $0.7$. The three discs do not touch, so the theorem makes a precise promise without any arithmetic beyond addition: one eigenvalue within $1.5$ of $4$, one within $1.4$ of $-1$, one within $0.7$ of $-5$.

The eigenvalues turn out to be $4.14$, $-1.06$ and $-5.09$, and they sit close to the centres — far closer than the radii allow. That is typical. The radius is a worst case, obtained by assuming every off-diagonal entry pushes in the same direction at once, and in practice the pushes partly cancel. The theorem is loose in exactly the way a triangle inequality is loose, and for the same reason: it is one.

What makes the fence worth having is that it costs a row sum. For a matrix with a thousand rows it costs a thousand row sums, which is nothing, and it says something true about every eigenvalue simultaneously. No iterative method gives a guaranteed statement about all of them until it has finished.

The proof is one line about the largest entry #

Suppose $Ax = \lambda x$ with $x$ not zero. Pick the index $i$ at which $|x_i|$ is largest, and read off the $i$-th row of the equation:

$$\sum_j a_{ij} x_j = \lambda x_i, \qquad\text{so}\qquad (\lambda - a_{ii})\,x_i = \sum_{j \ne i} a_{ij} x_j.$$

Take sizes of both sides. On the right every $|x_j|$ is at most $|x_i|$, because $i$ was chosen to make $|x_i|$ the largest. So

$$|\lambda - a_{ii}|\,|x_i| \le \sum_{j\ne i} |a_{ij}|\,|x_i|,$$

and dividing by $|x_i|$, which is not zero, gives $|\lambda - a_{ii}| \le r_i$: the eigenvalue is in the $i$-th disc.

That is the whole proof, and it tells more than it seems to. It says which disc: the one belonging to the row where the eigenvector is largest. An eigenvector concentrated on its first coordinate puts its eigenvalue in the first disc. That is the intuition worth keeping. A diagonal entry is the eigenvalue the matrix would have if its row did not talk to the others, and the radius measures how loudly the other rows talk back.

The same argument appears in a place that looks unrelated. The rule that forgets where it came from is a matrix of transition probabilities whose rows add up to one. Every entry is between nought and one, so each disc is centred at $p_{ii}$ with radius $1 - p_{ii}$, and every such disc sits inside the unit disc, touching it at $1$. No eigenvalue of any transition matrix can be larger than one in size — which is the fact that makes the long-run behaviour of a Markov chain settle rather than blow up, and here it costs nothing but the row sums the chain was defined by.

A disc that holds nothing #

The counting statement is about clusters, not about individual discs, and the reason it has to be becomes obvious on the smallest example where it matters.

$$B = \begin{pmatrix} 1 & -1 \\ 2 & -1 \end{pmatrix}$$

Row one gives a disc of radius $1$ about $1$. Row two gives a disc of radius $2$ about $-1$. The two discs touch, so they form a single cluster of two, and the theorem promises two eigenvalues in the union. It says nothing about how they divide between the discs.

The eigenvalues are $\pm i$ — the trace is $0$ and the determinant is $1$ — and both lie in the disc about $-1$, at distance $\sqrt 2$ from its centre, well inside its radius of $2$. The disc about $1$ is empty. Every eigenvector of $B$ is largest in its second coordinate, which is exactly what the one-line proof predicts: the eigenvalue goes to the disc of the row where the eigenvector peaks, and neither eigenvector peaks in row one.

It is worth dwelling on the fact that the eigenvalues here are not real, because it is what makes the theorem more than an inequality about numbers on a line. The discs live in the complex plane even when every entry of the matrix is real, and they have to, since a real matrix can turn rather than stretch. $B$ turns: applied twice it gives minus the identity, a half-turn, so applied once it is a quarter-turn in a skewed frame. The fence that contains its eigenvalues must reach off the real axis, and it does.

Why a separate cluster holds exactly its own share #

The count needs a different kind of argument, because the one-line proof only places each eigenvalue in some disc and never rules a disc out. The argument is a continuity argument, and it is the part of the theorem that is genuinely clever.

Split the matrix into its diagonal part $D$ and everything else $N$, and consider the family $A(t) = D + tN$ for $t$ running from nought to one. At $t = 0$ the matrix is diagonal, its eigenvalues are the diagonal entries, and the discs have shrunk to their centres. At $t = 1$ it is the matrix itself. For every $t$ in between, the discs of $A(t)$ have the same centres and radii $t\,r_i$, so they grow steadily and each one stays inside its final size.

Now take a cluster of $k$ discs at $t = 1$ that is separated from the rest by a gap. At every earlier $t$ the same discs are smaller, so the cluster is still separated by at least that gap. At $t = 0$ the cluster holds exactly $k$ eigenvalues, its $k$ diagonal entries. As $t$ increases the eigenvalues move — and they move continuously, because they are roots of a polynomial whose coefficients move continuously, and roots cannot jump. To leave the cluster an eigenvalue would have to cross the gap, and the gap is outside every disc at every stage, so no eigenvalue is ever there. The count cannot change. At $t = 1$ it is still $k$.

The figure shows the argument happening. Two of the four eigenvalues begin at $5$ and $4.6$, inside a pair of overlapping discs. As the off-diagonal part is switched on they drift together along the real axis, collide, and then leave it as a complex conjugate pair — a real matrix’s non-real eigenvalues always come in pairs, so two real ones must meet before they can do this. The collision is invisible to the theorem. The pair stays inside its two-disc cluster throughout, the cluster was promised two eigenvalues, and it has two, even though at the end neither of them is anywhere near either centre.

The other two eigenvalues barely move. Their discs are small and far from everything, and the paths are too short to see: each starts at a diagonal entry and ends a few hundredths away. That is the continuation argument’s quantitative content, stated loosely — an isolated disc of small radius holds an eigenvalue close to its centre, and a nearly diagonal matrix has eigenvalues nearly equal to its diagonal.

Rows or columns, whichever is tighter #

A matrix and its transpose have the same eigenvalues, since they have the same characteristic polynomial: transposing does not change a determinant. The transpose’s rows are the original’s columns, so there is a second set of discs, with the same centres and radii given by column sums, and every eigenvalue lies in the union of those too — and therefore in the intersection of the two unions.

The two sets can say very different things, which is the reason to draw both. Here is a matrix whose first row is heavy and whose first column is light:

$$C = \begin{pmatrix} 6 & 3 & 2 \\ 0.2 & 1 & 0.3 \\ 0.1 & 0.4 & -4 \end{pmatrix}.$$

By rows, the first disc has radius $5$ and engulfs the second, so rows promise two eigenvalues somewhere between $0.5$ and $11$ and one near $-4$. By columns, the first disc has radius $0.3$ and stands alone, so there is exactly one eigenvalue within $0.3$ of $6$; the other two columns give large discs that overlap. Neither set alone locates all three. Together they do: the eigenvalue near $6$ is fenced by column one, the one near $-4$ by row three, and the remaining one must be the other member of the two-disc row cluster — it is $0.90$, in row disc two, just as the heavy first row predicted.

There is nothing special about rows and columns here except that they are the two cheap choices. The next section shows that there are infinitely many more, all equally cheap, and that choosing among them is a way of sharpening the fence rather than replacing it.

Changing the matrix without changing its eigenvalues #

A matrix and $S^{-1}AS$ have the same eigenvalues for any invertible $S$ — they are the same map written against a different grid. The eigenvalues do not care about the change, but the discs very much do, because the discs are read off the entries and the entries do change. So every invertible $S$ gives a set of discs, every one of those sets contains all the eigenvalues, and the intersection of all of them is the true set of eigenvalues. That intersection is useless to compute. But one family of changes is cheap and often decisive: scaling by a diagonal matrix.

With $S = \operatorname{diag}(d_1, \ldots, d_n)$, the entry in row $i$ and column $j$ becomes $a_{ij}\,d_j/d_i$. The diagonal is untouched, so the centres stay put. Row $i$’s radius is multiplied through by $1/d_i$ and each entry in it by $d_j$. Making $d_1$ large shrinks row one’s disc by that factor and inflates the first column’s contribution to every other row by the same factor. It is a trade: one disc tightens and the others loosen, by amounts that can be computed before anything is drawn.

For the matrix $C$, weighting the first coordinate by four shrinks row one’s radius from $5$ to $1.25$. Rows two and three pay for it — their first entries are multiplied by four, raising their radii from $0.5$ to $1.1$ and $0.8$ — but those rows had small entries in the first column, so the price is low. The three discs come apart, and each eigenvalue is now isolated in its own. The eigenvalues did not move; the fence got tighter.

For a matrix with positive entries, the best such scaling gives the largest eigenvalue exactly. That is the Collatz–Wielandt formula, and it is the surprising end of this road: the largest eigenvalue of a positive matrix equals the smallest possible value of the largest row sum of $S^{-1}AS$ over positive diagonal $S$ — and a row sum of a positive matrix is exactly the right-hand edge of its disc. The bound is not merely good in that case — optimised, it is the answer, and the optimal weights are the entries of the eigenvector. This is the fact behind the ranking of pages by links and the growth rate of an age-structured population, both of which are the largest eigenvalue of a matrix with no negative entries, and both of which can be certified by exhibiting weights whose scaled row sums all agree.

A diagonal that dominates cannot be singular #

Turn the theorem round and it becomes a test of invertibility. A matrix is singular exactly when $0$ is an eigenvalue — when some arrow is sent to nothing — so if $0$ lies outside every disc, the matrix is invertible. And $0$ is outside the $i$-th disc exactly when $|a_{ii}| > r_i$: when each diagonal entry is larger in size than the rest of its row put together. A matrix like that is called strictly diagonally dominant, and the conclusion is that such a matrix is never singular.

This is older than Gershgorin’s theorem and is how the theorem was first used. Lévy proved it in 1881 for a determinant arising in electrostatics, and Desplanques in general in 1887. It is the reason diagonal dominance is the first thing checked in numerical work: the matrices produced by stepping a diffusion forward implicitly — heat spreading on a rod, advanced by one time step at a time — have exactly this shape, a positive diagonal and negative neighbours that sum to less than it, and the theorem guarantees in advance that every step’s linear system has a solution.

The boundary case is where it becomes interesting. A graph’s Laplacian — the degree of each vertex on the diagonal, minus one for each edge — has every row summing to zero, so every disc touches the origin, centred at the degree with radius equal to the degree. Zero is an eigenvalue, as it must be: the all-ones vector is sent to nothing. The discs also say that no eigenvalue exceeds twice the largest degree, for free. And the multiplicity of zero, which is not visible in the discs at all, is the number of connected pieces of the graph — a fact about the same matrix whose minors count spanning trees, read at the other end.

What the discs cannot see #

The fence is honest and it is coarse, and the ways in which it is coarse are worth stating precisely rather than waving at.

It cannot tell where an eigenvalue is inside a region. A cluster of four overlapping discs promises four eigenvalues in its union and nothing more. In the dominance figure the four eigenvalues sit in a tight knot between $4$ and $5.6$ while the union stretches from $1$ to $8.5$. The discs gave the invertibility test for free and gave almost no location.

It cannot see cancellation. The radius adds absolute values, so a row with entries $+1$ and $-1$ gets the same disc as a row with $+1$ and $+1$, although the two matrices can behave completely differently. Any fence built from sizes of entries must be blind in this way, and it is the price of costing only a row sum.

It cannot see sensitivity. A matrix can have its eigenvalues neatly fenced and still have eigenvalues that move enormously when an entry is nudged — the defective case, where a perturbation of size $\varepsilon$ moves eigenvalues by $\sqrt\varepsilon$. The discs contain the perturbed eigenvalues too, since they contain every eigenvalue of every matrix with those row sums, but they say nothing about how far inside the region the eigenvalues can wander. For symmetric matrices the story is much better, because their eigenvalues are values of a function on a sphere rather than roots of a polynomial, and that is where the next essay goes.

And the figures draw one matrix at a time. The theorem is a statement about every matrix with given diagonal and given row sums at once — a whole family, most of whose members have eigenvalues nowhere near the ones marked. A drawing of one member can show that the eigenvalues are inside; it cannot show which parts of the fence are actually reached by some member. The set of all eigenvalues of all members is in general strictly smaller than the union of the discs, and describing it exactly is a separate problem, studied by Richard Varga under the name of the minimal Gershgorin set.

Further up: eigenvalues as heights on a sphere #

For a symmetric matrix the eigenvalues are real, so the discs collapse to intervals on the line, and a much sharper description becomes available. The largest eigenvalue is the highest value that the form $x^{\mathsf T}Ax$ reaches on the unit sphere, the smallest is the lowest, and every eigenvalue in between is a saddle height characterised by a min–max over subspaces. That description does not need the eigenvector’s largest entry or any row sum, and it produces a theorem the discs could never give: deleting a row and column of a symmetric matrix moves each eigenvalue no further than the next one’s old position. The next essay draws that.

Sideways, the same spirit — locate roots from coefficients without solving — runs through the polynomial root bounds, where the roots of a derivative are fenced by the roots of the polynomial, and through the winding argument that a loop round a region counts the roots inside it. The continuation proof above is that winding count in disguise: a count that cannot change while nothing crosses the boundary.

A fence built from row sums #

Every eigenvalue of a square matrix lies within one of the discs centred on the diagonal entries, with radii the sums of the sizes of the other entries in each row, and a cluster of discs separated from the rest holds exactly as many eigenvalues as it has discs. The first half is one line about an eigenvector’s largest entry. The second is a continuity argument: switch the off-diagonal part on gradually and no eigenvalue can cross a gap that no disc ever reaches.

The fence can be taken from rows or from columns, and moved by any diagonal rescaling, since all of those leave the eigenvalues fixed and change only the entries; for a non-negative matrix the best rescaling fences the largest eigenvalue exactly. Turned round, it is a test: a matrix whose diagonal outweighs each row is invertible, which is why diffusion problems always have solutions.

When a quantity is expensive to compute and cheap to bound, bound it first — most of the time the question being asked was about the bound.