Toeplitz matrix
Encyclopedia
In linear algebra
Linear algebra
Linear algebra is a branch of mathematics that studies vector spaces, also called linear spaces, along with linear functions that input one vector and output another. Such functions are called linear maps and can be represented by matrices if a basis is given. Thus matrix theory is often...

, a Toeplitz matrix or diagonal-constant matrix, named after Otto Toeplitz
Otto Toeplitz
Otto Toeplitz was a German Jewish mathematician working in functional analysis.- Life and work :...

, is a matrix
Matrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...

 in which each descending diagonal from left to right is constant. For instance, the following matrix is a Toeplitz matrix:


Any n×n matrix A of the form


is a Toeplitz matrix. If the i,j element of A is denoted Ai,j, then we have

Solving a Toeplitz system

A matrix equation of the form


is called a Toeplitz system if A is a Toeplitz matrix. If A is an Toeplitz matrix, then the system has only 2n−1 degrees of freedom
Degrees of freedom (statistics)
In statistics, the number of degrees of freedom is the number of values in the final calculation of a statistic that are free to vary.Estimates of statistical parameters can be based upon different amounts of information or data. The number of independent pieces of information that go into the...

, rather than n2. 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 the Levinson algorithm
Levinson recursion
Levinson recursion or Levinson-Durbin recursion is a procedure in linear algebra to recursively calculate the solution to an equation involving a Toeplitz matrix...

 in Θ(n2) time. Variants of this algorithm have been shown to be weakly stable (i.e. they exhibit numerical stability
Numerical stability
In the mathematical subfield of numerical analysis, numerical stability is a desirable property of numerical algorithms. The precise definition of stability depends on the context, but it is related to the accuracy of the algorithm....

 for well-conditioned
Condition number
In the field of numerical analysis, the condition number of a function with respect to an argument measures the asymptotically worst case of how much the function can change in proportion to small changes in the argument...

 linear systems). The algorithm can also be used to find the determinant
Determinant
In linear algebra, the determinant is a value associated with a square matrix. It can be computed from the entries of the matrix by a specific arithmetic expression, while other ways to determine its value exist as well...

 of a Toeplitz matrix in O(n2)
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...

 time.

A Toeplitz matrix can also be decomposed (i.e. factored) in O(n2)
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...

 time. The Bareiss algorithm for an LU decomposition
LU decomposition
In linear algebra, LU decomposition is a matrix decomposition which writes a matrix as the product of a lower triangular matrix and an upper triangular matrix. The product sometimes includes a permutation matrix as well. This decomposition is used in numerical analysis to solve systems of linear...

 is stable. An LU decomposition gives a quick method for solving a Toeplitz system, and also for computing the determinant.

Algorithms that are asymptotically faster than those of Bareiss and Levinson have been described in the literature.

General properties

A Toeplitz matrix may be defined as a matrix A where Ai,j = ci−j, for constants c1−ncn−1.

Two Toeplitz matrices may be added in O(n)
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...

 time and multiplied
Matrix multiplication
In mathematics, matrix multiplication is a binary operation that takes a pair of matrices, and produces another matrix. If A is an n-by-m matrix and B is an m-by-p matrix, the result AB of their multiplication is an n-by-p matrix defined only if the number of columns m of the left matrix A is the...

 in O(n2).

Toeplitz matrices are persymmetric
Persymmetric matrix
In mathematics, persymmetric matrix may refer to:# a square matrix which is symmetric in the northeast-to-southwest diagonal; or# a square matrix such that the values on each line perpendicular to the main diagonal are the same for a given line....

. Symmetric Toeplitz matrices are both centrosymmetric
Centrosymmetric matrix
In mathematics, especially in linear algebra and matrix theory, a centrosymmetric matrix is a matrix which is symmetric about its center. More precisely, an n × n matrix A = [ Ai,j ] is centrosymmetric when its entries satisfy...

 and bisymmetric.

Toeplitz matrices are also closely connected with Fourier series
Fourier series
In mathematics, a Fourier series decomposes periodic functions or periodic signals into the sum of a set of simple oscillating functions, namely sines and cosines...

, because the multiplication operator
Multiplication operator
In operator theory, a multiplication operator is a linear operator T defined on some vector space of functions and whose value at a function φ is given by multiplication by a fixed function f...

 by a trigonometric polynomial
Trigonometric polynomial
In the mathematical subfields of numerical analysis and mathematical analysis, a trigonometric polynomial is a finite linear combination of functions sin and cos with n a natural number. The coefficients may be taken as real numbers, for real-valued functions...

, compressed
Compression (functional analysis)
In functional analysis, the compression of a linear operator T on a Hilbert space to a subspace K is the operatorP_K T \vert_K : K \rightarrow K...

 to a finite-dimensional space, can be represented by such a matrix.

All Toeplitz matrices commute
Commutator
In mathematics, the commutator gives an indication of the extent to which a certain binary operation fails to be commutative. There are different definitions used in group theory and ring theory.-Group theory:...

 asymptotically
Asymptotic analysis
In mathematical analysis, asymptotic analysis is a method of describing limiting behavior. The methodology has applications across science. Examples are...

. This means they diagonalize
Diagonalizable matrix
In linear algebra, a square matrix A is called diagonalizable if it is similar to a diagonal matrix, i.e., if there exists an invertible matrix P such that P −1AP is a diagonal matrix...

 in the same basis
Basis (linear algebra)
In linear algebra, a basis is a set of linearly independent vectors that, in a linear combination, can represent every vector in a given vector space or free module, or, more simply put, which define a "coordinate system"...

 when the row and column dimension tends to infinity.

Discrete convolution

The convolution
Convolution
In mathematics and, in particular, functional analysis, convolution is a mathematical operation on two functions f and g, producing a third function that is typically viewed as a modified version of one of the original functions. Convolution is similar to cross-correlation...

 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:



This approach can be extended to compute autocorrelation
Autocorrelation
Autocorrelation is the cross-correlation of a signal with itself. Informally, it is the similarity between observations as a function of the time separation between them...

, cross-correlation
Cross-correlation
In signal processing, cross-correlation is a measure of similarity of two waveforms as a function of a time-lag applied to one of them. This is also known as a sliding dot product or sliding inner-product. It is commonly used for searching a long-duration signal for a shorter, known feature...

, moving average etc.

See also

  • Circulant matrix
    Circulant matrix
    In linear algebra, a circulant matrix is a special kind of Toeplitz matrix where each row vector is rotated one element to the right relative to the preceding row vector. In numerical analysis, circulant matrices are important because they are diagonalized by a discrete Fourier transform, and hence...

    , a Toeplitz matrix with the additional property that .
  • Hankel matrix, a Toeplitz matrix "upside down".
  • Toeplitz operator
    Toeplitz operator
    In operator theory, a Toeplitz operator is the compression of a multiplication operator on the circle to the Hardy space.- Details :Let S1 be the circle, with the standard Lebesgue measure, and L2 be the Hilbert space of square-integrable functions. A bounded measurable function g on S1 defines a...

    , a Toeplitz matrix with infinitely many rows and columns.
The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK