The Symmetric Groups on n Elements

# The Symmetric Groups on n Elements

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

For example:

(1)
\begin{align} \quad S_1 = \left \{ \sigma_1 = \begin{pmatrix} 1\\ 1 \end{pmatrix} \right \} \end{align}
(2)
\begin{align} \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 \} \end{align}
(3)
\begin{align} \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.

 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:

(4)
\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:

(5)
\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 have exactly $n!$ elements (permutations).

 Proposition: 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:
(6)
\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$