Soit
σ∈Sn.
Existence de la décomposition en cycles disjoints.On construit la décomposition par l'algorithme suivant. Soit
a1 le plus petit élément de
[[1,n]] non encore placé. On considère l'orbite de
a1 sous l'action de
σ :
a1,σ(a1),σ2(a1),… Cette suite prend ses valeurs dans
[[1,n]] qui est fini, donc elle est ultimement périodique. Elle est en fait périodique dès le départ : il existe
p≥1 minimal tel que
σp(a1)=a1 (car si
σj(a1)=σk(a1) avec
j<k, alors
σk−j(a1)=a1 par bijectivité de
σ). On obtient ainsi le
p-cycle
c1=(a1,σ(a1),…,σp−1(a1)).
On recommence avec le plus petit élément
a2 non dans
{a1,σ(a1),…,σp−1(a1)}, et on construit de même un cycle
c2. Et ainsi de suite jusqu'à épuisement de
[[1,n]].
Les cycles
c1,c2,…,cs ainsi obtenus ont des supports disjoints et vérifient
σ=c1∘c2∘⋯∘cs (car tout élément de
[[1,n]] 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
c1∘⋯∘cs et
d1∘⋯∘dt deux décompositions de
σ en cycles à supports disjoints. Pour tout
a∈[[1,n]], l'orbite de
a sous
σ est entièrement déterminée par
σ : c'est
{a,σ(a),σ2(a),…,σp−1(a)} où
p est le plus petit entier
≥1 tel que
σ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é.