Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



The spectra of large Toeplitz band matrices with a randomly perturbed entry

Authors: A. Böttcher, M. Embree and V. I. Sokolov
Journal: Math. Comp. 72 (2003), 1329-1348
MSC (2000): Primary 47B35, 65F15; Secondary 15A18, 47B80, 82B44
Published electronically: February 3, 2003
MathSciNet review: 1972739
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: This paper is concerned with the union $\operatorname{sp}_\Omega^{(j,k)} T_n(a)$of all possible spectra that may emerge when perturbing a large $n \times n$ Toeplitz band matrix $T_n(a)$ in the $(j,k)$ site by a number randomly chosen from some set $\Omega$. The main results give descriptive bounds and, in several interesting situations, even provide complete identifications of the limit of $\operatorname{sp}_\Omega^{(j,k)} T_n(a)$ as $n \to \infty$. Also discussed are the cases of small and large sets $\Omega$ as well as the ``discontinuity of the infinite volume case'', which means that in general $\operatorname{sp}_\Omega^{(j,k)} T_n(a)$ does not converge to something close to $\operatorname{sp}_\Omega^{(j,k)} T(a)$ as $n \to \infty$, where $T(a)$ is the corresponding infinite Toeplitz matrix. Illustrations are provided for tridiagonal Toeplitz matrices, a notable special case.

