Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Cycle (permutation)

(Redirected from Cycle)

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)$.

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$

See also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Cycle_(permutation)&oldid=82294"