Toeplitz-matrix

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Een Toeplitz-matrix, genoemd naar Otto Toeplitz, is een matrix met constante waarden op de hoofddiagonaal en de hiermee evenwijdige diagonalen. Dit betekent dat het element t_{i,j} op rij i en kolom k gelijk is aan het element er rechtsonder, en in het algemeen aan element t_{i+k,j+k} voor alle positieve waarden van k.

Voorbeeld van een Toeplitz-matrix:


\begin{bmatrix}
a & b & c & d & e \\
f & a & b & c & d \\
g & f & a & b & c \\
h & g & f & a & b \\
i & h & g & f & a 
\end{bmatrix}.

Een Toeplitz-matrix is volledig bepaald door de eerste rij en de eerste kolom.

Verband met veeltermen[bewerken]

De coëfficiënten van een veeltermvermenigvuldiging van

a = a_1 + a_2x + \ldots + a_mx^{m-1}

en

b = b_1 + b_2x + \ldots + b_nx^{n-1}

zijn de elementen van de vector die het product is van de matrixvermenigvuldiging van een Toeplitz-matrix met de vector gevormd door de coëfficiënten van veelterm b:

c=a\cdot b=
    \begin{matrix}
            \begin{bmatrix}
                a_1 & 0 & \ldots & 0 & 0 \\
                a_2 & a_1 & \ldots & \vdots & \vdots \\
                a_3 & a_2 & \ldots & 0 & 0 \\
                \vdots & a_3 & \ldots & a_1 & 0 \\
                a_{m-1} & \vdots & \ldots & a_2 & a_1 \\
                a_m & a_{m-1} & \vdots & \vdots & a_2 \\
                0 & a_m & \ldots & a_{m-2} & \vdots \\
                0 & 0 & \ldots & a_{m-1} & a_{m-2} \\
                \vdots & \vdots & \vdots & a_m & a_{m-1} \\
                0 & 0 & 0 & \ldots & a_m \\
            \end{bmatrix}.
            \begin{bmatrix}
                b_1 \\
                b_2 \\
                b_3 \\
                \vdots \\
                b_n \\
            \end{bmatrix} \\
    \end{matrix}

Dit is equivalent aan het berekenen van de convolutie van twee rijen getallen. De Toeplitz-matrix is hier een bandmatrix: enkel de elementen op de hoofddiagonaal en een aantal diagonalen daarboven of daaronder zijn niet-nul. Rechtsboven en linksonder die diagonalen bestaat de matrix enkel uit nullen.

Voor deze en andere bewerkingen met Toeplitz-matrices bestaan efficiënte algoritmes. Dit is bijvoorbeeld zo voor het oplossen van een stelsel van lineaire vergelijkingen (in matrixvorm)

A\bold{x}=\bold{b}

wanneer A een Toeplitz-matrix is. Dergelijke stelsels duiken o.a. op in de digitale signaalverwerking (spraakherkenning en dergelijke).

Cyclische matrix[bewerken]

Een speciaal geval van een Toeplitz-matrix is een cyclische matrix. Dit is een matrix waarvan elke rij gelijk is aan de rij erboven maar dan één element naar rechts geroteerd:


\begin{bmatrix}
c_0     & c_{n-1} & \dots  & c_{2} & c_{1}  \\
c_{1} & c_0    & c_{n-1} &         & c_{2}  \\
\vdots  & c_{1}& c_0    & \ddots  & \vdots   \\
c_{n-2}  &        & \ddots & \ddots  & c_{n-1}   \\
c_{n-1}  & c_{n-2} & \dots  & c_{1} & c_0 \\
\end{bmatrix}.

Zo'n cyclische matrix is volledig bepaald door de eerste kolom (of rij); elke volgende kolom is een cyclische permutatie van de vorige kolom (of rij). Cyclische matrices komen bijvoorbeeld van pas bij de toepassing van discrete fouriertransformatie (DFT) op een rij getallen: de eigenwaarden van de cyclische matrix met die rij getallen als eerste rij vormen de DFT van die rij. Anders gezegd: de eerste rij van een cyclische matrix is de inverse DFT van de eigenwaarden van die matrix[1].

Zie ook[bewerken]

  • Hankel-matrix, waarin elk element gelijk is aan het element er rechtsboven in plaats van rechtsonder.

Voetnoten[bewerken]

  1. Robert M. Gray: "Toeplitz and circular matrices: a review."