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:

Any matrix of the form

is a Toeplitz matrix. If the element of is denoted then we have

A Toeplitz matrix is not necessarily square.

Solving a Toeplitz system

A matrix equation of the form

is called a Toeplitz system if is a Toeplitz matrix. If is an Toeplitz matrix, then the system has at most only unique values, rather than . 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 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 time.[4]

A Toeplitz matrix can also be decomposed (i.e. factored) in 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 Toeplitz matrix may be defined as a matrix where , for constants . The set of Toeplitz matrices is a subspace of the vector space of matrices (under matrix addition and scalar multiplication).
  • Two Toeplitz matrices may be added in time (by storing only one value of each diagonal) and multiplied in 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
where is the lower triangular part of .
where and are lower triangular Toeplitz matrices and 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 and can be formulated as:

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 ) induces a linear operator on .

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

In such cases, is called the symbol of the Toeplitz matrix , and the spectral norm of the Toeplitz matrix coincides with the norm of its symbol. The proof is easy to establish and can be found as Theorem 1.1 of.[8]

See also

Notes

References

Further reading

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.