Toeplitz matrix

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:

:$\qquad\begin 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.$

Any $n \times n$ matrix $A$ of the form

:$A = \begin a_0 & a_ & a_ & \cdots & \cdots & a_ \\ a_1 & a_0 & a_ & \ddots & & \vdots \\ a_2 & a_1 & \ddots & \ddots & \ddots & \vdots \\ \vdots & \ddots & \ddots & \ddots & a_ & a_ \\ \vdots & & \ddots & a_1 & a_0 & a_ \\ a_ & \cdots & \cdots & a_2 & a_1 & a_0 \end$

is a Toeplitz matrix. If the $i,j$ element of $A$ is denoted $A_$ then we have
:$A_ = A_ = a_.$

A Toeplitz matrix is not necessarily square.

Solving a Toeplitz system

A matrix equation of the form

:$Ax = b$

is called a Toeplitz system if $A$ is a Toeplitz matrix. If $A$ is an $n \times n$ Toeplitz matrix, then the system has at most only
$2n-1$ unique values, rather than $n^2$. 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 $O(n^2)$ time. Variants of the latter have been shown to be weakly stable (i.e. they exhibit numerical stability for well-conditioned linear systems). The algorithms can also be used to find the determinant of a Toeplitz matrix in $O(n^2)$ time.

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

Properties

* An $n\times n$ Toeplitz matrix may be defined as a matrix $A$ where $A_=c_$, for constants $c_,\ldots,c_$. The set of $n\times n$ Toeplitz matrices is a subspace of the vector space of $n\times n$ matrices (under matrix addition and scalar multiplication).
* Two Toeplitz matrices may be added in $O(n)$ time (by storing only one value of each diagonal) and multiplied in $O(n^2)$ 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

::$\frac A = G G^\operatorname - (G - I)(G - I)^\operatorname$

:where $G$ is the lower triangular part of $\frac A$.

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

::$A^ = \frac (B B^\operatorname - C C^\operatorname)$

:where $B$ and $C$ are lower triangular Toeplitz matrices and $C$ is a strictly lower triangular matrix.

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:

:$y = h \ast x = \begin 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_ & \vdots & \ddots & h_2 & h_1 \\ h_m & h_ & & \vdots & h_2 \\ 0 & h_m & \ddots & h_ & \vdots \\ 0 & 0 & \cdots & h_ & h_ \\ \vdots & \vdots & & h_m & h_ \\ 0 & 0 & 0 & \cdots & h_m \end \begin x_1 \\ x_2 \\ x_3 \\ \vdots \\ x_n \end$

: $y^T = \begin h_1 & h_2 & h_3 & \cdots & h_ & h_m \end \begin 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_ & x_ & x_n & 0 \\ 0 & \cdots & 0 & 0 & 0 & x_1 & \cdots & x_ & x_ & x_n \end.$

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

Infinite Toeplitz matrix

A bi-infinite Toeplitz matrix (i.e. entries indexed by $\mathbb Z\times\mathbb Z$) $A$ induces a linear operator on $\ell^2$.

:$A=\begin & \vdots & \vdots & \vdots & \vdots \\ \cdots & a_0 & a_ & a_ & a_ & \cdots \\ \cdots & a_1 & a_0 & a_ & a_ & \cdots \\ \cdots & a_2 & a_1 & a_0 & a_ & \cdots \\ \cdots & a_3 & a_2 & a_1 & a_0 & \cdots \\ & \vdots & \vdots & \vdots & \vdots \end.$

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

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

See also

* Circulant matrix, a square Toeplitz matrix with the additional property that $a_i=a_$
* Hankel matrix, an "upside down" (i.e., row-reversed) Toeplitz matrix
*
*

Notes

References

*
*
*
*
*
*
*
*
*
*
*
*
*

Further reading

*
*
*
*
*
*
*

{{Authority control

Matrices (mathematics)