Spectrum of random perturbations of Toeplitz matrices with finite symbols

Abstract

Let $T_N$ denote an $N\times N$ Toeplitz matrix with finite, $N$ independent symbol $\mathbf{a}$. For $E_N$ a noise matrix satisfying mild assumptions (ensuring, in particular, that $N^{-1/2}\Vert E_N{\Vert }_{\mathrm{HS}}{\to }_{N\to \infty }0$ at a polynomial rate), we prove that the empirical measure of eigenvalues of $T_N+E_N$ converges to the law of $\mathbf{a}(U)$, where $U$ is uniformly distributed on the unit circle in the complex plane. This extends results from arXiv:1712.00042 to the non-triangular setup and non complex Gaussian noise, and confirms predictions obtained in Reichel and Trefethen (1992) using the notion of pseudo-spectrum.

20 pages, to appear in Trans. Amer. Math. Soc