Toeplitz matrix

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\\i&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}.\$

Properties

Generally, a matrix equation

$Ax=b\$

is the general problem of n linear simultaneous equations to solve. If A is an $m\times n$ Toeplitz matrix, then the system is rather special (has only m+n-1 degrees of freedom, rather than m n). One could therefore expect that solution of a Toeplitz system would be easier.

This can be investigated by the transformation

$AU_{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_{m}A={\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 zeros.

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:

${\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}}$

This approach can be extended to compute autocorrelation, cross-correlation, moving average etc.

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^{2}$) time.

Toeplitz systems of form $Ax=b$ can be solved by the Levinson-Durbin Algorithm in Θ($n^{2}$) time. Variants of this algorithm have been shown to be weakly stable (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.

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

See also

• Hankel matrix, a Toeplitz matrix 'upside down'.
• Toeplitz operator, a Toeplitz matrix with 'infinitely many' rows and columns.

External links

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