Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

We all know Gershgorin's Circle Theorem, which I will summarise for convenience. Let $A=(a_{ij})$ be an $n\times n$ complex matrix. Define the disks $D_1,\ldots,D_n$ by $$D_i = \Bigl\{ z : |z-a_{ii}|\le \sum_{j\ne i} |a_{ij}|\Bigr\}.$$ Then each eigenvalue of $A$ lies in one of the disks. Moreover, if a connected component of the union of the disks contains $k$ disks, then exactly $k$ eigenvalues of $A$ lie in that union.

My question is when a stronger statement is true. When is it possible to list the eignvalues $\lambda_1,\ldots,\lambda_n$ in such an order that $\lambda_i\in D_i$ for all $i$?

What is a small counterexample for general matrices? Is there a counterexample for real symmetric matrices? Is there a nice family of matrices for which there is no counterexample?

Note that by Hall's marriage theorem, the stronger statement is equivalent to saying that for each $k$, the union of any $k$ disks includes at least $k$ eigenvalues.

share|improve this question
3  
A minimal counterexample to your stronger statement could be $$\left(\begin{array}{rr}1&-1\\2&-1\end{array}\right)$$ the eigenvalues are $i$ and $-i$, but they are both ouside the disk with center $1$ and radius $1$ ( or center $-1$ and radius $1$ if you want to use the columns). –  Samuele Aug 13 '11 at 14:32
    
However it is true that every connected component of the union consisting of k disks has exactly k zeroes in it :). –  fedja Aug 13 '11 at 16:28
1  
@fedja: that is a well know theorem ... i wasn't even trying to exhibit a counterexample for that :P Back to the problem, the matrices $$\left(\begin{array}{rr}-1&-a&0\\1/a&0&1/a\\0&-a&1\end{array}\right)$$ with $a$ small enough are again counterexamples (they have eigenvalues $0$, $\pm i$). –  Samuele Aug 13 '11 at 17:21
    
The strong statement being obviously false for general complex matrices, there remains the interesting question of its validity for Hermitian matrices or real symmetric ones. –  Denis Serre Aug 15 '11 at 20:38

1 Answer 1

Let $A$ be a Hermitian matrix. Let $c$ be column $j$ of $A$, but with element $j$ set to zero, and let $E = ce_j^T + e_j c^T$, where $e_j$ is a standard basis vector. Note that $A-E$ has $a_{jj}$ as an eigenvalue, and a straightforward computation gives that

$$\|E\|_2 = \|c\|_2 \leq \|c\|_1$$

Because $A$ and $A-E$ are both Hermitian, we know that there is an eigenvalue of $A$ within $\|E\|$ of each eigenvalue of $A-E$. In particular, there is an eigenvalue $\lambda$ of $A$ such that $|\lambda - a_{jj}| < \|c\|_1$ -- that is, there is an eigenvalue of $A$ in the $j$th Gerschgorin disk.

share|improve this answer
    
This is a great start. Can you show that each pair of disks contain between them two eigenvalues? Say there are disks $D_1,D_2,D_3$ with $D_1,D_2$ overlapping, $D_2,D_3$ overlapping, and $D_1,D_3$ not overlapping. Can we have one eigenvalue in $D_1\cap D_2$ and two in $D_3-D_1$? This would satisfy both the Gershgorin theorem and your theorem but would not allow a different eigenvalue to be selected for each disk. –  Brendan McKay Feb 22 '13 at 2:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.