Matrice de Toeplitz

Toute matrice A à n lignes et n colonnes de la forme

${\displaystyle A={\begin{pmatrix}a_{0}&a_{-1}&a_{-2}&\ldots &\ldots &a_{-n+1}\\a_{1}&a_{0}&a_{-1}&\ddots &&\vdots \\a_{2}&a_{1}&\ddots &\ddots &\ddots &\vdots \\\vdots &\ddots &\ddots &\ddots &a_{-1}&a_{-2}\\\vdots &&\ddots &a_{1}&a_{0}&a_{-1}\\a_{n-1}&\ldots &\ldots &a_{2}&a_{1}&a_{0}\end{pmatrix}}}$

est une matrice de Toeplitz. Si l'élément situé à l’intersection des ligne i et colonne j de A est noté A_i,j, alors on a :

${\displaystyle A_{i,j}=A_{i+1,j+1}=a_{i-j}}$.

En général, une équation matricielle

${\displaystyle Ax=b}$

correspond à un système de n équations linéaires à résoudre. Si A est une matrice de Toeplitz, alors le système est particulier : il ne contient que 2n – 1 informations arrangées d'une manière bien particulière, au lieu de n² dans le cas général.

Cette propriété peut être établie en observant la matrice :

${\displaystyle AU_{n}-U_{n}A}$.

Ici ${\displaystyle U_{n}}$ est donnée par

${\displaystyle U_{n}={\begin{pmatrix}0&\cdots &0&1\\1&0&&0\\\vdots &\ddots &\ddots &\vdots \\0&\cdots &1&0\end{pmatrix}}.}$

Si on effectue la multiplication de ${\displaystyle U_{n}}$ par un vecteur v, cela décale tous les coefficients de v d'une ligne vers le bas, et le dernier coefficient monte à la première ligne.

Un calcul simple donne

${\displaystyle D(A)=AU_{n}-U_{n}A={\begin{pmatrix}(a_{-1}-a_{m-1})&\cdots &(a_{-n+1}-a_{1})&0\\0&\cdots &0&(a_{1}-a_{-n+1})\\\vdots &\cdots &\vdots &\vdots \\0&\cdots &0&(a_{m-1}-a_{-1})\end{pmatrix}}}$.

On voit qu'elle est de rang au plus 2. On dira que D(A) est la matrice de déplacement de A.

Si A est inversible et de Toeplitz, son inverse n'est pas de Toeplitz, sauf si A est triangulaire. Néanmoins, l'inverse de A a quand même une propriété intéressante : si on multiplie D(A) par l'inverse de A, on obtient ${\displaystyle -D(A^{-1})}$, qui est donc aussi de rang au plus 2.

Pour cette raison, si A est une matrice telle que ${\displaystyle AU_{n}-U_{n}A}$ soit de rang r, on dira qu'elle est de type Toeplitz, de rang de déplacement r[1]. Un couple ${\displaystyle (G,H)}$ de matrices de taille ${\displaystyle n\times r}$ telles que ${\displaystyle AU_{n}-U_{n}A=G\cdot ^{t}H}$ est appelé générateur de déplacement pour la matrice ${\displaystyle A}$. Il fournit une façon compacte de représenter une matrice de type Toeplitz.

Ces matrices sont très intéressantes du point de vue de la complexité du calcul. Par exemple, le produit d'une matrice de Toeplitz par un vecteur peut s'effectuer aussi rapidement que le produit de deux polynômes de degrés au plus ${\displaystyle n-1}$ et ${\displaystyle 2n-2}$, c'est-à-dire en ${\displaystyle O(n\log n)}$ opérations.

La somme de deux matrices de Toeplitz est de Toeplitz, et peut être effectuée en O(n) opérations. Le produit de deux matrices de Toeplitz n'est pas de Toeplitz, mais il est cependant de type Toeplitz. En représentation par générateurs de déplacement, leur produit peut se calculer en ${\displaystyle O(n\log n)}$ opérations.

Pour la résolution d'un système linéaire dont la matrice est de Toeplitz, intervenant par exemple pour le calcul des coefficients d'un modèle autoregressif pour une série temporelle, l'algorithme de Levinson–Durbin (complexité : ${\displaystyle O(n^{2})}$) est souvent employé. Pour des n grands, la résolution de tels systèmes peut être rendu très rapide – typiquement en ${\displaystyle O(n\log(n)^{2})}$ opérations, au moyen de la conjonction de plusieurs procédés algorithmiques. Ces procédés s'étendent aux matrices de type Toeplitz, et ils sont intéressants pour une matrice de rang de déplacement r petit devant n, car ils fournissent des algorithmes en ${\displaystyle O(nr^{2}\log(n)^{2})}$ opérations, à comparer avec ${\displaystyle O(n^{3})}$ opérations pour une matrice pleine quelconque[2]. 

Cependant, une matrice de Toeplitz peut être fort mal conditionnée, et donc la solution obtenue avec une erreur relative forte si on calcule en nombres flottants, ou avec des fractions gigantesques, si on calcule exactement en rationnels[3].

Ces matrices sont aussi étroitement liées aux séries de Fourier car l'opérateur de multiplication (en) par un polynôme trigonométrique, comprimé (restreint) à un espace de dimension finie, peut être représentée par une telle matrice.

Si une matrice de Toeplitz vérifie de plus ${\displaystyle a_{i}=a_{i+n}}$, alors c'est une matrice circulante.

Les matrices de Toeplitz tridiagonales, telles que ${\displaystyle {\begin{pmatrix}a&b&0&0&0\\c&a&b&0&0\\0&c&a&b&0\\0&0&c&a&b\\0&0&0&c&a\end{pmatrix}},}$ ont pour valeurs propres les nombres ${\displaystyle a+2{\sqrt {bc}}\cos(k\pi /(n+1))}$ pour ${\displaystyle k=1,2,...,n}$, où ${\displaystyle n}$ est l'ordre de la matrice. Par exemple, pour une matrice avec ${\displaystyle n=2}$, les valeurs propres sont ${\displaystyle a\pm {\sqrt {bc}}}$.