Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Matrice de Toeplitz
Résumé
En algèbre linéaire, une matrice de Toeplitz (d'après Otto Toeplitz) ou matrice à diagonales constantes est une matrice dont les coefficients sur une diagonale descendant de gauche à droite sont les mêmes. Par exemple, la matrice suivante est une matrice de Toeplitz :
Toute matrice A à n lignes et n colonnes de la forme
est une matrice de Toeplitz. Si l'élément situé à l’intersection des ligne i et colonne j de A est noté Ai,j, alors on a :
En général, une équation matricielle
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 :
Ici est donnée par
Si on effectue la multiplication de 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
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 , qui est donc aussi de rang au plus 2.
Pour cette raison, si A est une matrice telle que soit de rang r, on dira qu'elle est de type Toeplitz, de rang de déplacement r. Un couple de matrices de taille telles que est appelé générateur de déplacement pour la matrice . 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 et , c'est-à-dire en opérations.
La somme de deux matrices de Toeplitz est de Toeplitz, et peut être effectuée en O(n) opérations.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.