Difference between revisions of "Cycle (permutation)"

Latest revision as of 21:13, 12 January 2017

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$

@@ Line 1: / Line 1: @@
 A '''cycle''' is a type of [[permutation]].
-Let <math>S_M</math> be the symmetric group on a [[set]] <math>M</math>.  Let <math>\zeta</math> be an element of <math>S_M</math>, and let <math>\bar{\zeta}</math> be the [[subgroup]] of <math>S_M</math> generated by <math>\zeta</math>.  Then <math>\zeta</math> is a '''cycle''' if <math>M</math> has exactly one [[orbit]] (under the operation of <math>\bar{\zeta}</math>) which does not consist of a single [[element]].   This orbit is called the ''support'' of <math>\zeta</math>, and is sometimes denoted <math>\text{supp}(\zeta})</math>.
+Let <math>S_M</math> be the symmetric group on a [[set]] <math>M</math>.  Let <math>\zeta</math> be an element of <math>S_M</math>, and let <math>\bar{\zeta}</math> be the [[subgroup]] of <math>S_M</math> generated by <math>\zeta</math>.  Then <math>\zeta</math> is a '''cycle''' if <math>M</math> has exactly one [[orbit]] (under the operation of <math>\bar{\zeta}</math>) which does not consist of a single [[element]].   This orbit is called the ''support'' of <math>\zeta</math>, and is sometimes denoted <math>\text{supp}(\zeta)</math>.
 == Some properties of cycles ==

Page

Toolbox

Search

Difference between revisions of "Cycle (permutation)"

Latest revision as of 21:13, 12 January 2017

Some properties of cycles

See also