Cyclic permutation#Transpositions

image:050712_perm_2.png

There is not widespread consensus about the precise definition of a cyclic permutation. Some authors define a permutation {{mvar|σ}} of a set {{mvar|X}} to be cyclic if "successive application would take each object of the permuted set successively through the positions of all the other objects", or, equivalently, if its representation in cycle notation consists of a single cycle. Others provide a more permissive definition which allows fixed points.

A nonempty subset {{mvar|S}} of {{mvar|X}} is a cycle of $\backslash sigma$ if the restriction of $\backslash sigma$ to {{mvar|S}} is a cyclic permutation of {{var|S}}. If {{mvar|X}} is finite, its cycles are disjoint, and their union is {{mvar|X}}. That is, they form a partition, called the cycle decomposition of $\backslash sigma.$ So, according to the more permissive definition, a permutation of {{mvar|X}} is cyclic if and only if {{mvar|X}} is its unique cycle.

For example, the permutation, written in cycle notation and two-line notation (in two ways) as

:$\backslash begin\{align\}$

(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{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.

image:050712_perm_3.pngWith the enlarged definition, there are cyclic permutations that do not consist of a single cycle.

More formally, for the enlarged definition, a permutation $\backslash sigma$ of a set X, viewed as a bijective function $\backslash sigma:X\backslash to\; X$, is called a cycle if the action on X of the subgroup generated by $\backslash sigma$ has at most one orbit with more than a single element.{{harvnb|Fraleigh|1993|loc=p. 103}} 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=\backslash sigma^i(s\_0)$ for any $i\backslash in\backslash mathbf\{Z\}$. If S is finite, there is a minimal number $k\; \backslash geq\; 1$ for which $s\_k=s\_0$. Then $S=\backslash \{\; s\_0,\; s\_1,\; \backslash ldots,\; s\_\{k-1\}\backslash \}$, and $\backslash sigma$ is the permutation defined by

:$\backslash sigma(s\_i)\; =\; s\_\{i+1\}$ for 0 ≤ i < k

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

:$s\_0\backslash mapsto\; s\_1\backslash mapsto\; s\_2\backslash mapsto\backslash cdots\backslash mapsto\; s\_\{k-1\}\backslash mapsto\; s\_k=s\_0$.

A cyclic permutation can be written using the compact cycle notation $\backslash sigma\; =\; (s\_0~s\_1~\backslash 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.{{harvnb|Rotman|2006|loc=p. 108}} When cycle notation is used, the 1-cycles are often omitted when no confusion will result.{{harvnb|Sagan|1991|loc=p. 2}}

{{Hatnote|In the remainder of the article, the enlarged definition is used.}}

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.{{efn|Note that the cycle notation is not unique: each k-cycle can itself be written in k different ways, depending on the choice of $s\_0$ in its orbit.}} 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.{{harvnb|Rotman|2006|loc=p. 117, 121}}

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

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

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

The inverse of a cycle $\backslash sigma\; =\; (s\_0~s\_1~\backslash dots~s\_\{k-1\})$ is given by reversing the order of the entries: $\backslash sigma^\{-1\}\; =\; (s\_\{k\; -\; 1\}~\backslash 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.

{{redirect|Transposition (mathematics)|matrix transposition|Transpose}}

File:4-el perm matrix 14.svg of $\backslash pi$]]

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

Any permutation can be expressed as the composition (product) of transpositions—formally, they are generators for the group.{{harvnb|Rotman|2006|loc=p. 118, Prop. 2.35}} In fact, when the set being permuted is {{math|{{mset|1, 2, ..., n}}}} for some integer {{math|n}}, then any permutation can be expressed as a product of {{visible anchor|adjacent transpositions}} $(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 $(k~~l)$ where by moving {{math|k}} to {{math|l}} one step at a time, then moving {{math|l}} back to where {{math|k}} was, which interchanges these two and makes no other changes:

:$(k~~l)\; =\; (k~~k+1)\backslash cdot(k+1~~k+2)\backslash cdots(l-1~~l)\backslash cdot(l-2~~l-1)\backslash 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~\backslash ldots~y~z)\; =\; (a~b)\backslash cdot\; (b~c~d~\backslash 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.{{harvnb|Rotman|2006|loc=p. 122}} This permits the parity of a permutation to be a well-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

{{notelist}}

{{reflist|30em}}

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

• [https://www.youtube.com/watch?v=MpKG6FmcIHk Cycle Notation of Permutations], video explains cyclic decomposition.

{{PlanetMath attribution|id=2262|title=cycle}}

{{DEFAULTSORT:Cycle (Mathematics)}}

Category:Permutations