In linear algebra, a Toeplitz matrix or diagonal-constant matrix, named after Otto Toeplitz, is a matrix in which each descending diagonal from left to right is constant. For instance, the following matrix is a Toeplitz matrix:
Any matrix of the form
is a Toeplitz matrix. If the element of is denoted then we have
is called a Toeplitz system if is a Toeplitz matrix. If is an Toeplitz matrix, then the system has at most only
unique values, rather than . We might therefore expect that the solution of a Toeplitz system would be easier, and indeed that is the case.
A Toeplitz matrix can also be decomposed (i.e. factored) in time.[5] The Bareiss algorithm for an LU decomposition is stable.[6] An LU decomposition gives a quick method for solving a Toeplitz system, and also for computing the determinant.
Properties
edit
An Toeplitz matrix may be defined as a matrix where , for constants . The set of Toeplitz matrices is a subspace of the vector space of matrices (under matrix addition and scalar multiplication).
Two Toeplitz matrices may be added in time (by storing only one value of each diagonal) and multiplied in time.
Toeplitz matrices are also closely connected with Fourier series, because the multiplication operator by a trigonometric polynomial, compressed to a finite-dimensional space, can be represented by such a matrix. Similarly, one can represent linear convolution as multiplication by a Toeplitz matrix.
Toeplitz matrices commute asymptotically. This means they diagonalize in the same basis when the row and column dimension tends to infinity.
For symmetric Toeplitz matrices, there is the decomposition
where is the lower triangular part of .
The inverse of a nonsingular symmetric Toeplitz matrix has the representation
where and are lower triangular Toeplitz matrices and is a strictly lower triangular matrix.[7]
Discrete convolution
edit
The convolution operation can be constructed as a matrix multiplication, where one of the inputs is converted into a Toeplitz matrix. For example, the convolution of and can be formulated as:
A bi-infinite Toeplitz matrix (i.e. entries indexed by ) induces a linear operator on .
The induced operator is bounded if and only if the coefficients of the Toeplitz matrix are the Fourier coefficients of some essentially bounded function .
In such cases, is called the symbol of the Toeplitz matrix , and the spectral norm of the Toeplitz matrix coincides with the norm of its symbol. The proof is easy to establish and can be found as Theorem 1.1 of.[8]
See also
edit
Circulant matrix, a square Toeplitz matrix with the additional property that
Hankel matrix, an "upside down" (i.e., row-reversed) Toeplitz matrix
Bojanczyk, A. W.; Brent, R. P.; de Hoog, F. R.; Sweet, D. R. (1995), "On the stability of the Bareiss and related Toeplitz factorization algorithms", SIAM Journal on Matrix Analysis and Applications, 16: 40–57, arXiv:1004.5510, doi:10.1137/S0895479891221563, S2CID 367586
Böttcher, Albrecht; Grudsky, Sergei M. (2012), Toeplitz Matrices, Asymptotic Linear Algebra, and Functional Analysis, Birkhäuser, ISBN 978-3-0348-8395-5
Brent, R. P. (1999), "Stability of fast algorithms for structured linear systems", in Kailath, T.; Sayed, A. H. (eds.), Fast Reliable Algorithms for Matrices with Structure, SIAM, pp. 103–116, doi:10.1137/1.9781611971354.ch4, hdl:1885/40746, S2CID 13905858
Chan, R. H.-F.; Jin, X.-Q. (2007), An Introduction to Iterative Toeplitz Solvers, SIAM, doi:10.1137/1.9780898718850, ISBN 978-0-89871-636-8
Chandrasekeran, S.; Gu, M.; Sun, X.; Xia, J.; Zhu, J. (2007), "A superfast algorithm for Toeplitz systems of linear equations", SIAM Journal on Matrix Analysis and Applications, 29 (4): 1247–66, CiteSeerX10.1.1.116.3297, doi:10.1137/040617200
Chen, W. W.; Hurvich, C. M.; Lu, Y. (2006), "On the correlation matrix of the discrete Fourier transform and the fast solution of large Toeplitz systems for long-memory time series", Journal of the American Statistical Association, 101 (474): 812–822, CiteSeerX10.1.1.574.4394, doi:10.1198/016214505000001069, S2CID 55893963
Hayes, Monson H. (1996), Statistical digital signal processing and modeling, Wiley, ISBN 0-471-59431-8
Krishna, H.; Wang, Y. (1993), "The Split Levinson Algorithm is weakly stable", SIAM Journal on Numerical Analysis, 30 (5): 1498–1508, doi:10.1137/0730078
Monahan, J. F. (2011), Numerical Methods of Statistics, Cambridge University Press, doi:10.1017/CBO9780511977176, ISBN 978-1-139-08211-2
Mukherjee, Bishwa Nath; Maiti, Sadhan Samar (1988), "On some properties of positive definite Toeplitz matrices and their possible applications" (PDF), Linear Algebra and Its Applications, 102: 211–240, doi:10.1016/0024-3795(88)90326-6
Yang, Zai; Xie, Lihua; Stoica, Petre (2016), "Vandermonde decomposition of multilevel Toeplitz matrices with application to multidimensional super-resolution", IEEE Transactions on Information Theory, 62 (6): 3685–3701, arXiv:1505.02510, doi:10.1109/TIT.2016.2553041, S2CID 6291005
Further reading
edit
Bareiss, E. H. (1969), "Numerical solution of linear equations with Toeplitz and vector Toeplitz matrices", Numerische Mathematik, 13 (5): 404–424, doi:10.1007/BF02163269, S2CID 121761517
Goldreich, O.; Tal, A. (2018), "Matrix rigidity of random Toeplitz matrices", Computational Complexity, 27 (2): 305–350, doi:10.1007/s00037-016-0144-9, S2CID 253641700
Gray, R. M., Toeplitz and Circulant Matrices: A Review(PDF), Now Publishers, doi:10.1561/0100000006
Noor, F.; Morgera, S. D. (1992), "Construction of a Hermitian Toeplitz matrix from an arbitrary set of eigenvalues", IEEE Transactions on Signal Processing, 40 (8): 2093–4, Bibcode:1992ITSP...40.2093N, doi:10.1109/78.149978
Pan, Victor Y. (2001), Structured Matrices and Polynomials: unified superfast algorithms, Birkhäuser, ISBN 978-0817642402