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.3.1   Suppose $X = \{1,2,3\}$ . We can describe $S_X$ in disjoint cycle notation 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$

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