Cyclic permutation
[1][2] In some cases, cyclic permutations are referred to as cycles;[3] if a cyclic permutation has k elements, it may be called a k-cycle.
Some authors widen this definition to include permutations with fixed points in addition to at most one non-trivial cycle.
[3][4] In cycle notation, cyclic permutations are denoted by the list of their elements enclosed with parentheses, in the order to which they are permuted.
For the wider definition of a cyclic permutation, allowing fixed points, these fixed points each constitute trivial orbits of the permutation, and there is a single non-trivial orbit containing all the remaining points.
This can be used as a definition: a cyclic permutation (allowing fixed points) is a permutation that has a single non-trivial orbit.
[5] The individual cyclic parts of a permutation are also called 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.
There is not widespread consensus about the precise definition of a cyclic permutation.
Some authors define a permutation σ of a set X to be cyclic if "successive application would take each object of the permuted set successively through the positions of all the other objects",[1] or, equivalently, if its representation in cycle notation consists of a single cycle.
[2] Others provide a more permissive definition which allows fixed points.
to S is a cyclic permutation of S. If X is finite, its cycles are disjoint, and their union is X.
That is, they form a partition, called the cycle decomposition of
So, according to the more permissive definition, a permutation of X is cyclic if and only if X is its unique cycle.
For example, the permutation, written in cycle notation and two-line notation (in two ways) as has one 6-cycle and two 1-cycles its cycle diagram is shown at right.
With the enlarged definition, there are cyclic permutations that do not consist of a single cycle.
More formally, for the enlarged definition, a permutation
of a set X, viewed as a bijective function
, is called a cycle if the action on X of the subgroup generated by
can be pictured as A cyclic permutation can be written using the compact cycle notation
(there are no commas between elements in this notation, to avoid confusion with a k-tuple).
The length of a cycle is the number of elements of its largest orbit.
A cycle of length k is also called a k-cycle.
[7] When cycle notation is used, the 1-cycles are often omitted when no confusion will result.
[a] 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.
[9] The number of k-cycles in the symmetric group Sn is given, for
A cycle with only two elements is called a transposition.
Any permutation can be expressed as the composition (product) of transpositions—formally, they are generators for the group.
by moving k to l one step at a time, then moving l back to where k was, which interchanges these two and makes no other changes: 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
where it is by executing the right factor first (as usual in operator notation, and following the convention in the article Permutation).
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.
[11] This permits the parity of a permutation to be a well-defined concept.
