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 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 Toeplitz matrix is not necessarily square.

A matrix equation of the form

is called a Toeplitz system if A is a Toeplitz matrix. If A is an ${\displaystyle n\times n}$ Toeplitz matrix, then the system has only 2n−1 degrees of freedom, 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 in Θ(n²) time. Variants of this algorithm have been shown to be weakly stable (i.e. they exhibit numerical stability for well-conditioned linear systems). The algorithm can also be used to find the determinant of a Toeplitz matrix in O(n²) time.

A Toeplitz matrix can also be decomposed (i.e. factored) in O(n²) 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.

...
Wikipedia