Toeplitz matrix

Template:Short description In 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>\qquad\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}.</math>

Any <math>n \times n</math> matrix <math>A</math> of the form

<math>A = \begin{bmatrix}

 a_0 & a_{-1}   & a_{-2} & \cdots & \cdots & 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} & \cdots & \cdots & a_2 & a_1 & a_0 \end{bmatrix}</math>

is a Toeplitz matrix. If the <math>i,j</math> element of <math>A</math> is denoted <math>A_{i,j}</math> then we have

<math>A_{i,j} = A_{i+1,j+1} = a_{i-j}.</math>

A Toeplitz matrix is not necessarily square.

Solving a Toeplitz system

A matrix equation of the form

<math>Ax = b</math>

is called a Toeplitz system if <math>A</math> is a Toeplitz matrix. If <math>A</math> is an <math>n \times n</math> Toeplitz matrix, then the system has at most only <math>2n-1</math> unique values, rather than <math>n^2</math>. We might therefore expect that the solution of a Toeplitz system would be easier, and indeed that is the case.

Toeplitz systems can be solved by algorithms such as the Schur algorithm or the Levinson algorithm in <math>O(n^2)</math> time.<ref>Template:Harvnb</ref><ref>Template:Harvnb</ref> Variants of the latter have been shown to be weakly stable (i.e. they exhibit numerical stability for well-conditioned linear systems).<ref>Template:Harvnb</ref> The algorithms can also be used to find the determinant of a Toeplitz matrix in <math>O(n^2)</math> time.<ref>Template:Harvnb</ref>

A Toeplitz matrix can also be decomposed (i.e. factored) in <math>O(n^2)</math> time.<ref>Template:Harvnb</ref> The Bareiss algorithm for an LU decomposition is stable.<ref>Template:Harvnb</ref> An LU decomposition gives a quick method for solving a Toeplitz system, and also for computing the determinant.

Properties

• An <math>n\times n</math> Toeplitz matrix may be defined as a matrix <math>A</math> where <math>A_{i,j}=c_{i-j}</math>, for constants <math>c_{1-n},\ldots,c_{n-1}</math>. The set of <math>n\times n</math> Toeplitz matrices is a subspace of the vector space of <math>n\times n</math> matrices (under matrix addition and scalar multiplication).
• Two Toeplitz matrices may be added in <math>O(n)</math> time (by storing only one value of each diagonal) and multiplied in <math>O(n^2)</math> time.
• Toeplitz matrices are persymmetric. Symmetric Toeplitz matrices are both centrosymmetric and bisymmetric.
• 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. Similarly, one can represent linear convolution as multiplication by a Toeplitz matrix.
• Toeplitz matrices commute asymptotically. This means they diagonalize in the same basis when the row and column dimension tends to infinity.

• For symmetric Toeplitz matrices, there is the decomposition

<math>\frac{1}{a_0} A = G G^\operatorname{T} - (G - I)(G - I)^\operatorname{T}</math>

where <math>G</math> is the lower triangular part of <math>\frac{1}{a_0} A</math>.

• The inverse of a nonsingular symmetric Toeplitz matrix has the representation

<math>A^{-1} = \frac{1}{\alpha_0} (B B^\operatorname{T} - C C^\operatorname{T})</math>

where <math>B</math> and <math>C</math> are lower triangular Toeplitz matrices and <math>C</math> is a strictly lower triangular matrix.<ref>Template:Harvnb</ref>

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 <math> h </math> and <math> x </math> can be formulated as:

<math>

       y = h \ast x =
           \begin{bmatrix}
               h_1 & 0 & \cdots & 0 & 0 \\
               h_2 & h_1 &      & \vdots & \vdots \\
               h_3 & h_2 & \cdots & 0 & 0 \\
               \vdots & h_3 & \cdots & h_1 & 0 \\
               h_{m-1} & \vdots & \ddots & h_2 & h_1 \\
               h_m & h_{m-1} &      & \vdots & h_2 \\
               0 & h_m & \ddots & h_{m-2} & \vdots \\
               0 & 0 & \cdots & h_{m-1} & h_{m-2} \\
               \vdots & \vdots &        & h_m & h_{m-1} \\
               0 & 0 & 0 & \cdots & h_m
           \end{bmatrix}
           \begin{bmatrix}
               x_1 \\
               x_2 \\
               x_3 \\
               \vdots \\
               x_n
           \end{bmatrix}

</math>

<math> y^T =

           \begin{bmatrix}
               h_1 & h_2 & h_3 & \cdots & h_{m-1} & h_m
           \end{bmatrix}
           \begin{bmatrix}
               x_1 & x_2 & x_3 & \cdots & x_n & 0 & 0 & 0& \cdots & 0 \\
               0 & x_1 & x_2 & x_3 & \cdots & x_n & 0 & 0 & \cdots & 0 \\
               0 & 0 & x_1 & x_2 & x_3 & \ldots & x_n & 0  & \cdots & 0 \\
               \vdots &    & \vdots & \vdots & \vdots &    & \vdots & \vdots  & & \vdots \\
               0 & \cdots & 0 & 0 & x_1 & \cdots & x_{n-2} & x_{n-1} & x_n & 0 \\
               0 & \cdots & 0 & 0 & 0 & x_1 & \cdots & x_{n-2} & x_{n-1} & x_n
           \end{bmatrix}.

</math>

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

Infinite Toeplitz matrix

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}} A bi-infinite Toeplitz matrix (i.e. entries indexed by <math>\mathbb Z\times\mathbb Z</math>) <math>A</math> induces a linear operator on <math>\ell^2</math>.

<math>

A=\begin{bmatrix}

      & \vdots & \vdots & \vdots & \vdots \\

\cdots & a_0 & a_{-1} & a_{-2} & a_{-3} & \cdots \\ \cdots & a_1 & a_0 & a_{-1} & a_{-2} & \cdots \\ \cdots & a_2 & a_1 & a_0 & a_{-1} & \cdots \\ \cdots & a_3 & a_2 & a_1 & a_0 & \cdots \\

      & \vdots  & \vdots & \vdots & \vdots

\end{bmatrix}.

</math>

The induced operator is bounded if and only if the coefficients of the Toeplitz matrix <math>A</math> are the Fourier coefficients of some essentially bounded function <math>f</math>.

In such cases, <math>f</math> is called the symbol of the Toeplitz matrix <math>A</math>, and the spectral norm of the Toeplitz matrix <math>A</math> coincides with the <math>L^\infty</math> norm of its symbol. The proof can be found as Theorem 1.1 of Böttcher and Grudsky.<ref>Template:Harvnb</ref>

See also

• Circulant matrix, a square Toeplitz matrix with the additional property that <math>a_i=a_{i+n}</math>
• Hankel matrix, an "upside down" (i.e., row-reversed) Toeplitz matrix
• Template:Annotated link
• Template:Annotated link

References

• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation

Further reading

• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation