AlgèbreObjet mathématique · Glossaire
matrice de permutation
Une matrice de permutation est une matrice carrée d'ordre n à coefficients dans {0, 1} telle que chaque ligne et chaque colonne contiennent exactement un coefficient égal à 1, tous les autres étant nuls. À toute permutation σ de l'ensemble {1, 2, …, n} est associée une matrice de permutation P_σ dont l'élément (i, j) vaut 1 si j = σ(i) et 0 sinon. Cette correspondance est une bijection entre l'ensemble S_n des permutations de {1, …, n} et l'ensemble des matrices de permutation d'ordre n. Le produit de deux matrices de permutation est encore une matrice de permutation ; avec cette convention, P_σP_τ = P_{τ∘σ}, donc le réarrangement σ est suivi du réarrangement τ. Une matrice de permutation est orthogonale : son inverse est égal à sa transposée, ce qui correspond à la permutation inverse. Le produit à droite d'une matrice par P_σ permute les colonnes, tandis que le produit à gauche permute les lignes.
Sommaire
Ce que vous allez apprendre
- Reconnaître une matrice de permutation grâce à l’unique 1 de chaque ligne et de chaque colonne.
- Construire la matrice associée au cycle 1 vers 2, 2 vers 3 et 3 vers 1.
- Contrôler l’inverse par transposition et par multiplication avec la matrice d’origine.
- Choisir le bon côté du produit pour permuter les lignes ou les colonnes.
- Distinguer une matrice de permutation d’une matrice 0-1 ou orthogonale quelconque.
En clair
Trois cartes numérotées 1, 2 et 3 changent de place : la première va en position 2, la deuxième en position 3 et la troisième en position 1. Une matrice de permutation enregistre ce réarrangement dans une grille carrée. Chaque ligne contient un unique 1, placé dans la colonne d’arrivée, et des 0 partout ailleurs. Comme chaque position de départ et chaque position d’arrivée intervient une seule fois, chaque colonne contient elle aussi un unique 1.
Définition
Soit n le nombre d’éléments à réordonner. Une matrice de permutation est une matrice carrée d’ordre n dont tous les coefficients valent 0 ou 1. Elle possède exactement un coefficient 1 sur chaque ligne et exactement un coefficient 1 sur chaque colonne. Ces deux conditions sont nécessaires : elles garantissent que chaque élément a une seule image et que chaque position est atteinte une seule fois.
Notons σ une permutation de l’ensemble {1, 2, …, n}. La matrice associée, notée Pσ, place son 1 de la ligne i dans la colonne σ(i). Autrement dit, son coefficient de ligne i et de colonne j vérifie
Cette règle établit une bijection entre les permutations de l’ensemble et les matrices de permutation d’ordre n.
Le produit de deux matrices de permutation en représente encore une : il traduit la composition des réarrangements. Avec cette convention, l’ordre est précis :
, ce qui signifie que le réarrangement σ est suivi du réarrangement τ. Toute matrice de permutation est orthogonale. Son inverse est sa transposée, selon l’identité
. Multipliée à gauche d’une matrice compatible, elle en permute les lignes ; multipliée à droite, elle en permute les colonnes.
De quoi c'est fait
La structure repose sur cinq éléments. L’ordre n fixe à la fois le nombre de lignes, le nombre de colonnes et le nombre d’éléments permutés. La grille carrée fournit une ligne de départ et une colonne d’arrivée pour chaque indice. Les coefficients sont exclusivement des 0 et des 1. Le 1 d’une ligne indique l’image de l’indice correspondant. L’unique 1 de chaque colonne garantit qu’aucune position d’arrivée n’est oubliée ou utilisée deux fois.
La contrainte sur les lignes ne suffit donc pas sans celle sur les colonnes. Réciproquement, dès lors qu’il y a exactement un 1 par ligne et par colonne, la position de ces n coefficients suffit à reconstruire toute la permutation : à la ligne i, il suffit de lire la colonne σ(i). Les zéros ne décrivent aucun déplacement supplémentaire ; ils excluent toutes les autres associations possibles.
Un exemple, pas à pas
On code le réarrangement cyclique de trois éléments.
Données :
• ensemble de départ : {1, 2, 3} ;
• permutation σ : σ(1) = 2, σ(2) = 3 et σ(3) = 1 ;
• ordre de la matrice : n = 3.
Objectif :
• construire Pσ, puis contrôler qu’elle représente bien une permutation.
Données :
• ensemble de départ : {1, 2, 3} ;
• permutation σ : σ(1) = 2, σ(2) = 3 et σ(3) = 1 ;
• ordre de la matrice : n = 3.
Objectif :
• construire Pσ, puis contrôler qu’elle représente bien une permutation.
1. Sur la ligne 1, placer 1 dans la colonne 2, car σ(1) = 2.
2. Sur la ligne 2, placer 1 dans la colonne 3, car σ(2) = 3.
3. Sur la ligne 3, placer 1 dans la colonne 1, car σ(3) = 1.
4. Compléter les six autres cases avec des 0. On obtient
2. Sur la ligne 2, placer 1 dans la colonne 3, car σ(2) = 3.
3. Sur la ligne 3, placer 1 dans la colonne 1, car σ(3) = 1.
4. Compléter les six autres cases avec des 0. On obtient
.
Chaque ligne et chaque colonne contient bien un seul 1. La transposée replace les 1 aux positions inverses et annule le réarrangement :
. Le résultat est la matrice identité d’ordre 3. Le contrôle peut être refait en vérifiant les trois produits scalaires des lignes avec elles-mêmes, égaux à 1, et les autres, égaux à 0. Une représentation graphique associe chaque image σ(i) à la position du 1 dans la ligne i.
En pratique
Pour déplacer la ligne i d’une matrice A vers la position σ(i), on construit Pσ puis on calcule PσTA. Une réécriture manuelle convient à un cas isolé ; le produit matriciel est préférable lorsque le réarrangement doit rester explicite, composable et réversible.
Pour déplacer la colonne i vers la position σ(i), la même matrice se place de l’autre côté : on calcule APσ. Le côté du produit est donc un critère immédiat : multiplication à gauche pour les lignes, multiplication à droite pour les colonnes.
Pour enchaîner deux réarrangements σ puis τ, on respecte cet ordre dans le produit : avec la convention j = σ(i), on forme PσPτ = Pτ∘σ. Pour les colonnes, ce produit se place à droite ; pour les lignes, sa transposée se place à gauche. L’inverse de l’enchaînement est la transposée du produit obtenu. Une liste d’images suffit pour décrire une permutation seule ; la matrice devient naturelle lorsque le calcul environnant est déjà matriciel.
À ne pas confondre
Une matrice à coefficients 0 ou 1. Cette seule propriété ne suffit pas. La matrice
contient bien seulement des 0 et des 1, mais sa première colonne contient deux 1 et sa seconde aucun : ce n’est pas une matrice de permutation.
Une matrice orthogonale quelconque. Toute matrice de permutation est orthogonale, mais la réciproque est fausse. La matrice d’ordre 1 dont l’unique coefficient vaut −1 est orthogonale ; elle n’est pas une matrice de permutation, car son coefficient n’appartient pas à {0, 1}.
La permutation elle-même. La permutation σ est une règle qui associe un indice d’arrivée à chaque indice de départ. Pσ est son écriture matricielle. Le test qui tranche consiste à regarder l’objet : une liste d’images décrit σ, tandis qu’une grille carrée de 0 et de 1 décrit Pσ.
Limites et pièges
Vérifier les deux directions. Un unique 1 par ligne ne garantit pas un unique 1 par colonne. Si deux lignes pointent vers la même colonne, le tableau ne représente pas une permutation. Il faut compter les 1 ligne par ligne, puis colonne par colonne.
Ne pas inverser le côté du produit. Le symptôme est un réarrangement des colonnes alors que les lignes étaient visées, ou l’inverse. Il faut écrire les dimensions, puis placer Pσ à gauche pour agir sur les lignes et à droite pour agir sur les colonnes.
Ne pas confondre inverse et égalité à la transposée. Toute matrice de permutation vérifie Pσ−1 = PσT, mais elle n’est pas nécessairement égale à sa transposée. Dans l’exemple d’ordre 3, les 1 changent de position après transposition. Pour annuler la permutation, il faut employer PσT, pas supposer que Pσ convient.
Pour aller plus loin
matrice orthogonale — Approfondir la relation entre transposée, inverse et conservation des produits scalaires.
Permutation paire — Étudier une classe particulière de permutations et le rôle de leur parité.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres