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 | + | 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 == |
+ | |||
+ | '''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 22:13, 12 January 2017
A cycle is a type of permutation.
Let be the symmetric group on a set
. Let
be an element of
, and let
be the subgroup of
generated by
. Then
is a cycle if
has exactly one orbit (under the operation of
) which does not consist of a single element. This orbit is called the support of
, and is sometimes denoted
.
Some properties of cycles
Lemma. Let be a family of cycles of
with pairwise disjoint supports
. Then the
commute. The product
is then well defined as
, for
, and
, for
. Let
be the subgroup generated by
. Then the function
is a bijection from
to the orbits of
containing more than one element.
Proof. Suppose and
are of the
. Then
so by symmetry
. This proves that the
commute and justifies the definition of
.
Suppose is a an orbit of
with more than one element, and suppose
. Then by our characterization of
,
must belong to
, for some
; since
is the orbit of
, it follows that
. Thus the mapping
is a surjection from
to the orbits of
with more than one element; since it is evidently injective, it follows that this mapping is a bijection.
Theorem (cycle notation). Let be an element of
. Then there exists a unique set
of cycles of
with pairwise disjoint supports such that
Proof. Let be the subgroup of
generated by
. Let
be the family of nonempty orbits of
. For all
, let
be the restriction of
to
; let
. Then by the lemma,
Since the mapping
must be a bijection from
to the orbits of
, it follows from the lemma that
is unique.