The Symmetric Groups, Sn

Definition: Consider the $n$-element set $\{1, 2, ..., n \}$. A Permutation on $\{ 1, 2, ..., n \}$ is a bijection function $\sigma : \{ 1, 2, ..., n \} \to \{ 1, 2, ..., n \}$. The set of all permutations on $\{ 1, 2, ..., n \}$ is denoted $S_n$.

A permutation $\sigma$ of $\{ 1, 2, ..., n \}$ can be written in "matrix form", i.e., of the form:

(1)

\begin{align} \quad \sigma = \begin{pmatrix} 1 & 2 & ... & n \\ a_1 & a_2 & ... & a_n \end{pmatrix} \end{align}

Where $\{a_1, a_2, ..., a_n \} = \{ 1, 2, ..., n \}$ and $\sigma$ is defined such that $\sigma(j) = a_j$ for each $1 \leq j \leq n$. For example:

(2)

\begin{align} \quad S_1 &= \left \{ \sigma_1 = \begin{pmatrix} 1\\ 1 \end{pmatrix} \right \} \\ \quad S_2 &= \left \{ \sigma_1 = \begin{pmatrix} 1 & 2\\ 1 & 2 \end{pmatrix} , \sigma_2 = \begin{pmatrix} 1 & 2\\ 2 & 1 \end{pmatrix} \right \} \\ \quad S_3 &= \left \{ \sigma_1 = \begin{pmatrix} 1 & 2 & 3\\ 1 & 2 & 3 \end{pmatrix} , \sigma_2 = \begin{pmatrix} 1 & 2 & 3\\ 1 & 3 & 2 \end{pmatrix} , \sigma_3 = \begin{pmatrix} 1 & 2 & 3\\ 2 & 1 & 3 \end{pmatrix} , \sigma_4 = \begin{pmatrix} 1 & 2 & 3\\ 2 & 3 & 1 \end{pmatrix} , \sigma_5 = \begin{pmatrix} 1 & 2 & 3\\ 3 & 1 & 2 \end{pmatrix} , \sigma_6 = \begin{pmatrix} 1 & 2 & 3\\ 3 & 2 & 1 \end{pmatrix} \right \} \end{align}

In general, $S_n$ will have $n!$ distinct permutations $\sigma_1, \sigma_2, ..., \sigma_{n!}$. This set of permutations along with the operation $\circ$ of function composition will define an important type of group that we formally define below.

Definition: The Symmetric Group on the $n$-element set $\{1, 2, ..., n \}$ is the set of permutations $S_n = \{ \sigma_1, \sigma_2, ..., \sigma_{n!} \}$ along with the operation $\circ : S_n \to S_n$ of function composition defined for all $f_1, f_2 \in S_n$ as $(f_1 \circ f_2)(x) = f_1(f_2(x))$.

For example, consider the group $S_3$ from above with the operation $\circ$. The composition of two permutations of the set $\{1, 2, 3 \}$ be a permutation of the set $\{1, 2, 3 \}$ so $S_3$ is closed under $\circ$. We've already seen that the composition of three functions is associative too. The identity permutation is $\sigma_1 = \begin{pmatrix} 1 & 2 & 3\\ 1 & 2 & 3 \end{pmatrix}$, and for permutation in $S_3$ there exists another permutation in $S_3$ that returns us to the identity permutation. In fact, the inverses are somewhat self-defined. For example, consider the following permutation:

(3)

\begin{align} \quad \sigma = \begin{pmatrix} 1 & 2 & 3\\ 3 & 1 & 2 \end{pmatrix} \end{align}

Then the inverse permutation is assigned $1 = \sigma^{-1}(3)$, $2 = \sigma^{-1}(1)$ and $3 = \sigma^{-1}(2)$ to get:

(4)

\begin{align} \quad \sigma^{-1} = \begin{pmatrix} 1 & 2 & 3\\ 2 & 3 & 1 \end{pmatrix} \end{align}

Then $\sigma(\sigma^{-1}(x)) = x = \sigma^{-1}(\sigma(x))$ for all $x \in \{1, 2, 3\}$

We will now look at a nice result which will tell us that a symmetric group on $n$-elements will indeed have exactly $n!$ elements (permutations).

Proposition 1: The symmetric group $(S_n, \circ)$ has order $n!$.

• Proof: Let $n \in \mathbb{N}$. Then any permutation $\sigma \in S_n$ is of the following form:

(5)

\begin{align} \quad \sigma = \begin{pmatrix} 1 & 2 & \cdots & n\\ x_1 & x_2 & \cdots & x_n \end{pmatrix} \end{align}

• Where $x_1, x_2, ..., x_n \in \{ 1, 2, ..., n \}$ are distinct. The value of $x_1$ can be one of $n$ numbers. The value of $x_2$ can be one of $n - 1$ numbers, and so forth. The final choice for $x_n$ must be fixed. Hence there are $n!$ such permutations $\sigma$ - each of which is indeed a permutation and is indeed unique. So the order of $(S_n, \circ)$ is $n!$. $\blacksquare$