Toeplitz matrix

Toeplitz Matrix

A Toeplitz matrix is any $n\times n$ matrix with values constant along each (top-left to lower-right) diagonal. That is, a Toeplitz matrix has the form

$$ \begin{bmatrix} a_0 & a_1 & a_2 & \cdots & a_{n-1} \\ a_{-1} & a_0 & a_1 & \ddots & \vdots \\ a_{-2} & a_{-1} & a_0 & \ddots & a_2 \\ \vdots & \ddots & \ddots & \ddots & a_1 \\ a_{-(n-1)} & \cdots & a_{-2} & a_{-1} & a_0 \end{bmatrix} $$

Numerical problems involving Toeplitz matrices typically have fast solutions (only $2n-1$ distinct elements need to be solved for, as opposed to $n^2$ ). For example, the inverse of a symmetric, positive-definite $n\times n$ Toeplitz matrix can be found in $\mathcal{O}(n^2)$ time.

Bibliography

1

Golub and Van Loan, Matrix Computations, Johns Hopkins University Press 1993