Matrices de permutation et signature

Stratégie : deux questions séparées. L'orthogonalité se lit directement sur les colonnes, qui sont la base canonique dans un autre ordre. Le déterminant s'obtient en décomposant la permutation en transpositions et en utilisant deux multiplicativités : celle du déterminant et celle de la signature.

Étape 0 — fixer la matrice. Soit $\sigma$ une permutation de $\{1,\dots ,n\}$. On appelle matrice de permutation associée à $\sigma$ la matrice $P_{\sigma }\in {\mathcal{M}}_n(\mathbb{R})$ dont la $j$-ième colonne est $e_{\sigma (j)}$, c'est-à-dire $$(P_{\sigma }{)}_{i,j}=\{\begin{array}{ll}1& \text{si }i=\sigma (j),\\ 0& \text{sinon.}\end{array}$$ Il y a bien exactement un $1$ par colonne (par définition) et exactement un $1$ par ligne (car $\sigma$ est bijective, donc chaque $i$ est atteint une fois et une seule).

Exemple pour $n=3$, avec $\sigma :1\mapsto 2,2\mapsto 3,3\mapsto 1$ : $$P_{\sigma }=\left(\begin{array}{ccc}0& 0& 1\\ 1& 0& 0\\ 0& 1& 0\end{array}\right)(\text{colonne 1}=e_2,\text{colonne 2}=e_3,\text{colonne 3}=e_1).$$

Étape 1 — $P_{\sigma }$ est orthogonale. Notons $C_1,\dots ,C_n$ ses colonnes, donc $C_j=e_{\sigma (j)}$. Pour tous $j,k$ : $$⟨C_j,C_k⟩=⟨e_{\sigma (j)},e_{\sigma (k)}⟩={\delta }_{\sigma (j),\sigma (k)}={\delta }_{j,k},$$ la dernière égalité venant de l'injectivité de $\sigma$ : $\sigma (j)=\sigma (k)$ équivaut à $j=k$. Les colonnes de $P_{\sigma }$ forment donc une famille orthonormale de $n$ vecteurs de ${\mathbb{R}}^n$, c'est-à-dire une base orthonormale, ce qui caractérise l'orthogonalité (proposition du cours) : $${}^t{P}_{\sigma }{P}_{\sigma }=I_n,P_{\sigma }\in {\mathrm{O}}_n(\mathbb{R}).$$ Autrement dit : $P_{\sigma }$ est la matrice de passage de la base canonique à elle-même réordonnée, et réordonner une base orthonormale la laisse orthonormale.

Le point délicat. C'est la bijectivité de $\sigma$ qui fait tout, et l'énoncé le dit à sa manière en exigeant « une fois $1$ par ligne et par colonne ». La matrice $\left(\begin{array}{cc}1& 1\\ 0& 0\end{array}\right)$ a un unique $1$ par colonne et n'est pas orthogonale — ses deux colonnes sont égales, elle n'est même pas inversible. Sans l'injectivité, l'égalité ${\delta }_{\sigma (j),\sigma (k)}={\delta }_{j,k}$ tombe.

Conséquence. $P_{\sigma }^{-1}={}^t{P}_{\sigma }$, et l'on vérifie sur les coefficients que ${}^t{P}_{\sigma }=P_{{\sigma }^{-1}}$ : en effet $({}^t{P}_{\sigma }{)}_{i,j}=(P_{\sigma }{)}_{j,i}=1⟺j=\sigma (i)⟺i={\sigma }^{-1}(j)$, ce qui est bien la définition de $P_{{\sigma }^{-1}}$. Inverser la matrice, c'est inverser la permutation.

Étape 2 — le produit suit la composition. Soient $\sigma$ et ${\sigma }^{\prime }$ deux permutations. La $j$-ième colonne de $P_{\sigma }{P}_{{\sigma }^{\prime }}$ s'obtient en multipliant $P_{\sigma }$ par la $j$-ième colonne de $P_{{\sigma }^{\prime }}$, laquelle vaut $e_{{\sigma }^{\prime }(j)}$. Or $P_{\sigma }{e}_{{\sigma }^{\prime }(j)}$ est la ${\sigma }^{\prime }(j)$-ième colonne de $P_{\sigma }$, soit $e_{\sigma ({\sigma }^{\prime }(j))}$ : c'est bien la $j$-ième colonne de $P_{\sigma \circ {\sigma }^{\prime }}$. Donc $$P_{\sigma }{P}_{{\sigma }^{\prime }}=P_{\sigma \circ {\sigma }^{\prime }}.$$

