# Toeplitz matrix

Last updated

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:

## Contents

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

A Toeplitz matrix can also be decomposed (i.e. factored) in ${\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.

## General properties

• An ${\displaystyle n\times n}$ Toeplitz matrix may be defined as a matrix ${\displaystyle A}$ where ${\displaystyle A_{i,j}=c_{i-j}}$, for constants ${\displaystyle c_{1-n},\ldots ,c_{n-1}}$. The set of ${\displaystyle n\times n}$ Toeplitz matrices is a subspace of the vector space of ${\displaystyle n\times n}$ matrices (under matrix addition and scalar multiplication).
• Two Toeplitz matrices may be added in ${\displaystyle O(n)}$ time (by storing only one value of each diagonal) and multiplied in ${\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 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
${\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. [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 ${\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 of: [8]

## Notes

1. Hayes 1996 , Chapter 5.2.6
2. Monahan 2011 , §4.5Toeplitz systems

## Related Research Articles

In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. The determinant of a matrix A is commonly denoted det(A), det A, or |A|. Its value characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if and only if the matrix is invertible and the linear map represented by the matrix is an isomorphism. The determinant of a product of matrices is the product of their determinants (which follows directly from the above properties).

In mathematics, matrix addition is the operation of adding two matrices by adding the corresponding entries together.

In mathematics, particularly in linear algebra, matrix multiplication is a binary operation that produces a matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the number of rows in the second matrix. The resulting matrix, known as the matrix product, has the number of rows of the first and the number of columns of the second matrix. The product of matrices A and B is denoted as AB.

In linear algebra, an n-by-n square matrix A is called invertible, if there exists an n-by-n square matrix B such that

Levinson recursion or Levinson–Durbin recursion is a procedure in linear algebra to recursively calculate the solution to an equation involving a Toeplitz matrix. The algorithm runs in Θ(n2) time, which is a strong improvement over Gauss–Jordan elimination, which runs in Θ(n3).

In linear algebra, a Hankel matrix, named after Hermann Hankel, is a square matrix in which each ascending skew-diagonal from left to right is constant, e.g.:

In mathematics, a block matrix or a partitioned matrix is a matrix that is interpreted as having been broken into sections called blocks or submatrices. Intuitively, a matrix interpreted as a block matrix can be visualized as the original matrix with a collection of horizontal and vertical lines, which break it up, or partition it, into a collection of smaller matrices. Any matrix may be interpreted as a block matrix in one or more ways, with each interpretation defined by how its rows and columns are partitioned.

In linear algebra, a tridiagonal matrix is a band matrix that has nonzero elements only on the main diagonal, the subdiagonal/lower diagonal, and the supradiagonal/upper diagonal. For example, the following matrix is tridiagonal:

In numerical linear algebra, a Givens rotation is a rotation in the plane spanned by two coordinates axes. Givens rotations are named after Wallace Givens, who introduced them to numerical analysts in the 1950s while he was working at Argonne National Laboratory.

In mathematics, the Kronecker product, sometimes denoted by ⊗, is an operation on two matrices of arbitrary size resulting in a block matrix. It is a specialization of the tensor product from vectors to matrices and gives the matrix of the tensor product linear map with respect to a standard choice of basis. The Kronecker product is to be distinguished from the usual matrix multiplication, which is an entirely different operation. The Kronecker product is also sometimes called matrix direct product.

In linear algebra, a circulant matrix is a square matrix in which all row vectors are composed of the same elements and each row vector is rotated one element to the right relative to the preceding row vector. It is a particular kind of Toeplitz matrix.

In numerical linear algebra, the Arnoldi iteration is an eigenvalue algorithm and an important example of an iterative method. Arnoldi finds an approximation to the eigenvalues and eigenvectors of general matrices by constructing an orthonormal basis of the Krylov subspace, which makes it particularly useful when dealing with large sparse matrices.

In linear algebra, a nilpotent matrix is a square matrix N such that

In mathematics, particularly matrix theory, a band matrix or banded matrix is a sparse matrix whose non-zero entries are confined to a diagonal band, comprising the main diagonal and zero or more diagonals on either side.

In mathematics, matrix calculus is a specialized notation for doing multivariable calculus, especially over spaces of matrices. It collects the various partial derivatives of a single function with respect to many variables, and/or of a multivariate function with respect to a single variable, into vectors and matrices that can be treated as single entities. This greatly simplifies operations such as finding the maximum or minimum of a multivariate function and solving systems of differential equations. The notation used here is commonly used in statistics and engineering, while the tensor index notation is preferred in physics.

In mathematics, a logarithm of a matrix is another matrix such that the matrix exponential of the latter matrix equals the original matrix. It is thus a generalization of the scalar logarithm and in some sense an inverse function of the matrix exponential. Not all matrices have a logarithm and those matrices that do have a logarithm may have more than one logarithm. The study of logarithms of matrices leads to Lie theory since when a matrix has a logarithm then it is in an element of a Lie group and the logarithm is the corresponding element of the vector space of the Lie algebra.

In numerical analysis and linear algebra, lower–upper (LU) decomposition or factorization factors a matrix as the product of a lower triangular matrix and an upper triangular matrix. The product sometimes includes a permutation matrix as well. LU decomposition can be viewed as the matrix form of Gaussian elimination. Computers usually solve square systems of linear equations using LU decomposition, and it is also a key step when inverting a matrix or computing the determinant of a matrix. The LU decomposition was introduced by the Polish astronomer Tadeusz Banachiewicz in 1938. To quote: "It appears that Gauss and Doolittle applied the method [of elimination] only to symmetric equations. More recent authors, for example, Aitken, Banachiewicz, Dwyer, and Crout … have emphasized the use of the method, or variations of it, in connection with non-symmetric problems … Banachiewicz … saw the point … that the basic problem is really one of matrix factorization, or “decomposition” as he called it." It's also referred to as LR decomposition.

In mathematics, every analytic function can be used for defining a matrix function that maps square matrices with complex entries to square matrices of the same size.

In mathematics, a matrix is a rectangular array or table of numbers, symbols, or expressions, arranged in rows and columns, which is used to represent a mathematical object or a property of such an object.

In mathematics, a Bunce–Deddens algebra, named after John W. Bunce and James A. Deddens, is a certain type of AT algebra, a direct limit of matrix algebras over the continuous functions on the circle, in which the connecting maps are given by embeddings between families of shift operators with periodic weights.