EIGENVALUES AND PSEUDO-EIGENVALUES OF TOEPLITZ MATRICES

The eigenvalues of a nonhermitian Toeplitz matrix A are usually highly sensitive to perturbations, having condition numbers that increase exponentially with the dimension N. An equivalent statement is that the resolvent (zI - A)-1 of a Toeplitz matrix may be much larger in norm than the eigenvalues alone would suggest-exponentially large as a function of N, even when z is far from the spectrum. Because of these facts, the meaningfulness of the eigenvalues of nonhermitian Toeplitz matrices for any but the most theoretical purposes should be considered suspect. In many applications it is more meaningful to investigate the epsilon-pseudo-eigenvalues: the complex numbers z with parallel-to (zI - A)-1 parallel-to greater-than-or-equal-to epsilon--1. This paper analyzes the pseudospectra of Toeplitz matrices, and in particular relates them to the symbols of the matrices and thereby to the spectra of the associated Toeplitz and Laurent operators. Our results are reasonably complete in the triangular case, and preliminary in the cases of nontriangular Toeplitz matrices, block Toeplitz matrices, and Toeplitz-like matrices with smoothly varying coefficients. Computed examples of pseudospectra are presented throughout, and applications in numerical analysis are mentioned.