Cycle notation

From Wikipedia, the free encyclopedia

For the cyclic decomposition of graphs, see Cycle decomposition (graph theory). For cycling terminology, see glossary of bicycling.

In combinatorial mathematics, the cycle notation is a useful convention for writing down a permutation in terms of its constituent cycles.^[1] This is also called circular notation and the permutation called a cyclic or circular permutation.^[2]

Definition

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.^[3] The identity permutation can also be written as an empty cycle, "()".^[4]

Permutation as product of cycles

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$ with more than 1 element. Consider an element $S_{j}$ , $j=1,\ldots ,k$ , let $n_{j}$ denote the cardinality of $S_{j}$ , $|S_{j}|$ = $n_{j}$ . Also, choose an $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}}).\,$

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

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:

$()\,$

$(12),\;(13),\;(14),\;(23),\;(24),\;(34)$ (transpositions)

$(123),\;(132),\;(124),\;(142),\;(134),\;(143),\;(234),\;(243)$

$(12)(34),\;(13)(24),\;(14)(23)$

$(1234),\;(1243),\;(1324),\;(1342),\;(1423),\;(1432)$

Notes

↑ Fraleigh 2002:89; Hungerford 1997:230
↑ Dehn 1930:19
↑ Hungerford 1997:231
↑ Johnson 2003:691

References

Dehn, Edgar (1960) [1930], Algebraic Equations, Dover .
Fraleigh, John (2003), A first course in abstract algebra (7th ed.), Addison Wesley, p. 88–90, ISBN 978-0-201-76390-4 .
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.

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.