The symmetric group

Before defining anything, we shall provide a little motivation for some general notions which will arise later. Let $X$ be any finite set and let $S_X$ denote the set of all permutations of $X$ onto itself:

$$S_X = \{ f : X \rightarrow X \ \vert\ f\ {\rm is\ a\ bijection}\}.$$

This set has the following properties:

1. if $f,g$ belong to $S_X$ then $fg$ (the composition of these permutations) also belongs to $S_X$ (``closed under compositions"),
2. if $f,g,h$ all belong to $S_X$ then $(fg)h=f(gh)$ (``associativity"),
3. the identity permutation $I : X \rightarrow X$ belongs to $S_X$ (``existence of the identity"),
4. if $f$ belongs to $S_X$ then the inverse permutation $f^{-1}$ also belongs to $S_X$ (``existence of the inverse").

The set $S_X$ is called the symmetric group of $X$. We shall usually take for the set $X$ a set of the form $\{1,2,...,n\}$, in which case we shall denote the symmetric group by $S_n$. Note that the elements of $S_n$ are exactly the permutations first introduced in the previous chapter. This group is also called the symmetric group on $n$ letters.

Example 5.2.1   Suppose $X = \{1,2,3\}$. We can describe $S_X$ as

$$S_X = \{ I, s_1=(1\ 2), s_2=(2\ 3), s_3=(1\ 3\ 2), s_4=(1\ 2\ 3), s_5=(1\ 3)\}.$$

We can compute all possible products of two elements of the group and tabulate them:

	$I$	$s_1$	$s_2$	$s_3$	$s_4$	$s_5$
$I$	$I$	$s_1$	$s_2$	$s_3$	$s_4$	$s_5$
$s_1$	$s_1$	$I$	$s_3$	$s_2$	$s_5$	$s_4$
$s_2$	$s_2$	$s_4$	$I$	$s_5$	$s_1$	$s_3$
$s_3$	$s_3$	$s_5$	$s_1$	$s_4$	$I$	$s_2$
$s_4$	$s_4$	$s_2$	$s_5$	$I$	$s_3$	$s_1$
$s_5$	$s_5$	$s_3$	$s_4$	$s_1$	$s_2$	$I$

Example 5.2.2   Let us revisit the result of Steinhaus' algorithm in the case of $S_3$. Recall the output from §4.5:

$$\begin{array}{ccc} 1& 2&3\\ 1& 3&2\\ 3&1& 2\\ 3&2& 1\\ 2&3& 1\\ 2& 1&3 \end{array}$$

In disjoint cycle notation,

$$\begin{array}{c} \ [1,2,3]=(1)=g_1, \ \ \ \ [1,3,2]=(2,3... ...3)g_4=g_5, \ \ \ \ [2,1,3]=(1,2)=(2,3)g_6=g_6. \end{array}$$

Note that every element $g\in S_3$ can be written in the form of a product of the simple transpositions $(1,2)$ and $(2,3)$.

Exercise 5.2.3   Verify the four properties of $S_X$ mentioned above for Example 5.2.1. (Note that the verification of associativity follows from the associative property of the composition of functions - see Exercise 4.1.15).