13 - Gerschgorin's Theorem

Gerschgorin's Theorem

Let $A=\{a_{ij}{\}}_{1\le i,j\le n}\in {\mathbb{R}}^{n\times n}$
Let $\lambda$ be an eigenvalue of $A$ then

$\lambda$ lies in union of Gerschgorin Discs

$$D_i=\left\{z\in \mathbb{C}\mid |a_{ii}-z|\le \sum _{\begin{array}{rl}j& \ne i\\ j& =1\end{array}}^n|a_{ij}|\right\}\text{ for }i=1,\cdots ,n$$

Proof

Let $\lambda$ be an eigenvalue of $A\in {\mathbb{R}}^{n\times n}$
Exists eigenvector $x\in {\mathbb{R}}^n$ with $Ax=\lambda x$ and $x\ne 0$ so

$$\sum _{j=1}^n{a}_{ij}{x}_j=\lambda x_i\text{ for }i=1,\cdots ,n$$

Suppose $|x_k|>|x_l|$ for $l=1,\cdots ,n$ so $x_k$ is the largest entry then
At $k$-th row for $Ax=\lambda x$ then

$$\sum _{j=1}^n{a}_{kj}{x}_j=\lambda x_k$$

Hence

$$(a_{kk}-\lambda )x_k=-\sum _{\begin{array}{rl}j& \ne k\\ j& =1\end{array}}^n{a}_{kj}{x}_j$$

Hence dividing by $x_k$ then taking absolute

$$|a_{kk}-\lambda |=\left|\sum _{\begin{array}{c}j=1\\ j\ne k\end{array}}^n{a}_{kj}\frac{x_j}{x_k}\right|\le \sum _{\begin{array}{c}j=1\\ j\ne k\end{array}}^n|a_{kj}|\left|\frac{x_j}{x_k}\right|\le \sum _{\begin{array}{c}j=1\\ j\ne k\end{array}}^n|a_{kj}|$$