Inmathematics, and in particular ingroup theory, acyclic permutation is apermutation consisting of a single cycle.^[1][2] In some cases, cyclic permutations are referred to ascycles;^[3] if a cyclic permutation hask elements, it may be called ak-cycle. Some authors widen this definition to include permutations with fixed points in addition to at most one non-trivial cycle.^[3][4] Incycle notation, cyclic permutations are denoted by the list of their elements enclosed with parentheses, in the order to which they are permuted.

For example, the permutation (1 3 2 4) that sends 1 to 3, 3 to 2, 2 to 4 and 4 to 1 is a 4-cycle, and the permutation (1 3 2)(4) that sends 1 to 3, 3 to 2, 2 to 1 and 4 to 4 is considered a 3-cycle by some authors. On the other hand, the permutation (1 3)(2 4) 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}.

For the wider definition of a cyclic permutation, allowing fixed points, these fixed points each constitute trivialorbits 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. Every permutation on finitely many elements can be decomposed into cyclic permutations whose non-trivial orbits are disjoint.^[5]

The individual cyclic parts of a permutation are also calledcycles, thus the second example is composed of a 3-cycle and a 1-cycle (orfixed 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 apermutationσ of a setX 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.^[3][4]

A nonempty subsetS ofX is acycle of${\displaystyle \sigma }$ if the restriction of${\displaystyle \sigma }$ toS is a cyclic permutation ofS. IfX isfinite, its cycles aredisjoint, and theirunion isX. That is, they form apartition, called thecycle decomposition of${\displaystyle \sigma .}$ So, according to the more permissive definition, a permutation ofX is cyclic if and only ifX is its unique cycle.

For example, the permutation, written incycle notation andtwo-line notation (in two ways) as

has one 6-cycle and two 1-cycles its cycle diagram is shown at right. Some authors consider this permutation cyclic while others do not.

With the enlarged definition, there are cyclic permutations that do not consist of a single cycle.

More formally, for the enlarged definition, a permutation${\displaystyle \sigma }$ of a setX, viewed as abijective function${\displaystyle \sigma :X\to X}$, is called a cycle if the action onX of the subgroup generated by${\displaystyle \sigma }$ has at most one orbit with more than a single element.^[6] This notion is most commonly used whenX is a finite set; then the largest orbit,S, is also finite. Let${\displaystyle s_0}$ be any element ofS, and put${\displaystyle s_i={\sigma }^i(s_0)}$ for any${\displaystyle i\in \mathbf{Z}}$. IfS is finite, there is a minimal number${\displaystyle k\ge 1}$ for which${\displaystyle s_k=s_0}$. Then${\displaystyle S=\{s_0,s_1,\dots ,s_{k-1}\}}$, and${\displaystyle \sigma }$ is the permutation defined by

${\displaystyle \sigma (s_i)=s_{i+1}}$ for 0 ≤i <k

and${\displaystyle \sigma (x)=x}$ for any element of${\displaystyle X\setminus S}$. The elements not fixed by${\displaystyle \sigma }$ can be pictured as

${\displaystyle s_0\mapsto s_1\mapsto s_2\mapsto \cdots \mapsto s_{k-1}\mapsto s_k=s_0}$.

A cyclic permutation can be written using the compactcycle notation${\displaystyle \sigma =(s_0{s}_1\dots s_{k-1})}$ (there are no commas between elements in this notation, to avoid confusion with ak-tuple). Thelength of a cycle is the number of elements of its largest orbit. A cycle of lengthk is also called ak-cycle.

The orbit of a 1-cycle is called afixed point of the permutation, but as a permutation every 1-cycle is theidentity permutation.^[7] When cycle notation is used, the 1-cycles are often omitted when no confusion will result.^[8]

One of the basic results onsymmetric groups is that any permutation can be expressed as the product ofdisjoint 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.^[a] Themultiset of lengths of the cycles in this expression (thecycle type) is therefore uniquely determined by the permutation, and both the signature and theconjugacy class of the permutation in the symmetric group are determined by it.^[9]

The number ofk-cycles in the symmetric groupS_n is given, for${\displaystyle 1\le k\le n}$, by the following equivalent formulas:$${\displaystyle (\genfrac{}{}{0ex}{}{n}{k})(k-1)!=\frac{n(n-1)\cdots (n-k+1)}{k}=\frac{n!}{(n-k)!k}.}$$

Ak-cycle hassignature (−1)^k − 1.

Theinverse of a cycle${\displaystyle \sigma =(s_0{s}_1\dots s_{k-1})}$ is given by reversing the order of the entries:${\displaystyle {\sigma }^{-1}=(s_{k-1}\dots s_1{s}_0)}$. In particular, since${\displaystyle (ab)=(ba)}$, every two-cycle is its own inverse. Since disjoint cycles commute, the inverse of a product of disjoint cycles is the result of reversing each of the cycles separately.

A cycle with only two elements is called atransposition. For example, the permutation that swaps 2 and 4. Since it is a 2-cycle, it can be written as${\displaystyle \pi =(2,4)}$.

Any permutation can be expressed as thecomposition (product) of transpositions—formally, they aregenerators for thegroup.^[10] In fact, when the set being permuted is{1, 2, ...,n} for some integern, then any permutation can be expressed as a product ofadjacent transpositions${\displaystyle (12),(23),(34),}$ and so on. This follows because an arbitrary transposition can be expressed as the product of adjacent transpositions. Concretely, one can express the transposition${\displaystyle (kl)}$ where by movingk tol one step at a time, then movingl back to wherek was, which interchanges these two and makes no other changes:

${\displaystyle (kl)=(kk+1)\cdot (k+1k+2)\cdots (l-1l)\cdot (l-2l-1)\cdots (kk+1).}$

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:

${\displaystyle (abcd\dots yz)=(ab)\cdot (bcd\dots yz).}$

This means the initial request is to move${\displaystyle a}$ to${\displaystyle b,}$${\displaystyle b}$ to${\displaystyle c,}$${\displaystyle y}$ to${\displaystyle z,}$ and finally${\displaystyle z}$ to${\displaystyle a.}$ Instead one may roll the elements keeping${\displaystyle a}$ where it is by executing the right factor first (as usual in operator notation, and following the convention in the articlePermutation). This has moved${\displaystyle z}$ to the position of${\displaystyle b,}$ so after the first permutation, the elements${\displaystyle a}$ and${\displaystyle z}$ are not yet at their final positions. The transposition${\displaystyle (ab),}$ executed thereafter, then addresses${\displaystyle z}$ by the index of${\displaystyle b}$ to swap what initially were${\displaystyle a}$ and${\displaystyle z.}$

In fact, thesymmetric group is aCoxeter 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.^[11] This permits theparity of a permutation to be awell-defined concept.

• Cycle sort – a sorting algorithm that is based on the idea that the permutation to be sorted can be factored into cycles, which can individually be rotated to give a sorted result
• Cycles and fixed points
• Cyclic permutation of integer
• Cycle notation
• Circular permutation in proteins
• Fisher–Yates shuffle

• Anderson, Marlow and Feil, Todd (2005),A First Course in Abstract Algebra, Chapman & Hall/CRC; 2nd edition.ISBN 1-58488-515-7.
• Fraleigh, John (1993),A first course in abstract algebra (5th ed.), Addison Wesley,ISBN 978-0-201-53467-2
• Rotman, Joseph J. (2006),A First Course in Abstract Algebra with Applications (3rd ed.), Prentice-Hall,ISBN 978-0-13-186267-8
• Sagan, Bruce E. (1991),The Symmetric Group / Representations, Combinatorial Algorithms & Symmetric Functions, Wadsworth & Brooks/Cole,ISBN 978-0-534-15540-7

• Cycle Notation of Permutations, video explains cyclic decomposition.

This article incorporates material from cycle onPlanetMath, which is licensed under theCreative Commons Attribution/Share-Alike License.

• Permutations

• Articles with short description
• Short description matches Wikidata
• Wikipedia articles incorporating text from PlanetMath