Proof of a theorem connecting Gerschgorin circles and eigenvalues

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$?

• Are you familiar with Taussky's theorem that irreducibly diagonally dominant matrices are nonsingular? – Andrés E. Caicedo Apr 12 '14 at 16:14

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.)

• Uh-huh. Actually I've never heard of this theorem and can't find it on the web. How do I prove it? NB for myself: my assumption gives that because $\lambda$ is in the boundary of the union, and not in the union of the boundaries, and therefore is outside each circle or at most on the boundary, as the inequality you state says. Finally, $B$ remains irreducible because modifying the diagonal cannot modify the matrix's graph, and because of math.stackexchange.com/questions/750817/… cannot render it reducible either. – MickG Apr 12 '14 at 16:39
• @MickG I figured that was a chance. I've added a proof of Taussky's theorem, for completeness. – Andrés E. Caicedo Apr 12 '14 at 16:50
• When you say "strong directedness", do you mean there is a path in both directions between each couple of nodes? Because that is strong connectedness to me. Then a few NBs for myself. The passage from the inequality right before (2) to (2) is obtained by applying the absolute value on both sides, then using $|ab|=|a||b|$ and $|x_j|=1$ on the left and $|a+b|\leq|a|+|b|$ and $|ab|=|a||b|$ and $|x_j|\leq1$ $\forall j$ on the right. The However is due to the equality of the two sums in (2), which gives that either $b_{kj}=0$ or $|x_j|=1$. – MickG Apr 12 '14 at 17:13
• @MickG Yes, it should be connectedness. I've edited accordingly, thanks, – Andrés E. Caicedo Apr 12 '14 at 17:24