16
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 4
    $\begingroup$ 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). $\endgroup$
    – Samuele
    Commented Aug 13, 2011 at 14:32
  • $\begingroup$ However it is true that every connected component of the union consisting of k disks has exactly k zeroes in it :). $\endgroup$
    – fedja
    Commented Aug 13, 2011 at 16:28
  • 1
    $\begingroup$ @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$). $\endgroup$
    – Samuele
    Commented Aug 13, 2011 at 17:21
  • $\begingroup$ 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. $\endgroup$
    – Denis Serre
    Commented Aug 15, 2011 at 20:38

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Brendan McKay
    Commented Feb 22, 2013 at 2:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .