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:

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

Any n × n {\displaystyle n\times n} matrix A {\displaystyle A} of the form

A = [ a 0 a − 1 a − 2 ⋯ ⋯ a − ( n − 1 ) a 1 a 0 a − 1 ⋱ ⋮ a 2 a 1 ⋱ ⋱ ⋱ ⋮ ⋮ ⋱ ⋱ ⋱ a − 1 a − 2 ⋮ ⋱ a 1 a 0 a − 1 a n − 1 ⋯ ⋯ a 2 a 1 a 0 ] {\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 {\displaystyle i,j} element of A {\displaystyle A} is denoted A i , j {\displaystyle A_{i,j}} then we have

A i , j = A i + 1 , j + 1 = a i − j . {\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

A x = b {\displaystyle Ax=b}

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

A Toeplitz matrix can also be decomposed (i.e. factored) in O ( n 2 ) {\displaystyle O(n^{2})} time.^[5] The Bareiss algorithm for an LU decomposition is stable.^[6] An LU decomposition gives a quick method for solving a Toeplitz system, and also for computing the determinant. Using displacement rank we obtain method requiring O ~ ( α ω − 1 n ) {\displaystyle {\tilde {O}}({\alpha ^{\omega -1}}n)} ops with the use of fast matrix multiplication algorithms, where α {\displaystyle \alpha } is the rank and ∼ 2.37 ≤ ω < 3 {\displaystyle ^{\sim }2.37\leq \omega <3} ^[7].

Properties

• An n × n {\displaystyle n\times n} Toeplitz matrix may be defined as a matrix A {\displaystyle A} where A i , j = c i − j {\displaystyle A_{i,j}=c_{i-j}} , for constants c 1 − n , … , c n − 1 {\displaystyle c_{1-n},\ldots ,c_{n-1}} . The set of n × n {\displaystyle n\times n} Toeplitz matrices is a subspace of the vector space of n × n {\displaystyle n\times n} matrices (under matrix addition and scalar multiplication).
• Two Toeplitz matrices may be added in O ( n ) {\displaystyle O(n)} time (by storing only one value of each diagonal) and multiplied in O ( n 2 ) {\displaystyle 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 are asymptotically equivalent to circulant matrices as the dimension grows, a result known as the Grenander–Szegő theorem.^[8] This asymptotic circulant property is the reason that the discrete Fourier transform approximately diagonalizes large Toeplitz matrices, and underlies the effectiveness of DFT-based spectral density estimation for stationary processes.
• 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 T − ( G − I ) ( G − I ) T {\displaystyle {\frac {1}{a_{0}}}A=GG^{\operatorname {T} }-(G-I)(G-I)^{\operatorname {T} }}

where G {\displaystyle G} is the lower triangular part of 1 a 0 A {\displaystyle {\frac {1}{a_{0}}}A} .

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

A − 1 = 1 α 0 ( B B T − C C T ) {\displaystyle A^{-1}={\frac {1}{\alpha _{0}}}(BB^{\operatorname {T} }-CC^{\operatorname {T} })}

where B {\displaystyle B} and C {\displaystyle C} are lower triangular Toeplitz matrices and C {\displaystyle C} is a strictly lower triangular matrix.^[9]

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

y = h ∗ x = [ h 1 0 ⋯ 0 0 h 2 h 1 ⋮ ⋮ h 3 h 2 ⋯ 0 0 ⋮ h 3 ⋯ h 1 0 h m − 1 ⋮ ⋱ h 2 h 1 h m h m − 1 ⋮ h 2 0 h m ⋱ h m − 2 ⋮ 0 0 ⋯ h m − 1 h m − 2 ⋮ ⋮ h m h m − 1 0 0 0 ⋯ h m ] [ x 1 x 2 x 3 ⋮ x n ] {\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}}}

y T = [ h 1 h 2 h 3 ⋯ h m − 1 h m ] [ 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 … x n 0 ⋯ 0 ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ 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 ] . {\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 Z × Z {\displaystyle \mathbb {Z} \times \mathbb {Z} } ) A {\displaystyle A} induces a linear operator on ℓ 2 {\displaystyle \ell ^{2}} .

A = [ ⋮ ⋮ ⋮ ⋮ ⋯ 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 ⋯ ⋮ ⋮ ⋮ ⋮ ] . {\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 A {\displaystyle A} are the Fourier coefficients of some essentially bounded function f {\displaystyle f} .

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

See also

• Circulant matrix, a square Toeplitz matrix with the additional property that a i = a i + n {\displaystyle a_{i}=a_{i+n}}
• Hankel matrix, an "upside down" (i.e., row-reversed) Toeplitz matrix
• Szegő limit theorems – Determinant of large Toeplitz matrices
• Toeplitz operator

Notes

References

Further reading