World Library  
Flag as Inappropriate
Email this Article

Cyclic permutation

Article Id: WHEBN0000449166
Reproduction Date:

Title: Cyclic permutation  
Author: World Heritage Encyclopedia
Language: English
Subject: Permutation, Fisher–Yates shuffle, Parity of a permutation, Marian Rejewski, Cubic function
Collection:
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Cyclic permutation

In mathematics, and in particular in group theory, a cyclic permutation 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 (i.e., mapping to themselves) all other elements of X. For example, the permutation of {1, 2, 3, 4} that sends 1 to 3, 3 to 2, 2 to 4 and 4 to 1 is a cycle, while the permutation that sends 1 to 3, 3 to 1, 2 to 4 and 4 to 2 is not (it separately permutes the pairs {1, 3} and {2, 4}).

A cycle in a permutation is a subset of the elements that are permuted in this way. 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. In some contexts, a cyclic permutation itself is called a cycle.

Contents

  • Definition 1
  • Basic properties 2
  • Transpositions 3
    • Properties 3.1
  • See also 4
  • Notes 5
  • References 6
  • External links 7

Definition

mapping of permutation

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

Example:

\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} = (146837)(2)(5)

Some authors restrict the definition to only those permutations which have precisely one cycle (that is, no fixed points allowed).[2]

mapping of permutation

Example:

\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} = (14625837)

More formally, a permutation of a set X, which is 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.[3] This notion is most commonly used when X is a finite set; then of course 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} \quad\mbox{for }0\leq i

and \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 cycle 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.[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 says 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 (but 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).[6] 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.[7]

The number of k-cycles in the symmetric group Sn is given, for 1\leq k\leq n, by the following equivalent formulas

\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.

Transpositions

Array of transpositions

A cycle with only two elements is called a transposition. For example, the permutation of {1, 2, 3, 4} that sends 1 to 1, 2 to 4, 3 to 3 and 4 to 2 is a transposition (specifically, the transposition that swaps 2 and 4).

Properties

Any permutation can be expressed as the composition (product) of transpositions—formally, they are generators for the group.[8] In fact, if one takes a=1, b=2, ..., e=5, then any permutation can be expressed as a product of adjacent transpositions, meaning the transpositions (k~~k+1), in this case (1~2), (2~3), (3~4), and (4~5). This follows because an arbitrary transposition can be expressed as the product of adjacent transpositions. Concretely, one can express the transposition (k~~l) where 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:

(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 on Permutations). 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.[9] This permits the parity of a permutation to be a well-defined concept.

See also

Notes

  1. ^ Bogart, Kenneth P. (1990), Introductory Combinatorics (2nd ed.), Harcourt, Brace, Jovanovich, p. 486,  
  2. ^ Gross, Jonathan L. (2008), Combinatorial Methods with Computer Applications, Chapman & Hall/CRC, p. 29,  
  3. ^ Fraleigh 1993, p. 103
  4. ^ Rotman 2006, p. 108
  5. ^ Sagan 1991, p. 2
  6. ^ To be technically correct a factorization should contain one 1-cycle for each fixed point of the permutation. See Rotman (2006, pp. 113-114).
  7. ^ Rotman 2006, p. 117, 121
  8. ^ Rotman 2006, p. 118, Prop. 2.35
  9. ^ Rotman 2006, p. 122

References

  • Anderson, Marlow and Feil, Todd (2005), A First Course in Abstract Algebra, Chapman & Hall/CRC; 2nd edition. ISBN 1-58488-515-7.
  • Fraleigh, John (1993), A first course in abstract algebra (5th ed.), Addison Wesley,  
  • Rotman, Joseph J. (2006), A First Course in Abstract Algebra with Applications (3rd ed.), Prentice-Hall,  
  • Sagan, Bruce E. (1991), The Symmetric Group / Representations, Combinatorial Algorithms & Symmetric Functions, Wadsworth & Brooks/Cole,  

External links

  • Permutations as a Product of Transpositions

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

This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.