Menu
Home Explore People Places Arts History Plants & Animals Science Life & Culture Technology
On this page
Toeplitz matrix
Matrix with shifting rows

In linear algebra, a Toeplitz matrix, named after Otto Toeplitz, is a matrix with constant values along each descending diagonal from left to right. For an n × n Toeplitz matrix A, each element satisfies Ai,j = ai−j, meaning the value depends only on the difference between row and column indices. Such matrices have a structure where every diagonal parallel to the main diagonal contains identical elements. Note that a Toeplitz matrix is not necessarily square. This property makes Toeplitz matrices useful in various applications including signal processing and system theory.

We don't have any images related to Toeplitz matrix yet.
We don't have any YouTube videos related to Toeplitz matrix yet.
We don't have any PDF documents related to Toeplitz matrix yet.
We don't have any Books related to Toeplitz matrix yet.
We don't have any archived web articles related to Toeplitz matrix yet.

Solving a Toeplitz system

A matrix equation of the form

A x = b {\displaystyle Ax=b}

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

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

Properties

  • An n × n {\displaystyle n\times n} Toeplitz matrix may be defined as a matrix A {\displaystyle A} where A i , j = c i − j {\displaystyle A_{i,j}=c_{i-j}} , for constants c 1 − n , … , c n − 1 {\displaystyle c_{1-n},\ldots ,c_{n-1}} . The set of n × n {\displaystyle n\times n} Toeplitz matrices is a subspace of the vector space of n × n {\displaystyle n\times n} matrices (under matrix addition and scalar multiplication).
  • Two Toeplitz matrices may be added in O ( n ) {\displaystyle O(n)} time (by storing only one value of each diagonal) and multiplied in O ( n 2 ) {\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
1 a 0 A = G G T − ( G − I ) ( G − I ) T {\displaystyle {\frac {1}{a_{0}}}A=GG^{\operatorname {T} }-(G-I)(G-I)^{\operatorname {T} }} where G {\displaystyle G} is the lower triangular part of 1 a 0 A {\displaystyle {\frac {1}{a_{0}}}A} . A − 1 = 1 α 0 ( B B T − C C T ) {\displaystyle A^{-1}={\frac {1}{\alpha _{0}}}(BB^{\operatorname {T} }-CC^{\operatorname {T} })} where B {\displaystyle B} and C {\displaystyle C} are lower triangular Toeplitz matrices and C {\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 h {\displaystyle h} and x {\displaystyle x} can be formulated as:

y = h ∗ x = [ h 1 0 ⋯ 0 0 h 2 h 1 ⋮ ⋮ h 3 h 2 ⋯ 0 0 ⋮ h 3 ⋯ h 1 0 h m − 1 ⋮ ⋱ h 2 h 1 h m h m − 1 ⋮ h 2 0 h m ⋱ h m − 2 ⋮ 0 0 ⋯ h m − 1 h m − 2 ⋮ ⋮ h m h m − 1 0 0 0 ⋯ h m ] [ x 1 x 2 x 3 ⋮ x n ] {\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}}} y T = [ h 1 h 2 h 3 ⋯ h m − 1 h m ] [ x 1 x 2 x 3 ⋯ x n 0 0 0 ⋯ 0 0 x 1 x 2 x 3 ⋯ x n 0 0 ⋯ 0 0 0 x 1 x 2 x 3 … x n 0 ⋯ 0 ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ 0 ⋯ 0 0 x 1 ⋯ x n − 2 x n − 1 x n 0 0 ⋯ 0 0 0 x 1 ⋯ x n − 2 x n − 1 x n ] . {\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 Z × Z {\displaystyle \mathbb {Z} \times \mathbb {Z} } ) A {\displaystyle A} induces a linear operator on ℓ 2 {\displaystyle \ell ^{2}} .

A = [ ⋮ ⋮ ⋮ ⋮ ⋯ a 0 a − 1 a − 2 a − 3 ⋯ ⋯ a 1 a 0 a − 1 a − 2 ⋯ ⋯ a 2 a 1 a 0 a − 1 ⋯ ⋯ a 3 a 2 a 1 a 0 ⋯ ⋮ ⋮ ⋮ ⋮ ] . {\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 A {\displaystyle A} are the Fourier coefficients of some essentially bounded function f {\displaystyle f} .

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

See also

  • Circulant matrix, a square Toeplitz matrix with the additional property that a i = a i + n {\displaystyle a_{i}=a_{i+n}}
  • Hankel matrix, an "upside down" (i.e., row-reversed) Toeplitz matrix
  • Szegő limit theorems – Determinant of large Toeplitz matrices
  • Toeplitz operator – compression of a multiplication operator on the circle to the Hardy spacePages displaying wikidata descriptions as a fallback

Notes

Further reading

References

  1. Press et al. 2007, §2.8.2—Toeplitz matrices - 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 ↩

  2. Hayes 1996, Chapter 5.2.6 - Hayes, Monson H. (1996), Statistical digital signal processing and modeling, Wiley, ISBN 0-471-59431-8 ↩

  3. Krishna & Wang 1993 - 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 ↩

  4. Monahan 2011, §4.5—Toeplitz systems - Monahan, J. F. (2011), Numerical Methods of Statistics, Cambridge University Press, doi:10.1017/CBO9780511977176, ISBN 978-1-139-08211-2 https://doi.org/10.1017%2FCBO9780511977176 ↩

  5. Brent 1999 - 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 https://arxiv.org/abs/1005.0671 ↩

  6. Bojanczyk et al. 1995 - 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 https://arxiv.org/abs/1004.5510 ↩

  7. Mukherjee & Maiti 1988 - 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 https://core.ac.uk/download/pdf/82070573.pdf ↩

  8. Böttcher & Grudsky 2012 - 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 ↩