Difference between revisions of "Cycle (permutation)"

Revision as of 14:05, 25 May 2008

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$

@@ Line 3: / Line 3: @@
 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>.
-{{stub}}
+== Some properties of cycles ==
+'''Lemma.''' Let <math>(\zeta_i)_{i \in I}</math> be a family of cycles of <math>S_M</math> with pairwise [[disjoint]] supports <math>(S_i)_{i \in I}</math>.  Then the <math>\zeta_i</math> commute.  The product <math>\sigma = \prod_{i\in I} \zeta_i</math> is then well defined as <math>\sigma(x) = \zeta_i(x)</math>, for <math>x\in S_i</math>, and <math>x</math>, for <math>x \notin \bigcup_{i\in I} S_i</math>.  Let <math>\bar{\sigma}</math> be the [[subgroup]] generated by <math>\sigma</math>.  Then the function <math>i \mapsto S_i</math> is a [[bijection]] from <math>I</math> to the orbits of <math>\bar\sigma</math> containing more than one element.
+''Proof.''  Suppose <math>\zeta_a</math> and <math>\zeta_b</math> are of the <math>\zeta_i</math>.  Then
+<cmath>
+\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} </cmath>
+so by symmetry <math>\zeta_a\zeta_b = \zeta_b \zeta_a</math>.  This proves that the <math>\zeta_i</math> commute and justifies the definition of <math>\prod_{i\in I} \zeta_i</math>.
+Suppose <math>S</math> is a an orbit of <math>\bar\sigma</math> with more than one element, and suppose <math>x\in S</math>.  Then by our characterization of <math>\prod_{i \in I}</math>, <math>x</math> must belong to <math>S_i</math>, for some <math>i\in I</math>; since <math>S</math> is the orbit of <math>x</math>, it follows that <math>S_i = S</math>.  Thus the mapping <math>i \mapsto S_i</math> is a [[surjection]] from <math>I</math> to the orbits of <math>\bar\sigma</math> with more than one element; since it is evidently [[injective]], it follows that this mapping is a bijection.  <math>\blacksquare</math>
+'''Theorem (cycle notation).'''  Let <math>\sigma</math> be an element of <math>S_M</math>.  Then there exists a unique set <math>C</math> of cycles of <math>S_M</math> with pairwise disjoint supports such that
+<cmath> \sigma = \prod_{\zeta \in C} \zeta. </cmath>
+''Proof.''  Let <math>\bar\sigma</math> be the subgroup of <math>S_M</math> generated by <math>\sigma</math>.  Let <math>(O_i)_{i \in I}</math> be the family of nonempty orbits of <math>\bar\sigma</math>.  For all <math>i \in I</math>, let <math>\zeta_i</math> be the restriction of <math>\sigma</math> to <math>O_i</math>; let <math>C = \bigcup_{i\in I} \{\zeta_i\}</math>.  Then by the lemma,
+<cmath> \sigma = \prod_{\zeta \in C} \zeta. </cmath>
+Since the mapping <math>i\mapsto O_i</math> must be a bijection from <math>I</math> to the orbits of <math>\bar\sigma</math>, it follows from the lemma that <math>C</math> is unique.  <math>\blacksquare</math>
 == See also ==

Page

Toolbox

Search

Difference between revisions of "Cycle (permutation)"

Revision as of 14:05, 25 May 2008

Some properties of cycles

See also