Déterminants

Soient $c_1 = (a_1, \dots, a_p)$ et $c_2 = (b_1, \dots, b_q)$ deux cycles de supports disjoints. Notons $A = \\{a_1, \dots, a_p\\}$ et $B = \\{b_1, \dots, b_q\\}$ leurs supports respectifs, avec $A \cap B = \emptyset$.

Soit $k \in \llbracket 1, n \rrbracket$. On distingue trois cas :

Cas 1 : $k \in A$. Alors $c_2(k) = k$ (car $k \notin B$) et $c_1(k) \in A$ (car $c_1$ permute circulairement $A$), donc $c_2(c_1(k)) \notin B$, d'où $c_2(c_1(k)) = c_1(k)$. De même, $c_1(c_2(k)) = c_1(k)$. Ainsi $(c_1 \circ c_2)(k) = (c_2 \circ c_1)(k) = c_1(k)$.

Cas 2 : $k \in B$. Alors $c_1(k) = k$ (car $k \notin A$) donc $(c_2 \circ c_1)(k) = c_2(k)$. De même, $c_2(k) \in B$ donc $c_1(c_2(k)) = c_2(k)$, d'où $(c_1 \circ c_2)(k) = c_2(k)$. Ainsi $(c_1 \circ c_2)(k) = (c_2 \circ c_1)(k) = c_2(k)$.

Cas 3 : $k \notin A \cup B$. Alors $c_1(k) = k$ et $c_2(k) = k$, donc $(c_1 \circ c_2)(k) = k = (c_2 \circ c_1)(k)$.

Dans tous les cas, $(c_1 \circ c_2)(k) = (c_2 \circ c_1)(k)$. Donc $c_1 \circ c_2 = c_2 \circ c_1$.

Soit $\sigma \in \mathfrak{S}_n$.

Existence de la décomposition en cycles disjoints.

On construit la décomposition par l'algorithme suivant. Soit $a_1$ le plus petit élément de $\llbracket 1, n \rrbracket$ non encore placé. On considère l'orbite de $a_1$ sous l'action de $\sigma$ : $a_1, \sigma(a_1), \sigma^2(a_1), \ldots$ Cette suite prend ses valeurs dans $\llbracket 1, n \rrbracket$ qui est fini, donc elle est ultimement périodique. Elle est en fait périodique dès le départ : il existe $p \geq 1$ minimal tel que $\sigma^p(a_1) = a_1$ (car si $\sigma^j(a_1) = \sigma^k(a_1)$ avec $j < k$, alors $\sigma^{k-j}(a_1) = a_1$ par bijectivité de $\sigma$). On obtient ainsi le $p$-cycle $c_1 = (a_1, \sigma(a_1), \ldots, \sigma^{p-1}(a_1))$.

On recommence avec le plus petit élément $a_2$ non dans $\{a_1, \sigma(a_1), \ldots, \sigma^{p-1}(a_1)\}$, et on construit de même un cycle $c_2$. Et ainsi de suite jusqu'à épuisement de $\llbracket 1, n \rrbracket$.

Les cycles $c_1, c_2, \ldots, c_s$ ainsi obtenus ont des supports disjoints et vérifient $\sigma = c_1 \circ c_2 \circ \cdots \circ c_s$ (car tout élément de $\llbracket 1, n \rrbracket$ appartient à exactement un support). Par la Proposition 1.2, ces cycles à supports disjoints commutent, donc la composée est commutative.

Unicité à l'ordre près.

