# 3.1: Symmetric Groups

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

##### Definition: Symmetric Group

Let $$X=\{1,\ldots,n\}$$, be a set. Then $$S_n$$ is the set of all the bijections from $$X$$ to $$X$$. (permutations) Note that there are $$n!$$ permutations. The operation $$\star : =$$ composition of bijections.  $$S_n$$ with compositions forms a group; this group is called a Symmetric group. $$S_n$$ is a finite group of order $$n!$$ and are permutation groups consisting of all possible permutations of n objects.

##### Example $$\PageIndex{1}$$

Let $$\sigma = \begin{bmatrix} 1 & 2& 3& 4 & 5\\ 2 & 4 & 3 & 5 & 1 \end{bmatrix} \in S_5$$ and

$$\gamma = \begin{bmatrix} 1 & 2& 3& 4 & 5\\ 5 & 4 & 1 & 2 & 3 \end{bmatrix} \in S_5$$.

Consider $$\gamma \circ \sigma = \gamma \sigma =$$ $$\begin{bmatrix} 1 & 2& 3& 4 & 5\\ 5 & 4 & 1 & 2 & 3 \end{bmatrix} \begin{bmatrix} 1 & 2& 3& 4 & 5\\ 2 & 4 & 3 & 5 & 1 \end{bmatrix}= \begin{bmatrix} 1 & 2& 3& 4 & 5\\ 4 & 2 & 1 & 3 & 5 \end{bmatrix}$$ The process of moving from one function to another is illustrated at right.  Note the system is closed since it is a bijection. Completing the process, we obtain the following:

Note, if we switch the order of the functions are switched, we obtain: $$\sigma \gamma = \begin{bmatrix} 1 & 2& 3& 4 & 5\\ 1 & 5 & 2 & 4 & 3 \end{bmatrix}$$.

Note that $$\sigma \gamma \ne \gamma \sigma$$.  To prove not abelian, we need only show that for any one element, $$k$$, $$\sigma \gamma(k) \ne \gamma \sigma(k)$$.

The following theorem proves that $$S_n$$ are non-Abelian for integer n ≥ 3, which means that the order in which we compose permutations matters.

##### Theorem $$\PageIndex{1}$$

$$S_n$$ is non-Abelian for  all integers n ≥ 3.

Proof

Let $$a,b \in S_3$$.

We will show that $$\thereexist a, b \in S_n, s.t. ab \ne ba$$, $$n \ge 3$$.

Note $$S_3=\{e,(1,2),(1,3),(2,3),(1,2,3),(1,3,2)\}$$.

Let $$a=(1,2)$$ and $$b=(2,3)$$ both elements of $$S_3$$.

Consider $$ab=(1,2)(1,3)=(1,3,2)$$ and $$ba=(1,3)(1,2)=(1,2,3)$$.

Since $$(1,3,2) \ne (1,2,3)$$, $$ab\ne ba \; \forall a,b \in S_3$$, thus $$S_3$$ is non-abelian.

Since $$S_3 \le S_n, \; \forall n \ge 3$$, $$S_n$$ in non-abelian for $$n\ge 3$$.◻

#### Cycle Notation

##### Example $$\PageIndex{2}$$

Let $$\gamma = \begin{bmatrix} 1 & 2& 3& 4 & 5\\ 5 & 4 & 1 & 2 & 3 \end{bmatrix}=(1,5,3)(2,4)$$.

This can be read as 1 goes to 5, 5 goes to 3, and 3 goes back to 1.  Then 2 goes to 4, and then 4 goes back to 2.  If the two cycles are disjoint, the order does not matter.

##### Note

$$(1,2,4,5)$$ means that 1 goes to 2, 2 goes to 4, 4 goes to 5 and 5 goes to 1.  Note that 3 is not included, so 3 goes to 3.  Note that there is no cycle notation in the case of the identity, $$e$$, and we use $$e$$.

##### Definition: disjoint cycles

Two cycles in $$S_n$$, $$\gamma=(a_1,\ldots,a_k)$$ and $$\sigma=(b_1,\ldots,b_l)$$ are disjoint if $$a_i \ne b_j, \; \forall i,j$$.

Note that the length of the cycles do not need to be the same.

Example:  $$(1, 2)$$ and $$(3, 4)$$ are disjoint, but $$(1, 2, 3)$$ and $$(3, 4)$$ are not disjoint.

##### Example $$\PageIndex{3}$$

Let $$\sigma = \begin{bmatrix} 1 & 2& 3& 4 & 5& 6 & 7 & 8 & 9 &10 &11&12\\ 12 & 2 & 3 & 1 & 11 & 9 & 5 &10 & 6 &4& 7 & 8 \end{bmatrix}$$

Then a cycle decomposition of

$$\sigma = (1, 12, 8, 10, 4) (2)(3)(5,11,7)(6,9)= (1, 12, 8, 10, 4) (5,11,7)(6,9)$$.

