|
The Gershgorin circle theorem, http://en.wikipedia.org/wiki/Gershgorin_circle_theorem, gives bounds on the eigenvalues of a square matrix, and works well for nearly diagonal matrices. For a triangular matrix, however, the bounds are not useful in general, despite the fact that the eigenvalues are known to be the diagonal elements. Is there a version (or can some helpful person develop a version) of the Gershgorin circle theorem that gives more useful bounds in the nearly triangular case? |
|||
|
|
If $A = (a_{ij})$ is your $n \times n$ matrix, and $\alpha > 0$, let $R_i(\alpha) = \sum_{j \ne i} \alpha^{i-j} |a_{ij}|$. Then every eigenvalue $\lambda$ has $|\lambda - a_{ii}| \le R_i(\alpha)$ for some $i$. Note that if $A$ is upper triangular, $R_i(\alpha) \to 0$ as $\alpha \to \infty$, so we get the eigenvalues exactly in that limit. This is just the regular Gershgorin theorem applied to $U A U^{-1}$ where $U$ is the diagonal matrix with entries $u_{ii} = \alpha^i$. |
||||
|
|
|
There is a difference between diagonal and triangular matrices. Diagonal matrices are normal, so its eigenvalues are well-conditioned. Gershgorin's theorem makes this explicit. Triangular matrices are not necessarily normal, so its eigenvalues can be ill-conditioned. Explicit example: the eigenvalues of $\bigl[ \begin{smallmatrix} 0 & 1 \\ \epsilon & 0 \end{smallmatrix} \bigr]$ are $\pm\sqrt\epsilon$. This means that perturbation results for triangular matrices cannot be as strong as for diagonal matrices. Gershgorin's theorem can be formulated as follows: If $D$ is a diagonal matrix, then the eigenvalues of $D+E$ are within $|E|_1$ of the eigenvalues of $D$, where the norm is defined by $|E|_1 = \sum_{i,j} |e_{ij}|$. However, the example shows that there cannot be a theorem of the form: If $T$ is a triangular matrix, then the eigenvalues of $T+E$ are within $C|E|_*$ of the eigenvalues of $T$ (for some norm $|\cdot|_*$ and some constant $C$). |
|||
|
|
