Overlapping Gershgorin disks - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T15:38:42Z http://mathoverflow.net/feeds/question/72832 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/72832/overlapping-gershgorin-disks Overlapping Gershgorin disks Brendan McKay 2011-08-13T13:38:05Z 2013-02-18T14:29:11Z <p>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 <code>$$D_i = \Bigl\{ z : |z-a_{ii}|\le \sum_{j\ne i} |a_{ij}|\Bigr\}.$$</code> 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.</p> <p>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$?</p> <p>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?</p> <p>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.</p> http://mathoverflow.net/questions/72832/overlapping-gershgorin-disks/122174#122174 Answer by David Bindel for Overlapping Gershgorin disks David Bindel 2013-02-18T14:29:11Z 2013-02-18T14:29:11Z <p>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 </p> <p>$$\|E\|_2 = \|c\|_2 \leq \|c\|_1$$</p> <p>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}| &lt; \|c\|_1$ -- that is, there is an eigenvalue of $A$ in the $j$th Gerschgorin disk.</p>