Group of permutations

 

Def 1

Let $A$ be a set

1.  A permutation of $A$ is a 1-1 onto function from $A$ to $A$

2.  The symmetric group on $A$ is

$S_{A} = \left\{\sigma \; | \; \sigma : A \to A \text{ is a permutaion} \right\}$

(or $\mathrm{Sym}(A)$)

3.  $\sigma, \tau \in S_{A}$ ,  $\sigma \tau = \sigma \circ \tau$  $(\in S_{A})$

 

 

 

Notation

$B_{n} = \left\{1, 2, \cdots, n \right\} $

$S_{n} = S_{B_{n}}$

 

$\sigma \in S_{n}$ ,  $\sigma(i) = a_{i}$  $(1 \leq i \leq n)$     $\Rightarrow$     $\sigma =\begin{pmatrix}
1 & 2 & \cdots & n \\
a_{1} & a_{2} & \cdots & a_{n} \\
\end{pmatrix} $

 

 

 

Thm 1

Let $A$ and $B$ be sets.

1.  $S_{A}$ is a group

2.  $\left|S_{n} \right| = n!$

3.  $\left|A \right| = \left|B \right|$  $\Rightarrow$  $S_{A} \simeq S_{B}$

 

pf)

  Show 1 : associative

  The composition of functions is associative.

 

  end

 

 

  Show 2 : identity

  $e = \mathrm{id}_{A}$ 

  $(\sigma \circ \mathrm{id}_{A} = \mathrm{id}_{A} \circ \sigma = \sigma)$

 

  end

 

 

  Show 3 : inverse

  The inverse of $\sigma \in S_{A}$ is the inverse function $\sigma^{-1}$

  $(\sigma \circ \sigma^{-1} = \sigma^{-1} \circ \sigma = \mathrm{id}_{A})$

 

  end

 

  Since $\left|A \right| = \left|B \right|$, there exists 1-1 onto function $f : A \to B$

  Define $\phi : S_{A} \to S_{B}$ by

  $\phi(\sigma) = f \circ \sigma \circ f^{-1}$

 

 

  Show 1 : $\phi$ is 1-1

  $\forall \sigma_{1}, \sigma_{2} \in S_{A}$

  $\phi(\sigma_{1}) = \phi(\sigma_{2})$     $\Rightarrow$     $f \circ \sigma_{1} \circ f^{-1} = f \circ \sigma_{2} \circ f^{-1}$     $\Rightarrow$     $\sigma_{1} = \sigma_{2}$

 

  end

 

 

  Show 2 : $\phi$ is onto

  $\forall \tau \in S_{B}$

  Since $f, \tau$ is 1-1 onto,

  $f^{-1} \circ \tau \circ f \in S_{A}$

  Also

  $\phi(f^{-1} \circ \tau \circ f) = f \circ (f^{-1} \circ \tau \circ f) \circ f^{-1} = \tau$

 

  end

 

 

  Show 3 : $\phi$ is a homomorphism

  For $\sigma, \tau \in S_{A}$

  $\phi(\sigma \tau) = f \circ (\sigma \tau) \circ f^{-1}$

                $= f \circ (\sigma \circ \tau) \circ f^{-1}$

                $= f \circ \sigma \circ \mathrm{id}_{A} \circ \tau \circ f^{-1}$

                $= (f \circ \sigma \circ f^{-1}) \circ (f \circ \tau \circ f^{-1})$

                $= \phi (\sigma) \phi (\tau)$

 

  end

 

 

 

Def 2

A group of permutations means a subgroup of $S_{A}$

 

 

 

Def 3

$D_{n}$ $=$ group of symmetries of a regular $n$-gon

We called Dihedral group

 

# $\left|D_{n} \right| = 2n $,  $S_{3} \simeq D_{3}$

 

 

 

Prop 1

$S_{3}$ is nonabelian

 

  Let

  $\rho_{0} = \begin{pmatrix}
1 & 2 & 3 \\
1 & 2 & 3 \\
\end{pmatrix}$,     $\rho_{1} = \begin{pmatrix}
1 & 2 & 3 \\
2 & 3 & 1 \\
\end{pmatrix}$,     $\rho_{2} = \begin{pmatrix}
1 & 2 & 3 \\
3 & 1 & 2 \\
\end{pmatrix}$

 

  $\mu_{1} = \begin{pmatrix}
1 & 2 & 3 \\
1 & 3 & 2 \\
\end{pmatrix}$,     $\mu_{2} = \begin{pmatrix}
1 & 2 & 3 \\
3 & 2 & 1 \\
\end{pmatrix}$,     $\mu_{3} = \begin{pmatrix}
1 & 2 & 3 \\
2 & 1 & 3 \\
\end{pmatrix}$

 

  So $S_{3} = \left\{\rho_{0}, \rho_{1}, \rho_{2}, \mu_{1}, \mu_{2}, \mu_{3} \right\}$

 

  $\rho_{1} \mu_{1} = \begin{pmatrix}
