06. Matrix Eigenvalues

Ostrowski

Let $A,B\in {\mathbb{R}}^{n\times n}$
Let $A=(a_{ij})$ and $B=(b_{ij})$ for $1\le i,j\le n$

Eigenvalues of $A$ are continuously dependent on $(a_{ij})$

Let

$$\{{\lambda }_i,i=1,\cdots ,n\}\text{ and }\{{\mu }_i:i=1,\cdots ,n\}$$

be the eigenvalues of $A$ and $A+B$ respectively

For any $ϵ>0$ there exists $\delta >0$ such that

$$\underset{i,j}{\max }|b_{ij}|<\delta ⟹|{\lambda }_i-{\mu }_i|<ϵ$$

Link to original

Eigenvalue Decomposition

Let $A\in {\mathbb{R}}^{n\times n}$
Let $A{x}_i={\lambda }_i{x}_i$ for $i=1,\cdots ,n$ where $x_i$ is linearly independent

Define

$$X:=[x_1,x_2,\cdots ,x_n]$$

Then $X$ is non-singular with

$$A=X\Lambda X^{-1}$$

Link to original

Schur Decomposition

Let $A\in {\mathbb{R}}^{n\times n}$ then

$$A=QT{Q}^{\ast }$$

where

$Q$ is unitary so $Q{Q}^{\ast }=Q^{\ast }Q=I_n$
$T$ is triangular

Link to original

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}|$$

Link to original

Gerschgorin's 2nd Theorem

Consider Gerschgorin Discs from Gerschgorin’s Theorem

If any union of $l$ discs is disjoint from the other discs then it contains exactly $l$ eigenvalues

Proof

Consider $B(\theta )=\theta A+(1-\theta )D$ where $D=\mathrm{diag}(A)$

As $\theta$ varies from $0$ to $1$ then $B(\theta )$ has entries varying from

$$B(0)=D\text{ to }B(1)=A$$

Hence eigenvalues vary continuously by Ostrowski’s Theorem

Gerschgorin Discs of $B(0)=D$ are points (diagonal entries) being eigenvalues of $D$
As $\theta$ increases then Gerschgorin Discs of $B(\theta )$ increase in radius about same points

Hence if $A=B(1)$ has a set of disjoint set of $l$ Gerschgorin Discs then
By continuity of eigenvalues it must contain exactly $l$ eigenvalues

Link to original