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

Difference between revisions of "Cycle (permutation)"

(stub)
 
m
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
A '''cycle''' is a type of [[permutation]].
 
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>.
  
−
{{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 ==
 
== See also ==

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$

See also

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