Toeplitz matrix - AbsoluteAstronomy.com

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 A_i,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 n². 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 Θ(n²) 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(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.

A Toeplitz matrix can also be decomposed (i.e. factored) in O(n²)

Big O notation

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 A_i,j = c_i−j, for constants c_1−n … c_n−1.

Two Toeplitz matrices may be added in O(n)

Big O notation

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(n²).

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.

Solving a Toeplitz system

General properties

Discrete convolution

See also