Toeplitz matrix

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

Any ${\displaystyle n\times n}$ matrix ${\displaystyle A}$ of the form

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

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

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

${\displaystyle Ax=b}$

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

A Toeplitz matrix can also be decomposed (i.e. factored) in ${\displaystyle O(n^{2})}$ 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.

General properties

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

${\displaystyle {\frac {1}{a_{0}}}A=GG^{\operatorname {T} }-(G-I)(G-I)^{\operatorname {T} }}$

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

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

${\displaystyle A^{-1}={\frac {1}{\alpha _{0}}}(BB^{\operatorname {T} }-CC^{\operatorname {T} })}$

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

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

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

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

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

Infinite Toeplitz matrix

Main article: Toeplitz operator

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

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

The induced operator is bounded if and only if the coefficients of the Toeplitz matrix ${\displaystyle A}$ are 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 of: ^[8]

See also

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

Notes

1. Press et al. 2007 , §2.8.2—Toeplitz matrices
2. Hayes 1996 , Chapter 5.2.6
3. Krishna & Wang 1993
4. Monahan 2011 , §4.5—Toeplitz systems
5. Brent 1999
6. Bojanczyk et al. 1995
7. Mukherjee & Maiti 1988
8. Böttcher & Grudsky 2012

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, 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–1266, 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, 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
• 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" (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 (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, 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
• 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, 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