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:

of the form

is a Toeplitz matrix 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. 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 ops with the use of fast matrix multiplication algorithms.

Properties

• . The set Toeplitz matrices is a subspace of the vector space matrices (under matrix addition and scalar multiplication).

• time (by storing only one value of each diagonal) and multiplied 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

• .

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

• are lower triangular is a strictly lower triangular matrix.

Discrete convolution

The convolution can be formulated as:

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

Infinite Toeplitz matrix

induces a linear operator.

The induced operator is bounded are the Fourier coefficients of some essentially bounded.

is called the symbol norm of its symbol. The proof can be found as Theorem 1.1 of Böttcher and Grudsky.

See also

• Circulant matrix

• Hankel matrix, an "upside down" (i.e., row-reversed) Toeplitz matrix

Notes

References

Further reading