Asymptotics of eigenvalues and eigenvectors of Toeplitz matrices

A. Böttcher   ; J. M. Bogoya   ; S. M. Grudsky   ; E. A. Maximenko

Sbornik. Mathematics, Tome 208 (2017) no. 11, pp. 1578-1601

Résumé

Analysis of the asymptotic behaviour of the spectral characteristics of Toeplitz matrices as the dimension of the matrix tends to infinity has a history of over 100 years. For instance, quite a number of versions of Szegő's theorem on the asymptotic behaviour of eigenvalues and of the so-called strong Szegő theorem on the asymptotic behaviour of the determinants of Toeplitz matrices are known. Starting in the 1950s, the asymptotics of the maximum and minimum eigenvalues were actively investigated. However, investigation of the individual asymptotics of all the eigenvalues and eigenvectors of Toeplitz matrices started only quite recently: the first papers on this subject were published in 2009–2010. A survey of this new field is presented here. Bibliography: 55 titles.

Détail

Keywords: Toeplitz matrices, eigenvalues, eigenvectors, asymptotic expansion.

Bibliographie

[1] G. Szegő, “Ein Grenzwertsatz über die Toeplitzschen Determinanten einer reellen positiven Funktion”, Math. Ann., 76:4 (1915), 490–503 | DOI | MR | Zbl

[2] U. Grenander, G. Szegö, Toeplitz forms and their applications, 2nd ed., Chelsea Publishing Co., New York, 1984, x+245 pp. | MR | MR | Zbl | Zbl

[3] A. Böttcher, B. Silbermann, Introduction to large truncated Toeplitz matrices, Universitext, Springer-Verlag, New York, 1999, xii+258 pp. | DOI | MR | Zbl

[4] A. Böttcher, B. Silbermann, Analysis of Toeplitz operators, Springer Monogr. Math., 2nd ed., Springer-Verlag, Berlin, 2006, xiv+665 pp. | MR | Zbl

[5] A. Böttcher, S. M. Grudsky, Spectral properties of banded Toeplitz matrices, SIAM, Philadelphia, PA, 2005, x+411 pp. | DOI | MR | Zbl

[6] B. Simon, Orthogonal polynomials on the unit circle, Part 1. Classical theory, Amer. Math. Soc. Colloq. Publ., 54, Part 1, Amer. Math. Soc., Providence, RI, 2005, xxvi+466 pp. ; Part 2. Spectral theory, Amer. Math. Soc. Colloq. Publ., 54, Part 2, i–xxii and 467–1044 | DOI | MR | Zbl | DOI | MR | Zbl

[7] G. Szegő, “Beiträge zur Theorie der Toeplitzschen Formen. I”, Math. Z., 6:3-4 (1920), 167–202 | DOI | MR | Zbl

[8] S. V. Parter, “On the distribution of the singular values of Toeplitz matrices”, Linear Algebra Appl., 80 (1986), 115–130 | DOI | MR | Zbl

[9] F. Avram, “On bilinear forms in Gaussian random variables and Toeplitz matrices”, Probab. Theory Related Fields, 79:1 (1988), 37–45 | DOI | MR | Zbl

[10] E. E. Tyrtyshnikov, “A unifying approach to some old and new theorems on distribution and clustering”, Linear Algebra Appl., 232 (1996), 1–43 | DOI | MR | Zbl

[11] S. Serra Capizzano, “Test functions, growth conditions and Toeplitz matrices”, Rend. Circ. Mat. Palermo (2) Suppl., 68, Part 2 (2002), 791–795 | MR | Zbl

[12] A. Böttcher, S. M. Grudsky, E. A. Maksimenko, “Pushing the envelope of the test functions in the Szegő and Avram–Parter theorems”, Linear Algebra Appl., 429:1 (2008), 346–366 | DOI | MR | Zbl

[13] H. Widom, “Toeplitz determinants with singular generating functions”, Amer. J. Math., 95:2 (1973), 333–383 | DOI | MR | Zbl

[14] H. Widom, “Asymptotic behavior of block Toeplitz matrices and determinants. II”, Advances in Math., 21 (1976), 1–29 | DOI | MR | Zbl

[15] H. Widom, “Eigenvalue distribution of nonselfadjoint Toeplitz matrices and the asymptotics of Toeplitz determinants in the case of nonvanishing index”, Topics in operator theory, Oper. Theory Adv. Appl., 48, Birkhäuser, Basel, 1990, 387–421 | MR | Zbl

[16] A. Böttcher, H. Widom, “Szegő via Jacobi”, Linear Algebra Appl., 419:2-3 (2006), 656–667 | DOI | MR | Zbl

[17] I. Krasovsky, “Aspects of Toeplitz determinants”, Random walks, boundaries and spectra, Progr. Probab., 64, Birkhäuser/Springer Basel AG, Basel, 2011, 305–324 | DOI | MR | Zbl

