# 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:

${\displaystyle {\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×n matrix A of the form

${\displaystyle 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}}}$

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

${\displaystyle A_{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

${\displaystyle Ax=b\ }$

is called a Toeplitz system if A is a Toeplitz matrix. If A is an ${\displaystyle n\times n}$  Toeplitz matrix, then the system has only 2n−1 degrees of freedom, rather than n2. 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 the Levinson algorithm in Θ(n2) time.[1] Variants of this algorithm have been shown to be weakly stable (i.e. they exhibit numerical stability for well-conditioned linear systems).[2] The algorithm can also be used to find the determinant of a Toeplitz matrix in O(n2) time.[3]

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

Algorithms that are asymptotically faster than those of Bareiss and Levinson have been described in the literature, but their accuracy cannot be relied upon.[6][7][8][9]

## General properties

• A Toeplitz matrix may be defined as a matrix A where Ai,j = ci−j, for constants c1−ncn−1. The set of n×n Toeplitz matrices is a subspace of the vector space of n×n matrices under matrix addition and scalar multiplication.
• Two Toeplitz matrices may be added in O(n) time and multiplied in O(n2) time.
• A positive semi-definite n×n Toeplitz matrix ${\displaystyle A}$  of rank r < n can be uniquely factored as
${\displaystyle A=\sum _{k=1}^{r}d_{i}v(f_{k})v(f_{k})^{\operatorname {H} }=VDV^{\operatorname {H} }}$
where ${\displaystyle D=\mathrm {diag} (d_{1},\ldots ,d_{r})}$  is an r×r positive definite diagonal matrix, ${\displaystyle V=[v(f_{1}),\ldots ,v(f_{r})]}$  is an n×r Vandermonde matrix such that the columns are ${\displaystyle v(f)=[1,e^{i2\pi f},\ldots ,e^{i2\pi (n-1)f}]^{\operatorname {T} }}$ . Here ${\displaystyle i={\sqrt {-1}}}$  and ${\displaystyle f_{k}\in [0,1]}$  is normalized frequency, and ${\displaystyle V^{\operatorname {H} }}$  is the Hermitian transpose of ${\displaystyle V}$ . If the rank r = n, then the Vandermonde decomposition is not unique.[10]
• For symmetric Toeplitz matrices, there is the decomposition
${\displaystyle {\frac {1}{a_{0}}}A=GG^{\operatorname {T} }-(G-I)(G-I)^{\operatorname {T} }}$
where ${\displaystyle G}$  is the lower triangular part of ${\displaystyle {\frac {1}{a_{0}}}A}$ .
• The inverse of a nonsingular symmetric Toeplitz matrix has the representation
${\displaystyle A^{-1}={\frac {1}{\alpha _{0}}}(BB^{\operatorname {T} }-CC^{\operatorname {T} })}$
where ${\displaystyle B}$  and ${\displaystyle C}$  are lower triangular Toeplitz matrices and ${\displaystyle C}$  is a strictly lower triangular matrix.[11]

## 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 ${\displaystyle h}$  and ${\displaystyle x}$  can be formulated as:

${\displaystyle 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}}}$
${\displaystyle 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}}.}$

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 ${\displaystyle \mathbb {Z} \times \mathbb {Z} }$ ) ${\displaystyle A}$  induces a linear operator on ${\displaystyle \ell ^{2}}$ .

${\displaystyle 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}}.}$

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

In such cases, ${\displaystyle f}$  is called the symbol of the Toeplitz matrix ${\displaystyle A}$ , and the spectral norm of the Toeplitz matrix ${\displaystyle A}$  coincides with the ${\displaystyle L^{\infty }}$  norm of its symbol. The proof is easy to establish and can be found as Theorem 1.1 in the google book link: [12]

• Circulant matrix, a Toeplitz matrix with the additional property that ${\displaystyle a_{i}=a_{i+n}}$