avewright/proofwiki-math huggingface dataset:
Theorem: Orbit-Stabilizer Theorem

Let $G$ be a group which acts on a finite set $X$.
Let $x \in X$.
Let $\Orb x$ denote  the orbit of $x$.
Let $\Stab x$ denote the stabilizer of $x$ by $G$.
Let $\index G {\Stab x}$ denote the index of $\Stab x$ in $G$.
Then:
:$\order {\Orb x} = \index G {\Stab x} = \dfrac {\order G} {\order {\Stab x} }$

Proof:
Let $x \in X$.
Let $\phi: \Orb x \to G \mathbin / \Stab x$ be a mapping from the orbit of $x$ to the left coset space of $\Stab x$ defined as:
:$\forall g \in G: \map \phi {g * x} = g \, \Stab x$
where $*$ is the group action.
Note: this is ''not'' a homomorphism because $\Orb x$ is not a group.
Suppose $g * x = h * x$ for some $g, h \in G$.
Then:
{{begin-eqn}}
{{eqn | l = h^{-1} * g * x
      | r = h^{-1} * h * x
      | c = applying $h^{-1}$ to both sides
}}
{{eqn | l = \paren{h^{-1} g } * x
      | r = \paren{h^{-1} h } * x
      | c = {{GroupActionAxiom|1}}
}}
{{eqn | r = e * x
      | c = {{Defof|Inverse Element}}
}}
{{eqn | r = x
      | c = {{GroupActionAxiom|2}}
}}
{{end-eqn}}
Thus:
:$h^{-1} g \in \Stab x$
so by Left Coset Space forms Partition:
:$g \, \Stab x = h \, \Stab x$
demonstrating that $\phi$ is well-defined.
Let $\map \phi {g_1 * x} = \map \phi {g_2 * x}$ for some $g_1, g_2 \in G$.
Then:
:$g_1 \, \Stab x = g_2 \, \Stab x$
and so by Left Coset Space forms Partition:
:$g_2^{-1} g_1 \in \Stab x$
So by definition of $\Stab x$:
:$x = \paren{g_2^{-1} g_1 }* x$
Thus:
{{begin-eqn}}
{{eqn | l = g_2 * x
      | r = g_2 * \paren {g_2^{-1} g_1 * x}
      | c = applying $g_2$ to both sides
}}
{{eqn | r = \paren {g_2 g_2^{-1} g_1} * x
      | c = {{GroupActionAxiom|1}}
}}
{{eqn | r = g_1 * x
      | c = 
}}
{{end-eqn}}
thus demonstrating that $\phi$ is injective.
As the left coset $g \, \Stab x$ is $\map \phi {g * x}$ by definition of $\phi$, it follows that $\phi$ is a surjection.
The result follows.
{{qed}}
Theorem: Group Acts on Itself

Let $\struct {G, \circ}$ be a group whose identity is $e$.
Then $\struct {G, \circ}$ acts on itself by the rule:
:$\forall g, h \in G: g * h = g \circ h$

Proof:
Follows directly from the group axioms and the definition of a group action.
{{qed}}
Theorem: Action of Group on Coset Space is Group Action

