Toeplitz matrix
|
|
In the mathematical discipline of linear algebra, a Toeplitz matrix, named after Otto Toeplitz, or diagonal constant matrix is a special kind of matrix where each descending diagonal from left to right is constant. For instance, the following matrix is Toeplitz:
\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}.
<math>| Contents |
Definition
A mxn 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_{m-1} & \ldots & \ldots & a_{2} & a_{1} & a_{0} \end{bmatrix} <math> is called a Toeplitz matrix. If the i,j element of A is denoted Ai,j, then we have
- <math>A_{i,j} = a_{i-j}.<math>
Properties
Generally, a matrix equation <math>Ax=b<math> has n equations to solve, but if A is Toeplitz, then the system has only 2n-1 degrees of freedom. One could therefore expect that solution of a Toeplitz system would therefore be easier. In fact, this property can be investigated by the transformation <math>AU_n-U_mA<math>, which has rank 2, when <math>U_k<math> is the down-shift operator. Specifically, we can by simple calculation show that
- <math>
AU_n-U_mA= \begin{bmatrix} a_{-1} & \dots & a_{-n+1} & 0 \\
& & & -a_{-n+1} \\
& & & \vdots \\
0 & & & -a_{m-n-1}
\end{bmatrix} <math>
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 and the matrix multiplication of two Toeplitz matrices can be done in O(n log n) time. Toeplitz systems of form <math>Ax=b<math> 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 <math>a_i=a_{i+n}<math>, then it is a circulant matrix.
External link
Toeplitz and Circulant Matices: A Review, by R. M. Gray (http://www-ee.stanford.edu/~gray/toeplitz.pdf)