The n-Category Café

To be honest, I don’t. Maybe that’s not surprising: I guess Gershgorin’s theorem is most often used (and taught) in the context of numerical linear algebra, and I know very little about that subject. But I have a biologist friend who’s got a real thing about Gershgorin discs — I should ask him why!

But speaking generally, here are some uses of the theorem:

• Any square matrix $A$ whose diagonal entries are big enough relative to the rest of the row (precisely: $|a_{i i}| \gt \sum_{j \neq i} |a_{i j}|$ for all $i$) is invertible.

• Any real symmetric matrix such that $a_{i i} \gt \sum_{j \neq i} |a_{i j}|$ for all $i$ is positive definite.

• For any square matrix, we get an upper bound on the absolute values of the eigenvalues: they can be no greater than the largest of the absolute row-sums $\sum_j |a_{i j}|$. Since the dominant eigenvalue is very important in many dynamics problems, often governing rates of growth, that’s potentially quite useful.

I think the only time I’ve seriously used Gershgorin’s theorem in my own research was in Proposition 10.8 of this. I can’t claim that this is a particularly compelling application, but here’s what we (or rather my coauthor Mark Meckes) did:

• We started with a real symmetric matrix $Z$ with $1$s all the way down the diagonal and $\sum_{j \neq i} |Z_{i j}| \lt 1$ for all $i$.

• By Gershgorin, every eigenvalue is in the interval $(0, 2)$.

• It follows that every eigenvalue of $I - Z$ has absolute value strictly less than $1$.

• And from this it follows that the infinite sum $\sum_{k \geq 0} (I - Z)^k$ converges — to $Z^{-1}$, of course.

So in this case, it helped us get a series expansion for the inverse of a matrix.

Sometimes called “Gershgorin’s Circle Theorem”

Right — lots of people do call it that. But mathematicians settled long ago on using “circle” for the hollow shape and “disc” for the solid shape, and the actual circles play no particular role in Gershgorin’s theorem; it’s the discs that matter. So I prefer the name “Gershgorin disc theorem”. The canonical text Matrix Analysis of Horn and Johnson also calls it that.

Aha, I hadn’t realized that equivalence — that’s nice. Let me repeat what you wrote for anyone too lazy to click.

We’re talking about two theorems here:

• the Gershgorin disc theorem

• what’s sometimes called the Levy–Desplanques theorem: any square matrix $A$ satisfying $|a_{i i}| \gt \sum_{j \neq i} |a_{i j}|$ for all $i$ is invertible. (Such matrices are called “strictly diagonally dominant”.)

I observed that Levy–Desplanques is an easy consequence of Gershgorin (since if $A$ satisfies the hypotheses of the L-D theorem then none of the discs contains $0$).

But you’re observing the converse: Gershgorin is also an easy consequence of Levy–Desplanques! Indeed, assume L-D and let $\lambda$ be an eigenvalue of a matrix $A$. Then $A - \lambda$ is not invertible, so by the contrapositive of L-D, there is some $i$ such that $|a_{i i} - \lambda| \leq \sum_{j \neq i} |a_{i j}|$. Done!

I seem to have hit on something important. There’s a book called Geršgorin and his Circles by the distinguished numerical linear algebraist Richard Varga, and in the introduction he writes:

There are two main recurring themes which the reader will see in this book. The first recurring theme is that a nonsingularity theorem for matrices gives rise to an equivalent eigenvalue inclusion set in the complex plane for matrices, and conversely. Though common knowledge today, this was not widely recognized until many years after Geršgorin’s paper appeared [in 1931].

He gives an example later on: the Levy–Desplanques theorem (which is a nonsingularity theorem) and the Gershgorin theorem (which gives an “eigenvalue inclusion set” — the union of the Gershgorin discs). But I don’t know any other examples. I’m viewing the book via Amazon’s preview, and it doesn’t let me see any more. I wonder what other examples there are.

Lucky you! I never took a course on matrix analysis, and that kind of thing didn’t appeal to me at all when I was an undergraduate.

The course I teach is for students entering directly into the second year of our degree programme. It’s called “Accelerated Algebra”, and it’s very accelerated because they have to catch up with all the first year linear algebra in less than half the usual time. So it’s really very difficult for me to fit in anything non-essential. Nevertheless, I now plan to set a couple of exercises on Gershgorin’s theorem: one to guide the students through a proof, and another to get them to apply it to some specific matrices.

Thanks!

Evelyn Lamb on Twitter also asked who’d been taught this, and got lots of responses. Well: perhaps it’s predictable that those who’d seen it would be more likely to respond than those who hadn’t. But I liked her ultimate verdict.

Wowee! That’s a nice companion to Andrej Bauer’s recent story about nuclear safety relying on the convergence of the harmonic series. (I exaggerate… at least a little!)

Ah yes, that’s a good alternative.

It moves me to point out a different connection between the operator norm $\|\cdot\|_\infty$ and the Gershgorin disc theorem. Well, I say “point out”, but not because I think you don’t know it, Mark — more because it’s the kind of thing I’m likely to forget unless I write it down.

Gershgorin swiftly implies that for any eigenvalue $\lambda$ of a matrix $A = (a_{i j})$,

$$|\lambda| \leq \max_i \sum_j |a_{i j}|.$$

But as you point out, the right-hand side here is an explicit expression for $\|A\|_\infty$. So,

$$|\lambda| \leq \|A\|_\infty.$$

On the other hand, that’s very easy to see without going anywhere near Gershgorin’s theorem: simply choose a $\lambda$-eigenvector $x$, note that

$$|\lambda| \|x\|_\infty = \|\lambda x\|_\infty = \|A x\|_\infty \leq \|A\|_\infty \|x\|_\infty,$$

and cancel $\|x\|_\infty$. (Of course, the same argument shows that all the other norms $\|A\|_p$ are also upper bounds for the absolute eigenvalues.)

You’re absolutely right: you could use columns instead. It’s a trade-off, though! When you switch from rows to columns, some discs may get smaller… but then others must get bigger. It’s never the case that they all get smaller.

Take the example matrix I gave in the post:

$$\begin{pmatrix} 3 &i& 1\\ -1 &4+5i &2\\ 2&1&-1 \end{pmatrix}.$$

Using rows gives you discs with:

• centre $3$, radius $2$;
• centre $4+5i$, radius $3$;
• centre $-1$, radius $3$.

Write $G$ for the union of those three discs.

On the other hand, using columns gives you discs with:

• centre $3$, radius $3$;
• centre $4+5i$, radius $2$;
• centre $-1$, radius $3$.

Write $G'$ for the union of these three discs.

When you switch from rows to columns, the first disc grows, the second shrinks, and the third stays the same. It’s easy to see why they can’t all shrink: for whether you use rows or columns, the sum of the three radii is the same, $\sum_{i \neq j} |a_{i j}|$. In this case, both sums are $8$.

Nevertheless, since the eigenvalues all lie in $G$ and all lie in $G'$, they all lie in $G \cap G'$. This is a smaller set than $G$ (or $G'$), so you do gain something by considering columns as well as rows.

If I was more energetic I’d insert a picture here.

There are related theorems that look at the rows and columns simultaneously. For example, a theorem of Ostrowski (different from the one already mentioned above) states that for each $\alpha \in [0,1]$, the eigenvalues of $A$ lie in one of the discs $$\{ z : |z-a_{ii} \le r_i^\alpha c_i^{1-\alpha} \},$$ where $$r_i = \sum_{j \neq i} |a_{ij}| \; and \; c_i = \sum_{j \neq i} |a_{ji}|.$$