Note that these are disjoint cycles; therefore, they commute.

##### Theorem $$\PageIndex{1}$$

1. Disjoint cycles are commutative.

Let $$\gamma$$ and $$\sigma$$ be disjoint cycles, then $$\gamma \sigma = \sigma \gamma$$.

2. Every permutation of a finite set can be written as a cycle or as a product of disjoint cycles.

### The inverse of a cycle:

##### Theorem $$\PageIndex{1}$$

$$(a_1, a_2, \cdots, a_k)^{-1}= (a_k, a_{k-1}, \cdots, a_1)$$

##### Example $$\PageIndex{4}$$

$$(1,2,3)^{-1} = (3,2,1)$$, and $$(1,2)^{-1}=(2,1)=(1,2).$$

Hence  $$\sigma^{-1} =(6,9)^{-1}(5, 11, 7)^{-1} (1, 12, 8, 10, 4)^{-1}=(9,6)(7, 11, 5) (4, 10, 8, 12, 1)$$

##### Caution

$$(2,3)(1,2) = (1,3,2)$$ Note:  one goes to 2 first, then to 2 and then gets to  3.

$$(1,2)(2,3)= (1,2,3)=(2,3,1)=(3,2,1)$$  Note: Since there is no 1 in the inner function, it goes to itself

then goes to 2 which goes to 3

##### Example $$\PageIndex{5}$$

$$S_3= \{1,(1,2),(1,3), (2,3), (1,2,3),(1,3,2)\}$$.  This is the list of possible permutations of the above triangle. Note that $$(1,2,3)$$ and $$(3,2,1)$$ are rotations, while $$(1,2), (1,3),$$ and $$(2,3)$$ are reflections around the missing angles bisection.  $$|S_3|=3!=2\cdot 3=6$$.

 Cayley Table for $$S_3$$ 1 (1,2,3) (1,3) (1,2) (2,3) (1,3,2) 1 1 (1,2,3) (1,3) (1,2) (2,3) (1,3,2) (1,2,3) (1,2,3) (1,3,2) (2,3) (1,3) (1,2) 1 (1,3) (1,3) (1,2) 1 (1,2,3) (1,3,2) (2,3) (1,2) (1,2) (2,3) (1,3,2) 1 (1,2,3) (1,3) (2,3) (2,3) (1,3) (1,2,3) (1,3,2) 1 (1,2) (1,3,2) (1,3,2) 1 (1,2) (2,3) (1,3) (1,2,3) ##### Example $$\PageIndex{6}$$

Given $$\alpha, \beta \in S_4$$ with $$\alpha \beta =(1,4,3,2), \; \beta \alpha = (1,2,4,3)$$, and $$\alpha(1)=4$$, determine $$\alpha$$ and $$\beta$$.

Solution:

Let $$\alpha=(1,4,c,d)$$ and $$\beta=(w,x,y,z)$$.

Since $$\alpha(1)=4$$ and $$\beta \alpha(1)=2$$, implies $$\beta(4)=2$$.

Since $$\beta(4)=2$$ and $$\alpha \beta(4)=3$$, implies $$\alpha(2)=3$$.

Since $$\alpha(2)=3$$ and $$\beta \alpha(2)=4$$, implies $$\beta(3)=4$$.

Since $$\beta(3)=4$$ and $$\alpha \beta(3)=2$$, implies $$\alpha(4)=2$$.

Since $$\alpha(4)=2$$ and $$\beta \alpha(4)=3$$, implies $$\beta(2)=3$$.

Since $$\beta(2)=3$$ and $$\alpha \beta(2)=1$$, implies $$\alpha(3)=1$$.

Since $$\alpha(3)=1$$ and $$\beta \alpha(3)=1$$, implies $$\beta(1)=1$$.

$$\alpha=(1,4,2,3)$$ and $$\beta=(2,3,4)$$.

Then $$\beta \alpha =(2,3,4)(1,4,2,3)=(2,4,3,1)=(1,2,4,3)$$.

And $$\alpha \beta =(1,4,2,3)(2,3,4)=(4,3,2,1)=(1,4,3,2)$$.

Note that every permutation of a finite set can be written as a cycle or as a product of disjoint cycles.

#### 2 Cycle (Transposition)

$$(i,j), \; i\le j, \; j\le n, \; i \ne j$$.

$$(i,j)^{-1}=(j,i)=(i,j)$$.

Note:  Any cycle can be written as a composition of two cycles.

Example 1:  (1, 3, 2) = (1, 2) (1, 3)  1 goes to 3, 3 goes to itself, then to 1 then to 2.

Example 2:  (1, 2, 3) = (1, 3) (1, 2).

Example 3:  (2, 4, 1, 3, 5) = (2, 5) (2, 3) (2, 1) (2, 4)

