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{align} i: &\, 1\\ (12): &\,10\\ (123): &\,20\\ (1234): &\,30\\ (12345): &\,24\\ (12)(34): &\,15\\ (12)(345): &\,20\\ \end{align} \] 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