16.2 Symmetric Groups

#Type/Example #Topic/Linear_Algebra #Type/Definition #Type/Theorem

Types: 16.2.4 Cycles
Examples: N/A
Constructions: N/A
Generalizations: 16.1 Permutation

Properties: 16.2.1 Inversion of a pair (i, j) with respect to pi, 16.2.2 Set of All Inversions for a Given pi in Sn
Sufficiencies: N/A
Questions: N/A

The set of all permutations of

n

elements (

S_{n}

)

Let $[n] = {j \in N : 1 \leq j \leq n}$ . The permutation group on $[n]$ , denoted as $S_{n}$ , is the 1.1 Set of all permutations of the set $[n] = {1, 2, \dots, n}$ . These are exactly the set of one-to-one maps from the set of the first $n$ integers to itself. For any element $n \in S_{n}$ , $π$ maps ${1, 2, \dots, n}$ onto itself.

Remark. Cauchy's two-line notation for a permutation of the integers

π : {1, 2, \dots, n} \to {1, 2, \dots, n}

is given as:

\overset{input}{\underset{output}{(\begin{matrix} 1 & 2 & 3 & \dots & n \\ π (1) & π (2) & π (3) & \dots & π (n) \end{matrix})}}

$⧫$

The Number of Elements of

S_{n}

Let $[n] = {1, 2, \dots, n}$ . If $S_{n}$ is the set of all bijections from $[n]$ to $[n]$ , then there are a total of $n! = n \cdot (n - 1) \dots 2 \cdot 1$ elements of $S_{n}$ .

\begin{proof}
Let $π : [n] \to [n]$ be a 16.1 Permutation.
\end{proof}

S_{1}

Let's look at the symmetric group on $1$ element.

\begin{aligned} S_{1} & = {π : π [1] \to [1]} \end{aligned}

This is the set of all permutations where $π$ goes from $1$ to $1$ .

π (1) = 1

Let's take a look at the permutation diagram.

This is known as the identity permutation, and it is written via function notation.

It is known as the identity permutation because it doesn't change anything.
Equivalent to multiplying by 1 in multiplication.

Therefore,

\begin{aligned} S_{1} & = {π : π [1] \to [1]} = {π_{id}} \end{aligned}

S_{2}

Now, let's look at the symmetric group on $2$ elements.

S_{2} = {π : π [2] - [2]}

This is the set of all permutations on $[2] = {1, 2}$ . Let's look at the permutations in function notation and as permutation diagrams.

\begin{aligned} π_{id} (1) & = 1 & π_{2} (1) & = 2 \\ π_{id} (2) & = 2 & π_{2} (2) & = 1 \end{aligned}

Our second permutation is a special permutation known as a transposition. It only swaps a pair of inputs.

S_{2} = {π : π [2] - [2]} = {π_{1}, π_{2}}

Therefore, a the set of two bijective functions $S_{2}$ is the identity permutation and the unique transposition.

S_{3}

Let's look at a symmetric group of 3 elements.

S_{3} = {π : π [3] \to [3]}

This is the set of all permutations on ${1, 2, 3}$ . How many permutations would there be?

We have 3 different choices for element 3. We have 2 different choices for our element 2. Lastly, we have 1 choice for element 1. Therefore,

| S_{3} | = 3! = 6

$S_{3}$ has 6 permutations. Let's look at the function notation and diagrams of each permutation.
!16
This leads into our theorem that 16.3 Transpositions Generate Permutations