Soient $c_1 \circ \cdots \circ c_s$ et $d_1 \circ \cdots \circ d_t$ deux décompositions de $\sigma$ en cycles à supports disjoints. Pour tout $a \in \llbracket 1, n \rrbracket$, l'orbite de $a$ sous $\sigma$ est entièrement déterminée par $\sigma$ : c'est $\{a, \sigma(a), \sigma^2(a), \ldots, \sigma^{p-1}(a)\}$ où $p$ est le plus petit entier $\geq 1$ tel que $\sigma^p(a) = a$. Cette orbite coïncide avec le support du cycle contenant $a$ dans chaque décomposition. Donc les deux décompositions ont les mêmes cycles (à l'ordre près), ce qui établit l'unicité.

Montrons par récurrence sur $n \ge 1$ que toute permutation de $\mathfrak{S}_n$ est une composée de transpositions.

Initialisation. Pour $n = 1$, $\mathfrak{S}_1 = \\{\mathrm{Id}\\}$ et $\mathrm{Id} = \mathrm{Id}$ (composée vide de transpositions, ou $\mathrm{Id} = \tau \circ \tau$ pour toute transposition $\tau$ si on veut une écriture non vide).

Hérédité. Supposons que tout élément de $\mathfrak{S}_{n-1}$ est une composée de transpositions. Soit $\sigma \in \mathfrak{S}_n$.

- Si $\sigma(n) = n$, alors la restriction $\sigma|_{\llbracket 1, n-1 \rrbracket}$ appartient à $\mathfrak{S}_{n-1}$, donc par hypothèse de récurrence elle s'écrit comme composée de transpositions, et il en est de même pour $\sigma$.

- Si $\sigma(n) = k \ne n$, posons $\tau = (k, n)$ la transposition qui échange $k$ et $n$. Alors $(\tau \circ \sigma)(n) = \tau(k) = n$, donc $\tau \circ \sigma$ fixe $n$ et, par le cas précédent, $\tau \circ \sigma$ est une composée de transpositions. Puisque $\tau = \tau^{-1}$, on en déduit $\sigma = \tau \circ (\tau \circ \sigma)$ est également une composée de transpositions.

Par le principe de récurrence, le résultat est établi.

Soit $\tau \in \mathfrak{S}_n$ une transposition. D'après le Théorème 1.3 (Signature), $\varepsilon$ est un morphisme de groupes de $(\mathfrak{S}_n, \circ)$ dans $(\\{-1, 1\\}, \times)$.

Comme $\tau^2 = \mathrm{Id}$, en appliquant le morphisme $\varepsilon$ :
$$\varepsilon(\tau^2) = \varepsilon(\tau)^2 = \varepsilon(\mathrm{Id}) = 1$$

Donc $\varepsilon(\tau)^2 = 1$, ce qui implique $\varepsilon(\tau) \in \\{-1, 1\\}$.

Il reste à exclure $\varepsilon(\tau) = 1$. Si toutes les transpositions avaient pour image $1$, alors, par le Théorème 1.2, toute permutation $\sigma = \tau_1 \circ \cdots \circ \tau_k$ (produit de transpositions) vérifierait :
$$\varepsilon(\sigma) = \varepsilon(\tau_1) \cdots \varepsilon(\tau_k) = 1$$

Ainsi $\varepsilon$ serait le morphisme constant égal à $1$, ce qui contredirait le fait que $\varepsilon$ est non trivial (d'après le Théorème 1.3).

Donc $\varepsilon(\tau) = -1$.

Soit $c = (a_1, a_2, \dots, a_p)$ un $p$-cycle. On peut écrire (voir l'exemple illustré dans le cours) :
$$c = (a_1, a_2) \circ (a_2, a_3) \circ \cdots \circ (a_{p-1}, a_p)$$

ceci est une décomposition en $p - 1$ transpositions.

Puisque $\varepsilon$ est un morphisme de groupes (Théorème 1.3) et que la signature de chaque transposition est $-1$ (Proposition 1.3) :
$$\varepsilon(c) = \varepsilon((a_1, a_2)) \cdot \varepsilon((a_2, a_3)) \cdots \varepsilon((a_{p-1}, a_p)) = (-1)^{p-1}$$

En particulier, pour $p = 2$ (transposition), $\varepsilon(c) = (-1)^1 = -1$, ce qui est cohérent avec la Proposition 1.3.