Cyclic permutation

A cyclic permutation consisting of a single 8-cycle.

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.[3][4]

A nonempty subset S of X is a cycle of ${\displaystyle \sigma }$ if the restriction of ${\displaystyle \sigma }$ 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 ${\displaystyle \sigma .}$ 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

${\displaystyle {\begin{aligned}(1\ 4\ 6\ &8\ 3\ 7)(2)(5)\\&={\begin{pmatrix}1&2&3&4&5&6&7&8\\4&2&7&6&5&8&1&3\end{pmatrix}}\\&={\begin{pmatrix}1&4&6&8&3&7&2&5\\4&6&8&3&7&1&2&5\end{pmatrix}}\end{aligned}}}$

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.

A permutation that is cyclic for the enlarged definition but not for the restricted one, with two fixed points (1-cycles) and a 6-cycle

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 set X, viewed as a bijective function ${\displaystyle \sigma :X\to X}$, is called a cycle if the action on X of the subgroup generated by ${\displaystyle \sigma }$ has at most one orbit with more than a single element.[5] This notion is most commonly used when X is a finite set; then the largest orbit, S, is also finite. Let ${\displaystyle s_{0}}$ be any element of S, and put ${\displaystyle s_{i}=\sigma ^{i}(s_{0})}$ for any ${\displaystyle i\in \mathbf {Z} }$. If S is finite, there is a minimal number ${\displaystyle k\geq 1}$ for which ${\displaystyle s_{k}=s_{0}}$. Then ${\displaystyle S=\{s_{0},s_{1},\ldots ,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 compact cycle notation ${\displaystyle \sigma =(s_{0}~s_{1}~\dots ~s_{k-1})}$ (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.

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.[6] When cycle notation is used, the 1-cycles are often omitted when no confusion will result.[7]

One of the basic results on symmetric groups is 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.[lower-alpha 1] 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.[8]

The number of k-cycles in the symmetric group S_n is given, for ${\displaystyle 1\leq k\leq n}$, by the following equivalent formulas:

$${\displaystyle {\binom {n}{k}}(k-1)!={\frac {n(n-1)\cdots (n-k+1)}{k}}={\frac {n!}{(n-k)!k}}.}$$

A k-cycle has signature (−1)^k − 1.

The inverse 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 (a~b)=(b~a)}$, 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.

Matrix of ${\displaystyle \pi }$

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

• 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

This article incorporates material from cycle on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.