Numerical Analysis HT24, Gerschgorin's theorems
Flashcards
State Gerschgorin’s (first) theorem, which places bounds on the locations of eigenvalues for a given matrix $A$.
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$.
Quickly prove Gerschgorin’s (first) theorem, i.e. that if
- $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.
Gerschgorin’s first theorem states that if:
- $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$. Can you state Gerschgorin’s second theorem, which strengthens this result?
If any union of $k$ discs is disjoint from the other discs, then it contains $k$ eigenvalues.
Gerschgorin’s first theorem states that if:
- $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$. Gerschgorin’s second theorem then says that if any union of $k$ discs is disjoint from the other discs, then it contains $k$ eigenvalues.
Give a counterexample to show that it is not true that every disc $D _ i$ contains at least one eigenvalue.::
\[\begin{pmatrix} 1 & 1 \\\\ -\varepsilon & 1 \end{pmatrix}\]Then the eigenvalues are $1 \pm i\sqrt \varepsilon$ and the Gerschgorin discs are:
\[\begin{aligned} &|z - 1| \le 1 \\\\ &|z - 1| \le \varepsilon \end{aligned}\]Since $\sqrt \varepsilon \ge \varepsilon$ for $\varepsilon < 1$, $1 \pm i\sqrt \varepsilon$ are not in the second disc.
Gerschgorin’s first theorem states that if:
- $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$. Gerschgorin’s second theorem then says that if any union of $k$ discs is disjoint from the other discs, then it contains $k$ eigenvalues. What’s the rough idea behind the proof?
Consider $\gamma : [0, 1] \to \mathbb C^{n \times n}$ given by $\gamma(t) = tA + (1 - t)D$ where $D$ is the diagonal matrix with entries from the diagonal of $A$. Then $\gamma(0) = D$ and all discs are actually just points. Then as $t$ increases, $\gamma(t)$ smoothly transitions between $D$ and $A$, which means that the eigenvalues smoothly transition from their location as points to the final discs (by Ostrowski’s theorem, which is non-examinable). Since the eigenvalues can’t “jump”, the result follows.
Gerschgorin’s first theorem states that if:
- $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$. Can you give an example to show that eigenvalues can in fact lie on the boundary of the discs?
Then it has eigenvalue $3$, which lies on the bounary of the discs.
Gerschgorin’s first theorem states that if:
- $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}| \\}\]There is another result that $\lambda$ lies in the subset of $\bigcup D _ i$ given by the $n \choose 2$ discs given by
\[C_{i,j} = \\{ z \in \mathbb{C} \, \Bigg| \, |a_{ii} - z||a_{jj} - z| \leq \left( \sum_{\substack{k=1 \\ k \neq i}}^n |a_{ik}| \right) \left( \sum_{\substack{k=1 \\ k \neq j}}^n |a_{jk}| \right) \\}, \quad 1 \leq i < j \leq n\]What’s the rough idea behind proving this?::
In the original proof of Gerschgorin’s theorem, you only keep track of the largest component of the eigenvector. For this, you keep track of both, and then multiply the inequalities together.
How could you work out the matrix
\[A = \begin{bmatrix} 9 & 1 & 0 & 0 \\\\ -1 & 3 & 1 & 0 \\\\ 0 & 1 & -4 & 1 \\\\ 0 & 0 & 1 & -5 \end{bmatrix}\]is nonsingular (or other properties of the eigenvalues) without explicitly finding the determinant?::
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.