1 & 2 & 3 \\
2 & 3 & 1 \\
\end{pmatrix} \begin{pmatrix}
1 & 2 & 3 \\
1 & 3 & 2 \\
\end{pmatrix} = \begin{pmatrix}
1 & 2 & 3 \\
2 & 1 & 3 \\
\end{pmatrix} = \mu_{3}$

 

  $\mu_{1} \rho_{1} = \begin{pmatrix}
1 & 2 & 3 \\
1 & 3 & 2 \\
\end{pmatrix} \begin{pmatrix}
1 & 2 & 3 \\
2 & 3 & 1 \\
\end{pmatrix} = \begin{pmatrix}
1 & 2 & 3 \\
3 & 2 & 1 \\
\end{pmatrix} = \mu_{2}$

 

  $\therefore$  $S_{3}$ is nonabelian

 

 

 

Prop 2

Let $G, G'$ be groups  and  $\phi : G \to G'$ is 1-1 homomorphism. Then

$G \simeq \phi[G]$  $(\leq G')$

 

# $\phi[G] \leq G'$ is proved by Homomorphism and Factor Groups - Homomorphism - Thm 1

 

  Since $\phi : G \to G'$ is 1-1 homomorphism,

  $\phi : G \to \phi[G]$ is isomorphism.

  $\therefore$  $G \simeq \phi[G]$

 

 

 

Thm 2

Let $n < m$. Then

there exists 1-1 homomorphism $\phi : S_{n} \to S_{m}$

 

# So we can consider $S_{n}$ as a subgroup of $S_{m}$

 

  Define $\phi : S_{n} \to S_{m}$ as follows.

  For $\sigma = \begin{pmatrix}
1 & 2 & \cdots & n \\
a_{1} & a_{2} & \cdots & a_{n} \\
\end{pmatrix} \in S_{n}$,

 

  $\phi(\sigma) = \begin{pmatrix}
1 & 2 & \cdots & n & n+1 & \cdots & m \\
a_{1} & a_{2} & \cdots & a_{n} & n+1 & \cdots & m \\
\end{pmatrix}$

 

  Then $\phi$ is clearly 1-1 homomorphism

 

 

 

Cor 1

$S_{n}$ is nonabelian if $n \geq 3$

 

 

 

Thm 3 Caley's Theorem

Every Group $G$ is isomorphic to a group of permutations.

(That is if $G$ is group, there is a $S_{A}$ and $H \leq S_{A}$ such that $G \simeq H$)

 

  By Prop 2, it is sufficient to show

  there exists a 1-1 homorphism $\phi : G \to S_{A}$  for some set $A$

 

  Now we have $S_{G} = \left\{\sigma \; | \; \sigma : G \to G \text{ is a permutaion} \right\} $

  Fix $g \in G$, and define $\lambda_{g} : G \to G$ by

  $\lambda_{g}(x) = gx$

 

 

  Claim 1 : $\lambda_{g} \in S_{G}$

  $(1)$  $\lambda_{g}$ is 1-1

  For $x, y \in G$,

  $\lambda_{g}(x) = \lambda_{g}(y)$  $\Rightarrow$  $gx = gy$  $\Rightarrow$  $x = y$

 

  $(2)$  $\lambda_{g}$ is onto

  For $y \in G$,

  $\lambda_{g}(g^{-1}y) = g(g^{-1}y) = y$  and  $g^{-1}y \in G$

 

  end

 

  Now define $\phi : G \to S_{G}$ by

  $\phi(g) = \lambda_{g}$

 

 

  Claim 2 : $\phi$ is 1-1 homomorphism

  $(1)$  $\phi$ is 1-1

  $\forall a, b \in G$,

  $\phi(a) = \phi(b)$  $\Rightarrow$  $\lambda_{a} = \lambda_{b}$  $\Rightarrow$  $\lambda_{a}(e) = \lambda_{b}(e)$  $\Rightarrow$  $a = b$

 

  $(2)$  $\phi$ is homomorphism

  $\forall a, b \in G$,

  For all $x \in G$,

  $(\phi(ab))(x) = \lambda_{ab}(x)$

                          $= (ab)x$

                          $= a(bx)$

                          $= \phi(a)(bx)$

                          $= \phi(a)(\phi(b)(x))$

                          $= (\phi(a) \phi(b))(x)$

 

  $\therefore$  $\phi(ab) = \phi(a) \phi(b)$

 

  end