Toeplitz matrix

Short description: Matrix with equal values along diagonals

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:

[math]\displaystyle{ \qquad\begin{bmatrix} a & b & c & d & e \\ f & a & b & c & d \\ g & f & a & b & c \\ h & g & f & a & b \\ i & h & g & f & a \end{bmatrix}. }[/math]

Any [math]\displaystyle{ n \times n }[/math] matrix [math]\displaystyle{ A }[/math] of the form

[math]\displaystyle{ A = \begin{bmatrix} a_0 & a_{-1} & a_{-2} & \cdots & \cdots & a_{-(n-1)} \\ a_1 & a_0 & a_{-1} & \ddots & & \vdots \\ a_2 & a_1 & \ddots & \ddots & \ddots & \vdots \\ \vdots & \ddots & \ddots & \ddots & a_{-1} & a_{-2} \\ \vdots & & \ddots & a_1 & a_0 & a_{-1} \\ a_{n-1} & \cdots & \cdots & a_2 & a_1 & a_0 \end{bmatrix} }[/math]

is a Toeplitz matrix. If the [math]\displaystyle{ i,j }[/math] element of [math]\displaystyle{ A }[/math] is denoted [math]\displaystyle{ A_{i,j} }[/math] then we have

[math]\displaystyle{ A_{i,j} = A_{i+1,j+1} = a_{i-j}. }[/math]

A Toeplitz matrix is not necessarily square.

Solving a Toeplitz system

A matrix equation of the form

[math]\displaystyle{ Ax = b }[/math]

is called a Toeplitz system if [math]\displaystyle{ A }[/math] is a Toeplitz matrix. If [math]\displaystyle{ A }[/math] is an [math]\displaystyle{ n \times n }[/math] Toeplitz matrix, then the system has at most only [math]\displaystyle{ 2n-1 }[/math] unique values, rather than [math]\displaystyle{ n^2 }[/math]. 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 algorithms such as the Schur algorithm or the Levinson algorithm in [math]\displaystyle{ O(n^2) }[/math] time. Variants of the latter have been shown to be weakly stable (i.e. they exhibit numerical stability for well-conditioned linear systems). The algorithms can also be used to find the determinant of a Toeplitz matrix in [math]\displaystyle{ O(n^2) }[/math] time.

A Toeplitz matrix can also be decomposed (i.e. factored) in [math]\displaystyle{ O(n^2) }[/math] time. The Bareiss algorithm for an LU decomposition is stable. An LU decomposition gives a quick method for solving a Toeplitz system, and also for computing the determinant.

General properties

• An [math]\displaystyle{ n\times n }[/math] Toeplitz matrix may be defined as a matrix [math]\displaystyle{ A }[/math] where [math]\displaystyle{ A_{i,j}=c_{i-j} }[/math], for constants [math]\displaystyle{ c_{1-n},\ldots,c_{n-1} }[/math]. The set of [math]\displaystyle{ n\times n }[/math] Toeplitz matrices is a subspace of the vector space of [math]\displaystyle{ n\times n }[/math] matrices (under matrix addition and scalar multiplication).
• Two Toeplitz matrices may be added in [math]\displaystyle{ O(n) }[/math] time (by storing only one value of each diagonal) and multiplied in [math]\displaystyle{ O(n^2) }[/math] time.
• Toeplitz matrices are persymmetric. Symmetric Toeplitz matrices are both centrosymmetric and bisymmetric.
• 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

[math]\displaystyle{ \frac{1}{a_0} A = G G^\operatorname{T} - (G - I)(G - I)^\operatorname{T} }[/math]

where [math]\displaystyle{ G }[/math] is the lower triangular part of [math]\displaystyle{ \frac{1}{a_0} A }[/math].

• The inverse of a nonsingular symmetric Toeplitz matrix has the representation

[math]\displaystyle{ A^{-1} = \frac{1}{\alpha_0} (B B^\operatorname{T} - C C^\operatorname{T}) }[/math]

where [math]\displaystyle{ B }[/math] and [math]\displaystyle{ C }[/math] are lower triangular Toeplitz matrices and [math]\displaystyle{ C }[/math] is a strictly lower triangular matrix.

Discrete convolution

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 [math]\displaystyle{ h }[/math] and [math]\displaystyle{ x }[/math] can be formulated as:

[math]\displaystyle{ y = h \ast x = \begin{bmatrix} h_1 & 0 & \cdots & 0 & 0 \\ h_2 & h_1 & & \vdots & \vdots \\ h_3 & h_2 & \cdots & 0 & 0 \\ \vdots & h_3 & \cdots & h_1 & 0 \\ h_{m-1} & \vdots & \ddots & h_2 & h_1 \\ h_m & h_{m-1} & & \vdots & h_2 \\ 0 & h_m & \ddots & h_{m-2} & \vdots \\ 0 & 0 & \cdots & h_{m-1} & h_{m-2} \\ \vdots & \vdots & & h_m & h_{m-1} \\ 0 & 0 & 0 & \cdots & h_m \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ \vdots \\ x_n \end{bmatrix} }[/math]

