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:

<math>

\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} </math>

Any n×n matrix A of the form

<math>

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} </math>

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

1 Properties
2 Notes
3 See also
4 External link

[edit] Properties

Generally, a matrix equation

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

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

<math>

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} </math>

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(<math>n^2</math>) time.

Toeplitz systems of form <math>Ax=b</math> can be solved by the Levinson-Durbin Algorithm in Θ(<math>n^2</math>) 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 <math>a_i=a_{i+n}</math>, then it is a circulant matrix.

Toeplitz matrices are persymmetric. Symmetric Toeplitz matrices are centrosymmetric.