Matrice de permutation

En mathématiques , et plus particulièrement en théorie des matrices , une matrice de permutation est une matrice binaire carrée qui possède exactement une entrée de 1 dans chaque ligne et chaque colonne avec toutes les autres entrées de 0. Une matrice de permutation n × n peut représenter une permutation de n éléments. La pré- multiplication d'une matrice à n lignes M par une matrice de permutation P , formant PM , entraîne la permutation des lignes de M , tandis que la post-multiplication d'une matrice à n colonnes M , formant MP , entraîne la permutation des colonnes de M.

Toute matrice de permutation P est orthogonale , avec son inverse égal à sa transposée : . En effet, les matrices de permutation peuvent être caractérisées comme les matrices orthogonales dont les entrées sont toutes non négatives .

Il existe deux correspondances bijectives naturelles entre les permutations et les matrices de permutation, l'une fonctionnant selon les lignes de la matrice, l'autre selon ses colonnes. Voici un exemple, commençant par une permutation π sous forme de deux lignes en haut à gauche :

La correspondance par ligne prend la permutation π dans la matrice en haut à droite. La première ligne de a son 1 dans la troisième colonne car . Plus généralement, nous avons où quand et sinon.

La correspondance basée sur les colonnes prend π dans la matrice en bas à gauche. La première colonne de a son 1 dans la troisième ligne car . Plus généralement, nous avons où est 1 lorsque et 0 sinon. Puisque les deux recettes ne diffèrent que par l'échange de i avec j , la matrice est la transposée de ; et, puisque est une matrice de permutation, nous avons . En traçant les deux autres côtés du grand carré, nous avons et .

La multiplication d'une matrice M par ou à gauche ou à droite permutera les lignes ou les colonnes de M par π ou π ⁻¹ . Les détails sont un peu délicats.

Pour commencer, lorsque nous permutons les entrées d'un vecteur par une permutation π , nous déplaçons l' entrée du vecteur d'entrée dans l' emplacement du vecteur de sortie. Quelle entrée se retrouve alors, par exemple, dans le premier emplacement de la sortie ? Réponse : L'entrée pour laquelle , et donc . En argumentant de la même manière sur chacun des emplacements, nous constatons que le vecteur de sortie est

même si nous permutons par , et non par . Ainsi, pour permuter les entrées par , nous devons permuter les indices par . (La permutation des entrées par est parfois appelée adopter le point de vue de l'alibi , tandis que la permutation des indices par adopterait le point de vue de l'alias . )

Supposons maintenant que nous prémultiplions une matrice à n lignes par la matrice de permutation . Selon la règle de multiplication de matrices , l' entrée dans le produit est

où est 0 sauf lorsque , lorsqu'il est 1. Ainsi, le seul terme de la somme qui survit est le terme dans lequel , et la somme se réduit à . Puisque nous avons permuté l'indice de ligne par , nous avons permuté les lignes de M elles-mêmes par π . Un argument similaire montre que la post-multiplication d'une matrice à n colonnes M par permute ses colonnes par π .

Les deux autres options sont la pré-multiplication par ou la post-multiplication par , et elles permutent les lignes ou les colonnes respectivement par π ⁻¹ , au lieu de par π .

Un argument connexe prouve que, comme nous l'avons affirmé ci-dessus, la transposée de toute matrice de permutation P agit également comme son inverse, ce qui implique que P est inversible. (Artin laisse cette preuve comme exercice, que nous résolvons ici.) Si , alors l' élément de sa transposée est . L' élément du produit est alors

Lorsque , le terme de cette somme est le produit de deux entrées différentes dans la colonne de P ; donc tous les termes sont 0, et la somme est 0. Lorsque , nous additionnons les carrés des entrées dans la ligne de P , donc la somme est 1. Le produit est donc la matrice identité. Un argument symétrique montre la même chose pour , ce qui implique que P est inversible avec .

Étant donné deux permutations de n éléments 𝜎 et 𝜏, le produit des matrices de permutation basées sur les colonnes correspondantes C _σ et C _τ est donné, comme on pouvait s'y attendre, par où la permutation composée s'applique d'abord 𝜏 puis 𝜎, en travaillant de droite à gauche : Cela s'ensuit que prémultiplier une matrice par C _τ puis prémultiplier le produit résultant par C _σ donne le même résultat que prémultiplier une seule fois par le combiné .

Pour les matrices basées sur les lignes, il y a une variante : le produit de R _σ et R _τ est donné par

avec 𝜎 appliqué avant 𝜏 dans la permutation composée. Cela se produit parce que nous devons post-multiplier pour éviter les inversions sous l'option basée sur les lignes, nous post-multiplierions donc d'abord par R _σ puis par R _τ .

