AlgèbreObjet mathématique · Glossaire
matrice de Toeplitz
Une matrice de Toeplitz est une matrice de m lignes et n colonnes dont les coefficients sont constants le long de chaque diagonale descendante. Formellement, l'élément ne dépend que de la différence j − i : il existe une suite telle que pour tout (i, j). Une matrice de Toeplitz est ainsi entièrement déterminée par ses m + n − 1 valeurs diagonales, ce qui représente une compression importante de l'information. Les matrices de Toeplitz carrées symétriques apparaissent naturellement dans le traitement du signal stationnaire, en particulier dans l'estimation spectrale et dans l'étude des processus stochastiques stationnaires. Le produit matrice-vecteur par une matrice de Toeplitz peut être calculé efficacement en O(n log n) à l'aide de la transformée de Fourier rapide.
Sommaire
Ce que vous allez apprendre
- Reconnaître une matrice de Toeplitz par ses diagonales descendantes.
- La reconstruire à partir de m + n − 1 valeurs.
- Vérifier un produit matrice-vecteur sur un exemple 4 × 4.
- Distinguer la structure de Toeplitz des propriétés diagonale et symétrique.
En clair
Imaginez une grille de nombres. Partez d’une case et descendez d’une ligne tout en avançant d’une colonne : le nombre rencontré reste le même. Cette règle vaut pour chacune des diagonales descendantes, mais deux diagonales peuvent porter des valeurs différentes.
Cette répétition caractérise une matrice de Toeplitz. Il suffit donc de connaître sa première ligne et sa première colonne, avec leur case commune, pour reconstituer toute la grille.
Définition
Une matrice de Toeplitz peut avoir m lignes et n colonnes. Les lignes sont numérotées de 1 à m et les colonnes de 1 à n. Le coefficient situé à la ligne d’indice i et à la colonne d’indice j est noté ai,j. La matrice est de Toeplitz si ce coefficient dépend uniquement de la différence entre les deux indices.
En associant une valeur ck à chaque différence entière k, la condition s’écrit . Deux positions ayant la même différence j − i appartiennent donc à la même diagonale descendante et contiennent la même valeur. Les différences vont de 1 − m à n − 1 : les m + n − 1 valeurs correspondantes déterminent toute la matrice.
Dans le cas carré, une matrice de Toeplitz peut en plus être symétrique. Cette forme apparaît dans le traitement du signal stationnaire, notamment en estimation spectrale et pour les processus stochastiques stationnaires. Pour une matrice carrée de taille n, son produit par un vecteur peut être calculé en O(n log n) avec la transformée de Fourier rapide.
De quoi c'est fait
La première ligne fournit les valeurs c0, c1, …, cn−1. La première colonne fournit c0, c−1, …, c1−m. Leur case commune contient c0, la valeur de la diagonale principale. On compte donc n + m − 1 valeurs indépendantes, et non mn.
Chaque autre case dépend à la fois de sa ligne et de sa colonne par la différence j − i. Dans la matrice de l’exemple conducteur, la diagonale principale contient quatre fois 2 et la diagonale suivante trois fois −1. L’illustration distingue ces deux répétitions en jaune et en rouge. Les sept valeurs de bord suffisent à construire les seize coefficients de cette matrice 4 × 4.
Un exemple, pas à pas
On considère une matrice carrée A de taille 4 et un vecteur x de quatre composantes.
Données diagonales : c0 = 2, c1 = −1, c2 = 0, c3 = 3, c−1 = 4, c−2 = 5 et c−3 = 6.
Vecteur : x = (1, 2, 0, −1).
Données diagonales : c0 = 2, c1 = −1, c2 = 0, c3 = 3, c−1 = 4, c−2 = 5 et c−3 = 6.
Vecteur : x = (1, 2, 0, −1).
1. On place c0 sur la diagonale principale, puis chaque ck sur les cases où j − i = k :
2. La première composante du produit vaut 2 × 1 − 1 × 2 + 0 × 0 + 3 × (−1) = −3.
3. Les trois autres lignes donnent successivement 4 × 1 + 2 × 2 = 8, puis 5 × 1 + 4 × 2 + (−1) × (−1) = 14, et enfin 6 × 1 + 5 × 2 + 2 × (−1) = 14.
4. Le résultat est donc . Pour contrôler la structure avant le calcul, on suit chaque diagonale descendante : 2 se répète quatre fois, −1 trois fois, 4 trois fois, 0 et 5 deux fois, tandis que 3 et 6 apparaissent une fois.
En pratique
Pour stocker une matrice, on vérifie d’abord si chaque diagonale descendante est constante. Si oui, la première ligne et la première colonne suffisent ; sinon, il faut conserver les coefficients séparément.
En traitement d’un signal stationnaire ou dans l’étude d’un processus stochastique stationnaire, on reconnaît la structure en comparant les coefficients situés à décalage égal. Si cette répétition disparaît, le modèle matriciel général reste nécessaire.
Pour multiplier une grande matrice de Toeplitz par un vecteur, la structure répétitive rend possible un calcul en O(n log n) par transformée de Fourier rapide. Sur l’exemple 4 × 4, le calcul ligne par ligne garde l’avantage d’être directement vérifiable.
À ne pas confondre
Matrice diagonale. Ses coefficients hors de la diagonale principale sont nuls. Une matrice de Toeplitz impose plutôt une valeur constante sur chacune des diagonales descendantes. La matrice identité vérifie les deux définitions, mais la matrice de l’exemple, dont plusieurs diagonales non principales sont non nulles, n’est pas diagonale.
Matrice symétrique. Dans une matrice symétrique, échanger ligne et colonne ne change pas le coefficient. Une matrice de Toeplitz n’est pas forcément symétrique : dans l’exemple, a1,2 = −1 alors que a2,1 = 4. Elle devient symétrique lorsque les diagonales placées de part et d’autre de la diagonale principale portent les mêmes valeurs.
Limites et pièges
Une seule ligne ou une seule colonne. Toute matrice de taille 1 × n ou m × 1 satisfait la condition, car chaque diagonale ne contient qu’une case. Le nombre m + n − 1 vaut alors mn : la structure n’apporte aucune compression.
Mauvais sens de lecture. La constance se vérifie en descendant d’une ligne et en avançant d’une colonne. Suivre les diagonales opposées peut faire accepter une matrice qui ne convient pas. Le contrôle fiable consiste à comparer les cases ayant la même différence j − i.
Compression et calcul rapide. Connaître m + n − 1 valeurs suffit à décrire la matrice, mais ne réalise pas automatiquement le produit rapide. Pour une matrice carrée de taille n, la complexité O(n log n) annoncée repose sur l’emploi effectif de la transformée de Fourier rapide.
Pour aller plus loin
Transformée de Fourier — Pour situer l’outil qui accélère le produit entre une matrice de Toeplitz et un vecteur.
signal — Pour approfondir le contexte dans lequel les matrices de Toeplitz carrées symétriques apparaissent naturellement.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres