Toeplitz matrix explained

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:

\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 x n matrix A of the formA = \begin{bmatrix} a _{0} & a _{-1} & a _{-2} & … & … & 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} & … & … & 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 haveA _{i,j} = A _{i+1,j+1} = a _{i-j} .

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 x n Toeplitz matrix, then the system has at most only 2 n -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.

General properties

• An

n x n Toeplitz matrix may be defined as a matrix A where A _{i,j} = c _{i-j} , for constants c _{1-n} ,\ldots,c _{n-1} . The set of n x n Toeplitz matrices is a subspace of the vector space of n x 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

(1)/(a _{0}) A = G G ^{\operatorname{T}} - (G - I)(G - I) ^{\operatorname{T}}

where

G is the lower triangular part of (1)/(a _{0}) A .

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

A ^{-1} = (1)/(\alpha _{0}) (B B ^{\operatorname{T}} - C C ^{\operatorname{T})}

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{bmatrix} h _{1} & 0 & … & 0 & 0 \\ h _{2} & h _{1} & & \vdots & \vdots \\ h _{3} & h _{2} & … & 0 & 0 \\ \vdots & h _{3} & … & 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 & … & h _{m-1} & h _{m-2} \\ \vdots & \vdots & & h _{m} & h _{m-1} \\ 0 & 0 & 0 & … & 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} & … & h _{m-1} & h _{m} \end{bmatrix} \begin{bmatrix} x _{1} & x _{2} & x _{3} & … & x _{n} & 0 & 0 & 0 & … & 0 \\ 0 & x _{1} & x _{2} & x _{3} & … & x _{n} & 0 & 0 & … & 0 \\ 0 & 0 & x _{1} & x _{2} & x _{3} & \ldots & x _{n} & 0 & … & 0 \\ \vdots & & \vdots & \vdots & \vdots & & \vdots & \vdots & & \vdots \\ 0 & … & 0 & 0 & x _{1} & … & x _{n-2} & x _{n-1} & x _{n} & 0 \\ 0 & … & 0 & 0 & 0 & x _{1} & … & x _{n-2} & x _{n-1} & x _{n} \end{bmatrix}.

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

Infinite Toeplitz matrix

See main article: Toeplitz operator. A bi-infinite Toeplitz matrix (i.e. entries indexed by

Z x Z ) A induces a linear operator on \ell ^{2} .A = \begin{bmatrix} & \vdots & \vdots & \vdots & \vdots \\ … & a _{0} & a _{-1} & a _{-2} & a _{-3} & … \\ … & a _{1} & a _{0} & a _{-1} & a _{-2} & … \\ … & a _{2} & a _{1} & a _{0} & a _{-1} & … \\ … & a _{3} & a _{2} & a _{1} & a _{0} & … \\ & \vdots & \vdots & \vdots & \vdots \end{bmatrix}.

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 is easy to establish and can be found as Theorem 1.1 of.

See also

• Circulant matrix, a square Toeplitz matrix with the additional property that

a _{i=a} _{i+n}

• Hankel matrix, an "upside down" (i.e., row-reversed) Toeplitz matrix

Further reading

• • • Golub G. H., van Loan C. F. (1996), Matrix Computations (Johns Hopkins University Press) §4.7 - Toeplitz and Related Systems
• Gray R. M., Toeplitz and Circulant Matrices: A Review (Now Publishers)