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 n \times n matrix A of the form is a Toeplitz matrix. If the i,j element of A is denoted A_{i,j} 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 A is a Toeplitz matrix. If A is an n \times n Toeplitz matrix, then the system has at most only 2n-1 unique values, rather than 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) 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.

Properties

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 and x 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 ) A induces a linear operator on \ell^2. The induced operator is bounded if and only if the coefficients of the Toeplitz matrix A are the Fourier coefficients of some essentially bounded function f. In such cases, f is called the symbol of the Toeplitz matrix A, and the spectral norm of the Toeplitz matrix A coincides with the L^\infty norm of its symbol. The proof is easy to establish and can be found as Theorem 1.1 of.