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:

$\begin{bmatrix} a & b & c & d & k \\ f & a & b & c & d \\ g & f & a & b & c \\ h & g & f & a & b \\ j & h & g & f & a \end{bmatrix}$

Any n×n matrix A of the form

$A = \begin{bmatrix} a_{0} & a_{-1} & a_{-2} & \ldots & \ldots &a_{-n+1} \\ a_{1} & a_0 & a_{-1} & \ddots & & \vdots \\ a_{2} & a_{1} & \ddots & \ddots & \ddots& \vdots \\ \vdots & \ddots & \ddots & \ddots & a_{-1} & a_{-2}\\ \vdots & & \ddots & a_{1} & a_{0}& a_{-1} \\ a_{n-1} & \ldots & \ldots & a_{2} & a_{1} & a_{0} \end{bmatrix}$

is a Toeplitz matrix. If the i,j element of A is denoted A_i,j, then we have

A i, j = a i - j .

1 Properties
2 Notes
3 See also
4 External link

[edit] Properties

Generally, a matrix equation

A x = 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

A U n - U m A,

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

$AU_n-U_mA= \begin{bmatrix} a_{-1} & \cdots & a_{-n+1} & 0 \\ \vdots & & & -a_{-n+1} \\ \vdots & & & \vdots \\ 0 & \cdots & & -a_{n-n-1} \end{bmatrix}$

where empty places in the matrix are replaced by zeros.

[edit] Notes

These matrices have uses in computer science because it can be shown that the addition of two Toeplitz matrices can be done 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 2$ ) time.

Toeplitz systems of form $A x = b$ can be solved by the Levinson-Durbin Algorithm in Θ( $n 2$ ) time. Variants of this algorithm have been shown to be weakly stable in the sense of James Bunch (i.e., they exhibit numerical stability for well-conditioned linear systems).

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 centrosymmetric.