Cycle (permutation)

A cycle is a type of permutation.

Let $S_M$ be the symmetric group on a set $M$ . Let $\zeta$ be an element of $S_M$ , and let $\bar{\zeta}$ be the subgroup of $S_M$ generated by $\zeta$ . Then $\zeta$ is a cycle if $M$ has exactly one orbit (under the operation of $\bar{\zeta}$ ) which does not consist of a single element. This orbit is called the support of $\zeta$ , and is sometimes denoted $\text{supp}(\zeta})$ (Error compiling LaTeX. Unknown error_msg).

Some properties of cycles

Lemma. Let $(\zeta_i)_{i \in I}$ be a family of cycles of $S_M$ with pairwise disjoint supports $(S_i)_{i \in I}$ . Then the $\zeta_i$ commute. The product $\sigma = \prod_{i\in I} \zeta_i$ is then well defined as $\sigma(x) = \zeta_i(x)$ , for $x\in S_i$ , and $x$ , for $x \notin \bigcup_{i\in I} S_i$ . Let $\bar{\sigma}$ be the subgroup generated by $\sigma$ . Then the function $i \mapsto S_i$ is a bijection from $I$ to the orbits of $\bar\sigma$ containing more than one element.

Proof. Suppose $\zeta_a$ and $\zeta_b$ are of the $\zeta_i$ . Then $\zeta_a \zeta_b(x) = \begin{cases} \zeta_a(x),& x \in S_a, \\ \zeta_b (x), &x\in S_b , \\ x, & x \notin S_a \cup S_b, \end{cases}$ so by symmetry $\zeta_a\zeta_b = \zeta_b \zeta_a$ . This proves that the $\zeta_i$ commute and justifies the definition of $\prod_{i\in I} \zeta_i$ .

Suppose $S$ is a an orbit of $\bar\sigma$ with more than one element, and suppose $x\in S$ . Then by our characterization of $\prod_{i \in I}$ , $x$ must belong to $S_i$ , for some $i\in I$ ; since $S$ is the orbit of $x$ , it follows that $S_i = S$ . Thus the mapping $i \mapsto S_i$ is a surjection from $I$ to the orbits of $\bar\sigma$ with more than one element; since it is evidently injective, it follows that this mapping is a bijection. $\blacksquare$

Theorem (cycle notation). Let $\sigma$ be an element of $S_M$ . Then there exists a unique set $C$ of cycles of $S_M$ with pairwise disjoint supports such that $\sigma = \prod_{\zeta \in C} \zeta.$

Proof. Let $\bar\sigma$ be the subgroup of $S_M$ generated by $\sigma$ . Let $(O_i)_{i \in I}$ be the family of nonempty orbits of $\bar\sigma$ . For all $i \in I$ , let $\zeta_i$ be the restriction of $\sigma$ to $O_i$ ; let $C = \bigcup_{i\in I} \{\zeta_i\}$ . Then by the lemma, $\sigma = \prod_{\zeta \in C} \zeta.$ Since the mapping $i\mapsto O_i$ must be a bijection from $I$ to the orbits of $\bar\sigma$ , it follows from the lemma that $C$ is unique. $\blacksquare$

Page

Toolbox

Search

Cycle (permutation)

Some properties of cycles

See also