Symmetric Group

The symmetric group $S_n$ is the group of permutations on $n$ objects. Usually the objects are labeled $\{1,2,\ldots,n\},$ and elements of $S_n$ are given by bijective functions $\sigma \colon \{1,2,\ldots,n\} \to \{1,2,\ldots,n\}.$ The group operation on $S_n$ is composition of functions.

The symmetric group is important in many different areas of mathematics, including combinatorics, Galois theory, and the definition of the determinant of a matrix. It is also a key object in group theory itself; in fact, every finite group is a subgroup of $S_n$ for some $n,$ so understanding the subgroups of $S_n$ is equivalent to understanding every finite group.

Let $X_n = \{1,2,\ldots,n\}.$ Then $S_n$ is the set of bijections $\sigma \colon X_n \to X_n.$ Since the composition of two bijections is a bijection, composition is a binary operation on $S_n,$ which turns it into a group. The identity element of the group is the identity function $i$: $i(k) = k$ for all $k \in X_n.$

The order of the group $S_n,$ the number of permutations on $n$ objects, is $n!.$ See the permutation wiki for a discussion.

$S_n$ is non-abelian for $n\ge 3.$ For a proof, see example 5 in the group theory wiki exercises. $S_3$ is the smallest non-abelian group, of order $3!=6.$

A subgroup of $S_n$ is called a permutation group. Every finite group is isomorphic to a permutation group:

