6
$\begingroup$

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?

  • 0
    I don't have the book with me to check, but you might be able to find something useful in Varga's *[Geršgorin and His Circles](http://books.google.com/books?hl=en&id=W3k0a70-Hs0C)*.2012-07-31

2 Answers 2

6

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

  • 0
    Very nice, thanks!2012-07-31
1

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$).