Certaines personnes, lorsqu'elles appliquent une fonction à un argument, écrivent la fonction après l'argument ( notation postfixée ), plutôt qu'avant. Lorsqu'elles font de l'algèbre linéaire, elles travaillent avec des espaces linéaires de vecteurs de lignes et elles appliquent une application linéaire à un argument en utilisant la matrice de l'application pour post-multiplier le vecteur de lignes de l'argument. Elles utilisent souvent un opérateur de composition de gauche à droite, que nous désignons ici par un point-virgule ; la composition est donc définie soit par

ou, plus élégamment, par

avec 𝜎 appliqué en premier. Cette notation nous donne une règle plus simple pour multiplier les matrices de permutation basées sur les lignes :

Lorsque π est la permutation d'identité, qui a pour tout i , C _π et R _π sont tous deux la matrice identité .

Il y a n ! matrices de permutation, puisqu'il y a n ! permutations et que la carte est une correspondance bijective entre les permutations et les matrices de permutation. (La carte est une autre correspondance de ce type.) Par les formules ci-dessus, ces matrices de permutation n × n forment un groupe d'ordre n ! sous multiplication matricielle, avec la matrice identité comme élément identité , un groupe que nous désignons . Le groupe est un sous-groupe du groupe linéaire général des matrices n × n inversibles de nombres réels. En effet, pour tout corps F , le groupe est aussi un sous-groupe du groupe , où les entrées de la matrice appartiennent à F . (Chaque corps contient 0 et 1 avec et et c'est tout ce dont nous avons besoin pour multiplier les matrices de permutation. Différents corps ne sont pas d'accord sur le fait que , mais cette somme n'apparaît pas.)

Soit le groupe symétrique , ou groupe de permutations , sur {1,2,..., n } où l'opération de groupe est la composition standard de droite à gauche " "; et soit le groupe opposé , qui utilise la composition de gauche à droite " ". L'application qui prend π pour sa matrice à base de colonnes est une représentation fidèle , et de même pour l'application qui prend π pour .

Chaque matrice de permutation est doublement stochastique . L'ensemble de toutes les matrices doublement stochastiques est appelé le polytope de Birkhoff , et les matrices de permutation jouent un rôle particulier dans ce polytope. Le théorème de Birkhoff–von Neumann dit que chaque matrice réelle doublement stochastique est une combinaison convexe de matrices de permutation du même ordre, les matrices de permutation étant précisément les points extrêmes (les sommets) du polytope de Birkhoff. Le polytope de Birkhoff est donc l' enveloppe convexe des matrices de permutation.

De même que chaque permutation est associée à deux matrices de permutation, chaque matrice de permutation est associée à deux permutations, comme on peut le voir en renommant l'exemple dans le grand carré ci-dessus en commençant par la matrice P en haut à droite :

Nous désignons donc ici l'inverse de C par et l'inverse de R par . Nous pouvons alors calculer les propriétés linéaires-algébriques de P à partir de certaines propriétés combinatoires partagées par les deux permutations et .

Un point est fixé par juste quand il est fixé par , et la trace de P est le nombre de ces points fixes partagés. Si l'entier k est l'un d'eux, alors le vecteur de base standard e _k est un vecteur propre de P .

Pour calculer les valeurs propres complexes de P , écrivez la permutation comme une composition de cycles disjoints , disons . (Les permutations de sous-ensembles disjoints commutent, donc il n'importe pas ici que nous composions de droite à gauche ou de gauche à droite.) Pour , soit la longueur du cycle , et soit l'ensemble des solutions complexes de , ces solutions étant les racines de l'unité . L' union multi-ensemble des est alors le multi-ensemble des valeurs propres de P . Puisque l'écriture comme un produit de cycles donnerait le même nombre de cycles de mêmes longueurs, l'analyse donnerait le même résultat. La multiplicité de toute valeur propre v est le nombre de i pour lequel contient v . (Puisque toute matrice de permutation est normale et que toute matrice normale est diagonalisable sur les nombres complexes, les multiplicités algébrique et géométrique d'une valeur propre v sont les mêmes.)

La théorie des groupes nous apprend que toute permutation peut être écrite comme une composition de transpositions . Par conséquent, toute matrice de permutation se factorise comme un produit de matrices élémentaires à commutation de lignes , dont chacune a pour déterminant −1. Ainsi, le déterminant de la matrice de permutation P est le signe de la permutation , qui est également le signe de .

• Tableau de Costas , une matrice de permutation dans laquelle les vecteurs de déplacement entre les entrées sont tous distincts
• Puzzle à n reines , une matrice de permutation dans laquelle il y a au plus une entrée dans chaque diagonale et antidiagonale