Eigenvalues and eigenvectors of banded Toeplitz matrices and the related symbols. (English) Zbl 1513.65095

Ekström, S.-E.; Serra-Capizzano, S.

Numer. Linear Algebra Appl. 25, No. 5, e2137, 17 p. (2018).

Summary: It is known that for a tridiagonal Toeplitz matrix, having on the main diagonal the constant \(a_0\) and on the two first off-diagonals the constants \(a_1\) (lower) and \(a_{-1}\) (upper), which are all complex values, there exist closed form formulas, giving the eigenvalues of the matrix and a set of associated eigenvectors. For example, for the 1D discrete Laplacian, this triple is \((a_0,a_1,a_{-1})=(2,-1,-1)\). In the first part of this article, we consider a tridiagonal Toeplitz matrix of the same form \((a_0,a_{\omega},a_{-\omega})\), but where the two off-diagonals are positioned \(\omega\) steps from the main diagonal instead of only one. We show that its eigenvalues and eigenvectors can also be identified in closed form and that interesting connections with the standard Toeplitz symbol are identified. Furthermore, as numerical evidences clearly suggest, it turns out that the eigenvalue behavior of a general banded symmetric Toeplitz matrix with real entries can be described qualitatively in terms of the symmetrically sparse tridiagonal case with real \(a_0\), \(a_{\omega}=a_{-\omega}\), \(\omega=2,3,\dots\), and also quantitatively in terms of those having monotone symbols. A discussion on the use of such results and on possible extensions complements the paper.

MSC:

65F15	Numerical computation of eigenvalues and eigenvectors of matrices
15B05	Toeplitz, Cauchy, and related matrices

Keywords:

eigensolver; generating function and spectral symbol; Toeplitz matrix

References:

[1]	BöttcherA, SilbermannB. Introduction to large truncated Toeplitz matrices. New York: Springer‐Verlag; 1999. · Zbl 0916.15012
[2]	Serra‐CapizzanoS. On the extreme eigenvalues of Hermitian (block) Toeplitz matrices. Linear Algebra Appl. 1998;270:109-129. · Zbl 0892.15014
[3]	GrenanderU, SzegőG. Toeplitz forms and their applications. 2nd ed.New York: Chelsea; 1984. · Zbl 0611.47018
[4]	TilliP. A note on the spectral distribution of Toeplitz matrices. Linear Multil Algebra. 1998;45(2/3):147-159. · Zbl 0951.65033
[5]	TyrtyshnikovE. A unifying approach to some old and new theorems on distribution and clustering. Linear Algebra Appl. 1996;232:1-43. · Zbl 0841.15006
[6]	Serra‐CapizzanoS, BertacciniD, GolubG. How to deduce a proper eigenvalue cluster from a proper singular value cluster in the nonnormal case. SIAM J Matrix Anal Appl. 2005;27(1):82-86. · Zbl 1088.65031
[7]	BiniD, CapovaniM. Spectral and computational properties of band symmetric Toeplitz matrices. Linear Algebra Appl. 1983;52/53:99-126. · Zbl 0549.15005
[8]	BogoyaJ, BöttcherA, MaximenkoE. From convergence in distribution to uniform convergence. Bol Soc Mat Mex. 2016;3(22):695-710. · Zbl 1419.60005
[9]	EkströmS‐E, GaroniC, Serra‐CapizzanoS. Are the eigenvalues of banded symmetric Toeplitz matrices known in almost closed form?Exp Math. 2017. https://doi.org/10.1080/10586458.2017.1320241 · Zbl 1405.15037 · doi:10.1080/10586458.2017.1320241
[10]	Serra‐CapizzanoS. On the extreme spectral properties of Toeplitz matrices generated by L1 functions with several minima/maxima. BIT. 1996;36(1): 135-142. · Zbl 0851.15008
[11]	SteinEM, WeissG. Introduction to Fourier analysis on Euclidean spaces. Princeton, NJ: Princeton University Press; 1971. · Zbl 0232.42007
[12]	BogoyaJ, GrudskyS, MaximenkoE. Eigenvalues of Hermitian Toeplitz matrices generated by simple‐loop symbols with relaxed smoothness. Oper Theory Adv Appl. 2017;259:179-212. · Zbl 1468.15007
[13]	AhmadF, Al‐AidarousE, AlrehailiD, EkströmS‐E, FurciI, Serra‐CapizzanoS. Are the eigenvalues of preconditioned banded symmetric Toeplitz matrices known in almost closed form?Numer Algoritm1-27,2017. In press.
[14]	EkströmS‐E, FurciI, Serra‐CapizzanoS. Are the Eigenvalues of the B‐spline IgA approximation of −Δu=λu known in almost closed form?2017. TR Division of Scientific Computing, IT Department, Uppsala University. http://www.it.uu.se/research/publications/reports/2017-016
[15]	BogoyaJ, BöttcherA, GrudskyS, MaximenkoE. Eigenvalues of Hermitian Toeplitz matrices with smooth simple‐loop symbols. J Math Anal Appl. 2015;422(2):1308-1334. · Zbl 1302.65086
[16]	BöttcherA, GrudskyS, MaximenkoE. Inside the eigenvalues of certain Hermitian Toeplitz band matrices. J Comput Appl Math. 2010;233(9): 2245-2264. · Zbl 1195.15009
[17]	BöttcherA, GrudskyS. Spectral properties of banded Toeplitz matrices. Philadelphia: SIAM; 2005. · Zbl 1089.47001
[18]	ElliottJF. The characteristic roots of certain real symmetric matrices [master’s thesis]. Knoxville: University of Tennessee; 1953. http://trace.tennessee.edu/utk_gradthes/2384
[19]	GantmakherFR, KreinMG. Ostsilliatsionnye matritsy i iadra i malye kolebaniia mekhanicheskikh sistem (Oscillation matrices and kernels and small vibrations of mechanical systems). Soviet Union: Gostekhizdat; 1950. · Zbl 0041.35502
[20]	NoscheseS, PasquiniL, ReichelL. Tridiagonal Toeplitz matrices: Properties and novel applications. Numer Linear Algebra Appl. 2013;20(2):302-326. · Zbl 1289.65082
[21]	SmithGD. Numerical solution of partial differential equations: Finite difference methods. 2nd ed. Oxford: Clarendon Press; 1978. · Zbl 0389.65040
[22]	EkströmS‐E, Serra‐CapizzanoS. Eigenvalues and eigenvectors of banded Toeplitz matrices and the related symbols. 2017. TR Division of Scientific Computing, IT Department, Uppsala University. http://www.it.uu.se/research/publications/reports/2017-010/
[23]	TyrtyshnikovE, ZamarashkinN. Spectra of multilevel Toeplitz matrices: Advanced theory via simple matrix relationships. Linear Algebra Appl. 1998;270:15-27. · Zbl 0890.15006
[24]	BrezinskiC, Redivo ZagliaM. Extrapolation methods theory and practice, studies in computational mathematics. 2nd ed.Amsterdam: North‐Holland Publishing Co; 1991. · Zbl 0744.65004