### Cycle decomposition

The points which form the first row need not be written in their natural order,
e.g.
Keeping this in mind, we call a permutation * pÎS*_{n} a *cyclic*
permutation or a *cycle* if and only if it can be written
in the form
where *r ³1*.
In order to emphasize *r* we also call it an *r-cycle* .
We note that in this case the orbits of the subgroup generated by
this permutation are the following
subsets of * *__n__: * {i*_{1}, ...,i_{r} }, {i_{r+1} }, ..., {i_{n} }.
We therefore abbreviate
this cycle by *(i*_{1}, ...,i_{r})(i_{r+1}) ...(i_{n}),
where the points which are *cyclically permuted* are put together in
round brackets. For example
Commas which seperate the points may be omitted if no confusion
can arise (e.g if *n £10*), and 1-cycles can be left out if it is clear
which *n* is meant. Hence we can write * p=(i*_{1} ...i_{r}) for the
*r*-cycle introduced above. This cycle * p* can also be expressed in
terms of *i*_{1}
alone: * p=(i*_{1} pi_{1} ...p^{r-1}i_{1}). Using all these
abbreviations and denoting by *1:=(1) ...(n)* the identity element,
we obtain for example
*S*_{ 3}= {1,(12),(13),(23),(123),(132) }.

There are the elements of the
symmetric group * S*_{n}
in cycle notation.
The notation for a cyclic permutation is not uniquely determined, since
*
(i*_{1} ...i_{r})=(i_{2} ...i_{r} i_{1})= ...=(i_{r} i_{1} ...i_{r-1}).

2-cycles are called *transpositions* .
The *order*
of a cycle
*(i*_{1} ...i_{r}), i.e. the order of the cyclic group * á(i*_{1}
...i_{r}) ñ generated by this cycle, is equal to its *length*
:
*
| á(i*_{1} ...i_{r}) ñ | =r.

Two cycles * p* and * r* are called *disjoint* ,
if the two sets
of points which are not fixed by * p* and * r* are disjoint sets.
Notice that, for example, *1=(1)(2)(3) and (123)* are disjoint cycles.
Disjoint cycles * p* and * r* commute, i.e. * pr= rp*.
(We read compositions of mappings from right to left, so that
*( pr)x= p( rx)*.) *Each permutation of a
finite set can be
written as a product of pairwise different disjoint cycles, e.g.*
There are some more examples for the
cycle decomposition of a
permutation.
The disjoint cyclic factors * not =1* of * pÎS*_{n} are
uniquely determined by * p* and therefore we call these factors together
with the
fixed point
cycles of * p* *the cyclic factors*
of * p*.
Let *c( p)* denote the number of these cyclic factors of * p*
(including 1-cycles), let *l*_{ n} be their lengths, * nÎ *__
c( p)__ (recall that * *__c( p)__= {1, ...,c( p) }),
choose, for each * n* an element *j*_{ n} of the * n*-th cyclic
factor. Then

*
p= Õ*_{ nÎ c( p)}
(j_{ n} pj_{ n} ...p^{l n-1}j_{ n}).

This notation becomes uniquely determined if we choose the *j*_{ n} so
that
*
" m Î ***N** : j_{ n}
£p^{m}j_{ n}, and
" n<c( p) : j_{ n}<j_{ n+1}.

If this holds, then the notation as was given above
is called the *(standard) cycle notation*
for * p*. We note in passing that the sets * {j*_{ n}, pj_{ n},
..., p^{l n-1}j_{ n} } of points which
are cyclically permuted by * p*
are just the orbits of the cyclic group * ápñ* generated
by * p*.

harald.fripertinger@kfunigraz.ac.at,

last changed: August 28, 2001