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:

[\begin{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 \end{matrix}] .

Any $n \times n$ matrix $A$ of the form

A = [\begin{matrix} a_{0} & a_{- 1} & a_{- 2} & \dots & \dots & 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} & \dots & \dots & a_{2} & a_{1} & a_{0} \end{matrix}]

is a Toeplitz matrix. If the $i, j$ element of $A$ is denoted $A_{i, j}$ then we have

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

is called a Toeplitz system if $A$ is a Toeplitz matrix. If $A$ is an $n \times 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. Using displacement rank we obtain method requiring $\tilde{O} (α^{ω - 1} n)$ ops with the use of fast matrix multiplication algorithms, where $α$ is the rank and $^{\sim} 2.37 \leq ω < 3$ .

Properties

An $n \times n$ Toeplitz matrix may be defined as a matrix $A$ where $A_{i, j} = c_{i - j}$ , for constants $c_{1 - n}, \dots, c_{n - 1}$ . The set of $n \times n$ Toeplitz matrices is a subspace of the vector space of $n \times 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 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

\frac{1}{a_{0}} A = G G^{T} - (G - I) (G - I)^{T}

where

G

is the lower triangular part of

\frac{1}{a_{0}} A

.

The inverse of a nonsingular symmetric Toeplitz matrix has the representation

