Numerical Analysis HT24, Gerschgorin's theorems

Suppose:

• $A \in \mathbb C^{n \times n}$
• $\lambda$ eigenvalue of $A$.

Then $\lambda$ lies in the union of the Gerschgorin discs

\[D_i = \\{ z \in \mathbb C \\;\Big\vert\\; |a_{ii} - z| \le \sum^n_{j \ne i, j = 1} |a_{ij}| \\}\]

for $i = 1, \cdots, n$.

Consider an arbitrary eigenvalue $\lambda$. Then there exists eigenvector $x \in \mathbb C^n \setminus \{\pmb 0\}$ where $Ax = \lambda x$. Expanding, for each entry $i = 1, \cdots, n$ we then have:

\[\sum_{j = 1}^n a_{ij} x_j = \lambda x_i\]

Let $x _ k = \text{argmax} \; \vert x _ j \vert $, which is guaranteed to be nonzero (since $x$ is nonzero). Then the $k$-th row of the equation $Ax = \lambda x$ gives

\[\sum^n_{j = 1} a_{kj} x_j = \lambda x_k\]

Or, moving $\lambda x _ k$ to the other side and taking out the case where $j \ne k$

\[(a_{kk} - \lambda) x_k = -\sum^n_{j = 1, j \ne k} a_{kj} x_j\]

Then dividing through by $x _ k$,

\[\begin{aligned} |a_{kk} - \lambda| &= \left| \sum^n_{j = 1, j \ne k} a_{kj} \frac{x_j}{x_k} \right| \\\\ &\le \sum^n_{j = 1, j\ne k} |a_{kj}| \left| \frac{x_j}{x_k} \right| \\\\ &\le \sum^n_{j = 1, j \ne k} |a_{kj}| \end{aligned}\]

whihch implies the result, since this is guaranteed to be a subset of the Gerschgorin discs.

If any union of $k$ discs is disjoint from the other discs, then it contains $k$ eigenvalues.

Use Gerschgorin’s first theorem, so all the eigenvalues lie in the discs

\[\begin{aligned} &|z - 9| \le 1 \\\\ &|z - 3| \le 2 \\\\ &|z + 4| \le 2 \\\\ &|z + 5| \le 1 \end{aligned}\]

which does not include the origin.