Théorème 1
Toute permutation est décomposable en produit de cycles disjoints, et la décomposition est unique.
Démo
Soit p une permutation et p ≠ id, donc ∃a tel que p(a) ≠ a disons p(a) = b
on forme alors la suite: a, p(a)=b, p(b)=c, p(c)=d, p(d)=e, p(e)=f,...
Tout d'abord on ne peut pas continuer indéfiniment car on a un nombre fini d'éléments, donc à un certain moment on revient forcément au début p(m)=a,
en effet si on tombe avant le début par ex p(m)=d=p(c), p ne serait pas injective (p(m) = p(c) et m ≠ c) ce qui contredit le fait que p est une bijection.
On a donc un cycle (a, p(a), p²(a), p3(a), ...pk(a)) et on recommence avec un point u extérieur des cycles trouvés ...
(a,p(a),p²(a),p3(a), ...pk(a))
(u,p(u),p²(u),p3(u), ...ph(u))
(v,p(v),p²(v),p3(v), ...pt(v))
....
etc
et on s'arrête le processus car on a un nombre fini de points à traiter.
les cycles trouvés sont disjoints sinon p ne sera pas injective.
Théorème 2
A) Toute permutation est décomposable en produit de transpositions (la décomposition n'est pas unique).
B) La parité du nombre de transpositions est la même.
Démo1 A)
Remarque , on peut décomposer un k-cycle en (k-1) transpositions , par ex
(a,b,c) = (a,c)(a,b) (on notz pq pour poq)
(a,b,c,d) = (a,d)(a,c)(a,b)
(a,b,c,d,e) = (a,e)(a,d)(a,c)(a,b)
...
Donc le théorème 1+la remarque, nous montre que toute permutation est décomposable en transpositions (la décomposition n'est pas unique.)
Démo2 A)
On va démontrer A) par récurrence sur n.
Pour n=2 , le théorème est vrai en effet S2 = {id, t=(a,b)} et t=(a,b) et id=(a,b)(a,b)
Supposons que le théorème soit vrai pour n, et voyons s'il est encore vrai pour (n+1), donc
soit p une permutation de Sn+1 et p ≠ id, donc ∃a tel que p(a) ≠ a disons p(a) = b
p s'éscrit alors sous la forme p = u(a,b) avec u∈Sn-1 car on a "supprimé" 'a' de l'ensemble de départ et 'b' de l'ensemble d'arrivé,
Sn-1 = Sn - {a,b} et Sn-1 ⊂ Sn
Or d'après l'hypothèse de récurrence u est le produit des transpositions, u=t1t2...tk , d'où
p=t1t2...tk(a,b) car les transpositions de Sn-1 sont aussi des transpositions de Sn
Lemme 1 : p et (a,b)p n'ont pas la même parité.
Soient (a,b) une transposition et q un cycle
cas 1: (a,b) et q sont disjoints ==> (a,b)q transpositions +1
cas 2: (a,b) et q ont une lettre en commun (a,b)(a,c,d,e,f) = (a,c,d,e,f,b) ==> (a,b)q transpositions +1
cas 3: (a,b) dans un seul cycle : (a,b)(a,c,d,b,e,f) = (a,c,d)(b,e,f) ==> (a,b)q transpositions -1
cas 4: (a,b) dans deux cycles disjoints: (a,b)(a,d,c,e,f)(b,u,v) = (a,d,c,e,f,b,u,v) ==> (a,d)q transpositions +1
donc pour une permutation p (décomposé en cycles disjoints) la multiplication par une transposition change de parité, p et (a,b)p n'ont pas la même parité.
Lemme 2 : Une transposition est décomposable en nombre impair de transpositions.
cas 1:
(a,b) = u ; u=pair
(a,b) = v(x,y) avec v=pair
d'où
v ; pair
(a,b)v = uv ; pair ==> impossible d'après lemme 1
cas 2:
(a,b) = u ; u=pair
(a,b) = v ; v=pair
d'où
v ; pair
(a,b)v = uv ; pair ==> impossible d'après lemme 1
Lemme 3 : L'identité id se décompose en nombre pair de transpositions
cas 1:
id = u ; u=pair
id = (a,b)v avec v=pair
d'où
(a,b)v = u
(a,b) = uv-1 ; pair ==> impossible d'après lemme 2
cas 2:
id = (x,y)u ; avec u=pair
id = (a,b)v ; avec v=pair
d'où
(a,b) = v-1 ; pair ==> impossible d'après lemme 2
Démo théorème 2
B) Soient t le nombre de transpositions dans une décomposition, et t' dans une autre décomposition , il s'agit de montrer
t = t' (mod 2)
p = q1q2...qt ; 1er décomposition
p = m1m2m3...mt' ; 2er décomposition
pp-1 = id = q1q2...qt mt'...m3m2m1
t+t' = 0 (mod 2) car id se décompose en nombre pair de transpositions
t = t' (mod 2)
Il y a une autre façon de démontrer le lemme 3
Lemme 3 : L'identité id se décompose en nombre pair de transpositions
Démo :
Soit
id = (,)...(,)(,)(,)(a,b) ; une décomposition de id en k transpositions
id = u.(a,b) ;k transpositions
on calcule id(b)
id(b) = b = u(a) , u déplace forcément a, sinon ça ne serait pas l'identité id , donc il y a des transpositions de type (a,.) dans u , soit (a,x) la 1ère (compté de droite à gauche)
id = (,)(a,y)...(,)(a,x)(c,d)(,)...(a,b)
Prétons nous l'attention sur (a,x)(c,d)
cas 1: (a,x)(c,d) disjoints, on utilise (a,x)(c,d)=(c,d)(a,x) pour remonter (a,.) jusqu'à (a,b)
cas 2: (a,x)(c,d) non-disjoint, on a forcément c=x (non c=a car (a,x) le 1er à partir de droite), on utilise (a,x)(x,d)=(d,x)(a,d) pour remonter (a,.) jusqu'à (a,b)
donc
id = (,)(,)..(,)(a,z)(a,b) avec z=x,d
==> si z=b on simplifie donc on a (k-2) transpositions
==> si z ≠ b on remplace (a,z)(a,b)=(z,b)(a,z) et id = v.(a,z) ; avec k transpositions, on a le même type de décomposition que u.(a,b) , mais une transposition (a,.) de moins .
Il y a donc 2 issus
==> soit on sort par la porte 1 , avec (k-2) transpositions
==> soit on sort par la porte 2 , avec v.(a,z) mais une transposition (a,.) en moins
on ne peut pas sortir par la porte 2, tout temps , en effet à un certain moment il n'y a plus de transpositions du type (a,.), par ex w.(a,h) et w ne bouge plus a,
donc id(h) = w.(a,h).h = w(a) = a donc ce n'est pas l'identité.
Finalement tôt ou tard on sort par la porte 1. à chaque fois qu'on sort par la porte 1, on diminue les transpositions de 2: donc
k-2, k-2-2, k-2-2-2,... , k-2m.
il ne peut pas rester une transposition car c'est id, donc il restera 0, c'est à dire
k-2m = 0 ==> k = 2m pair.
[1]
Accueil
DMJ: 04/09/2017