Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Permutation circulaire
Résumé
En mathématiques, une permutation circulaire ou cycle est un cas particulier de permutation. Une permutation circulaire agit comme un décalage circulaire pour un certain nombre d'éléments, et laisse tous les autres inchangés.
Les permutations circulaires permettent d'illustrer le fonctionnement général des permutations, puisqu'une permutation quelconque se décompose en un produit de cycles fonctionnant de manière indépendante.
Soit un entier k ≥ 2. Une permutation est un k-cycle, ou permutation circulaire de longueur k, s'il existe des éléments a1, ... , ak distincts tels que σ envoie l'élément a1 sur a2, puis a2 sur a3, et enfin ak sur a1 et si tous les autres éléments restent inchangés.
Un tel cycle se note habituellement sous la forme (a1 ... ak). Avec cette notation, (a1 ... ak) = (a2 ... ak a1).
Si c est un k-cycle, ses puissances successives vérifient
ce qui veut dire que c est d'ordre k, ou encore : engendre un groupe cyclique d'ordre k.
En revanche, les puissances de c ne sont pas toutes à proprement parler des permutations circulaires (même si ce sont encore des décalages circulaires). Par exemple si c = (1 2 3 4) alors c2 = (1 3)(2 4) est un produit de deux permutations circulaires d'ordre 2, des transpositions. Plus précisément, c est une permutation circulaire si et seulement si i et k sont premiers entre eux.
Un k-cycle est :
une permutation paire si k est impair ;
une permutation impaire si k est pair.
Une démonstration est fournie dans l'article sur la signature d'une permutation. Une autre méthode consiste à exhiber une décomposition de la permutation en transpositions :
La permutation est donc la composée de k – 1 transpositions.
La conjuguée d'une permutation circulaire d'ordre k, c = (a1 a2 ... ak) par une permutation σ, est la permutation σ ∘ c ∘ σ. Il s'agit encore d'un k-cycle :
et réciproquement, tout k-cycle peut s'écrire sous cette forme en choisissant convenablement σ, ce qui signifie que la classe de conjugaison (ensemble des conjuguées) d'un k-cycle c est l'ensemble de tous les k-cycles (pour une généralisation, voir le § « Classes de conjugaison » de l'article sur le groupe symétrique).
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.