Toeplitz matrix

From Wikipedia, the free encyclopedia

In the mathematical discipline of 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×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_i,j = A_{i − 1,j − 1}.

Contents 1 Properties 2 Notes 3 See also 4 External links

[edit] Properties

Generally, a matrix equation

Ax = b

is the general problem of n linear simultaneous equations to solve. If A is a Toeplitz matrix, then the system is rather special (has only 2n − 1 degrees of freedom, rather than n²). One could therefore expect that solution of a Toeplitz system would be easier.

This can be investigated by the transformation

AU_n − U_mA,

which has rank 2, where U_k is the down-shift operator. Specifically, one can by simple calculation show that

where empty places in the matrix are replaced by zeros.

[edit] Notes

Two Toeplitz matrices may be added in O(n) time. A Toeplitz matrix can be multiplied by a vector in O(n log n) time, and the matrix multiplication of two Toeplitz matrices can be done in O(n²) time.

Toeplitz systems of form Ax = b can be solved by the Levinson-Durbin Algorithm in Θ(n²) time. Variants of this algorithm have been shown to be weakly stable (i.e., they exhibit numerical stability for well-conditioned linear systems). ^[1]

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.

If a Toeplitz matrix has the additional property that a_i = a_{i + n}, then it is a circulant matrix.

Toeplitz matrices are persymmetric. Symmetric Toeplitz matrices are both centrosymmetric and bisymmetric.

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.

All Toeplitz matrices commute asymptotically. This means they diagonalize in the same basis when the row and column dimension tends to infinity.

[edit] See also

• Circulant matrix
• Hankel matrix, a Toeplitz matrix 'upside down'.

[edit] External links

• Toeplitz and Circulant Matrices: A Review, by R. M. Gray