Cycle notation

From Wikipedia, the free encyclopedia
Jump to: navigation, search
For the cyclic decomposition of graphs, see Cycle decomposition (graph theory). For cycling terminology, see glossary of bicycling.

In mathematics, cycle notation is a useful convention for writing down a permutation in terms of its constituent cycles.[1] This had sometimes been called circular notation and a permutation consisting of a single cycle was called a circular permutation.[2] Modern terminology uses the term cyclic to mean a permutation with one cycle or one set of non-fixed points, and restricts a circular permutation to mean a permutation of objects arranged in a circle up to cyclic permutations, so that there is no fixed starting object on the circle.[3]

Definition[edit]

Let S be the set \{1,\dots,n\}, n \in \mathbb{N}, and

 a_1,\ldots,a_k,\quad 1 \leq k \leq n

be distinct elements of S. The expression

(a_1\ \ldots\ a_k)

denotes the cycle σ whose action is

 a_1\mapsto a_2\mapsto a_3\mapsto \ldots \mapsto a_k \mapsto a_1.

For each index i,

\sigma (a_i) = a_{i+1},

where a_{k+1} is taken to mean a_1.

There are k different expressions for the same cycle; the following all represent the same cycle:

 (a_1\ a_2\ a_3\ \ldots\ a_k) = (a_2\ a_3\ \ldots\ a_k\ a_1) = \cdots = (a_k\ a_1\ a_2\ \ldots\ a_{k-1}).\,

A 1-element cycle such as (3) is the identity permutation.[4] The identity permutation can also be written as the empty cycle, "()".[5]

Permutation as product of cycles[edit]

Let \pi be a permutation of S, and let

 S_1,\ldots, S_k\subset S,\quad k\in\mathbb{N}

be the orbits of \pi. For an orbit S_j (j=1,\ldots,k), let n_j:=|S_j| denote the cardinality of S_j. Also, choose an element a_{1,j}\in S_j, and define

 a_{i+1,j} = \pi(a_{i,j}),\quad\text{for } 1\leq i<n_j;\quad\text{then also }\pi(a_{n_j,j})=a_{1,j}.\,

We can now express \pi as a product of disjoint cycles, namely

 \pi = (a_{1,1}\ \ldots a_{n_1,1}) (a_{1,2}\ \ldots\ a_{n_2,2}) \ldots (a_{1,k}\ \ldots\ a_{n_k,k}).\,

In such an expression, it is typical, but not necessary, to suppress the 1-cycles.[6] Thus, the permutation σ = (2 4 5)(1 6)(3) would be written as (2 4 5)(1 6) provided that it is understood that σ acts on S= {1,...,6}.

Since disjoint cycles commute with each other, the meaning of this expression is independent of the convention used for the order in products of permutations, namely whether the factors in such a product operate rightmost-first (as is usual more generally for function composition), or leftmost-first as some authors prefer. The meaning of individual cycles is also independent of this convention, namely always as described above.

Example[edit]

Here are the 24 elements of the symmetric group on \{1,2,3,4\} expressed using the cycle notation, and grouped according to their conjugacy classes:

 ( )\,
 (1 2), \;(1 3),\; (1 4),\; (2 3),\; (2 4),\; (3 4) (transpositions)
 (1 2 3),\; (1 3 2),\; (1 2 4),\; (1 4 2),\; (1 3 4),\; (1 4 3),\; (2 3 4),\; (2 4 3)
 (1 2)(3 4),\;(1 3)(2 4),\; (1 4)(2 3)
 (1 2 3 4),\; (1 2 4 3),\; (1 3 2 4),\; (1 3 4 2),\; (1 4 2 3),\; (1 4 3 2)

See also[edit]

Notes[edit]

  1. ^ Fraleigh 2002, p. 89; Hungerford 1997, p. 230
  2. ^ Dehn 1930, p. 19
  3. ^ Brualdi 2010, pp. 38-40
  4. ^ Hungerford 1997, p. 231
  5. ^ Johnson 2003, p. 691
  6. ^ Gerstein 1987, p. 240

References[edit]

  • Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Prentice-Hall, ISBN 978-0-13-602040-0 
  • Dehn, Edgar (1960) [1930], Algebraic Equations, Dover 
  • Fraleigh, John (2003), A first course in abstract algebra (7th ed.), Addison Wesley, pp. 88–90, ISBN 978-0-201-76390-4 
  • Gerstein, Larry J. (1987), Discrete Mathematics and Algebraic Structures, W.H. Freeman & Co., ISBN 0-7167-1804-9 
  • Hungerford, Thomas W. (1997), Abstract Algebra: An Introduction, Brooks/Cole, ISBN 978-0-03-010559-3 
  • Johnson, James L. (2003), Probability and Statistics for Computer Science, Wiley Interscience, ISBN 978-0-471-32672-4 

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