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
is 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.
A Toeplitz matrix can also be decomposed (i.e. factored) in
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 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 (under matrix addition and scalar multiplication).
Two Toeplitz matrices may be added in time (by storing only one value of each diagonal) and
multiplied in time.
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
where is the lower triangular part of .
The
inverse of a
nonsingular symmetric Toeplitz matrix has the representation
where and are
lower triangular Toeplitz matrices and 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 and can be formulated as:
A bi-infinite Toeplitz matrix (i.e. entries indexed by ) 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 is easy to establish and can be found as Theorem 1.1 of.[8]
See also
Circulant matrix, a square Toeplitz matrix with the additional property that
Hankel matrix, an "upside down" (i.e., row-reversed) 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
is 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.
A Toeplitz matrix can also be decomposed (i.e. factored) in
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 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 (under matrix addition and scalar multiplication).
Two Toeplitz matrices may be added in time (by storing only one value of each diagonal) and
multiplied in time.
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
where is the lower triangular part of .
The
inverse of a
nonsingular symmetric Toeplitz matrix has the representation
where and are
lower triangular Toeplitz matrices and 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 and can be formulated as:
A bi-infinite Toeplitz matrix (i.e. entries indexed by ) 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 is easy to establish and can be found as Theorem 1.1 of.[8]
See also
Circulant matrix, a square Toeplitz matrix with the additional property that
Hankel matrix, an "upside down" (i.e., row-reversed) Toeplitz matrix