Symmetric Groups

Definition. The set of all permutations of $X$ is denoted by $\text{Sym} X$ or $\mathcal{P}(X)$.

Proposition. $\text{Sym} X$ with composition forms a group.

Proof.

0. Given $\sigma, \tau \in \text{Sym} X$, $\sigma \circ \tau$ is also a bijection so $\sigma \circ \tau \in \text{Sym} X$.

1. The permutation $1_X: X \to X$ which fixes all elements is the identity.

2. Given $\sigma \in \text{Sym} X$, $\sigma^{-1}: X \to X$ is also a bijection and $\sigma^{-1} \circ \sigma = 1_X$ by definition.

3. Composition of functions is associative.

Definition. If $X$ is finite, say $\vert X \vert = n$, we usually use $X = \set{1, 2, …, n}$ and $\text{Sym} X = S_n$, which is called a symmetric group.

Definition. The degree of a symmetric group $S_n$ is the number of underlying elements (not permutations), i.e. $\text{deg}\,S_n = n$.

Proposition. The order of $S_n$, denoted by $\vert S_n \vert$, is $n!$.

Proof.

For a permutation $(a_1\;a_2\;…\;a_n) \in S_n$, $a_1$ has $n$ choices, $a_2$ has $n - 1$ choices and so on. Hence, $\vert S_n \vert = n!$.

Generating Sets

There are a few choices of generating set for $S_n$.

Proposition. $S_n$ is generated by transpositions.

Proof.

As every permutation is a product of transpositions, $S_n$ is generated by transpositions.

Proposition. The set $\set{(1\;2), (1\;3), …, (1\;n)}$ generates $S_n$.

Proof.

As $(a\;b) = (1\;a)(1\;b)(1\;a)$, the above set generates $S_n$.

Proposition. The set $\set{(1\;2), (2\;3), …, (n-1\;n)}$ generates $S_n$.

Proof.

As $(a\;b) = (b-1\;b)(b-2\;b-1)…(a+1\;a+2)(a\;a+1)(a+1\;a+2)…(b-2\;b-1)(b-1\;b)$, the above set generates $S_n$.

Proposition. The set $\set{(1\;2), (1\;2\;…\;n)}$ (a transposition and a $n$-cycle) generates $S_n$.

Proof.

In general,

\[(k\;k+1) = (1\;2\;...\;n)^{k-1}(1\;2)(1\;2\;...\;n)^{1-k}\]

for $2 \le k < n$ and we can construct the set $\set{(1\;2), (2\;3), …, (n-1\;n)}$ to generate $S_n$.

$\text{sgn}$ as homomorphism

Proposition. For $n \ge 2$, $\text{sgn}: S_n \to \set{\pm 1}$ is a surjective group homomorphism

Proof.

\[\text{sgn}(\sigma_1\sigma_2) = (-1)^{k_1 + k_2} = (-1)^{k_1}(-1)^{k_2} = \text{sgn}(\sigma_1)\text{sgn}(\sigma_2)\]

It is surjective as we always have $\text{sgn}(e) = 1$ and $\text{sgn}((1\;2)) = -1$.

Alternating Group

Proposition. The even permutations in $S_n$ form a subgroup, which is called the alternating group $A_n$.

Proof.

Product of even permutation is even. The identity is even. Inverse of even permutation is even.

Also, $A_n = \ker \text{sgn}$ which is a subgroup of $S_n$.

Proposition. The order of $A_n$ is $n!/2$.

Proof.

For every even permutation $\sigma \in S_n$, $(1\;2)\sigma$ is odd and distinct. We can therefore pair each of them and show that precisely half its elements are even.

Proposition. For $n \ge 3$, $A_n$ is generated by 3-cycles.

Proof.

Given a permutation $\sigma \in A_n$, it has even number of transpositions. For each adjacent pair, there are 2 cases: $(b\;c)(a\;b) = (a\;c\;b)$ and $(c\;d)(a\;b) = (a\;d\;c)(a\;b\;c)$. As both of the cases can be expressed as 3-cycles, $A_n$ is generated by them.

Subgroup of $S_n$

Proposition. Any subgroup of $S_n$ contains either no odd permutations, or precisely half.

Proof.

Let $G \le S_n$ and $a_1, a_2, …, a_n$ be the even elements in $G$.

If there are no odd elements, $G \le A_n$.

If there is an odd element $g \in G$, then the elements $ga_1, ga_2, ga_3, …, ga_n$ are all odd. Also, if $ga_i = ga_j$ for some $i, j$, $g^{-1}(ga_i) = g^{-1}(ga_j)$ and $a_i = a_j$. Thus, they are all distinct.

Hence, $G$ has either no odd elements, or exactly half of them are odd.

$S_n$ can be viewed as subgroup of $S_m$ with $n \le m$, by fixing $n+1, n+2, …, m$.

$D_{2n}$ can also be viewed as a subgroup of $S_n$ by numbering the vertices of a regular $n$-gon.

Using $D_6$ as example, we can write

\[S_3 = \set{e, (1\,2\,3) = r, (1\,3\,2) = r^2, (2\,3) = s, (1\,2) = rs, (1\,3) = r^2s }\]

From the above, we can see $S_3 \cong D_6$.

Conjugacy in $S_n$

Proposition. Two permutations are conjugate iff they have the same cycle type.

Proof.

