Décomposition permutation

[invite7b72de50]

Bonjour !

Voila, la théorie dit que toute permutation est un produit de transpositions.
Comment peut on effectuer une telle transposition ? Par exemple dans le cas suivant :

mu = (1 2 3 4 5)
(5 4 2 1 3)

Merci d'avance !
-----

[indian58]

mu=(54321)??

dans ce cas, mu=[5,1][4,2]
tu décomposes mu en produits de cycles que tu décomposes en produits de transpositions

[invite7b72de50]

Oui mais comment on arrive a décomposer ce cycle en transopositions ? J'ai bien des exemples, mais je ne comprend pas comment on, y arrive ! Et a quoi ca sert concrètement ?

[GuYem]

Concrètement ça sert à avoir des générateurs "simples" de S_n. Une transposition c'est quand même assez simple.

Pour la décomposition effective, ça dépend de ce que tu veux ; il en existe plusieurs de possibles.

Je crois qu'indian n'a pas bien saisi ton exemple. La décomposition de ta permutation en produit de cyles à supports disjoints est : (1 5 3 4) (il n'y a qu'un cycle!)

[A voir en vidéo sur Futura]

[invite7b72de50]

Oui tout à fait d'accord, un seul cycle mais on peut encore le déocomposer en un produit de transpositions. D'après mon cours, on ferait comme ca pour une permutation décomposée en deux cycles : (1 2 3)(4 5 7 8 9)

Décomposition en un produit de transpositions :

(1 2)(2 3)(4 5)(5 7)(7 8)(8 9) =
(1 3)(1 2)(4 9)(4 8)(4 7)(4 5)

C'est ce que moi j'ai compris, maintenant, quant à savoir si c'est juste !

[matthias]

La décomposition de ta permutation en produit de cyles à supports disjoints est : (1 5 3 4) (il n'y a qu'un cycle!)

Euh, l'image de 3 c'est 2.
L'exemple d'amwus est déjà un cycle de longueur 5:
(1 5 3 2 4)

D'après mon cours, on ferait comme ca pour une permutation décomposée en deux cycles : (1 2 3)(4 5 7 8 9)

Décomposition en un produit de transpositions :

(1 2)(2 3)(4 5)(5 7)(7 8)(8 9) =
(1 3)(1 2)(4 9)(4 8)(4 7)(4 5)

C'est ce que moi j'ai compris, maintenant, quant à savoir si c'est juste !

Ce n'est pas bien dur de vérifier que:
(a1 a2)(a2 a3)...(a(n-1) an) donne bien:
a1->a2->a3->...->a(n-1)->an->a1
donc que c'est le cycle (a1 a2 a3 .... a(n-1) an)
(pour des ai distincts)

[invite7b72de50]

Donc c'est bien comme ca qu'on fait ? Alors c'est assez simple ^^ !