References [Enhancements On Off] (What's this?)

  • 1. R. M. Beam and R. F. Warming: The asymptotic spectra of banded Toeplitz and quasi-Toeplitz matrices. SIAM J. Sci. Comput. 14 (1993), 971-1006. MR 94g:65041
  • 2. A. Böttcher: Pseudospectra and singular values of large convolution operators. J. Integral Equations Appl. 6 (1994), 267-301. MR 96a:47044
  • 3. A. Böttcher, M. Embree, and M. Lindner: Spectral approximation of banded Laurent matrices with localized random perturbations. Integral Equations Operator Theory 42 (2002), 142-165.
  • 4. A. Böttcher, M. Embree, and V. I. Sokolov: Infinite Toeplitz and Laurent matrices with localized impurities. Linear Algebra Appl. 343-344 (2002), 101-118.
  • 5. A. Böttcher, M. Embree, and V. I. Sokolov: On large Toeplitz matrices with an uncertain block. Linear Algebra Appl., to appear.
  • 6. A. Böttcher and S. M. Grudsky: Can spectral value sets of Toeplitz band matrices jump? Linear Algebra Appl. 351-352 (2002), 99-116.
  • 7. A. Böttcher and B. Silbermann: Introduction to Large Truncated Toeplitz Matrices. Universitext, Springer-Verlag, New York 1999. MR 2001b:47043
  • 8. E. B. Davies: Spectral properties of random non-self-adjoint matrices and operators. Proc. Roy. Soc. London Ser. A 457 (2001), 191-206. MR 2002f:47082
  • 9. U. Elsner, V. Mehrmann, F. Milde, R. A. Römer, and M. Schreiber: The Anderson model of localization: a challenge for modern eigenvalue methods. SIAM J. Sci. Comput. 20 (1999), 2089-2102. MR 2000f:65031
  • 10. J. Feinberg and A. Zee: Non-Hermitian localization and delocalization. Phys. Rev. E 59 (1999), 6433-6443.
  • 11. C. W. Gear: A simple set of test matrices for eigenvalue programs. Math. Comp. 23 (1969), 119-125. MR 38:6753
  • 12. I. Gohberg: On an application of the theory of normed rings to singular integral equations. Uspekhi Matem. Nauk 7 (1952), no. 2, 149-156 [Russian]. MR 14:54a
  • 13. B. Gustafsson, H.-O. Kreiss, and A. Sundström: Stability theory of difference approximations for mixed initial boundary value problems II. Math. Comp. 26 (1972), 649-686. MR 49:6634
  • 14. R. Hagen, S. Roch, and B. Silbermann: $C^*$-Algebras in Numerical Analysis. Marcel Dekker, New York 2001. MR 2002g:46133
  • 15. N. Hatano and D. R. Nelson: Vortex pinning and non-Hermitian quantum mechanics. Phys. Rev. B 56 (1997), 8651-8673.
  • 16. F. Hausdorff: Set Theory. Chelsea, New York 1957. MR 19:111a
  • 17. D. Hinrichsen and B. Kelb: Spectral value sets: a graphical tool for robustness analysis. Systems & Control Letters 21 (1993), 127-136. MR 94e:93038
  • 18. D. Hinrichsen and A. J. Pritchard: Real and complex stability radii: a survey. In: D. Hinrichsen and B. Mårtensson (eds.), Control of Uncertain Systems, Progress in Systems and Control Theory, Vol. 6, pp. 119-162, Birkhäuser Verlag, Basel 1990. MR 94j:93002
  • 19. H.-O. Kreiss: Stability theory of difference approximations for mixed initial boundary value problems I. Math. Comp. 22 (1968), 703-714. MR 39:2355
  • 20. H. J. Landau: On Szego's eigenvalue distribution theorem and non-Hermitian kernels. J. d'Analyse Math. 28 (1975), 335-357. MR 58:7219
  • 21. X. Liu, G. Strang, and S. Ott: Localized eigenvectors from widely spaced matrix modifications, in preparation; see also G. Strang, ``From the SIAM President'', SIAM News, April 2000, May 2000.
  • 22. Yanuan Ma and Alan Edelman: Nongeneric eigenvalue perturbations of Jordan blocks. Linear Algebra Appl. 273 (1998), 45-63. MR 99d:15016
  • 23. D. R. Nelson and N. M. Shnerb: Non-Hermitian localization and population biology, Phys. Rev. E 58 (1998), 1383-1403. MR 99g:92029
  • 24. L. Reichel and L. N. Trefethen: Eigenvalues and pseudo-eigenvalues of Toeplitz matrices. Linear Algebra Appl. 162 (1992), 153-185. MR 92k:15028
  • 25. R. Remmert: Funktionentheorie 1. Fourth edition, Springer-Verlag, Berlin and Heidelberg 1995. MR 85h:30001
  • 26. P. Schmidt and F. Spitzer: The Toeplitz matrices of an arbitrary Laurent polynomial. Math. Scand. 8 (1960), 15-38. MR 23:A1977
  • 27. L. N. Trefethen: Pseudospectra of linear operators. SIAM Review 39 (1997), 383-406. MR 98i:47004
  • 28. L. N. Trefethen: Spectra and pseudospectra: the behavior of non-normal matrices and operators. In: M. Ainsworth, J. Levesley, and M. Marletta (eds.), The Graduate Student's Guide to Numerical Analysis '98, pp. 217-250, Springer-Verlag, Berlin 1999. MR 2000e:65001
  • 29. L. N. Trefethen, M. Contedini, and M. Embree: Spectra, pseudospectra, and localization for random bidiagonal matrices. Comm. Pure Appl. Math. 54 (2001), 595-623. MR 2002c:15047
  • 30. T. G. Wright: MATLAB Pseudospectra GUI (2001). Available online at http://www.comlab.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 47B35, 65F15, 15A18, 47B80, 82B44

Retrieve articles in all journals with MSC (2000): 47B35, 65F15, 15A18, 47B80, 82B44

Additional Information

A. Böttcher
Affiliation: Fakultät für Mathematik, TU Chemnitz, 09107 Chemnitz, Germany

M. Embree
Affiliation: Oxford University Computing Laboratory, Wolfson Building, Parks Road, Oxford OX1 3QD, United Kingdom
Address at time of publication: Department of Computational and Applied Mathematics, Rice University, 6100 Main Street – MS 134, Houston, Texas 77005–1892

V. I. Sokolov
Affiliation: Fakultät für Mathematik, TU Chemnitz, 09107 Chemnitz, Germany
Address at time of publication: Institut für Mathematik, TU Berlin, 10623 Berlin, Germany

Keywords: Toeplitz operator, pseudospectrum, random perturbation
Received by editor(s): August 3, 2001
Published electronically: February 3, 2003
Additional Notes: The work of the second author was supported by UK Engineering and Physical Sciences Research Council Grant GR/M12414.
Article copyright: © Copyright 2003 American Mathematical Society

American Mathematical Society