![]() | ||
In mathematics, and in particular in group theory, a cyclic permutation (or cycle) is a permutation of the elements of some set X which maps the elements of some subset S of X to each other in a cyclic fashion, while fixing (that is, mapping to themselves) all other elements of X. If S has k elements, the cycle is called a k-cycle.
Contents
For example, given X = {1, 2, 3, 4}, the permutation that sends 1 to 3, 3 to 2, 2 to 4 and 4 to 1 (so S = X) is a 4-cycle, and the permutation that sends 1 to 3, 3 to 2, 2 to 1 and 4 to 4 (so S = {1, 2, 3} and 4 is a fixed element) is a 3-cycle. On the other hand, the permutation that sends 1 to 3, 3 to 1, 2 to 4 and 4 to 2 is not a cyclic permutation because it separately permutes the pairs {1, 3} and {2, 4}.
The set S is called the orbit of the cycle. Every permutation on finitely many elements can be decomposed into a collection of cycles on disjoint orbits.
The cyclic parts of a permutation are cycles, thus the second example is composed of a 3-cycle and a 1-cycle (or fixed point) and the third is composed of two 2-cycles.
Definition
A permutation is called a cyclic permutation if and only if it has a single nontrivial cycle (a cycle of length > 1).
For example, the permutation, written in two-line (in two ways) and also cycle notations,
is a six-cycle; its cycle diagram is shown at right.
Some authors restrict the definition to only those permutations which consist of one nontrivial cycle (that is, no fixed points allowed).
For example, the permutation
is a cyclic permutation under this more restrictive definition, while the preceding example is not.
More formally, a permutation
and
A cycle can be written using the compact cycle notation
The orbit of a 1-cycle is called a fixed point of the permutation, but as a permutation every 1-cycle is the identity permutation. When cycle notation is used, the 1-cycles are often suppressed when no confusion will result.
Basic properties
One of the basic results on symmetric groups says that any permutation can be expressed as the product of disjoint cycles (more precisely: cycles with disjoint orbits); such cycles commute with each other, and the expression of the permutation is unique up to the order of the cycles. The multiset of lengths of the cycles in this expression (the cycle type) is therefore uniquely determined by the permutation, and both the signature and the conjugacy class of the permutation in the symmetric group are determined by it.
The number of k-cycles in the symmetric group Sn is given, for
A k-cycle has signature (−1)k − 1.
Transpositions
A cycle with only two elements is called a transposition. For example the permutation
Properties
Any permutation can be expressed as the composition (product) of transpositions—formally, they are generators for the group. In fact, when the set being permuted is {1, 2, ..., n} for some integer n, then any permutation can be expressed as a product of adjacent transpositions
The decomposition of a permutation into a product of transpositions is obtained for example by writing the permutation as a product of disjoint cycles, and then splitting iteratively each of the cycles of length 3 and longer into a product of a transposition and a cycle of length one less:
This means the initial request is to move
In fact, the symmetric group is a Coxeter group, meaning that it is generated by elements of order 2 (the adjacent transpositions), and all relations are of a certain form.
One of the main results on symmetric groups states that either all of the decompositions of a given permutation into transpositions have an even number of transpositions, or they all have an odd number of transpositions. This permits the parity of a permutation to be a well-defined concept.