Let $G$ be a group whose identity is $e$.
Let $H$ be a subgroup of $G$.
Let $*: G \times G / H \to G / H$ be the action on the (left) coset space:
:$\forall g \in G, \forall g' H \in G / H: g * \paren {g' H} := \paren {g g'} H$
Then $G$ is a group action.

Proof:
{{begin-eqn}}
{{eqn | l = a * \paren {b * g' H}
      | r = a * \paren {\paren {b g'} H}
      | c = Definition of $*$
}}
{{eqn | r = \paren {a \paren {b g'} } H
      | c = Definition of $*$
}}
{{eqn | r = \paren {\paren {a b } g' } H
      | c = {{Group-axiom|1}}
}}
{{eqn | r = \paren {a b} \paren{g' H }
      | c = Subset Product within Semigroup is Associative/Corollary
}}
{{end-eqn}}
demonstrating that $*$ satisfies {{GroupActionAxiom|2}}.
Then:
{{begin-eqn}}
{{eqn | l = e * g' H
      | r = \paren {e g'} H
      | c = Definition of $*$
}}
{{eqn | r = g'H
      | c = {{Group-axiom|2}}
}}
{{end-eqn}}
demonstrating that $*$ satisfies {{GroupActionAxiom|1}}.
{{qed}}
Theorem: Group Action on Sets with k Elements

Let $\struct {G, \circ}$ be a finite group whose identity is $e$.
Let $\Bbb S = \set {S \subseteq G: \card S = k}$, that is, the set of all of subsets of $G$ which have exactly $k$ elements.
Let $G$ act on $\Bbb S$ by the rule:
:$\forall S \in \Bbb S: g * S = g S = \set {x \in G: x = g s: s \in S}$
This is a group action, and:
:$\forall S \in \Bbb S: \order {\Stab S} \divides \card S$
where $\Stab S$ denotes the stabilizer of $S$ by $G$.

Proof:
First it is necessary to prove that this is a group action.
The action is the same as the one defined in Group Action on Coset Space, but this time we are limiting ourselves to the subsets of $G$ which have the same number of elements.
From the result in Group Action on Coset Space, we only have to prove that:
:$\card {g S} = \card S$
This follows directly from Order of Subset Product with Singleton.
It remains to be shown that:
:$\order {\Stab S} \divides \card S$
By definition of stabilizer:
:$\Stab S = \set {g \in G: g S = S}$
It follows that:
:$\forall s \in S: g s \in S$
Then:
:$\Stab S s \subseteq S$
Thus:
:$\card {\Stab S s} \le \card S$
We have from Stabilizer is Subgroup that the stabilizer contains the identity:
:$e \in \Stab S \le G$
It therefore follows that:
:$s \in S \implies s \in \Stab S s$
Thus:
:$\ds S = \bigcup_{t \mathop \in S} \Stab S t$
By Congruence Class Modulo Subgroup is Coset and Right Coset Space forms Partition, distinct right cosets are disjoint.
Thus $S$ consists of a union of disjoint right cosets of $\Stab S$.
Thus $\ds \bigcup_{t \mathop \in S} \Stab S t$ is a partition of $S$.
Therefore:
:$\forall s \in S: \card {\Stab S s} \divides \card S$
As we have:
:$\forall s \in S: \card {\Stab S s} = \order {\Stab S}$
the result follows:
:$\card {\Stab S} \divides \card S$
{{qed}}
Theorem: Group Action on Subgroup of Symmetric Group

Let $S_n$ be the symmetric group of $n$ elements.
Let $H$ be a subgroup of $S_n$.
Let $X$ be any set with $n$ elements.
Then $H$ acts on $X$ as a group of transformations on $X$.

Proof:
The identity permutation takes each element of $X$ to itself, thus fulfilling {{GroupActionAxiom|2}}.
The group operation in $S_n$ ensures fulfilment of {{GroupActionAxiom|1}}.
{{qed}}
Theorem: Quotient of Transformation Group acts Effectively

Let $G$ be a transformation group (which may or may not be effective) acting on $X$.
Then the quotient group $G / G_0$, where $G_0$ is the kernel, ''does'' act effectively on $X$.

Proof:
Let $g G_0 \in G / G_0$.
Let $x \in X$.
Let $G / G_0$ act on $X$ by the rule:
:$g G_0 * x := g x$
Then by definition of effective transformation group:
:$G / G_0$ acts effectively on $X$ {{iff}}:
::$g G_0 * x = x \implies g G_0 = G_0$
Suppose $g G_0 * x = g x = x$.
We want to show $g G_0 = G_0$.
By definition of kernel of group action of $G$ on $X$:
:$g * x = gx = x \iff g \in G_0$
So $gG_0 = G_0$ by closure of subgroups.
Hence the result.
{{qed}}
Theorem: Condition for Group to Act Effectively on Left Coset Space

Let $G$ be a group whose identity is $e$.
Let $H$ be a subgroup of $G$.
Then $G$ acts effectively on the left coset space $G / H$ {{iff}}:
:$\ds \bigcap_{a \mathop \in G} H^a = \set e$
where $H^a$ denotes the conjugate of $H$ by $a$.

Proof:
$G$ acts effectively on the left coset space $G / H$ {{iff}} $a H \mapsto g a H$ is faithful, {{iff}}:
{{begin-eqn}}
{{eqn | q = \forall g \in G: \forall a H \in G / H
      | l = g a H = a H
      | o = \implies
      | r = g = e
      | c = {{Defof|Faithful Group Action}}
}}
{{eqn | ll= \leadstoandfrom
      | q = \forall g \in G: \forall a \in G
      | l = a^{-1} g a \in H
      | o = \implies
      | r = g = e
      | c = Left Cosets are Equal iff Product with Inverse in Subgroup
}}
{{eqn | ll= \leadstoandfrom
      | q = \forall g \in G: \forall a \in G
      | l = g \in a H a^{-1}
      | o = \implies
      | r = g = e
}}
{{eqn | ll= \leadstoandfrom
      | q = \forall g \in G: \forall a \in G
      | l = g \in H^a
      | o = \implies
      | r = g = e
      | c = {{Defof|Conjugate of Group Subset}}
}}
{{eqn | ll= \leadstoandfrom
      | l = \bigcap_{a \mathop \in G} H^a
      | r  = \set e
      | c = {{Defof|Intersection of Family}}
}}
{{end-eqn}}
{{qed}}
Theorem: Conjugacy Action on Identity

Let $G$ be a group whose identity is $e$.
For the conjugacy action:
:$\order {\Orb e} = 1$
and thus:
:$\Stab e = G$

Proof:
{{begin-eqn}}
{{eqn | l = g * e
      | r = g e g^{-1}
      | c = 
}}
{{eqn | r = g g^{-1}
      | c = 
}}
{{eqn | r = e
      | c = 
}}
{{end-eqn}}
So the only conjugate of $e$ is $e$ itself.
Thus:
:$\Orb e = \set e$
and so:
:$\order {\Orb e} = 1$
From the Orbit-Stabilizer Theorem, it follows immediately that:
:$\Stab e = G$
{{qed}}
Theorem: Cauchy's Lemma (Group Theory)

Let $\struct {G, \circ}$ be a group of finite order whose identity is $e$.
Let $p$ be a prime number which divides the order of $G$.
Then $\struct {G, \circ}$ has an element of order $p$.

Proof:
Let $\order G = n$ such that $p \divides n$.
Let:
:$X = \set {\tuple {a_1, a_2, \ldots, a_p} \in G^p: a_1 a_2 \cdots a_p = e}$
where $G^p$ is the cartesian product $\underbrace {G \times G \times \cdots \times G}_p$.
The first $p - 1$ coordinates of an element of $X$ can be chosen arbitrarily.
The last coordinate is determined by the fact that:
:$a_1 a_2 \cdots a_{p - 1} = a_p^{-1}$
So from the Product Rule for Counting, it follows that:
:$\card X = n^{p - 1}$
Let $C_p$ be a cyclic group of order $p$ generated by the element $c$.
Let $C_p$ act on the set $X$ by the rule:
:$c * \tuple {a_1, a_2, \ldots, a_p} = \tuple {a_2, a_3, \ldots, a_p, a_1}$
By the Orbit-Stabilizer Theorem, the number of elements in any orbit is a divisor of the order of $C_p$, which is $p$.
As $p$ is prime, an orbit has either $p$ elements or $1$ element by definition.
Let $r$ be the number of orbits with one element.
Let $s$ be the number of orbits with $p$ elements.
Then by the Partition Equation:
:$r + s p = n^{p - 1} = \card X$
By hypothesis, $p \divides n$, so:
:$r + s p = n^{p - 1} \implies p \divides r$
We know that $r \ne 0$ because, for example, the orbit of $\tuple {e, e, \ldots, e} \in X$ has only one element.
So there must be at least $p$ orbits with only one element.
Each such element has the form $\tuple {a, a, \ldots, a} \in X$ so $a^p = e$.
So $G$ contains at least $p$ elements $x$ satisfying $x^p = e$.
So $G$ contains an element $a \ne e$ such that $a^p = e$.
That is, $a$ must have order $p$.
{{qed}}
Theorem: Cauchy's Lemma (Group Theory)

Let $\struct {G, \circ}$ be a group of finite order whose identity is $e$.
Let $p$ be a prime number which divides the order of $G$.
Then $\struct {G, \circ}$ has an element of order $p$.

Proof:
By {{Corollary|First Sylow Theorem}}, $G$ has subgroups of order $p^r$ for all $r$ such that $p^r \divides \order G$.
Thus $G$ has at least one subgroup $H$ of order $p$.
As a Prime Group is Cyclic, $H$ is a cyclic group.
Thus by definition $H$ has an element of order $p$.
Hence the result.
{{qed}}
Theorem: Transposition is Self-Inverse

All transpositions are self-inverse.

Proof:
Let $\pi = \begin{bmatrix} k_1 & k_2 \end{bmatrix}$ be a transposition.
Writing $\pi \pi$ in cycle notation gives:
:$\begin{bmatrix} k_1 & k_2 \end{bmatrix} \begin{bmatrix} k_1 & k_2 \end{bmatrix}$
from which we see that $k_1 \to k_2 \to k_1$ and $k_2 \to k_1 \to k_2$.
The result follows from the definition of self-inverse.
{{qed}}
Category:Symmetric Groups
lehv6tztngn5ci5vftba2lh34nrl8ch
Theorem: Conjugates of Transpositions

Let $k_1, k_2, k_3 \in \set {1, 2, \ldots, n}$.
Then:
{{begin-eqn}}
{{eqn | n = 1
      | l = \begin{pmatrix} k_1 & k_2 \end{pmatrix}
      | r = \begin{pmatrix} k_3 & k_2 \end{pmatrix} \begin{pmatrix} k_1 & k_3 \end{pmatrix} \begin{pmatrix} k_3 & k_2 \end{pmatrix}
}}
{{eqn | n = 2
      | l = \begin{pmatrix} k_1 & k_2 \end{pmatrix}
      | r = \begin{pmatrix} k_3 & k_1 \end{pmatrix} \begin{pmatrix} k_3 & k_2 \end{pmatrix} \begin{pmatrix} k_3 & k_1 \end{pmatrix}
}}
{{end-eqn}}

Proof:
$(1):$ Calculating the product of $\begin{pmatrix} k_3 & k_2 \end{pmatrix} \begin{pmatrix} k_1 & k_3 \end{pmatrix} \begin{pmatrix} k_3 & k_2 \end{pmatrix}$:
:: $k_1 \to k_3 \to k_2$
:: $k_2 \to k_3 \to k_1$
:: $k_3 \to k_2 \to k_3$
hence the result.
{{qed|lemma}}
$(2):$ Calculating the product of $\begin{pmatrix} k_3 & k_1 \end{pmatrix} \begin{pmatrix} k_3 & k_2 \end{pmatrix} \begin{pmatrix} k_3 & k_1 \end{pmatrix}$:
:: $k_1 \to k_3 \to k_2$
:: $k_2 \to k_3 \to k_1$
:: $k_3 \to k_1 \to k_3$
hence the result.
{{qed}}
Category:Symmetric Groups
Category:Conjugacy
Category:Transpositions
tipv1y1r4uk2r1eiima2p6sc1i1jqsa
Theorem: K-Cycle can be Factored into Transpositions

Every $k$-cycle can be factorised into the product of $k - 1$ transpositions.
This factorisation is not unique.

Proof:
The cycle $\begin{pmatrix} 1 & 2 & \ldots & k \end{pmatrix}$ has the factorisation:
:$\begin{pmatrix} 1 & 2 & \ldots & k \end{pmatrix} = \begin{pmatrix} 1 & k \end{pmatrix} \ldots \begin{pmatrix} 1 & 3 \end{pmatrix} \begin{pmatrix} 1 & 2 \end{pmatrix}$
Therefore, the general $k$-cycle $\begin{pmatrix} i_1 & i_2 & \ldots & i_k \end{pmatrix}$ has the factorisation:
:$\begin{pmatrix} i_1 & i_2 & \ldots & i_k \end{pmatrix} = \begin{pmatrix} i_1 & i_k \end{pmatrix} \ldots \begin{pmatrix} i_1 & i_3 \end{pmatrix} \begin{pmatrix} i_1 & i_2 \end{pmatrix}$
The cycle $\begin{pmatrix} 1 & 2 & \ldots & k \end{pmatrix}$ also has the factorisation:
:$\begin{pmatrix} 1 & 2 & \ldots & k \end{pmatrix} = \begin{pmatrix} 1 & 2 \end{pmatrix} \begin{pmatrix} 2 & 3 \end{pmatrix} \ldots \begin{pmatrix} k - 1 & k \end{pmatrix}$
Therefore, the general $k$-cycle $\begin{pmatrix} i_1 & i_2 & \ldots & i_k \end{pmatrix}$ also has the factorisation:
:$\begin{pmatrix} i_1 & i_2 & \ldots & i_k \end{pmatrix} = \begin{pmatrix} i_1 & i_2 \end{pmatrix} \begin{pmatrix} i_2 & i_3 \end{pmatrix} \ldots \begin{pmatrix} i_{k - 1} & i_k \end{pmatrix}$
{{qed}}
Theorem: Sign of Permutation is Plus or Minus Unity

Let $n \in \N$ be a natural number.
Let $\N_n$ denote the set of natural numbers $\set {1, 2, \ldots, n}$.
Let $S_n$ denote the symmetric group on $n$ letters.
Let $\sequence {x_k}_{k \mathop \in \N_n}$ be a finite sequence in $\R$.
Let $\pi \in S_n$.
Let $\map {\Delta_n} {x_1, x_2, \ldots, x_n}$ be the product of differences of $\tuple {x_1, x_2, \ldots, x_n}$.
Let $\map \sgn \pi$ be the sign of $\pi$.
Let $\pi \cdot \map {\Delta_n} {x_1, x_2, \ldots, x_n}$ be defined as:
:$\pi \cdot \map {\Delta_n} {x_1, x_2, \ldots, x_n} := \map {\Delta_n} {x_{\map \pi 1}, x_{\map \pi 2}, \ldots, x_{\map \pi n} }$
Then either:
:$\pi \cdot \Delta_n = \Delta_n$
or:
:$\pi \cdot \Delta_n = -\Delta_n$
That is:
:<nowiki>$\map \sgn \pi = \begin {cases}
1 & :\pi \cdot \Delta_n = \Delta_n \\
-1 & : \pi \cdot \Delta_n = -\Delta_n
\end {cases}$</nowiki>
Thus:
:$\pi \cdot \Delta_n = \map \sgn \pi \Delta_n$

Proof:
If $\exists i, j \in \N_n$ such that $x_i = x_j$, then $\map {\Delta_n} {x_1, x_2, \ldots, x_n} = 0$ and the result follows trivially.
So, suppose all the elements $x_k$ are distinct.
Let us use $\Delta_n$ to denote $\map {\Delta_n} {x_1, x_2, \ldots, x_n}$.
Let $1 \le a < b \le n$.
Then $x_a - x_b$ is a divisor of $\Delta_n$.
Then $x_{\map \pi a} - x_{\map \pi b}$ is a factor of $\pi \cdot \Delta_n$.
There are two possibilities for the ordering of $\map \pi a$ and $\map \pi b$:
Either $\map \pi a < \map \pi b$ or $\map \pi a > \map \pi b$.
If the former, then $x_{\map \pi a} - x_{\map \pi b}$ is a factor of $\Delta_n$.
If the latter, then $-\paren {x_{\map \pi a} - x_{\map \pi b} }$ is a factor of $\Delta_n$.
The same applies to all factors of $\Delta_n$.
Thus:
{{begin-eqn}}
{{eqn | l = \pi \cdot \Delta_n
      | r = \pi \cdot \prod_{1 \mathop \le i \mathop < j \mathop \le n} \paren {x_i - x_j}
      | c = 
}}
{{eqn | r = \pm \prod_{1 \mathop \le i \mathop < j \mathop \le n} \paren {x_i - x_j}
      | c = 
}}
{{eqn | r = \pm \Delta_n
      | c = 
}}
{{end-eqn}}
{{Qed}}
Theorem: Parity Function is Homomorphism

Let $S_n$ denote the symmetric group on $n$ letters.
Let $\pi \in S_n$.
Let $\map \sgn \pi$ be the sign of $\pi$.
Let the parity function of $\pi$ be defined as:
:Parity of $\pi = \begin {cases} \mathrm {Even} & : \map \sgn \pi = 1 \\ \mathrm {Odd} & : \map \sgn \pi = -1 \end {cases}$
The mapping $\sgn: S_n \to C_2$, where $C_2$ is the cyclic group of order 2, is a homomorphism.

Proof:
We need to show that:
:$\forall \pi, \rho \in S_n: \map \sgn \pi \, \map \sgn \rho = \map \sgn {\pi \rho}$
Let $\Delta_n$ be an arbitrary product of differences.
{{begin-eqn}}
{{eqn | l = \map \sgn {\pi \rho} \Delta_n
      | r = \pi \rho \cdot \Delta_n
      | c = {{Defof|Sign of Permutation}}
}}
{{eqn | r = \pi \cdot \paren {\rho \cdot \Delta_n}
      | c = Permutation on Polynomial is Group Action
}}
{{eqn | r = \pi \cdot \paren {\map \sgn \rho \cdot \Delta_n}
      | c = {{Defof|Sign of Permutation}}
}}
{{eqn | r = \pi \, \map \sgn \rho \cdot \Delta_n
      | c = Permutation on Polynomial is Group Action
}}
{{eqn | r = \map \sgn \pi \, \map \sgn \rho \Delta_n
      | c = {{Defof|Sign of Permutation}}
}}
{{end-eqn}}
As $\struct {\set {1, -1}, \times}$ is the parity group, the result follows immediately.
{{Qed}}
Theorem: Permutation on Polynomial is Group Action

Let $n \in \Z: n > 0$.
Let $F_n$ be the set of all polynomials in $n$ variables $x_1, x_2, \ldots, x_n$:
:$F = \set {\map f {x_1, x_2, \ldots, x_n}: f \text{ is a polynomial in $n$ variables} }$
Let $S_n$ denote the symmetric group on $n$ letters.
Let $*: S_n \times F \to F$ be the mapping defined as:
:$\forall \pi \in S_n, f \in F: \pi * \map f {x_1, x_2, \ldots, x_n} = \map f {x_{\map \pi 1}, x_{\map \pi 2}, \ldots, x_{\map \pi n} }$
Then $*$ is a group action.

Proof:
Let $\pi, \rho \in S_n$.
Let $\pi * f$ be the permutation on the polynomial $f$ by $\pi$.
Let $e \in S_n$ be the identity of $S_n$.
From Symmetric Group is Group:
:$e * f = f$
thus fulfilling {{GroupActionAxiom|1}}.
Then we have that:
{{begin-eqn}}
{{eqn | l = \paren {\pi \circ \rho} * f
      | r = \map \pi {\rho * f}
      | c = 
}}
{{eqn | r = \pi * \paren {\rho * f}
      | c = 
}}
{{end-eqn}}
thus fulfilling {{GroupActionAxiom|2}}
{{qed}}
Theorem: Parity of Inverse of Permutation

Let $S_n$ denote the symmetric group on $n$ letters.
Then:
:$\forall \pi \in S_n: \map \sgn \pi = \map \sgn {\pi^{-1} }$

Proof:
From Parity Function is Homomorphism:
:$\map \sgn {I_{S_n} } = 1$
Thus:
:$\pi \pi^{-1} = I_{S_n} \implies \map \sgn \pi \, \map \sgn {\pi^{-1} } = 1$
The result follows immediately.
{{qed}}
Theorem: Parity of Conjugate of Permutation

Let $S_n$ denote the symmetric group on $n$ letters.
Then:
:$\forall \pi, \rho \in S_n: \map \sgn {\pi \rho \pi^{-1} } = \map \sgn \rho$
where $\map \sgn \pi$ is the sign of $\pi$.

Proof:
As $\map \sgn \pi = \pm 1$ for any $\pi \in S_n$, we can apply the laws of commutativity and associativity:
{{begin-eqn}}
{{eqn | l = \map \sgn \pi \, \map \sgn \rho
      | r = \map \sgn \rho \, \map \sgn \pi
      | c = 
}}
{{eqn | ll= \leadsto
      | l = \map \sgn \pi \, \map \sgn \rho \, \map \sgn {\pi^{-1} }
      | r = \map \sgn \rho \, \map \sgn \pi \, \map \sgn {\pi^{-1} }
      | c = 
}}
{{eqn | ll= \leadsto
      | l = \map \sgn {\pi \rho \pi^{-1} }
      | r = \map \sgn \rho
      | c = Parity Function is Homomorphism
}}
{{end-eqn}}
{{Qed}}
Theorem: Parity of K-Cycle

Let $\pi$ be a $k$-cycle.
Then:
:$\map \sgn \pi = \begin{cases} 1 & : k \ \text {odd} \\ -1 & : k \ \text {even} \end{cases}$
Thus:
:$\map \sgn \pi = \paren {-1}^{k - 1}$
or equivalently:
:$\map \sgn \pi = \paren {-1}^{k + 1}$

Proof:
From Transposition is of Odd Parity, any transposition is of odd parity.
From K-Cycle can be Factored into Transpositions, we see that a $k$-cycle is the product of $k - 1$ transpositions.
Thus $\pi$ is even {{iff}} $k$ is odd.
{{qed}}
Theorem: Alternating Group is Normal Subgroup of Symmetric Group

Let $n \ge 2$ be a natural number.
Let $S_n$ denote the symmetric group on $n$ letters.
Let $A_n$ be the alternating group on $n$ letters.
Then $A_n$ is a normal subgroup of $S_n$ whose index is $2$.

Proof:
We have that $\map \sgn {S_n}$ is onto $C_2$.
Thus from the First Isomorphism Theorem, $A_n$ consists of the set of even permutations of $S_n$.
The result follows from Subgroup of Index 2 is Normal.
{{Qed}}
Theorem: Group of Permutations either All or Half Even

Let $G$ be a group of permutations.
Then either ''exactly half'' of the permutations in $G$ are even, or they are ''all'' even.

Proof:
From Parity Function is Homomorphism, the mapping:
:$\sgn : G \to \Z_2$
is a homomorphism.
Then:
:$G / \map \ker \sgn \cong \Img \sgn$
from the First Isomorphism Theorem.
The only possibilities for $\Img \sgn$ are $\set 0$ or $\Z_2$.
So either:
:$\order {G / \map \ker \sgn} = 1$
in which case all the permutations of $G$ are even, or:
:$\order {G / \map \ker \sgn} = 2$
in which case exactly half of them are.
{{qed}}
Category:Symmetric Groups
jktrlc08nm231gxlx8dba3n056hbeqi
Theorem: Cycle Decomposition of Conjugate

Let $S_n$ denote the symmetric group on $n$ letters.
Let $\pi, \rho \in S_n$.
The cycle decomposition of the permutation $\pi \rho \pi^{-1}$ can be obtained from that of $\rho$ by replacing each $i$ in the cycle decomposition of $\rho$ with $\map \pi i$.

Proof:
Consider the effect of $\pi \rho \pi^{-1}$ on $\map \pi i$:
:$\map {\pi \rho \pi^{-1} } {\map \pi i} = \map \pi {\map \rho i}$
That is:
:$\pi \rho \pi^{-1}$ maps $\map \pi i$ to $\map \pi {\map \rho i}$
In the cycle decomposition of $\pi \rho \pi^{-1}$, $\map \pi i$ lies to the left of $\map \pi {\map \rho i}$, whereas in the cycle decomposition of $\rho$, $i$ lies to the left of $\map \rho i$.
{{qed}}
Theorem: Conjugate Permutations have Same Cycle Type

Let $n \ge 1$ be a natural number.
Let $G$ be a subgroup of the symmetric group on $n$ letters $S_n$.
Let $\sigma, \rho \in G$.
Then $\sigma$ and $\rho$ are conjugate {{iff}} they have the same cycle type.

Proof:
Let $\sigma \in G$ have cycle type $\tuple {k_1, k_2, \ldots, k_n}$.
From Existence and Uniqueness of Cycle Decomposition, $\sigma$ can be expressed uniquely as the product of disjoint cycles:
:$\sigma = \alpha_1 \alpha_2 \dotsm \alpha_l$
where $\alpha_i$ is a $k_i$-cycle for some $i\in \set {1, 2, \ldots, l}$.
Let $\tau \in G$ such that:
:$\rho = \tau \sigma \tau^{-1}$
Then:
{{begin-eqn}}
{{eqn | l = \tau \sigma \tau^{-1}
      | r = \tau \alpha_1 \alpha_2 \dotsm \alpha_l \tau^{-1}
      | c = 
}}
{{eqn | n = 1
      | r = \tau \alpha_1 \tau^{-1} \tau \alpha_2 \tau^{-1} \dotsm \tau \alpha_l \tau^{-1}
      | c = Product of Conjugates equals Conjugate of Products
}}
{{eqn | r = \alpha_{\map \tau 1} \alpha_{\map \tau 2} \dotsm \alpha_{\map \tau l}
      | c = Cycle Decomposition of Conjugate
}}
{{end-eqn}}
We have that for $i, j \in \set {1, 2, \ldots, l}$, $\alpha_i$ and $\alpha_j$ are disjoint.
We also have that $\tau$ is a bijection, and so an injection.
It follows that $\alpha_{\map \tau i}$ and $\alpha_{\map \tau j}$ are also disjoint for all $i, j \in \set {1, 2, \ldots, l}$.
Thus:
:the product in $(1)$ is $\rho$ written as the product of disjoint cycles
where:
:$\tau \alpha_i \tau^{-1}$ is a $k_i$-cycle.
Thus $\rho$ has the same cycle type as $\sigma$.
{{questionable|The above only shows the $\leadsto$ direction. In fact, (if I remember correctly) the other direction is not true for $A_5$, if the 'conjugate' means conjugating by elements in $G$.}}
{{qed}}
Theorem: Transpositions of Adjacent Elements generate Symmetric Group

Let $n \in \Z: n > 1$.
Let $S_n$ denote the symmetric group on $n$ letters.
Then the transpositions $a_k = \begin{pmatrix} k & k + 1 \end{pmatrix}$ for $1 \le k < n$ are a set of generators for $S_n$.
They satisfy the relations:
{{begin-eqn}}
{{eqn | l = a_k^2
      | r = e
      | c = (for $1 \le k < n$)
}}
{{eqn | l = \paren {a_k a_{k + 1} }^3
      | r = e
      | c = (for $1 \le k < n - 1$)
}}
{{eqn | l = \paren {a_i a_j}^2
      | r = e
      | c = (for $1 \le i, j < n, \size {i - j} > 1$)
}}
{{end-eqn}}

Proof:
First, we show that each $\begin{pmatrix} i & j \end{pmatrix}$ where $i < j$ is in the subgroup $\gen {a_1, a_2, \ldots, a_{n - 1} }$.
From Cycle Decomposition of Conjugate, we can conjugate $a_i$ by $a_{i + 1}$ to give:
:$\begin{pmatrix} i & i + 2 \end{pmatrix}$
Conjugating $a_i$ by the product $a_{j - 1} a_{j - 2} \ldots a_{i + 1}$ will give:
:$\begin{pmatrix} i & j \end{pmatrix}$
Next, we note that:
:from K-Cycle can be Factored into Transpositions, every cycle is a product of transpositions.
and:
:from Existence and Uniqueness of Cycle Decomposition, every permutation is a product of cycles.
Thus, every permutation can be obtained from some product of the given transpositions.
Thus $\gen {a_1, a_2, \ldots, a_{n - 1} }$ is a generator of $S_n$.
From Transposition is Self-Inverse, we have:
:$a_k^2 = e$
From K-Cycle can be Factored into Transpositions, $a_i a_{i + 1}$ is the $3$-cycle $\begin{pmatrix} i & i + 1 & i + 2 \end{pmatrix}$.
Thus:
:$\paren {a_k a_{k + 1} }^3 = e$
If $\size {i - j} > 1$, then from Disjoint Permutations Commute, $a_i$ and $a_j$ are disjoint.
Thus:
:$\paren {a_i a_j}^2 = a_i^2 a_j^2 = e$
{{qed}}