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 & e \\ 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 - 1, j - 1 .

1 Properties
2 Notes
3 See also
4 External links

[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 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:

$\begin{matrix} y & = & h \ast x \\ & = & \begin{bmatrix} h_1 & 0 & \ldots & 0 & 0 \\ h_2 & h_1 & \ldots & \vdots & \vdots \\ h_3 & h_2 & \ldots & 0 & 0 \\ \vdots & h_3 & \ldots & h_1 & 0 \\ h_{m-1} & \vdots & \ldots & h_2 & h_1 \\ h_m & h_{m-1} & \vdots & \vdots & h_2 \\ 0 & h_m & \ldots & h_{m-2} & \vdots \\ 0 & 0 & \ldots & h_{m-1} & h_{m-2} \\ \vdots & \vdots & \vdots & h_m & h_{m-1} \\ 0 & 0 & 0 & \ldots & h_m \\ \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ \vdots \\ x_n \\ \end{bmatrix} \\ y^T & = & \begin{bmatrix} h_1 & h_2 & h_3 & \ldots & h_{m-1} & h_m \\ \end{bmatrix} \begin{bmatrix} x_1 & x_2 & x_3 & \ldots & x_n & 0 & 0 & 0& \ldots & 0 \\ 0 & x_1 & x_2 & x_3 & \ldots & x_n & 0 & 0 & \ldots & 0 \\ 0 & 0 & x_1 & x_2 & x_3 & \ldots & x_n & 0 & \ldots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ldots & \vdots & \vdots & \ldots & 0 \\ 0 & \ldots & 0 & 0 & x_1 & \ldots & x_{n-2} & x_{n-1} & x_{n} & \vdots \\ 0 & \ldots & 0 & 0 & 0 & x_1 & \ldots & x_{n-2} & x_{n-1} & x_{n} \\ \end{bmatrix}. \end{matrix}$