Réduction des matrices de permutation

Soit $n \in \mathbb{N}^*$ . On considère $\sigma$ une permutation de l'ensemble $\{1, \dots, n\}$ . On note $M_{\sigma} \in \mathcal{M}_n(\mathbb{C})$ la matrice de permutation associée, définie par son coefficient général :

\forall (i,j) \in \llbracket 1, n \rrbracket^2,   (M_{\sigma})_{i,j} = \delta_{i, \sigma(j)}

Montrer qu'il existe un entier naturel $k \geq 1$ tel que $M_{\sigma}^k = I_n$ . En déduire que la matrice $M_{\sigma}$ est diagonalizable dans $\mathcal{M}_n(\mathbb{C})$ .
Soit $\sigma = c_1 \circ c_2 \circ \dots \circ c_r$ la décomposition de $\sigma$ en cycles de supports disjoints, de longueurs respectives $l_1, l_2, \dots, l_r$ . Déterminer le polynôme caractéristique de $M_{\sigma}$ en fonction de ces longueurs.
Donner une condition nécessaire et suffisante sur les permutations $\sigma$ et $\tau \in \mathfrak{S}_n$ pour que les matrices $M_{\sigma}$ et $M_{\tau}$ soient semblables dans $\mathcal{M}_n(\mathbb{C})$ .

1.

Pour la question 1, utiliser le fait que le groupe symétrique $\mathfrak{S}_n$ est de cardinal fini. Penser aux polynômes annulateurs.

2.

Pour la question 2, on pourra commencer par traiter le cas où $\sigma$ est un cycle unique de longueur $n$ , puis utiliser une réduction par blocs.

3.

Pour la question 3, deux matrices diagonalisables sont semblables si et seulement si elles ont le même spectre avec les mêmes multiplicités.

Idées clés

•

Lien entre composition de permutations et produit matriciel : $M_{\sigma} M_{\tau} = M_{\sigma \circ \tau}$ .

•

Critère de diagonalisabilité par les polynômes annulateurs scindés à racines simples.

•

Calcul du déterminant d'une matrice par blocs.

Résolution.

Considérons l'application $\phi : \mathfrak{S}_n \to \mathcal{M}_n(\mathbb{C})$ qui à $\sigma$ associe $M_{\sigma}$ . On vérifie aisément que $\phi$ est un morphisme de groupes. En particulier, pour tout $\sigma \in \mathfrak{S}_n$ , on a : $M_{\sigma}^k = M_{\sigma^k}$ Comme le groupe $\mathfrak{S}_n$ est fini, l'élément $\sigma$ est d'ordre fini. Il existe donc $k \in \mathbb{N}^*$ tel que $\sigma^k = \text{id}$ . On en déduit : $\boxed{M_{\sigma}^k = I_n}$ Le polynôme $P(X) = X^k - 1$ est donc un polynôme annulateur de $M_{\sigma}$ . Ce polynôme est scindé sur $\mathbb{C}$ et ses racines (les racines $k$ -ièmes de l'unité) sont toutes simples. D'après le cours sur la réduction, une matrice admettant un polynôme annulateur scindé à racines simples est diagonalizable. $\boxed{M_{\sigma} \text{ est diagonalizable dans } \mathcal{M}_n(\mathbb{C})}$
Supposons d'abord que $\sigma$ est un cycle de longueur $l$ . Quitte à renuméroter la base canonique, $M_{\sigma}$ est semblable à une matrice compagnon ou une matrice circulante dont le polynôme caractéristique est : $\chi_{\text{cycle}}(X) = X^l - 1$ Dans le cas général, la décomposition en cycles disjoints induit une décomposition de l'espace $\mathbb{C}^n$ en sous-espaces stables. La matrice $M_{\sigma}$ est donc semblable à une matrice diagonale par blocs de la forme $\text{diag}(M_{c_1}, \dots, M_{c_r})$ . Le déterminant d'une matrice bloc-diagonale étant le produit des déterminants des blocs, on obtient : $\chi_{M_{\sigma}}(X) = \prod_{j=1}^r \chi_{M_{c_j}}(X)$ En remplaçant par l'expression trouvée pour un cycle, nous obtenons le résultat final : $\boxed{\chi_{M_{\sigma}}(X) = \prod_{j=1}^r (X^{l_j} - 1)}$
Puisque les matrices $M_{\sigma}$ et $M_{\tau}$ sont diagonalisables sur $\mathbb{C}$ , elles sont semblables si et seulement si elles ont le même polynôme caractéristique (ce qui équivaut à avoir les mêmes valeurs propres avec les mêmes multiplicités). D'après la formule précédente, $\chi_{M_{\sigma}}$ est entièrement déterminé par la famille des longueurs des cycles disjoints de $\sigma$ (appelée type cyclique). Inversement, la donnée de $\chi_{M_{\sigma}}$ permet de retrouver les longueurs $l_j$ . En effet, les racines de $\chi_{M_{\sigma}}$ sont des racines de l'unité, et la multiplicité de la racine $1$ est égale au nombre de cycles (en comptant les points fixes comme des cycles de longueur 1). Ainsi, $M_{\sigma}$ et $M_{\tau}$ sont semblables si et seulement si $\sigma$ et $\tau$ ont la même structure de cycles. $\boxed{M_{\sigma} \sim M_{\tau} \iff \sigma \text{ et } \tau \text{ ont le même type cyclique}}$ Remarquons que cette condition équivaut également à dire que $\sigma$ et $\tau$ sont conjuguées dans le groupe $\mathfrak{S}_n$ .

Ne pas oublier de compter les points fixes de la permutation comme des cycles de longueur 1 dans le produit du polynôme caractéristique. Si $\sigma(i)=i$ , alors le facteur $(X^1 - 1)$ apparaît bien dans le produit.