Let $(a_1\,a_2\,…\,a_k)$ be a $k$-cycle and $\rho \in S_n$. Then

\[\rho(a_1\,a_2\,...\,a_k)\rho^{-1} = (\rho(a_1)\,\rho(a_2)\,...\,\rho(a_k))\]

since $\rho(a_1) \mapsto a_1 \mapsto a_2 \mapsto \rho(a_2)$.

Suppose $\sigma = \sigma_1 \sigma_2 … \sigma_l$, where $\sigma_i$ are disjoint cycles, then

\[\rho\sigma\rho^{-1} = (\rho\sigma_1\rho^{-1})(\rho\sigma_2\rho^{-1})...(\rho\sigma_l\rho^{-1})\]

which has the same cycle type as $\sigma$.

Conversely, if $\sigma, \tau \in S_n$ have the same cycle type, then

\[\rho = \begin{pmatrix} a_1 & a_2 & \cdots & a_n \\ b_1 & b_2 & \cdots & b_n \\ \end{pmatrix}\]

is the permutation that satisfies $\rho\sigma\rho^{-1} = \tau$.

$S_4$

The conjugacy classes are as follow base on the cycle type:

conjugacy class cycle type size size of centralizer sign
$e$ 1111 1 24 +
$[(1\,2)]$ 211 6 4 -
$[(1\,2)(3\,4)]$ 22 3 8 +
$[(1\,2\,3)]$ 31 8 3 +
$[(1\,2\,3\,4)]$ 4 6 4 -

It is useful for finding the normal subgroups of $S_4$ as a normal subgroup needs to have order divides $\vert S_4 \vert = 24$ and is a union of conjugacy classes.

order elements quotients $S_4/K$
1 $\set{e}$ $S_4$
4 $\set{e, (1\,2)(3\,4), (1\,3)(2\,4), (1\,4)(2\,3)} = V_4$ $S_3 \cong D_6$
12 $A_4$ $C_2$
24 $S_4$ $\set{e}$

(order $2, 3, 6, 8$ is not possible because there is no sum of sizes of conjugacy classes that equal to them.)

$S_5$

conjugacy class cycle type size size of centralizer sign
$e$ 11111 1 120 +
$[(1\,2)]$ 2111 10 12 -
$[(1\,2)(3\,4)]$ 221 15 8 +
$[(1\,2\,3)]$ 311 20 6 +
$[(1\,2\,3)(4\,5)]$ 32 20 6 -
$[(1\,2\,3\,4)]$ 41 30 4 -
$[(1\,2\,3\,4\,5)]$ 5 24 5 +

Conjugacy in $A_n$

As $A_n \subseteq S_n \implies [\sigma]_{A_n} \subseteq [\sigma]_{S_n}$ and $\vert A_n \vert = \vert S_n \vert / 2$, by Orbit-Stabilizer, there are two options:

Definition. If $\vert [\sigma]_{A_n} \vert = \vert [\sigma]_{A_n} \vert / 2$, we say that the conjugacy class of $\sigma$ splits in $A_n$.

Proposition. For $\sigma \in A_n$, $[\sigma]$ splits in $A_n$ iff no odd permutation commutes with $\sigma$, meaning $C_{S_n}(\sigma)$ has no odd elements.

Proof.

As $\vert [\sigma]_{A_n} \vert = \vert [\sigma]_{A_n} \vert / 2$ iff $C_{S_n}(\sigma) = C_{A_n}(\sigma)$. It is only possible if $C_{S_n}(\sigma)$ has no odd elements.

$A_4$

conjugacy class cycle type $\vert [\sigma]_{S_4} \vert$ odd elements in $C_{S_4}$ $\vert [\sigma]_{A_4} \vert$
$e$ 1111 1 yes, e.g. $(1\,2)$ 1
$[(1\,2)(3\,4)]$ 22 3 yes, e.g. $(1\,2)$ 3
$[(1\,2\,3)]$ 31 8 no 4 + 4

(As $\vert C_{S_4}([(1\,2\,3)]) \vert = 3$ and all powers of $(1\,2\,3)$ commutes with itself (three of them), so $C_{S_4}([(1\,2\,3)]) = \langle (1\,2\,3) \rangle$.)

$A_5$

conjugacy class cycle type $\vert [\sigma]_{S_5} \vert$ odd elements in $C_{S_5}$ $\vert [\sigma]_{A_5} \vert$
$e$ 1111 1 yes, e.g. $(1\,2)$ 1
$[(1\,2)(3\,4)]$ 22 15 yes, e.g. $(1\,2)$ 15
$[(1\,2\,3)]$ 31 20 yes, e.g. $(4\,5)$ 20
$[(1\,2\,3\,4\,5)]$ 5 24 no 12 + 12

(As $\vert C_{S_5}([(1\,2\,3\,4\,5)]) \vert = 5$ and all powers of $(1\,2\,3\,4\,5)$ commutes with itself (five of them), so $C_{S_5}([(1\,2\,3\,4\,5)]) = \langle (1\,2\,3\,4\,5) \rangle$.)

Proposition. $A_5$ is simple.

Proof.

The order of a normal subgroup of $A_5$ must divides $\vert A_5 \vert = 60$. Base on the orders of conjugacy classes, the only possible combinations are $1$ and $60$. So only $\set{e} \trianglelefteq A_5$ and $A_5 \trianglelefteq A_5$.

In fact, all $A_n$ for $n \ge 5$ are simple.

References