Matrice de permutation

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Une matrice de permutation est une matrice carrée qui vérifie les propriétés suivantes :

  • les coefficients sont 0 ou 1 ;
  • il y a un et un seul 1 par ligne ;
  • il y a un et un seul 1 par colonne.

Ainsi : \begin{pmatrix}
1 & 0 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1\\
0 & 1 & 0 & 0\end{pmatrix} est une matrice de permutation.

Propriétés[modifier | modifier le code]

Lien avec le groupe symétrique[modifier | modifier le code]

Les matrices de permutations carrées de taille n sont en bijection avec les permutations de l'ensemble {1,2,...n}. Si σ est une telle permutation, la matrice correspondante est P_\sigma de terme général

\left[P_\sigma\right]_{ij}=\delta_{i,\sigma(j)}=\begin{cases} 1 & \hbox {si } i=\sigma(j)\\
0&\hbox{sinon}\end{cases}

Cette bijection est un morphisme de groupes

P_\sigma.P_\tau = P_{\sigma\circ \tau}

En utilisant cette identité avec deux permutations inverses l'une de l'autre, on obtient le fait qu'une matrice de transposition est inversible, et que son inverse est la matrice de la transposition inverse. L'ensemble des matrices de permutation forme un sous-groupe du groupe général linéaire d'indice n, isomorphe au groupe symétrique {\mathfrak S}_n.

Notons que l'usage anglo-saxon conduit à définir les matrices de permutations différemment (en prenant l'inverse de la permutation). (voir la version anglaise)

Orthogonalité[modifier | modifier le code]

Les colonnes de la matrice P_\sigma sont les vecteurs de la base canonique de \R^n, dont on a modifié l'ordre. En effet si on note e_1, ..., e_n ces vecteurs,

P_\sigma(e_j)=e_{\sigma(j)}\,

Ainsi P_\sigma envoie une base orthonormale sur une base orthonormale : c'est une matrice orthogonale.

La matrice transposée de P_\sigma est également son inverse, et vaut P_{\sigma^{-1}}.

Le déterminant de la matrice est +1 si et seulement si les vecteurs images de la base canonique forment une base directe, c'est-à-dire si et seulement si σ est une permutation paire. Dans le cas contraire, le déterminant est -1.

La trace de P_\sigma est égale au nombre d'entiers i tels que σ(i)=i, c'est-à-dire au nombre de points fixes de \sigma.

Utilisations[modifier | modifier le code]

Application aux opérations élémentaires[modifier | modifier le code]

Article détaillé : Opération élémentaire.

De même que toute permutation est produit de transpositions, toute matrice de permutation est un produit de matrices de permutation élémentaires c'est-à-dire associées aux transpositions. Il est aisé de voir que multiplier à gauche (respectivement à droite) une matrice A par une telle matrice de permutation élémentaire revient à faire l'échange de deux lignes (resp. deux colonnes) de A.

Plus généralement, multiplier une matrice A à droite par une matrice de permutation P revient à permuter les colonnes de la matrice A, en suivant la permutation correspondant à P. Multiplier une matrice A à gauche par une matrice de permutation P revient à permuter les lignes de la matrice A, en suivant la permutation inverse.

Application aux matrices stochastiques[modifier | modifier le code]

Article détaillé : Matrice stochastique.

Les matrices de permutation sont des cas particuliers de matrices doublement stochastiques. Plus précisément, on peut montrer que l'ensemble des matrices stochastiques est une partie convexe, dont les matrices de permutation forment les points extrémaux.

Notamment, toute matrice doublement stochastique est barycentre à coefficients positifs de matrices de permutation.

Voir aussi[modifier | modifier le code]