Toeplitz matrix

1 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 (http://planetmath.org/TimeComplexity).

References

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