Aujourd’hui, nous allons étudier un thème fondamental de l’algèbre linéaire : les matrices de permutation. Bien que cette notion soit officiellement hors programme, elle possède de nombreuses propriétés intéressantes en lien avec plusieurs thèmes du programme, comme le dénombrement. Leur simplicité apparente cache cependant des propriétés remarquables et des applications pratiques qui en font des outils indispensables dans des domaines tels que la cryptographie. Dans cet article, je te présente l’intérêt de cette notion et plusieurs de ses propriétés qui te seront utiles lors de ta préparation aux écrits et aux oraux !
La notion expliquée en français
Une matrice de permutation est une représentation structurée des arrangements possibles d’éléments dans un ensemble fini. Chaque matrice de permutation indique comment des éléments doivent être déplacés pour obtenir une nouvelle disposition.
Ces matrices ont plusieurs propriétés qui les définissent : elles sont carrées, elles sont composées de 0 et de 1, il n’y a qu’un seul 1 par ligne et par colonne.
Les matrices de permutation
Une matrice carrée, \( P_{\sigma} \), est une matrice de permutation si et seulement si :
- les coefficients de \( P_{\sigma} \) sont 0 ou 1
- il y a un et un seul 1 par ligne de \( P_{\sigma} \)
- il y a un et un seul 1 par colonne de \( P_{\sigma} \)
De plus, une matrice de permutation, \( P_{\sigma} \), de \( \mathcal{M}_{n}(\mathbb{R})\) peut être associée à une permutation \( \sigma \) (c’est-à-dire une bijection de \( [\![1,n]\!] \) vers \( [\![1,n]\!] \)). En effet, la matrice correspondante à \( \sigma \) est \( P_{\sigma} \) de terme général : \( (P_{\sigma})_{(i,j)} =
\begin{cases}
1 &\text{si} \; i = \sigma(j)\\
0 &\text{sinon}
\end{cases}
\)
Exemple
La matrice \( A =\begin{pmatrix}
1 & 0 & 0 \\
0 & 0 & 1 \\
0 & 1 & 0
\end{pmatrix} \) est une matrice de permutation de \( \mathcal{M}_{3}(\mathbb{R})\).
De plus, la permutation associée à \(A\) est \( \sigma : i \in [\![1,3]\!] \to \begin{cases}
1 &\text{si} \; i = 1\\
3 &\text{si} \; i = 2 \\
2 &\text{si} \; i = 3
\end{cases}
\)
Les liens entre permutations et matrices de permutation
Nous pouvons compléter ce lien en affirmant que les matrices de permutation de \( \mathcal{M}_{n}(\mathbb{R})\) sont en bijection avec les permutations de \( [\![1,n]\!] \). En effet, en reprenant le lien entre ces deux objets que nous avons établi ci-dessus, nous pouvons nous rendre compte que toute matrice de permutation de \( \mathcal{M}_{n}(\mathbb{R})\) est associée à une unique permutation de \( [\![1,n]\!] \) et réciproquement que toute permutation de \( [\![1,n]\!] \) est associée à une unique matrice de permutation de \( \mathcal{M}_{n}(\mathbb{R})\).
Une question classique est d’établir combien il existe de matrices de permutation dans \(\mathcal{M}_{n}(\mathbb{R})\) (il est équivalent de compter le nombre de permutations de \( [\![1,n]\!] \) de par la bijection que nous venons d’établir ci-dessus). Pour cela, il faut faire du dénombrement en choisissant la place du 1 sur la première colonne parmi \(n\) possibilités, puis la place du 1 sur la deuxième colonne parmi \(n-1\) possibilités (car le 1 ne peut pas se trouver sur la même ligne que le 1 précédemment choisi), etc. Ainsi le nombre de matrices de permutation de \( \mathcal{M}_{n}(\mathbb{R})\) vaut \( \displaystyle \prod_{i=0}^{n-1} {{n-i}\choose{1}}=n!\)
Quelques propriétés
Produit de matrices de permutation
Soient \( \sigma \), \( \lambda\) deux permutations de \( [\![1,n]\!] \) et \( P_{\sigma} \), \( P_{\lambda}\) les matrices de permutation associées. Alors, par calcul, nous pouvons montrer que \( P_{\sigma}P_{\lambda}=P_{\sigma \circ \lambda}. \)
Ce résultat peut se généraliser à l’aide d’une récurrence : soient \( \sigma_1, …, \sigma_j, j\) permutations de \( [\![1,n]\!] \), alors \( \displaystyle \prod_{i=1}^j P_{\sigma_i}=P_{\sigma_1 \circ…\circ\sigma_j}.\)
Remarque : cette propriété permet de montrer l’inversibilité de \( P_{\sigma} \), en effet \( P_{\sigma}P_{\sigma^{-1}}=P_{\text{id}}=I_n \) d’où \( P_{\sigma} \in GL_n(\mathbb{R})\) et \( P_{\sigma}^{-1}=P_{\sigma^{-1}}.\)
Produit avec une matrice \(A\)
Soient \( P_{\sigma} \) une matrice de permutation de \( \mathcal{M}_{n}(\mathbb{R}) \) (et \( \sigma \) sa permutation associée) et \(A \in \mathcal{M}_{n}(\mathbb{R}). \) Alors :
- \(P_{\sigma}A\) est la matrice faite à partir de A en permutant ses lignes selon la permutation \( \sigma\).
- \(AP_{\sigma}\) est la matrice faite à partir de A en permutant ses colonnes selon la permutation \( \sigma \).
Matrice orthogonale
Soient \( P_{\sigma} \) une matrice de permutation de \( \mathcal{M}_{n}(\mathbb{R}) \) (et \( \sigma \) sa permutation associée) et \( E_1, …, E_n \) la base canonique de \( \mathcal{M}_{n,1}(\mathbb{R}) \). Alors, \( \forall i \in [\![1,n]\!], P_{\sigma}E_i = E_{\sigma(i)}. \) Donc \( P_{\sigma} \) envoie une base orthogonale sur une base orthogonale, donc \(P_{\sigma}\) est une matrice orthogonale i.e. \(P_{\sigma}^{-1}={}^tP_{\sigma}.\) De plus, nous pouvons en déduire que \({}^tP_{\sigma}=P_{\sigma^{-1}}.\)
Trace d’une matrice de permutation
Soient \( P_{\sigma} \) une matrice de permutation. Alors : \( \text{Tr}(P_{\sigma}) = \text{Card}(\text{{\( i \in [\![1,n]\!] \; | \;\sigma(i)=i\)}}). \) Autrement dit, la trace d’une matrice de permutation, \( P_{\sigma} \), est égale au nombre de points fixes de \(\sigma\).
Matrice stochastique
Toute matrice de permutation est une matrice stochastique. C’est-à-dire une matrice carrée dont la somme des éléments de chaque ligne vaut 1. Nous pouvons donc déduire que 1 est une valeur propre de toute matrice de permutation.
Conclusion
En résumé, les matrices de permutation sont des objets mathématiques particulièrement utiles en algèbre avec de nombreuses propriétés à connaître et à savoir démontrer si tu vises les Parisiennes ! Ainsi, bien que cette notion soit hors programme, son analyse approfondie enrichira ta préparation à toutes les épreuves de mathématiques, notamment aux Maths 1 et 2 !
Pour maîtriser cette notion, tu peux t’entraîner sur des sujets (mathématiques approfondies) :
Tu peux retrouver ici toutes nos autres ressources mathématiques !
