Matrice De Permutation

Matrice De Permutation

Matrice de permutation

Une matrice de permutation est une matrice carrée qui vérifie les propriétes 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.

Sommaire

Propriétés

Lien avec le groupe symétrique

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σ 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}

Ce qui signifie que 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.

Orthogonalité

Les colonnes de la matrice Pσ sont les vecteurs de la base canonique de \R^n, dont on a modifié l'ordre. En effet si on note e1,...,en ces vecteurs,

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

Ainsi Pσ envoie une base orthonormale sur une base orthonormale : c'est une matrice orthogonale.

La matrice transposée de Pσ 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σ est égale au nombre d'entiers i tels que σ(i)=i, c'est-à-dire au nombre de points fixes de σ.

Utilisations

Application aux opérations élémentaires

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

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

  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Matrice de permutation ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Matrice De Permutation de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Matrice de permutation — Une matrice de permutation est une matrice carrée qui vérifie les propriétes 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 : est une matrice de… …   Wikipédia en Français

  • Matrice elementaire — Matrice élémentaire Une matrice est dite élémentaire lorsqu elle est obtenue par des opérations élémentaires sur les lignes ou colonnes de la matrice identité. Les opérations élémentaires sur une matrice sont les suivantes : échanger deux… …   Wikipédia en Français

  • Matrice Élémentaire — Une matrice est dite élémentaire lorsqu elle est obtenue par des opérations élémentaires sur les lignes ou colonnes de la matrice identité. Les opérations élémentaires sur une matrice sont les suivantes : échanger deux lignes ou deux… …   Wikipédia en Français

  • Matrice positive — Sommaire 1 Matrice positive 1.1 Définitions 1.2 Relation d ordre sur les matrices réelles 2 Matrices carrées positives …   Wikipédia en Français

  • Matrice de rotation — En mathématiques, et plus précisément en algèbre linéaire, une matrice de rotation Q est une matrice orthogonale de déterminant 1, ce qui peut s exprimer par les équations suivantes : QtQ = I = QQt et det Q = 1, où Qt est la matrice… …   Wikipédia en Français

  • Matrice élémentaire — Une matrice est dite élémentaire lorsqu elle est obtenue en appliquant une seule opération élémentaire sur les lignes ou colonnes de la matrice identité[1]. Les opérations élémentaires sur une matrice sont les suivantes[2] : permuter deux… …   Wikipédia en Français

  • Permutation — En mathématiques, la notion de permutation exprime l idée de réarrangement d objets discernables. Une permutation de n objets distincts rangés dans un certain ordre, correspond à un changement de l ordre de succession de ces n objets. La… …   Wikipédia en Français

  • Matrice Inversible — En mathématiques et plus particulièrement en algèbre linéaire, une matrice carrée A d ordre n est dite inversible ou régulière ou encore non singulière, s il existe une matrice B d ordre n telle que AB = BA = In, ( AB = In suffit d aprés le… …   Wikipédia en Français

  • Matrice inverse — Matrice inversible En mathématiques et plus particulièrement en algèbre linéaire, une matrice carrée A d ordre n est dite inversible ou régulière ou encore non singulière, s il existe une matrice B d ordre n telle que AB = BA = In, ( AB = In… …   Wikipédia en Français

  • Matrice non singulière — Matrice inversible En mathématiques et plus particulièrement en algèbre linéaire, une matrice carrée A d ordre n est dite inversible ou régulière ou encore non singulière, s il existe une matrice B d ordre n telle que AB = BA = In, ( AB = In… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”