# Toeplitz matrix

 related topics {math, number, function}

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:

Any n×n matrix A of the form

is a Toeplitz matrix. If the i,j element of A is denoted Ai,j, then we have

## Contents

### Properties

Generally, a matrix equation

is the general problem of n linear simultaneous equations to solve. If A is an $m\times n$ Toeplitz matrix, then the system is rather special (has only m+n-1 degrees of freedom, rather than m n). One could therefore expect that solution of a Toeplitz system would be easier.

This can be investigated by the transformation

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

where empty places in the matrix are zeros.

### Discrete convolution

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:

$\begin{matrix} y & = & h \ast x \\ & = & \begin{bmatrix} h_1 & 0 & \ldots & 0 & 0 \\ h_2 & h_1 & \ldots & \vdots & \vdots \\ h_3 & h_2 & \ldots & 0 & 0 \\ \vdots & h_3 & \ldots & h_1 & 0 \\ h_{m-1} & \vdots & \ldots & h_2 & h_1 \\ h_m & h_{m-1} & \vdots & \vdots & h_2 \\ 0 & h_m & \ldots & h_{m-2} & \vdots \\ 0 & 0 & \ldots & h_{m-1} & h_{m-2} \\ \vdots & \vdots & \vdots & h_m & h_{m-1} \\ 0 & 0 & 0 & \ldots & h_m \\ \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ \vdots \\ x_n \\ \end{bmatrix} \\ y^T & = & \begin{bmatrix} h_1 & h_2 & h_3 & \ldots & h_{m-1} & h_m \\ \end{bmatrix} \begin{bmatrix} x_1 & x_2 & x_3 & \ldots & x_n & 0 & 0 & 0& \ldots & 0 \\ 0 & x_1 & x_2 & x_3 & \ldots & x_n & 0 & 0 & \ldots & 0 \\ 0 & 0 & x_1 & x_2 & x_3 & \ldots & x_n & 0 & \ldots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ldots & \vdots & \vdots & \ldots & 0 \\ 0 & \ldots & 0 & 0 & x_1 & \ldots & x_{n-2} & x_{n-1} & x_{n} & \vdots \\ 0 & \ldots & 0 & 0 & 0 & x_1 & \ldots & x_{n-2} & x_{n-1} & x_{n} \\ \end{bmatrix}. \end{matrix}$