Toeplitz matrix: Difference between revisions

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:

${\displaystyle {\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}}.}$

Any n×n matrix A of the form

${\displaystyle A={\begin{bmatrix}a_{0}&a_{-1}&a_{-2}&\ldots &\ldots &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}&\ldots &\ldots &a_{2}&a_{1}&a_{0}\end{bmatrix}}}$

is a Toeplitz matrix. If the i,j element of A is denoted A_i,j, then we have

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

A matrix equation of the form

${\displaystyle Ax=b\ }$

is called a Toeplitz system if A is a Toeplitz matrix. If A is an ${\displaystyle n\times n}$ Toeplitz matrix, then the system has only 2n−1 degrees of freedom, rather than n². 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 Θ(n²) 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(n²) time.^[3]

A Toeplitz matrix can also be decomposed (i.e. factored) in O(n²) 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.

Algorithms that are asymptotically faster than those of Bareiss and Levinson have been described in the literature.^[6][7][8][9]

A Toeplitz matrix may be defined as a matrix A where A_i,j = c_i−j, for constants c_1−n … c_n−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.

Two Toeplitz matrices may be added in O(n) time and multiplied in O(n²) 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.

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

${\displaystyle y=h\ast x={\begin{bmatrix}h_{1}&0&\ldots &0&0\\h_{2}&h_{1}&\ldots &\vdots &\vdots \\h_{3}&h_{2}&\ldots &0&0\\\vdots &h_{3}&\ldots &h_{1}&0\\h_{m-1}&\vdots &\ldots &h_{2}&h_{1}\\h_{m}&h_{m-1}&\vdots &\vdots &h_{2}\\0&h_{m}&\ldots &h_{m-2}&\vdots \\0&0&\ldots &h_{m-1}&h_{m-2}\\\vdots &\vdots &\vdots &h_{m}&h_{m-1}\\0&0&0&\ldots &h_{m}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\\vdots \\x_{n}\end{bmatrix}}}$

${\displaystyle y^{T}={\begin{bmatrix}h_{1}&h_{2}&h_{3}&\ldots &h_{m-1}&h_{m}\end{bmatrix}}{\begin{bmatrix}x_{1}&x_{2}&x_{3}&\ldots &x_{n}&0&0&0&\ldots &0\\0&x_{1}&x_{2}&x_{3}&\ldots &x_{n}&0&0&\ldots &0\\0&0&x_{1}&x_{2}&x_{3}&\ldots &x_{n}&0&\ldots &0\\\vdots &\vdots &\vdots &\vdots &\vdots &\ldots &\vdots &\vdots &\ldots &0\\0&\ldots &0&0&x_{1}&\ldots &x_{n-2}&x_{n-1}&x_{n}&\vdots \\0&\ldots &0&0&0&x_{1}&\ldots &x_{n-2}&x_{n-1}&x_{n}\end{bmatrix}}.}$

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

A bi-infinite Toeplitz matrix (i.e., entries indexed by ${\displaystyle \mathbb {Z} \times \mathbb {Z} }$, see below) ${\displaystyle A}$ induces a linear operator on ${\displaystyle \ell ^{2}}$.

${\displaystyle A={\begin{bmatrix}\ldots &\ldots &\ldots &\ldots &\ldots &\ldots \\\ldots &a_{0}&a_{-1}&a_{-2}&a_{-3}&\ldots \\\ldots &a_{1}&a_{0}&a_{-1}&a_{-2}&\ldots \\\ldots &a_{2}&a_{1}&a_{0}&a_{-1}&\ldots \\\ldots &a_{3}&a_{2}&a_{1}&a_{0}&\ldots \\\ldots &\ldots &\ldots &\ldots &\ldots &\ldots \\\end{bmatrix}}.}$

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

In such cases, ${\displaystyle f}$ is called the symbol of the Toeplitz matrix ${\displaystyle A}$, and the spectral norm of the Toeplitz matrix ${\displaystyle A}$ coincides with the ${\displaystyle L^{\infty }}$ norm of its symbol.

The proof is easy to establish and can be found as Theorem 1.1 in the google book link: ^[10]

• Circulant matrix, a Toeplitz matrix with the additional property that ${\displaystyle a_{i}=a_{i+n}}$.
• Hankel matrix, a Toeplitz matrix "upside down".

• Bareiss, E.H. (1969), "Numerical solution of linear equations with Toeplitz and vector Toeplitz matrices", Numerische Mathematik, 13: 404–424, doi:10.1007/BF02163269
• Bojanczyk, A.W.; Brent, R.P.; Hoog, F.R. De; 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
• 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) §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.
• Pan, Victor Y. (2001), Structured Matrices and Polynomials: unified superfast algorithms, Birkhäuser, ISBN 0817642404
• 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: 669–693, doi:10.1137/S089547980241791X
• Albrecht Böttcher; Sergei M. Grudsky (2012), Toeplitz Matrices, Asymptotic Linear Algebra, and Functional Analysis, Birkhäuser, pp. 1–, ISBN 978-3-0348-8395-5