Transposition (mathematics)

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.

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.

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 ${\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. This notion is most commonly used when X is a finite set; then of course 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

...
Wikipedia