A^{- 1} = \frac{1}{α_{0}} (B B^{T} - C C^{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 * x = [\begin{matrix} h_{1} & 0 & \dots & 0 & 0 \\ h_{2} & h_{1} & ⋮ & ⋮ \\ h_{3} & h_{2} & \dots & 0 & 0 \\ ⋮ & h_{3} & \dots & 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 & \dots & h_{m - 1} & h_{m - 2} \\ ⋮ & ⋮ & h_{m} & h_{m - 1} \\ 0 & 0 & 0 & \dots & h_{m} \end{matrix}] [\begin{matrix} x_{1} \\ x_{2} \\ x_{3} \\ ⋮ \\ x_{n} \end{matrix}]

y^{T} = [\begin{matrix} h_{1} & h_{2} & h_{3} & \dots & h_{m - 1} & h_{m} \end{matrix}] [\begin{matrix} x_{1} & x_{2} & x_{3} & \dots & x_{n} & 0 & 0 & 0 & \dots & 0 \\ 0 & x_{1} & x_{2} & x_{3} & \dots & x_{n} & 0 & 0 & \dots & 0 \\ 0 & 0 & x_{1} & x_{2} & x_{3} & \dots & x_{n} & 0 & \dots & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & \dots & 0 & 0 & x_{1} & \dots & x_{n - 2} & x_{n - 1} & x_{n} & 0 \\ 0 & \dots & 0 & 0 & 0 & x_{1} & \dots & x_{n - 2} & x_{n - 1} & x_{n} \end{matrix}] .

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 $ℤ \times ℤ$ ) $A$ induces a linear operator on $ℓ^{2}$ .

A = [\begin{matrix} ⋮ & ⋮ & ⋮ & ⋮ \\ \dots & a_{0} & a_{- 1} & a_{- 2} & a_{- 3} & \dots \\ \dots & a_{1} & a_{0} & a_{- 1} & a_{- 2} & \dots \\ \dots & a_{2} & a_{1} & a_{0} & a_{- 1} & \dots \\ \dots & a_{3} & a_{2} & a_{1} & a_{0} & \dots \\ ⋮ & ⋮ & ⋮ & ⋮ \end{matrix}] .

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 can be found as Theorem 1.1 of Böttcher and Grudsky.

Notes

↑ Press et al. 2007, §2.8.2—Toeplitz matrices
↑ Hayes 1996, Chapter 5.2.6
↑ Krishna & Wang 1993
↑ Monahan 2011, §4.5—Toeplitz systems
↑ Brent 1999
↑ Bojanczyk et al. 1995
↑ Bostan, A.; Jeannerod, C.-P.; Schost, É. (2008). "Solving structured linear systems with large displacement rank". Theoretical Computer Science. 407 (1–3): 155–181. doi:10.1016/j.tcs.2008.05.014.
↑ Grenander, Ulf; Szegő, Gábor (1958). Toeplitz Forms and Their Applications. Berkeley, CA: University of California Press.
↑ Mukherjee & Maiti 1988
↑ Böttcher & Grudsky 2012

References

Bojanczyk, A. W.; Brent, R. P.; de Hoog, F. R.; Sweet, D. R. (1995), "On the stability of the Bareiss and related Toeplitz factorization algorithms", SIAM Journal on Matrix Analysis and Applications, 16: 40–57, arXiv:1004.5510, doi:10.1137/S0895479891221563, S2CID 367586
Böttcher, Albrecht; Grudsky, Sergei M. (2012), Toeplitz Matrices, Asymptotic Linear Algebra, and Functional Analysis, Birkhäuser, ISBN 978-3-0348-8395-5
Brent, R. P. (1999), "Stability of fast algorithms for structured linear systems", in Kailath, T.; Sayed, A. H. (eds.), Fast Reliable Algorithms for Matrices with Structure, SIAM, pp. 103–116, arXiv:1005.0671, doi:10.1137/1.9781611971354.ch4, hdl:1885/40746, ISBN 978-0-89871-431-9, S2CID 13905858
Chan, R. H.-F.; Jin, X.-Q. (2007), An Introduction to Iterative Toeplitz Solvers, SIAM, doi:10.1137/1.9780898718850, ISBN 978-0-89871-636-8
Chandrasekeran, S.; Gu, M.; Sun, X.; Xia, J.; Zhu, J. (2007), "A superfast algorithm for Toeplitz systems of linear equations", SIAM Journal on Matrix Analysis and Applications, 29 (4): 1247–66, doi:10.1137/040617200
Chen, W. W.; Hurvich, C. M.; Lu, Y. (2006), "On the correlation matrix of the discrete Fourier transform and the fast solution of large Toeplitz systems for long-memory time series" (PDF), Journal of the American Statistical Association, 101 (474): 812–822, doi:10.1198/016214505000001069, S2CID 55893963
Hayes, Monson H. (1996), Statistical digital signal processing and modeling, Wiley, ISBN 0-471-59431-8
Krishna, H.; Wang, Y. (1993), "The Split Levinson Algorithm is weakly stable", SIAM Journal on Numerical Analysis, 30 (5): 1498–1508, doi:10.1137/0730078
Monahan, J. F. (2011), Numerical Methods of Statistics, Cambridge University Press, doi:10.1017/CBO9780511977176, ISBN 978-1-139-08211-2
Mukherjee, Bishwa Nath; Maiti, Sadhan Samar (1988), "On some properties of positive definite Toeplitz matrices and their possible applications" (PDF), Linear Algebra and Its Applications, 102: 211–240, doi:10.1016/0024-3795(88)90326-6
Press, W. H.; Teukolsky, S. A.; Vetterling, W. T.; Flannery, B. P. (2007), Numerical Recipes: The Art of Scientific Computing (3rd ed.), Cambridge University Press, ISBN 978-0-521-88068-8
Stewart, M. (2003), "A superfast Toeplitz solver with improved numerical stability", SIAM Journal on Matrix Analysis and Applications, 25 (3): 669–693, doi:10.1137/S089547980241791X, S2CID 15717371
Yang, Zai; Xie, Lihua; Stoica, Petre (2016), "Vandermonde decomposition of multilevel Toeplitz matrices with application to multidimensional super-resolution", IEEE Transactions on Information Theory, 62 (6): 3685–3701, arXiv:1505.02510, doi:10.1109/TIT.2016.2553041, S2CID 6291005

v t e Matrix classes
Explicitly constrained entries	Alternant Anti-diagonal Anti-Hermitian Anti-symmetric Arrowhead Band Bidiagonal Bisymmetric Block-diagonal Block Block tridiagonal Boolean Cauchy Centrosymmetric Conference Complex Hadamard Copositive Diagonally dominant Diagonal Discrete Fourier Transform Elementary Equivalent Frobenius Generalized permutation Hadamard Hankel Hermitian Hessenberg Hollow Integer Logical Matrix unit Metzler Moore Nonnegative Pentadiagonal Permutation Persymmetric Polynomial Quaternionic Signature Skew-Hermitian Skew-symmetric Skyline Sparse Sylvester Symmetric Toeplitz Triangular Tridiagonal Vandermonde Walsh Z
Constant	Exchange Hilbert Identity Lehmer Of ones Pascal Pauli Redheffer Shift Zero
Conditions on eigenvalues or eigenvectors	Companion Convergent Defective Definite Diagonalizable Hurwitz-stable Positive-definite Stieltjes
Satisfying conditions on products or inverses	Congruent Idempotent or Projection Invertible Involutory Nilpotent Normal Orthogonal Unimodular Unipotent Unitary Totally unimodular Weighing
With specific applications	Adjugate Alternating sign Augmented Bézout Jabotinsky Cartan Circulant Cofactor Commutation Confusion Coxeter Distance Duplication and elimination Euclidean distance Fundamental (linear differential equation) Generator Gram Hessian Householder Jacobian Moment Payoff Pick Random Rotation Routh-Hurwitz Seifert Shear Similarity Symplectic Totally positive Transformation
Used in statistics	Centering Correlation Covariance Design Doubly stochastic Fisher information Hat Precision Stochastic Transition
Used in graph theory	Adjacency Biadjacency Degree Edmonds Incidence Laplacian Seidel adjacency Tutte
Used in science and engineering	Cabibbo–Kobayashi–Maskawa Density Fundamental (computer vision) Fuzzy associative Gamma Gell-Mann Hamiltonian Irregular Overlap S State transition Substitution Z (chemistry)
Related terms	Jordan normal form Linear independence Matrix exponential Matrix representation of conic sections Perfect matrix Pseudoinverse Row echelon form Wronskian
Mathematics portal List of matrices Category:Matrices (mathematics)

Authority control databases
National	United States Israel
Other	Yale LUX