Toeplitz Matrix

Given $2n-1$ numbers $a_k$ where $k=-n+1$, ..., $-1$, 0, 1, ..., $n-1$, a Toeplitz matrix is Matrix which has constant values along negative-sloping diagonals, i.e., a matrix of the form

$$\left[{\matrix{ a_0 & a_{-1} & a_{-2} & \cdots & a_{-n+1}\c... ...s & a_{-1}\cr a_{n-1} & \cdots & a_2 & a_1 & a_0\cr}}\right].$$

Matrix equations of the form

$$\sum_{j=1}^n a_{i-j}x_j=y_i$$

can be solved with ${\mathcal O}(n^2)$ operations.

See also Vandermonde Matrix