Toeplitz matrix

From HandWiki
Short description: Matrix with equal values along diagonals

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]\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}. }[/math]

Any [math]\displaystyle{ n \times n }[/math] matrix [math]\displaystyle{ A }[/math] of the form

[math]\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} }[/math]

is a Toeplitz matrix. If the [math]\displaystyle{ i,j }[/math] element of [math]\displaystyle{ A }[/math] is denoted [math]\displaystyle{ A_{i,j} }[/math] then we have

[math]\displaystyle{ 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]\displaystyle{ Ax = b }[/math]

is called a Toeplitz system if [math]\displaystyle{ A }[/math] is a Toeplitz matrix. If [math]\displaystyle{ A }[/math] is an [math]\displaystyle{ n \times n }[/math] Toeplitz matrix, then the system has at most only [math]\displaystyle{ 2n-1 }[/math] unique values, rather than [math]\displaystyle{ 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]\displaystyle{ O(n^2) }[/math] 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 [math]\displaystyle{ O(n^2) }[/math] time.[4]

A Toeplitz matrix can also be decomposed (i.e. factored) in [math]\displaystyle{ O(n^2) }[/math] 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.

General properties

  • An [math]\displaystyle{ n\times n }[/math] Toeplitz matrix may be defined as a matrix [math]\displaystyle{ A }[/math] where [math]\displaystyle{ A_{i,j}=c_{i-j} }[/math], for constants [math]\displaystyle{ c_{1-n},\ldots,c_{n-1} }[/math]. The set of [math]\displaystyle{ n\times n }[/math] Toeplitz matrices is a subspace of the vector space of [math]\displaystyle{ n\times n }[/math] matrices (under matrix addition and scalar multiplication).
  • Two Toeplitz matrices may be added in [math]\displaystyle{ O(n) }[/math] time (by storing only one value of each diagonal) and multiplied in [math]\displaystyle{ 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]\displaystyle{ \frac{1}{a_0} A = G G^\operatorname{T} - (G - I)(G - I)^\operatorname{T} }[/math]
where [math]\displaystyle{ G }[/math] is the lower triangular part of [math]\displaystyle{ \frac{1}{a_0} A }[/math].
  • The inverse of a nonsingular symmetric Toeplitz matrix has the representation
[math]\displaystyle{ A^{-1} = \frac{1}{\alpha_0} (B B^\operatorname{T} - C C^\operatorname{T}) }[/math]
where [math]\displaystyle{ B }[/math] and [math]\displaystyle{ C }[/math] are lower triangular Toeplitz matrices and [math]\displaystyle{ C }[/math] is a strictly lower triangular matrix.[7]

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

[math]\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} }[/math]
[math]\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}. }[/math]

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

Infinite Toeplitz matrix

Main page: Toeplitz operator

A bi-infinite Toeplitz matrix (i.e. entries indexed by [math]\displaystyle{ \mathbb Z\times\mathbb Z }[/math]) [math]\displaystyle{ A }[/math] induces a linear operator on [math]\displaystyle{ \ell^2 }[/math].

[math]\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}. }[/math]

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

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

See also

Notes

  1. ↑ Press et al. 2007, §2.8.2—Toeplitz matrices
  2. ↑ Hayes 1996, Chapter 5.2.6
  3. ↑ Krishna & Wang 1993
  4. ↑ Monahan 2011, §4.5—Toeplitz systems
  5. ↑ Brent 1999
  6. ↑ Bojanczyk et al. 1995
  7. ↑ Mukherjee & Maiti 1988
  8. ↑ Böttcher & Grudsky 2012

References

Further reading



Retrieved from "https://handwiki.org/wiki/index.php?title=Toeplitz_matrix&oldid=3368878"