(Cayley's Theorem) Let $G$ be a finite group. Then there is a positive integer $n$ and an injective homomorphism $\phi \colon G \to S_n.$

In fact, we can choose $n = |G|.$ Label the elements of $G$ $x_1,x_2,\ldots,x_n.$ Then multiplication by an element $g\in G$ induces a permutation $\sigma_g$ of the elements of $G$ $\big($it is a bijection because its inverse is multiplication by $g^{-1}\big)$. The map $\phi \colon G \to S_n$ given by $\phi(g) = \sigma_g$ is clearly a homomorphism. It is also injective because its kernel, the set of elements going to the identity homomorphism, is the set of elements $g$ such that $gx_i = x_i$ for all $i,$ which is just the one-point set consisting of the identity of $G.$

This embedding of $G$ into $S_{|G|}$ is often called the regular representation.

The Klein four group $V = {\mathbb Z}_2 \times {\mathbb Z}_2$ has elements $x_1=(0,0),x_2=(1,0),x_3=(0,1),x_4=(1,1).$ Then $\phi$ sends $V$ to $S_4$ as follows:

$\phi(x_1) =$ the identity permutation

$\phi(x_2) =$ the double transposition switching $1$ and $2$, $3$ and $4$

$\phi(x_3) =$ the double transposition switching $1$ and $3$, $2$ and $4$

$\phi(x_4) =$ the double transposition switching $1$ and $4$, $2$ and $3$

One way to write permutations is by showing where $\{1,2,\ldots,n\}$ go. For instance, suppose $\sigma$ is a permutation in $S_4$ such that $\sigma(1) = 2, \sigma(2)=4, \sigma(3) = 3, \sigma(4) = 1.$ Then $\sigma$ can be written $$\begin{pmatrix} 1&2&3&4 \\ 2&4&3&1 \end{pmatrix}.$$ This is not a particularly compact form. It is more efficient to write the permutation as a product of disjoint cycles, where a $k$-cycle $(a_1a_2\cdots a_k)$ is a sequence of distinct numbers $a_1,a_2,\ldots,a_k$ such that $$\sigma(a_1)=a_2,\sigma(a_2)=a_3,\ldots,\sigma(a_{k-1})=a_k,\sigma(a_k)=a_1.$$ For instance, the above permutation can be written in cycle notation as $(124).$ $(3$ does not appear since $\sigma(3)=3.)$ This is a $3$-cycle.

Partition the elements of $S_5$ by their cycle structure, counting the number of elements of each kind.

---

Here is a list of each possible cycle structure, with a representative element, and the total number of elements with that structure in parentheses. $$\begin{aligned} i: &\, 1\\ (12): &\,10\\ (123): &\,20\\ (1234): &\,30\\ (12345): &\,24\\ (12)(34): &\,15\\ (12)(345): &\,20\\ \end{aligned}$$ The numbers of elements in each class add up to $5! = 120,$ as expected.

Counting the number of elements in each class is a straightforward but instructive combinatorics exercise. Remember that a $k$-cycle can be written in $k$ different ways. E.g. $(1234) = (2341) = (3412) = (4123).$

An important part of the study of non-abelian groups is classifying them by their conjugacy classes. In a non-abelian group, an element $g$ does not necessarily equal $h^{-1}gh,$ for an element $h\in G.$ In this case, the two elements $g$ and $h^{-1}gh$ are called conjugate. Being conjugate is an equivalence relation, so a group $G$ is partitioned into disjoint sets of elements which are all conjugate to each other, called conjugacy classes.

$S_3$ is the union of three conjugacy classes:

The identity element {i};
The three 2-cycles $\{(12),(13),(23)\}$;
The two 3-cycles $\{(123),(132)\}.$

For example, $(13)^{-1}(12)(13) = (13)(12)(13) = (23),$ so $(12)$ and $(23)$ are conjugate.
Similarly, $(13)^{-1}(123)(13) = (13)(123)(13) = (132),$ so $(123)$ and $(132)$ are conjugate.

The conjugacy classes of $S_n$ are quite easy to describe:

Two elements in $S_n$ are conjugate if and only if they have the same cycle structure.

This fact follows from the following explicit computation, which shows that the conjugate of a $k$-cycle is a $k$-cycle:

Given a $k$-cycle $(a_1 a_2 \ldots a_k)$ and a permutation $\sigma,$ both in $S_n,$
\[
\sigma (a_1 a_2 \ldots a_k) \sigma^{-1} = \big(\sigma(a_1) \sigma(a_2) \ldots \sigma(a_k)\big).
\]

So, for example, the breakdown of elements of $S_5$ into conjugacy classes coincides with the breakdown of elements by cycle structure in the above example.

The sign of a permutation $\sigma$ $($denoted $\epsilon(\sigma))$ can be defined as

$$\displaystyle \epsilon(\sigma) = (-1)^{\text{inv}(\sigma)},$$

where $\text{inv}(\sigma)$ is the number of inversions of $\sigma,$ or the number of pairs $(a,b)$ with $a,b \in \{1,2,\ldots,n\}$ such that $\sigma(a)>\sigma(b), a<b$. So $\epsilon(\sigma)$ gives the parity of the number of inversions.

This permutation has five inversions, so its sign is $-1.$ One of the five pairs is $i=2,j=4.$ ^[1]

The important property of $\epsilon$ is that it is a homomorphism $\epsilon \colon S_n \to \{\pm 1\}.$ Transpositions of two adjacent numbers have exactly one inversion, so they have sign $-1.$ So $\epsilon$ is surjective. Its kernel $A_n$ is called the alternating group, and consists of even permutations (permutations with sign $1$). Elements of $S_n$ not in $A_n$ are called odd permutations.

There are other ways to compute the sign; one common one is to write a permutation $\sigma$ as a product of $t$ transpositions. The sign of a transposition is $-1,$ so the sign of $\sigma$ is $(-1)^t.$ It is also convenient (and relatively easy to prove) that the sign of a $k$-cycle is $(-1)^{k-1}.$ For instance, the permutation pictured above can be written in cycle notation as $(13)(254),$ which is the product of an odd permutation and an even one, which is odd (has sign $-1$).

The sign of a permutation is used in a general definition of determinant:

$$\displaystyle \text{det }A = \sum_{\sigma \in S_n}{\epsilon(\sigma) \prod_{i=1}^{n}{A_{i,\sigma(i)}} }.$$

1. Quartl, . Inversion_qtl1. Retrieved February 20, 2013, from https://commons.wikimedia.org/wiki/File:Inversion_qtl1.svg