[math]\displaystyle{ y^T = \begin{bmatrix} h_1 & h_2 & h_3 & \cdots & h_{m-1} & h_m \end{bmatrix} \begin{bmatrix} x_1 & x_2 & x_3 & \cdots & x_n & 0 & 0 & 0& \cdots & 0 \\ 0 & x_1 & x_2 & x_3 & \cdots & x_n & 0 & 0 & \cdots & 0 \\ 0 & 0 & x_1 & x_2 & x_3 & \ldots & x_n & 0 & \cdots & 0 \\ \vdots & & \vdots & \vdots & \vdots & & \vdots & \vdots & & \vdots \\ 0 & \cdots & 0 & 0 & x_1 & \cdots & x_{n-2} & x_{n-1} & x_n & 0 \\ 0 & \cdots & 0 & 0 & 0 & x_1 & \cdots & x_{n-2} & x_{n-1} & x_n \end{bmatrix}. }[/math]

This approach can be extended to compute autocorrelation, cross-correlation, moving average etc.

Infinite Toeplitz matrix

A bi-infinite Toeplitz matrix (i.e. entries indexed by [math]\displaystyle{ \mathbb Z\times\mathbb Z }[/math]) [math]\displaystyle{ A }[/math] induces a linear operator on [math]\displaystyle{ \ell^2 }[/math].

[math]\displaystyle{ A=\begin{bmatrix} & \vdots & \vdots & \vdots & \vdots \\ \cdots & a_0 & a_{-1} & a_{-2} & a_{-3} & \cdots \\ \cdots & a_1 & a_0 & a_{-1} & a_{-2} & \cdots \\ \cdots & a_2 & a_1 & a_0 & a_{-1} & \cdots \\ \cdots & a_3 & a_2 & a_1 & a_0 & \cdots \\ & \vdots & \vdots & \vdots & \vdots \end{bmatrix}. }[/math]

The induced operator is bounded if and only if the coefficients of the Toeplitz matrix [math]\displaystyle{ A }[/math] are the Fourier coefficients of some essentially bounded function [math]\displaystyle{ f }[/math].

In such cases, [math]\displaystyle{ f }[/math] is called the symbol of the Toeplitz matrix [math]\displaystyle{ A }[/math], and the spectral norm of the Toeplitz matrix [math]\displaystyle{ A }[/math] coincides with the [math]\displaystyle{ L^\infty }[/math] norm of its symbol. The proof is easy to establish and can be found as Theorem 1.1 of.

See also

• Circulant matrix, a square Toeplitz matrix with the additional property that [math]\displaystyle{ a_i=a_{i+n} }[/math]
• Hankel matrix, an "upside down" (i.e., row-reversed) Toeplitz matrix
• Szegő limit theorems

References

• 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, doi:10.1137/S0895479891221563 
• Böttcher, Albrecht; Grudsky, Sergei M. (2012), Toeplitz Matrices, Asymptotic Linear Algebra, and Functional Analysis, Birkhäuser, ISBN 978-3-0348-8395-5, https://books.google.com/books?id=Dmr0BwAAQBAJ&pg=PA1 
• Brent, R. P. (1999), "Stability of fast algorithms for structured linear systems", in Kailath, T.; Sayed, A. H., Fast Reliable Algorithms for Matrices with Structure, SIAM, pp. 103–116, doi:10.1137/1.9781611971354.ch4 
• 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–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 (474): 812–822, doi:10.1198/016214505000001069 
• Hayes, Monson H. (1996), Statistical digital signal processing and modeling, John Wiley & Son, 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, http://scitation.aip.org/getabs/servlet/GetabsServlet?prog=normal&id=SJNAAM000030000005001498000001&idtype=cvips&gifs=yes 
• Monahan, J. F. (2011), Numerical Methods of Statistics, Cambridge University Press 
• Mukherjee, Bishwa Nath; Maiti, Sadhan Samar (1988), "On some properties of positive definite Toeplitz matrices and their possible applications", Linear Algebra and Its Applications 102: 211–240, doi:10.1016/0024-3795(88)90326-6, https://core.ac.uk/download/pdf/82070573.pdf 
• Press, W. H.; Teukolsky, S. A.; Vetterling, W. T.; Flannery, B. P. (2007), Numerical Recipes: The Art of Scientific Computing (Third ed.), Cambridge University Press, 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 (3): 669–693, doi:10.1137/S089547980241791X 
• 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, doi:10.1109/TIT.2016.2553041 

Further reading

• 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 
• Goldreich, O.; Tal, A. (2018), "Matrix rigidity of random Toeplitz matrices", Computational Complexity 27 (2): 305–350, doi:10.1007/s00037-016-0144-9 
• Golub G. H., van Loan C. F. (1996), Matrix Computations (Johns Hopkins University Press) §4.7—Toeplitz and Related Systems
• Gray R. M., Toeplitz and Circulant Matrices: A Review (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–2094, doi:10.1109/78.149978, Bibcode: 1992ITSP...40.2093N 
• Pan, Victor Y. (2001), Structured Matrices and Polynomials: unified superfast algorithms, Birkhäuser, ISBN 978-0817642402 
• Ye, Ke; Lim, Lek-Heng (2016), "Every matrix is a product of Toeplitz matrices", Foundations of Computational Mathematics 16 (3): 577–598, doi:10.1007/s10208-015-9254-z