[18] P. Deift, A. Its, I. Krasovsky, “Asymptotics of Toeplitz, Hankel and Toeplitz+Hankel determinants with Fisher–Hartwig singularities”, Ann. of Math. (2), 174:2 (2011), 1243–1299 | DOI | MR | Zbl

[19] P. Deift, A. Its, I. Krasovsky, “Toeplitz matrices and Toeplitz determinants under the impetus of the Ising model: some history and some recent results”, Comm. Pure Appl. Math., 66:9 (2013), 1360–1438 | DOI | MR | Zbl

[20] M. Kac, W. L. Murdock, G. Szegő, “On the eigen-values of certain Hermitian forms”, J. Rational Mech. Anal., 2 (1953), 767–800 | MR | Zbl

[21] H. Widom, “On the eigenvalues of certain Hermitian operators”, Trans. Amer. Math. Soc., 88:2 (1958), 491–522 | DOI | MR | Zbl

[22] H. Widom, “Extreme eigenvalues of $N$-dimensional convolution operators”, Trans. Amer. Math. Soc., 106:3 (1963), 391–414 | DOI | MR | Zbl

[23] S. V. Parter, “Extreme eigenvalues of Toeplitz forms and applications to elliptic difference equations”, Trans. Amer. Math. Soc., 99 (1961), 153–192 | DOI | MR | Zbl

[24] S. Serra, “On the extreme eigenvalues of Hermitian (block) Toeplitz matrices”, Linear Algebra Appl., 270 (1998), 109–129 | DOI | MR | Zbl

[25] A. Böttcher, S. Grudsky, E. A. Maksimenko, J. Unterberger, “The first order asymptotics of the extreme eigenvectors of certain Hermitian Toeplitz matrices”, Integral Equations Operator Theory, 63:2 (2009), 165–180 | DOI | MR | Zbl

[26] P. Schmidt, F. Spitzer, “The Toeplitz matrices of an arbitrary Laurent polynomial”, Math. Scand., 8 (1960), 15–38 | DOI | MR | Zbl

[27] K. M. Day, “Measures associated with Toeplitz matrices generated by the Laurent expansion of rational functions”, Trans. Amer. Math. Soc., 209 (1975), 175–183 | DOI | MR | Zbl

[28] A. Böttcher, S. M. Grudsky, “Asymptotic spectra of dense Toeplitz matrices are unstable”, Numer. Algorithms, 33:1-4 (2003), 105–112 | DOI | MR | Zbl

[29] D. Poland, “Toeplitz matrices and random walks with memory”, Phys. A, 223:1-2 (1996), 113–124 | DOI | MR

[30] Fu-Rong Lin, M. K. Ng, R. H. Chan, “Preconditioners for Wiener–Hopf equations with high-order quadrature rules”, SIAM J. Numer. Anal., 34:4 (1997), 1418–1431 | DOI | MR | Zbl

[31] P. C. Hansen, J. G. Nagy, D. P. O'Leary, Deblurring images. Matrices, spectra, and filtering, Fundam. Algorithms, 3, SIAM, Philadelphia, PA, 2006, xiv+130 pp. | DOI | MR | Zbl

[32] E. Eisenberg, A. Baram, M. Baer, “Calculation of the density of states using discrete variable representation and Toeplitz matrices”, J. Phys. A, 28:16 (1995), L433–L438 | DOI | MR | Zbl

[33] F. Bünger, “Inverses, determinants, eigenvalues, and eigenvectors of real symmetric Toeplitz matrices with linearly increasing entries”, Linear Algebra Appl., 459 (2014), 595–619 | DOI | MR | Zbl

[34] W. F. Trench, “Numerical solution of the eigenvalue problem for Hermitian Toeplitz matrices”, SIAM J. Matrix Anal. Appl., 10:2 (1989), 135–146 | DOI | MR | Zbl

[35] Yuanzhe Xi, Jianlin Xia, S. Cauley, V. Balakrishnan, “Superfast and stable structured solvers for Toeplitz least squares via randomized sampling”, SIAM J. Matrix Anal. Appl., 35:1 (2014), 44–72 | DOI | MR | Zbl

[36] A. Böttcher, S. M. Grudsky, E. A. Maksimenko, “On the asymptotics of all eigenvalues of Hermitian Toeplitz band matrices”, Dokl. Math., 80:2 (2009), 662–664 | DOI | MR | Zbl

[37] A. Böttcher, S. M. Grudsky, E. A. Maksimenko, “Inside the eigenvalues of certain Hermitian Toeplitz band matrices”, J. Comput. Appl. Math., 233:9 (2010), 2245–2264 | DOI | MR | Zbl

