In the mathematical discipline of 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: For other meanings of mathematics or uses of math and maths, see Mathematics (disambiguation) and Math (disambiguation). ... Linear algebra is the branch of mathematics concerned with the study of vectors, vector spaces (also called linear spaces), linear maps (also called linear transformations), and systems of linear equations. ... In mathematics, a matrix (plural matrices) is a rectangular table of elements (or entries), which may be numbers or, more generally, any abstract quantities that can be added and multiplied. ...

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

A_i,j = a_{i − j}.

Properties

Generally, a matrix equation

Ax = b

is the general problem of n linear simultaneous equations to solve. If A is a Toeplitz matrix, then the system is rather special (has only 2n − 1 degrees of freedom, rather than n²). One could therefore expect that solution of a Toeplitz system would be easier. In mathematics and linear algebra, a system of linear equations is a set of linear equations such as 3x1 + 2x2 − x3 = 1 2x1 − 2x2 + 4x3 = −2 −x1 + ½x2 − x3 = 0. ... This article or section is in need of attention from an expert on the subject. ...

This can be investigated by the transformation

AU_n − U_mA,

which has rank 2, where U_k is the down-shift operator. Specifically, one can by simple calculation show that

where empty places in the matrix are replaced by zeros.

Notes

These matrices have uses in computer science because it can be shown that the addition of two Toeplitz matrices can be done in O(n) time, a Toeplitz matrix can be multiplied by a vector in O(n log n) time, and the matrix multiplication of two Toeplitz matrices can be done in O(n²) time. Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... For other uses, see Big O. In computational complexity theory, big O notation is often used to describe how the size of the input data affects an algorithms usage of computational resources (usually running time or memory). ... This article gives an overview of the various ways to perform matrix multiplication. ...

Toeplitz systems of form Ax = b can be solved by the Levinson-Durbin Algorithm in Θ(n²) time. Variants of this algorithm have been shown to be weakly stable in the sense of James Bunch (i.e., they exhibit numerical stability for well-conditioned linear systems). Levinson recursion is a mathematical procedure which recursively calculates the solution to a Toeplitz matrix. ... In the mathematical subfield of numerical analysis, numerical stability is a property of numerical algorithms. ...

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. The Fourier series is a mathematical tool used for analyzing periodic functions by decomposing such a function into a weighted sum of much simpler sinusoidal component functions sometimes referred to as normal Fourier modes, or simply modes for short. ... 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. ... In the mathematical subfield of numerical analysis, a trigonometric polynomial is a finite linear linear combination of sin(nx) and cos(nx) with n a natural number. ... In functional analysis, the compression of a linear operator T on a Hilbert space to a subspace K is the operator PTP where P is the orthogonal projection onto K. This is a natural way to obtain an operator on K from an operator on the whole Hilbert space. ...

If a Toeplitz matrix has the additional property that a_i = a_{i + n}, then it is a circulant matrix. In linear algebra, a circulant matrix is a special kind of Toeplitz matrix where each row vector is shifted one element to the right relative to the preceding row vector. ...

Toeplitz matrices are persymmetric. Symmetric Toeplitz matrices are both centrosymmetric and bisymmetric. In mathematics, persymmetric matrix may refer to: a square matrix such that the values on each line perpendicular to the main diagonal are the same for a given line; or a square matrix which is symmetric in the northeast-to-southwest diagonal. ... In mathematics, especially in linear algebra and matrix theory, a centrosymmetric matrix is a matrix which is symmetric about its center. ... In mathematics, a bisymmetric matrix is a square matrix that is symmetric about both of its main diagonals. ...

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 h and x can be formulated as: In mathematics and, in particular, functional analysis, convolution is a mathematical operator which takes two functions f and g and produces a third function that in a sense represents the amount of overlap between f and a reversed and translated version of g. ...

.

This approach can be extended to compute autocorrelation, cross-correlation, moving average etc. A plot showing 100 random numbers with a hidden sine function, and an autocorrelation of the series on the bottom. ... In statistics, the term cross-correlation is sometimes used to refer to the covariance cov(X, Y) between two random vectors X and Y, in order to distinguish that concept from the covariance of a random vector X, which is understood to be the matrix of covariances between the scalar... The term moving average is used in different contexts. ...

See also

• Circulant matrix

In linear algebra, a circulant matrix is a special kind of Toeplitz matrix where each row vector is shifted one element to the right relative to the preceding row vector. ...

External link

• Toeplitz and Circulant Matrices: A Review, by R. M. Gray