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>\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>n \times n</math> matrix <math>A</math> of the form
:<math>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>i,j</math> element of <math>A</math> is denoted <math>A_{i,j}</math> then we have
:<math>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>Ax = b</math>
is called a Toeplitz system if <math>A</math> is a Toeplitz matrix. If <math>A</math> is an <math>n \times n</math> Toeplitz matrix, then the system has at most only
<math>2n-1</math> unique values, rather than <math>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>O(n^2)</math> 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 <math>O(n^2)</math> time.
A Toeplitz matrix can also be decomposed (i.e. factored) in <math>O(n^2)</math> time. The Bareiss algorithm <!--this is not 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. Using displacement rank we obtain method requiring <math>\tilde O({\alpha ^{\omega - 1n)</math> ops with the use of fast matrix multiplication algorithms, where <math>\alpha</math> is the rank and <math>^ \sim 2.37 \le \omega < 3</math>.
Properties
- An <math>n\times n</math> Toeplitz matrix may be defined as a matrix <math>A</math> where <math>A_{i,j}=c_{i-j}</math>, for constants <math>c_{1-n},\ldots,c_{n-1}</math>. The set of <math>n\times n</math> Toeplitz matrices is a subspace of the vector space of <math>n\times n</math> matrices (under matrix addition and scalar multiplication).
- Two Toeplitz matrices may be added in <math>O(n)</math> time (by storing only one value of each diagonal) and multiplied in <math>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 are asymptotically equivalent to circulant matrices as the dimension grows, a result known as the Grenander–Szegő theorem. 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
::<math>\frac{1}{a_0} A = G G^\operatorname{T} - (G - I)(G - I)^\operatorname{T}</math>
:where <math>G</math> is the lower triangular part of <math>\frac{1}{a_0} A</math>.
- The inverse of a nonsingular symmetric Toeplitz matrix has the representation
::<math>A^{-1} = \frac{1}{\alpha_0} (B B^\operatorname{T} - C C^\operatorname{T})</math>
:where <math>B</math> and <math>C</math> are lower triangular Toeplitz matrices and <math>C</math> 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 <math> h </math> and <math> x </math> can be formulated as:
:<math>
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> 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
A bi-infinite Toeplitz matrix (i.e. entries indexed by <math>\mathbb Z\times\mathbb Z</math>) <math>A</math> induces a linear operator on <math>\ell^2</math>.
:<math>
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>A</math> are the Fourier coefficients of some essentially bounded function <math>f</math>.
In such cases, <math>f</math> is called the symbol of the Toeplitz matrix <math>A</math>, and the spectral norm of the Toeplitz matrix <math>A</math> coincides with the <math>L^\infty</math> 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 <math>a_i=a_{i+n}</math>
- Hankel matrix, an "upside down" (i.e., row-reversed) Toeplitz matrix