Étape 3 — le déterminant, cas d'une transposition. Soit $\tau$ la transposition échangeant $p$ et $q$ ($p\ne q$). Alors $P_{\tau }$ est la matrice $I_n$ dont on a échangé les colonnes $p$ et $q$. Le déterminant étant une forme alternée des colonnes, échanger deux colonnes le change de signe (première année) : $$\det P_{\tau }=-\det I_n=-1.$$ Vérification pour $n=3$, $\tau$ échangeant $1$ et $2$ : $P_{\tau }=\left(\begin{array}{ccc}0& 1& 0\\ 1& 0& 0\\ 0& 0& 1\end{array}\right)$, dont le déterminant vaut $-1$ (développement selon la troisième ligne : $1\times (0-1)=-1$).

Étape 4 — le déterminant, cas général. Toute permutation se décompose en produit de transpositions : $\sigma ={\tau }_1\circ \cdots \circ {\tau }_p$ (chapitre Déterminants, première année). L'étape 2 donne alors $P_{\sigma }=P_{{\tau }_1}\cdots P_{{\tau }_p}$, et la multiplicativité du déterminant, jointe à l'étape 3 : $$\det P_{\sigma }=\prod _{k=1}^p\det P_{{\tau }_k}=(-1{)}^p.$$ Or c'est exactement la définition de la signature, $\epsilon (\sigma )=(-1{)}^p$, dont la première année établit qu'elle ne dépend pas de la décomposition choisie. Conclusion : $$\boxed{\det P_{\sigma }=\epsilon (\sigma )\in \{-1,+1\}.}$$ En particulier $P_{\sigma }\in {\mathrm{SO}}_n(\mathbb{R})$ si et seulement si $\sigma$ est paire.

Seconde lecture, plus rapide. La formule du déterminant comme somme sur les permutations, $$\det A=\sum _{\tau }\epsilon (\tau )\prod _{j=1}^n{a}_{\tau (j),j},$$ donne le résultat en une ligne pour $A=P_{\sigma }$ : le produit ${\prod }_j(P_{\sigma }{)}_{\tau (j),j}$ vaut $1$ si $\tau (j)=\sigma (j)$ pour tout $j$, c'est-à-dire si $\tau =\sigma$, et $0$ dans tous les autres cas (dès qu'un indice diffère, le facteur correspondant est nul). Il ne survit qu'un seul terme, $\epsilon (\sigma )$. Le chemin par les transpositions reste préférable en rédaction, parce qu'il n'utilise que la multiplicativité, mais celui-ci explique pourquoi la signature apparaît : elle est déjà dans la définition du déterminant.

Contrôle chiffré. Prenons $n=4$ et $\sigma :1\mapsto 3,2\mapsto 1,3\mapsto 4,4\mapsto 2$. C'est le cycle $(1342)$, donc un produit de $4-1=3$ transpositions : $\epsilon (\sigma )=(-1{)}^3=-1$. Sa matrice (colonne $j$ égale à $e_{\sigma (j)}$) est $$P_{\sigma }=\left(\begin{array}{cccc}0& 1& 0& 0\\ 0& 0& 0& 1\\ 1& 0& 0& 0\\ 0& 0& 1& 0\end{array}\right).$$

• Orthogonalité : les quatre colonnes sont $e_3,e_1,e_4,e_2$, deux à deux orthogonales et unitaires ; ${}^t{P}_{\sigma }{P}_{\sigma }=I_4$ $✓$.
• Déterminant : en développant selon la première colonne (unique $1$ en position $(3,1)$), $\det P_{\sigma }=(-1{)}^{3+1}\det \left(\begin{array}{ccc}1& 0& 0\\ 0& 0& 1\\ 0& 1& 0\end{array}\right)=1\times (-1)=-1=\epsilon (\sigma )$ $✓$.
• Vérification exhaustive faite par ailleurs sur les $24$ permutations de $\{1,2,3,4\}$ et les $120$ de $\{1,\dots ,5\}$ : dans tous les cas ${}^t{P}_{\sigma }{P}_{\sigma }=I_n$ et $\det P_{\sigma }=\epsilon (\sigma )$.

Ce qui est acquis, et une caractérisation en cadeau. Les matrices de permutation sont exactement les matrices orthogonales à coefficients dans $\{0,1\}$. En effet, si $A\in {\mathrm{O}}_n(\mathbb{R})$ n'a que des $0$ et des $1$, chaque colonne est unitaire donc contient exactement un $1$ ; et deux colonnes distinctes sont orthogonales, donc leurs $1$ occupent des lignes différentes — c'est une matrice de permutation. On reconnaît là le cas d'égalité de la majoration $|a_{i,j}|\le 1$, valable pour toute matrice orthogonale puisque ses colonnes sont unitaires : les matrices de permutation sont, à ce titre, les matrices orthogonales les plus « extrêmes » qui soient.