Cyclic permutation - en.LinkFang.org

Cyclic permutation


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. Cycles are often denoted by the list of their elements enclosed with parentheses, in the order to which they are permuted.

For example, given X = {1, 2, 3, 4}, the permutation (1, 3, 2, 4) 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 (1, 3, 2) 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 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, and denoted (1, 3) (2, 4).

Contents

Definition


A permutation is called a cyclic permutation if and only if it has a single nontrivial cycle (a cycle of length > 1).[1]

For example, the permutation, written in two-line (in two ways) and also cycle notations,

\({\displaystyle {\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}}=(1\ 4\ 6\ 8\ 3\ 7)(2)(5),}\)

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).[2]

For example, the permutation

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

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

\({\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 cycle 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.[4] When cycle notation is used, the 1-cycles are often suppressed when no confusion will result.[5]

Basic properties


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.[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.[6]

The number of k-cycles in the symmetric group Sn 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.

Transpositions


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.

Properties

Any permutation can be expressed as the composition (product) of transpositions—formally, they are generators for the group.[7] In fact, when the set being permuted is {1, 2, ..., n} for some integer n, then any permutation can be expressed as a product of adjacent transpositions \({\displaystyle (1~2),(2~3),(3~4),}\) 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 (k~~l)}\) where \({\displaystyle k<l}\) 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:

\({\displaystyle (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:

\({\displaystyle (a~b~c~d~\ldots ~y~z)=(a~b)\cdot (b~c~d~\ldots ~y~z).}\)

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 article on Permutations). 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 (a~b),}\) executed thereafter, then addresses \({\displaystyle z}\) by the index of \({\displaystyle b}\) to swap what initially were \({\displaystyle a}\) and \({\displaystyle 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.[8] This permits the parity of a permutation to be a well-defined concept.

See also


Notes


  1. ^ Note that the cycle notation is not unique: each k-cycle can itself be written in k different ways, depending on the choice of \({\displaystyle s_{0}}\) in its orbit.

References


  1. ^ Bogart, Kenneth P. (1990), Introductory Combinatorics (2nd ed.), Harcourt, Brace, Jovanovich, p. 486, ISBN 0-15-541576-X
  2. ^ Gross, Jonathan L. (2008), Combinatorial Methods with Computer Applications, Chapman & Hall/CRC, p. 29, ISBN 978-1-58488-743-0
  3. ^ Fraleigh 1993, p. 103
  4. ^ Rotman 2006, p. 108
  5. ^ Sagan 1991, p. 2
  6. ^ Rotman 2006, p. 117, 121
  7. ^ Rotman 2006, p. 118, Prop. 2.35
  8. ^ Rotman 2006, p. 122

Sources

External links


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










Categories: Permutations




Information as of: 17.06.2020 03:13:31 CEST

Source: Wikipedia (Authors [History])    License : CC-by-sa-3.0

Changes: All pictures and most design elements which are related to those, were removed. Some Icons were replaced by FontAwesome-Icons. Some templates were removed (like “article needs expansion) or assigned (like “hatnotes”). CSS classes were either removed or harmonized.
Wikipedia specific links which do not lead to an article or category (like “Redlinks”, “links to the edit page”, “links to portals”) were removed. Every external link has an additional FontAwesome-Icon. Beside some small changes of design, media-container, maps, navigation-boxes, spoken versions and Geo-microformats were removed.

Please note: Because the given content is automatically taken from Wikipedia at the given point of time, a manual verification was and is not possible. Therefore LinkFang.org does not guarantee the accuracy and actuality of the acquired content. If there is an Information which is wrong at the moment or has an inaccurate display please feel free to contact us: email.
See also: Legal Notice & Privacy policy.