Gerschgorin theorem

Question

One tricky question:

(a) Let $A\in\mathbb R^{n\times n}$ be a diagonal matrix and let $\tilde{A}=A+E$, where $E\in\mathbb R^{n\times n}$ is such that $e_{ii}=0$ for $i=1,2,\ldots,n$, and $2||E||_{\infty}<|a_{ii}-a_{jj}|$ for all $i,j\in\{1,2,\ldots,n\}$ such that $i\ne j$.

Show that:

$$|\tilde{\lambda}_i-\lambda_i|\le\sum_{j=1}^{n}|e_{ij}|,\qquad i=1,\ldots,n \qquad(*)$$

where $\lambda_i$ and $\tilde{\lambda}_i$ denote the $i$-th eigenvalue of the matrices $A$ and $\tilde{A}$, respectively.

Hint: You may use Gerschgorin theorem.

(b) Let $A=\begin{bmatrix}1&0\\0&2\end{bmatrix}$ and $E=\begin{bmatrix}0&\varepsilon\\\varepsilon&0\end{bmatrix}$, where $0\le 2\varepsilon\lt 1$. Find the eigenvalues of $A$ and $\tilde{A}=A+E$, then show that the estimate (*) holds for $i=1,2$.

---

I am aware of the Gerschgorin theorem and its proof, but it is a tricky one ! Any help would be much appreciated :)

Answer 1

For reference: Gershgorin circle theorem.

I believe your proof needs to show two things:

• The eigenvalues $\tilde{\lambda}_k$ of $\tilde{A}$ are really at the distance of not more than $\sum_{j=1}^n|e_{ij}|$ from the eigenvalues $\lambda_i$ of $A$. (Note as $A$ is diagonal, its diagonal elements are precisely $a_{ii}=\lambda_i$.)
• This inequality enables us to uniquely map the eigenvalues $\lambda_i$ of $A$ to the eigenvalues $\tilde{\lambda}_i$ of $\tilde{A}$.

The first point is a simple consequence of Gershgorin theorem applied to $\tilde{A}$. To see that, notice that $e_{ii}=0$, i.e. $\tilde{a}_{ii}=\lambda_i$ as well. Thus, every eigenvalue $\tilde{\lambda}_k$ lies in the circle centered at $\lambda_i$ (for some index $i$) with radius $\sum_{j=1,j\ne i}^n|\tilde{a}_{ij}|=\sum_{j=1,j\ne i}^n|e_{ij}|=\sum_{j=1}^n|e_{ij}|$ (as $e_{ii}=0$), i.e.

$$|\tilde{\lambda}_k-\lambda_i|\le \sum_{j=1}^n|e_{ij}|$$

for some $i$.

The second point follows from the fact that those circles are all disjoint. Namely, the distance between their centres is, per assumption, $|\lambda_i-\lambda_j|=|a_{ii}-a_{jj}|>2||E||_{\infty}=2\max_{1\le i\le n}\sum_{j=1}^{n}|e_{ij}|\ge \sum_{k=1}^n|e_{ik}|+\sum_{k=1}^n|e_{jk}|$ - i.e. the distance from their centres is strictly larger than the sum of their radiuses. Thus, as per "strengthening of Gershgorin theorem" (see the linked Wikipedia article) we can conclude that there is a bijection between the eigenvalues $\tilde{\lambda}_k$ of $\tilde{A}$ and the eigenvalues $\lambda_i$ of $A$. With a suitable renumbering of the former (so that $\tilde{\lambda}_i$ is in the circle centered at $\lambda_i$), we will have:

$$|\tilde{\lambda}_i-\lambda_i|\le \sum_{j=1}^n|e_{ij}|$$

q.e.d.