cyclic permutation

Uses your system voice; voice and rate in settings.

Q212130Snapshot

≈ 8 min read

Names in other languages

  • Françaispermutation circulaire
  • Deutschzyklische Permutation
  • Españolpermutación circular
  • СрпскиЦиклична пермутација
  • СрпскиCiklična permutacija
  • Portuguêspermutação circular
  • Englishcyclic permutation
  • eocikla permuto

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In mathematics, and in particular in group theory, a cyclic permutation is a permutation consisting of a single cycle. In some cases, cyclic permutations are referred to as cycles; 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. 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 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 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. Every permutation on finitely many elements can be decomposed into cyclic permutations whose non-trivial orbits are disjoint.…

In mathematics, and in particular in group theory, a cyclic permutation is a permutation consisting of a single cycle. In some cases, cyclic permutations are referred to as cycles; 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. 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 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 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. Every permutation on finitely many elements can be decomposed into cyclic permutations whose non-trivial orbits are disjoint.

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. &= \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{align} 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 \sigma of a set X, viewed as a bijective function \sigma:X\to X , is called a cycle if the action on X of the subgroup generated by \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 the largest orbit, S, is also finite. Let s_0 be any element of S, and put s_i=\sigma^i(s_0) for any i\in\mathbf{Z} .

If S is finite, there is a minimal number k \geq 1 for which s_k=s_0 . Then S=\{ s_0, s_1, \ldots, s_{k-1}\} , and \sigma is the permutation defined by \sigma(s_i) = s_{i+1} for 0 ≤ i \sigma(x)=x for any element of X\setminus S . The elements not fixed by \sigma can be pictured as 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 \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. When cycle notation is used, the 1-cycles are often omitted when no confusion will result. \binom nk(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 \sigma = (s_0~s_1~\dots~s_{k-1}) is given by reversing the order of the entries: \sigma^{-1} = (s_{k - 1}~\dots~s_1~s_{0}) . In particular, since (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. A cycle with only two elements is called a transposition. For example, the permutation \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 \pi = (2\ 4) . (k~~l) = (k~~k+1)\cdot(k+1~~k+2)\cdots(l-1~~l)\cdot(l-2~~l-1)\cdots(k~~k+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: (a~b~c~d~\ldots~y~z) = (a~b)\cdot (b~c~d~\ldots~y~z).

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

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.

Notes

References

Text derived from https://en.wikipedia.org/w/index.php?oldid=1362230582 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot cyclic-permutation-024999-8a53295dd1a795e2 · hash 8a53295dd1a795e26dbeeb0a1d51fde4ed57db15c314c56de28022c82df88a11 · captured 1783005899.0 · version history

Cite this page as: encyclopegia.org, “cyclic permutation”, snapshot cyclic-permutation-024999-8a53295dd1a795e2. https://encyclopegia.org/a/cyclic-permutation

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.