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}

Full article ▸

related documents
Congruence relation
CYK algorithm
Compiler-compiler
Deque
Normal subgroup
Hidden Markov model
Quaternion group
Identity element
Box-Muller transform
List of logarithmic identities
Interior (topology)
Bézout's theorem
Sigma-algebra
Parity (mathematics)
De Moivre's formula
Homeomorphism
Inverse element
Event (probability theory)
Nash embedding theorem
Euphoria (programming language)
PSPACE-complete
Combination
Uncountable set
Coset
Chomsky normal form
Infinite product
Linear congruential generator
Convex hull
Memento pattern
Simple LR parser