AoPSWiki

Looking for a challenging geometry text? Preparing for MATHCOUNTS or the AMC exams? Check out Art of Problem Solving's Introduction to Geometry by Richard Rusczyk.

Personal tools

Log in

Search

Toolbox

Cycle

From AoPSWiki

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_...$ 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 "http://www.artofproblemsolving.com/Wiki/index.php/Cycle"

Category: Group theory

Try our innovative online adaptive learning system, Alcumus.
Over 1100 problems and 60+ video lessons. FREE!

© Copyright 2008 AoPS Incorporated. All Rights Reserved. • Foundation • Privacy • Contact Us