Toeplitz matrix

Encyclopedia : T : TO : TOE : 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

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

Any m×n matrix A of the form

[A =\begin a_ & a_ & a_ & \ldots & \ldots &a_ \\ a_ & a_0 & a_ & \ddots & & \vdots \\ a_ & a_ & \ddots & \ddots & \ddots& \vdots \\ \vdots & \ddots & \ddots & \ddots & a_ & a_\\ \vdots & & \ddots & a_ & a_& a_ \\

a_ & \ldots & \ldots & a_ & a_ & a_\end ]

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

[A_ = a_.]

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

[AU_n-U_mA=\begin

a_ & \cdots & a_ & 0 \\\vdots & & & -a_ \\\vdots & & & \vdots \\ 0 & \cdots & & -a_\end]

where empty places in the matrix are replaced by zeros.

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 [Ax=b] can be solved by Levinson recursion.

They 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_], then it is a circulant matrix.

External link

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

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.