Toeplitz matrix

Template:Short description 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:

$\left[\begin{array}{ccccc}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{array}\right].$

Any $n\times n$ matrix $A$ of the form

$A=\left[\begin{array}{cccccc}{a}_0& a_{-1}& a_{-2}& \cdots & \cdots & a_{-(n-1)}\\ a_1& a_0& a_{-1}& \ddots & & ⋮\\ a_2& a_1& \ddots & \ddots & \ddots & ⋮\\ ⋮& \ddots & \ddots & \ddots & a_{-1}& a_{-2}\\ ⋮& & \ddots & a_1& a_0& a_{-1}\\ a_{n-1}& \cdots & \cdots & a_2& a_1& a_0\end{array}\right]$

is a Toeplitz matrix. If the $i,j$ element of $A$ is denoted $A_{i,j}$ then we have

$A_{i,j}=A_{i+1,j+1}=a_{i-j}.$

A Toeplitz matrix is not necessarily square.

Solving a Toeplitz system

A matrix equation of the form

$Ax=b$

is called a Toeplitz system if $A$ is a Toeplitz matrix. If $A$ is an $n\times n$ Toeplitz matrix, then the system has at most only $2n-1$ unique values, rather than $n^2$. 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 $O(n^2)$ 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 $O(n^2)$ time.

A Toeplitz matrix can also be decomposed (i.e. factored) in $O(n^2)$ 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. Using displacement rank we obtain method requiring $\tilde{O}({\alpha }^{\omega -1}n)$ ops with the use of fast matrix multiplication algorithms, where $\alpha$ is the rank and ${}^{\sim }2.37\le \omega <3$.

Properties

• An $n\times n$ Toeplitz matrix may be defined as a matrix $A$ where $A_{i,j}=c_{i-j}$, for constants $c_{1-n},\dots ,c_{n-1}$. The set of $n\times n$ Toeplitz matrices is a subspace of the vector space of $n\times n$ matrices (under matrix addition and scalar multiplication).
• Two Toeplitz matrices may be added in $O(n)$ time (by storing only one value of each diagonal) and multiplied in $O(n^2)$ 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 are asymptotically equivalent to circulant matrices as the dimension grows, a result known as the Grenander–Szegő theorem. This asymptotic circulant property is the reason that the discrete Fourier transform approximately diagonalizes large Toeplitz matrices, and underlies the effectiveness of DFT-based spectral density estimation for stationary processes.
• 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

$\frac{1}{a_0}A=G{G}^{\mathrm{T}}-(G-I)(G-I{)}^{\mathrm{T}}$

where $G$ is the lower triangular part of $\frac{1}{a_0}A$.

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

$A^{-1}=\frac{1}{{\alpha }_0}(B{B}^{\mathrm{T}}-C{C}^{\mathrm{T}})$

where $B$ and $C$ are lower triangular Toeplitz matrices and $C$ 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 $h$ and $x$ can be formulated as:

$y=h\ast x=\left[\begin{array}{ccccc}{h}_1& 0& \cdots & 0& 0\\ h_2& h_1& & ⋮& ⋮\\ h_3& h_2& \cdots & 0& 0\\ ⋮& h_3& \cdots & h_1& 0\\ h_{m-1}& ⋮& \ddots & h_2& h_1\\ h_m& h_{m-1}& & ⋮& h_2\\ 0& h_m& \ddots & h_{m-2}& ⋮\\ 0& 0& \cdots & h_{m-1}& h_{m-2}\\ ⋮& ⋮& & h_m& h_{m-1}\\ 0& 0& 0& \cdots & h_m\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\\ ⋮\\ x_n\end{array}\right]$

$y^T=\left[\begin{array}{cccccc}{h}_1& h_2& h_3& \cdots & h_{m-1}& h_m\end{array}\right]\left[\begin{array}{cccccccccc}{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& \dots & x_n& 0& \cdots & 0\\ ⋮& & ⋮& ⋮& ⋮& & ⋮& ⋮& & ⋮\\ 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{array}\right].$

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 $\mathbb{Z}\times \mathbb{Z}$) $A$ induces a linear operator on ${\ell }^2$.

$A=\left[\begin{array}{ccccc}& ⋮& ⋮& ⋮& ⋮\\ \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 \\ & ⋮& ⋮& ⋮& ⋮\end{array}\right].$

The induced operator is bounded if and only if the coefficients of the Toeplitz matrix $A$ are the Fourier coefficients of some essentially bounded function $f$.

In such cases, $f$ is called the symbol of the Toeplitz matrix $A$, and the spectral norm of the Toeplitz matrix $A$ coincides with the $L^{\mathrm{\infty }}$ norm of its symbol. The proof can be found as Theorem 1.1 of Böttcher and Grudsky.

See also

• Circulant matrix, a square Toeplitz matrix with the additional property that $a_i=a_{i+n}$
• Hankel matrix, an "upside down" (i.e., row-reversed) Toeplitz matrix
• Template:Annotated link
• Template:Annotated link

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, 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, arXiv:1005.0671, doi:10.1137/1.9781611971354.ch4, hdl:1885/40746, ISBN 978-0-89871-431-9, 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, CiteSeerX 10.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, CiteSeerX 10.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
• Press, W. H.; Teukolsky, S. A.; Vetterling, W. T.; Flannery, B. P. (2007), Numerical Recipes: The Art of Scientific Computing (3rd 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, S2CID 15717371
• 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

• 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
• Golub, G. H.; van Loan, C. F. (1996), Matrix Computations, Johns Hopkins University Press, §4.7—Toeplitz and Related Systems, ISBN 0-8018-5413-X, OCLC 34515797
• Gray, R. M. (2005), "Toeplitz and Circulant Matrices: A Review" (PDF), Foundations and Trends in Communications and Information Theory, 2 (3), Now Publishers: 155–239, 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
• Ye, Ke; Lim, Lek-Heng (2016), "Every matrix is a product of Toeplitz matrices", Foundations of Computational Mathematics, 16 (3): 577–598, arXiv:1307.5132, doi:10.1007/s10208-015-9254-z, S2CID 254166943