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?

$\endgroup$
6
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Very nice, thanks! $\endgroup$ – Brian S Jul 31 '12 at 21:43
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.