[38] A. Böttcher, S. M. Grudsky, E. A. Maksimenko, “On the structure of the eigenvectors of large Hermitian Toeplitz band matrices”, Recent trends in Toeplitz and pseudodifferential operators, Oper. Theory Adv. Appl., 210, Birkhäuser Verlag, Basel, 2010, 15–36 | DOI | MR | Zbl

[39] W. F. Trench, “Explicit inversion formulas for Toeplitz band matrices”, SIAM J. Algebraic Discrete Methods, 6:4 (1985), 546–554 | DOI | MR | Zbl

[40] P. Deift, A. Its, I. Krasovsky, “Eigenvalues of Toeplitz matrices in the bulk of the spectrum”, Bull. Inst. Math. Acad. Sin. (N.S.), 7:4 (2012), 437–461 | MR | Zbl

[41] J. M. Bogoya, A. Böttcher, S. M. Grudsky, E. A. Maximenko, “Eigenvalues of Hermitian Toeplitz matrices with smooth simple-loop symbols”, J. Math. Anal. Appl., 422:2 (2015), 1308–1334 | DOI | MR | Zbl

[42] J. M. Bogoya, A. Böttcher, S. M. Grudsky, E. A. Maximenko, “Eigenvectors of Hermitian Toeplitz matrices with smooth simple-loop symbols”, Linear Algebra Appl., 493 (2016), 606–637 | DOI | MR | Zbl

[43] J. M. Bogoya, S. M. Grudsky, E. A. Maximenko, “Eigenvalues of Hermitian Toeplitz matrices generated by simple-loop symbols with relaxed smoothness”, Large truncated Toeplitz matrices, Toeplitz operators, and related topics, Oper. Theory Adv. Appl., 259, Birkhäuser/Springer, Cham, 2017, 179–212 | DOI | MR | Zbl

[44] A. A. Batalshchikov, S. M. Grudsky, V. A. Stukopin, “Asymptotics of eigenvalues of symmetric Toeplitz band matrices”, Linear Algebra Appl., 469 (2015), 464–486 | DOI | MR | Zbl

[45] A. Batalshchikov, S. Grudsky, E. Ramírez de Arellano, V. Stukopin, “Asymptotics of eigenvectors of large symmetric banded Toeplitz matrices”, Integral Equations Operator Theory, 83:3 (2015), 301–330 | DOI | MR | Zbl

[46] Hui Dai, Z. Geary, L. P. Kadanoff, “Asymptotics of eigenvalues and eigenvectors of Toeplitz matrices”, J. Stat. Mech. Theory Exp., 2009, no. 5, P05012, 25 pp. | DOI | MR

[47] L. P. Kadanoff, “Expansions for eigenfunctions and eigenvalues of large-$n$ Toeplitz matrices”, Papers in Physics, 2 (2010), 020003, 14 pp. | DOI

[48] J. M. Bogoya, A. Böttcher, S. M. Grudsky, “Asymptotics of individual eigenvalues of a class of large Hessenberg Toeplitz matrices”, Recent progress in operator theory and its applications, Oper. Theory Adv. Appl., 220, Birkhäuser/Springer Basel AG, Basel, 2012, 77–95 | DOI | MR | Zbl

[49] J. M. Bogoya, A. Böttcher, S. M. Grudsky, E. A. Maksimenko, “Eigenvalues of Hessenberg Toeplitz matrices generated by symbols with several singularities”, Commun. Math. Anal., 2011, Conference 3, 23–41 | MR | Zbl

[50] J. M. Bogoya, A. Böttcher, S. M. Grudsky, E. A. Maksimenko, “Eigenvectors of Hessenberg Toeplitz matrices and a problem by Dai, Geary, and Kadanoff”, Linear Algebra Appl., 436:9 (2012), 3480–3492 | DOI | MR | Zbl

[51] A. Böttcher, S. Grudsky, A. Iserles, “Spectral theory of large Wiener–Hopf operators with complex-symmetric kernels and rational symbols”, Math. Proc. Cambridge Philos. Soc., 151:1 (2011), 161–191 | DOI | MR | Zbl

[52] J. M. Bogoya, A. Böttcher, S. M. Grudsky, E. A. Maximenko, “Maximum norm versions of the Szegő and Avram–Parter theorems for Toeplitz matrices”, J. Approx. Theory, 196 (2015), 79–100 | DOI | MR | Zbl

[53] J. M. Bogoya, A. Böttcher, E. A. Maximenko, “From convergence in distribution to uniform convergence”, Bol. Soc. Mat. Mex. (3), 22:2 (2016), 695–710 | DOI | MR | Zbl

[54] A. Böttcher, H. Widom, “Two remarks on spectral approximations for Wiener–Hopf operators”, J. Integral Equations Appl., 6:1 (1994), 31–36 | DOI | MR | Zbl

[55] A. Böttcher, “Wiener–Hopf determinants with rational symbols”, Math. Nachr., 144 (1989), 39–64 | DOI | MR | Zbl