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:
Any matrix of the form
is a Toeplitz matrix. If the element of is denoted then we have
A Toeplitz matrix is not necessarily square.
Solving a Toeplitz system
A matrix equation of the formis called a Toeplitz system if is a Toeplitz matrix. If is an Toeplitz matrix, then the system has at most only
unique values, rather than. 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 Big O notation#Family of Bachmann–Landau notations| time. Variants of the latter have been shown to be weakly stable. The algorithms can also be used to find the determinant of a Toeplitz matrix in Big O notation| time.
A Toeplitz matrix can also be decomposed in 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 ops with the use of fast matrix multiplication algorithms, where is just the rank and.
Properties
- An Toeplitz matrix may be defined as a matrix where, for constants. The set of Toeplitz matrices is a subspace of the vector space of matrices.
- Two Toeplitz matrices may be added in time and multiplied in 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
- The inverse of a nonsingular symmetric Toeplitz matrix has the representation
Discrete convolution
This approach can be extended to compute autocorrelation, cross-correlation, moving average etc.
Infinite Toeplitz matrix
A bi-infinite Toeplitz matrix induces a linear operator on.The induced operator is bounded if and only if the coefficients of the Toeplitz matrix are the Fourier coefficients of some essentially bounded function.
In such cases, is called the symbol of the Toeplitz matrix, and the spectral norm of the Toeplitz matrix coincides with the norm of its symbol. The proof can be found as Theorem 1.1 of Böttcher and Grudsky.