Proof of a theorem connecting Gerschgorin circles and eigenvalues

Question

How do I prove that, given $A\in\mathbb C^{n\times n}$, if $A$ is irreducible and $\lambda$ is an eigenvalue of $A$ such that $\lambda\in\partial\left(\displaystyle\bigcup_{i=1}^nK_i\right)$, where $K_i$ is the $i$-th Gerschgorin circle and $\partial(\cdot)$ denotes the boundary of the set $\cdot$, then for all $i=1,\dots,n$, $\lambda\in\partial K_i$?

Answer 1

Taussky's theorem gives us that if $B=(b_{ij})$ is irreducible, diagonally dominant -- that is, $$\tag{1}|b_{ii}|\ge\sum_{j=1,\,j\ne i}^n|b_{ij}|$$ for all $i$ --, and the inequality in (1) is strict for at least one $i$, then $B$ is invertible.

Your result follows from this immediately: Let $A=(a_{ij})$ and $\lambda$ be as in your assumptions, and let $B=(b_{ij})$ be the matrix $A-\lambda I$. Note that the $B$ is still irreducible. Your assumption gives us that, for any $i$, $|b_{ii}|=|\lambda-a_{ii}|\ge\sum_{j=1,\,j\ne i}^n|a_{ij}|=\sum_{j=1,\,j\ne i}^n|b_{ij}|$, that is, (1) holds. However, $B$ is not invertible, since $\lambda$ was an eigenvalue of $A$, and therefore $\lambda-\lambda=0$ is an eigenvalue of $B$.

It follows that the inequality in (1) cannot be strict for any $i$, and therefore we must have equality in (1) for all $i$, which means precisely that $\lambda$ is in the boundary of all Geršgorin circles.

---

Let me sketch Taussky's result, in case you have not seen the proof. The proof starts along the same lines of the proof of Geršgorin's theorem.

Let $B$ be $n\times n$. The argument assumes that irreducibility of $B$ is equivalent to the strong connectedness of the graph $G(B)$. Recall that $G(B)$ is the directed graph on $\{1,\dots,n\}$ where (for any $s,l$ with $1\le s,l\le n$) there is an arc from $s$ to $l$, $s\to l$, iff $b_{sl}\ne 0$. The graph is connected iff for any two (not necessarily distinct) vertices $s,l$ there is a (non-empty) directed path $s\to j_1\to\dots\to j_m\to l$. Irreducibility of $B$, on the other hand, means that $B$ is not similar via a permutation to a block upper triangular matrix with more than one block.

We may assume $B$ is $n\times n$ with $n>1$. Suppose $B$ is singular, so there is a vector $x=(x_1,\dots,x_n)^T\ne 0$ with $Bx=0$. By replacing $x$ with a nonzero multiple, if needed, we may assume that $$ 1=\max\{|x_k|\mid 1\le k\le n\}. $$
Let $S=\{j\mid |x_j|=1\}$. Since $Bx=0$, we have that $\sum_j b_{kj}x_j=0x_k=0$ for all $k$, that is, $$ -b_{kk}x_k=\sum_{j=1,\,j\ne k}^nb_{kj}x_j $$ for all $k$. In particular, if $k\in S$, we have that $$ \tag{2}|b_{k,k}|\le\sum_{j=1,\,j\ne k}^n|b_{kj}||x_j|\le\sum_{j=1,\,j\ne k}^n|b_{kj}|. $$ By (1), it follows that we actually have an equality here. Since one of the assumptions is that (1) is strict for at least one $i$, it follows that $S\ne \{1,2,\dots,n\}$.

Let $k\in S$. Since $B$ is irreducible, it cannot be that all $b_{kj}$ with $j\ne k$ are $0$. However, since we have equality in (2), if $j$ is such that $b_{kj}\ne0$, then we must have that $|x_j|=1$, that is, $j\in S$. We have reached a contradiction: Let $i\notin S$. By irreducibility, there is a path $$ k\to j_1\to j_2\to\dots\to j_m\to i $$ in the directed graph $G(B)$ associated to $B$. We just proved that if $s\in S$ and there is an arc $s\to l$ in this graph, then $l\in S$ as well. Since $k\in S$, it follows that $j_1\in S$ and, similarly, $j_2\in S,\dots,j_m\in S$ and, finally, $i\in S$. This is a contradiction.

A nice recent reference for this result is the book Geršgorin and his circles, by Richard S. Varga. (Coincidentally, I was lecturing on this topic a week ago.)