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 n×n matrix A of the form
is a Toeplitz matrix. If the i,j element of A is denoted Ai,j, then we have
A matrix equation of the form
is called a Toeplitz system if A is a Toeplitz matrix. If A is an Toeplitz matrix, then the system has only 2n−1 degrees of freedom, rather than n2. We might therefore expect that the solution of a Toeplitz system would be easier, and indeed that is the case.
Toeplitz systems can be solved by the Levinson algorithm in Θ(n2) time.1 Variants of this algorithm have been shown to be weakly stable (i.e. they exhibit numerical stability for well-conditioned linear systems).2 The algorithm can also be used to find the determinant of a Toeplitz matrix in O(n2) time.3
A Toeplitz matrix can also be decomposed (i.e. factored) in O(n2) time.4 The Bareiss algorithm for an LU decomposition is stable.5 An LU decomposition gives a quick method for solving a Toeplitz system, and also for computing the determinant.
A Toeplitz matrix may be defined as a matrix A where Ai,j = ci−j, for constants c1−n … cn−1. The set of n×n Toeplitz matrices is a subspace of the vector space of n×n matrices under matrix addition and scalar multiplication.
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.
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:
- Circulant matrix, a Toeplitz matrix with the additional property that .
- Hankel matrix, a Toeplitz matrix "upside down".
- Toeplitz operator, a Toeplitz matrix with infinitely many rows and columns.
- Press et al. (2007).
- Krishna & Wang (1993).
- Monahan (2011).
- Brent (1999).
- Bojanczyk et al. (1995).
- Stewart (2003).
- Chen et al. (2006)
- Chan & Jin (2007).
- Chandrasekeran et al. (2007).
- E.H. Bareiss (1969), "Numerical solution of linear equations with Toeplitz and vector Toeplitz matrices", Numerische Mathematik, 13: 404–424. doi:10.1007/BF02163269
- A.W. Bojanczyk, R.P. Brent, F.R. De Hoog, D.R. Sweet (1995), "On the stability of the Bareiss and related Toeplitz factorization algorithms", SIAM Journal on Matrix Analysis and Applications, 16: 40–57. doi:10.1137/S0895479891221563
- Brent R.P. (1999), "Stability of fast algorithms for structured linear systems", Fast Reliable Algorithms for Matrices with Structure (editors—T. Kailath, A.H. Sayed), ch.4 (SIAM).
- Chan R. H.-F., Jin X.-Q. (2007), An Introduction to Iterative Toeplitz Solvers (SIAM).
- 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: 1247–1266. 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: 812–822. doi:10.1198/016214505000001069
- Golub G.H., van Loan C.F. (1996), Matrix Computations (Johns Hopkins University Press), Section 4.7—Toeplitz and Related Systems.
- Gray R.M., Toeplitz and Circulant Matrices: A Review (Now Publishers).
- 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), §4.5—Toeplitz systems.
- Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P. (2007), Numerical Recipes: The Art of Scientific Computing, Third edition (Cambridge University Press), §2.8.2—Toeplitz matrices. ISBN 978-0-521-88068-8
- Stewart M. (2003), "A superfast Toeplitz solver with improved numerical stability", SIAM Journal on Matrix Analysis and Applications, 25: 669–693. doi:10.1137/S089547980241791X