Every permutation in $$S_n, n > 1,$$ is a product of 2-cycles. The number of 2 cycles will either be always even or always odd.

If a permutation α can be expressed as a product of an even number of 2-cycles, then every decomposition of α into a product of 2-cycles has an even number of 2-cycles.  A similar statement holds for odd.

## Permutation parity

Definition:

Let $$\sigma \in S_n$$.  (ie a permutation)

Then

(1) $$\sigma$$ is an even permutation if $$\sigma$$ can be expressed as a product of an even number of two cycles.,

(2) $$\sigma$$ is an odd permutation if $$\sigma$$ can be expressed as a product of an odd number of 2 cycles.

##### Example $$\PageIndex{1}$$

1. let’s explore $$S_4$$. Note $$S_4$$ has $$S_4$$ has $$4!=24$$ elements.

Consider $$S_4=\{e, (1,2), (1,3), (1,4), (2,3), (2,4), (3,4),(1,2)(3,4), (1,3)(2,4), (1,4)(2,3), (1,2,3), (1,3,2), (2,3,4), (2,4,3), (3,4,1), (3,1,4), (4,1,2), (4,2,1),(1,2,3,4), (1,2,4,3), (1,3,4,2), (1,3,2,4), (1,4,2,3), (1,4,3,2) \}$$

 1 Cycle 1111 2 Cycles 211 2 Cycle Compositions 22 3 Cycles 31 4 Cycles 4 1 6 3 8 6

2. Find the centre of $$S_4$$.

Since all symmetrical groups, $$S_n$$,  $$n \ge 3$$, are non-abelian, the centre of $$S_4$$ is trivial, being the identity e, or (1)(2)(3)(4). (what do you think of this proof? Is this a valid argument?)

Alternatively, proof by exhaustion:  Having tried all $$x \in S_4$$, the only $$x \in S_4$$ that satisfies $$xg=gx, \; \forall g \in S_4$$ is the identity.

3. Find the cyclic subgroup of $$S_4$$ that has an order of 4.

The subgroup of S4, C4 =\)\{e, (1,2,3,4),(1,3)(2,4),(1,4,3,2) \}\), has an order 4 and is generated by $$(1,2,3,4)$$.

$$(1,2,3,4)^2=(1,3)(2,4)$$, $$(1,2,3,4)^3=(1,4,3,2)$$, and $$(1,2,3,4)^4=e$$.

4. Find a non-cyclic subgroup of $$S_4$$ that has order 4.

The 2-2 cycles together will form an order 4 group.

$$\{e, (1,2)(3,4),(1,3)(2,4),(1,4)(2,3)\}$$ is a subgroup of $$S_4$$ and has order 4.  Note the inverse of $$(1,2)(3,4)$$ is $$(4,3)(2,1)$$, which is $$(1,2)(3,4)$$.  Since a similar argument can be made for the other 2-2 cycles, the inverses of each element exist.  In addition, the set is closed under composition.

#### Order of a permutation

Let $$\sigma=(1, 2, 3)$$.

Then $$\sigma^2=(1, 2, 3)(1, 2, 3)=(1, 3, 2)=\sigma^{-1}$$.

Further $$\sigma ^3=(1, 2, 3)(1, 3, 2)=(1)(2)(3)=e$$.  We shall refer to $$e$$ as 1.

Thus the order of $$\sigma$$, $$|\sigma |=3$$.

##### Theorem $$\PageIndex{1}$$

If $$\sigma=(a_1, \ldots, a_k)$$, then the $$|\sigma |=k$$. (Proof?)

##### Example $$\PageIndex{1}$$

Let $$\gamma = (1, 2, 4)$$. Then

$$\gamma^2=(1, 2, 4)(1,2, 4)=(1, 4, 2)$$.

$$\gamma^3=(1, 2, 4)(1, 4, 2)=(1)(2)(4)$$.

##### Theorem $$\PageIndex{1}$$

The order of a permutation of a finite set, written in disjoint cycle form, is the least common multiple of the lengths of the cycles. ##### Example $$\PageIndex{1}$$

Find the orders of the 5040 elements of $$S_7.$$

###### Solution

The longest cycle in $$S_7$$ is the one that includes all the elements -- 7. We will show cycle lengths as $$\underline{7}$$.  Note the underlining.  The possible cycles are shown in the table below.  Note that the leading term is the longest cycle in the permutation.

 Cycle Order Cycle Order Cycle Order 7 7 4 2 1 4 3 1 1 1 1 3 6 1 6 4 1 1 1 4 2 2 2 1 2 5 2 10 3 3 1 3 2 2 1 1 1 2 5 1 1 5 3 2 2 6 2 1 1 1 1 1 2 4 3 12 3 2 1 1 6 1 1 1 1 1 1 1 1

This page titled 3.1: Symmetric Groups is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Pamini Thangarajah.