$$
\newcommand{aster}{*}
\newcommand{exist}{\exists}
\newcommand{B}{\mathbb B}
\newcommand{C}{\mathbb C}
\newcommand{I}{\mathbb I}
\newcommand{N}{\mathbb N}
\newcommand{Q}{\mathbb Q}
\newcommand{R}{\mathbb R}
\newcommand{Z}{\mathbb Z}
\newcommand{eR}{\overline {\mathbb R}}
\newcommand{cD}{ {\mathbb D}}
\newcommand{dD}{ {\part \mathbb D}}
\newcommand{dH}{ {\part \mathbb H}}
\newcommand{eC}{\overline {\mathbb C}}
\newcommand{A}{\mathcal A}
\newcommand{D}{\mathcal D}
\newcommand{E}{\mathcal E}
\newcommand{F}{\mathcal F}
\newcommand{G}{\mathcal G}
\newcommand{H}{\mathcal H}
\newcommand{J}{\mathcal J}
\newcommand{L}{\mathcal L}
\newcommand{U}{\mathcal U}
\newcommand{M}{\mathcal M}
\newcommand{O}{\mathcal O}
\newcommand{P}{\mathcal P}
\newcommand{S}{\mathcal S}
\newcommand{T}{\mathcal T}
\newcommand{V}{\mathcal V}
\newcommand{W}{\mathcal W}
\newcommand{X}{\mathcal X}
\newcommand{Y}{\mathcal Y}
\newcommand{bE}{\symbf E}
\newcommand{bF}{\symbf F}
\newcommand{bD}{\symbf D}
\newcommand{bI}{\symbf I}
\newcommand{bX}{\symbf X}
\newcommand{bY}{\symbf Y}
\newcommand{nz}{\mathcal Z}
\newcommand{bT}{\mathbb T}
\newcommand{bB}{\mathbb B}
\newcommand{bS}{\mathbb S}
\newcommand{bA}{\mathbb A}
\newcommand{bL}{\mathbb L}
\newcommand{bP}{\symbf P}
\newcommand{bM}{\symbf M}
\newcommand{bH}{\mathbb H}
\newcommand{dd}{\mathrm d}
\newcommand{Mu}{\mathup M}
\newcommand{Tau}{\mathup T}
\newcommand{ae}{\operatorname{a.e.}}
\newcommand{aut}{\operatorname{aut}}
\newcommand{adj}{\operatorname{adj}}
\newcommand{char}{\operatorname{char}}
\newcommand{cov}{\operatorname{Cov}}
\newcommand{cl}{\operatorname{cl}}
\newcommand{cont}{\operatorname{cont}}
\newcommand{e}{\mathbb E}
\newcommand{pp}{\operatorname{primitive}}
\newcommand{dist}{\operatorname{dist}}
\newcommand{diam}{\operatorname{diam}}
\newcommand{fp}{\operatorname{Fp}}
\newcommand{from}{\leftarrow}
\newcommand{Gal}{\operatorname{Gal}}
\newcommand{GCD}{\operatorname{GCD}}
\newcommand{LCM}{\operatorname{LCM}}
\newcommand{fg}{\mathrm{fg}}
\newcommand{gf}{\mathrm{gf}}
\newcommand{im}{\operatorname{Im}}
\newcommand{image}{\operatorname{image}}
\newcommand{inj}{\hookrightarrow}
\newcommand{irr}{\operatorname{irr}}
\newcommand{lcm}{\operatorname{lcm}}
\newcommand{ltrieq}{\mathrel{\unlhd}}
\newcommand{ltri}{\mathrel{\lhd}}
\newcommand{loc}{ {\operatorname{loc}}}
\newcommand{null}{\operatorname{null}}
\newcommand{part}{\partial}
\newcommand{pf}{\operatorname{Pf}}
\newcommand{pv}{\operatorname{Pv}}
\newcommand{rank}{\operatorname{rank}}
\newcommand{range}{\operatorname{range}}
\newcommand{re}{\operatorname{Re}}
\newcommand{span}{\operatorname{span}}
\newcommand{su}{\operatorname{supp}}
\newcommand{sgn}{\operatorname{sgn}}
\newcommand{syn}{\operatorname{syn}}
\newcommand{var}{\operatorname{Var}}
\newcommand{res}{\operatorname{Res}}
\newcommand{data}{\operatorname{data}}
\newcommand{erfc}{\operatorname{erfc}}
\newcommand{erfcx}{\operatorname{erfcx}}
\newcommand{tr}{\operatorname{tr}}
\newcommand{col}{\operatorname{Col}}
\newcommand{row}{\operatorname{Row}}
\newcommand{sol}{\operatorname{Sol}}
\newcommand{lub}{\operatorname{lub}}
\newcommand{glb}{\operatorname{glb}}
\newcommand{ltrieq}{\mathrel{\unlhd}}
\newcommand{ltri}{\mathrel{\lhd}}
\newcommand{lr}{\leftrightarrow}
\newcommand{phat}{^\widehat{\,\,\,}}
\newcommand{what}{\widehat}
\newcommand{wbar}{\overline}
\newcommand{wtilde}{\widetilde}
\newcommand{iid}{\operatorname{i.i.d.}}
\newcommand{Exp}{\operatorname{Exp}}
\newcommand{abs}[1]{\left| {#1}\right|}
\newcommand{d}[2]{D_{\text{KL}}\left (#1\middle\| #2\right)}
\newcommand{n}[1]{\|#1\|}
\newcommand{norm}[1]{\left\|{#1}\right\|}
\newcommand{pd}[2]{\left \langle {#1},{#2} \right \rangle}
\newcommand{argmax}[1]{\underset{#1}{\operatorname{argmax}}}
\newcommand{argmin}[1]{\underset{#1}{\operatorname{argmin}}}
\newcommand{p}[1]{\left({#1}\right)}
\newcommand{c}[1]{\left \{ {#1}\right\}}
\newcommand{s}[1]{\left [{#1}\right]}
\newcommand{a}[1]{\left \langle{#1}\right\rangle}
\newcommand{cc}[2]{\left(\begin{array}{c} #1 \\ #2 \end{array}\right)}
\newcommand{f}{\mathfrak F}
\newcommand{fi}{\mathfrak F^{-1}}
\newcommand{Fi}{\mathcal F^{-1}}
\newcommand{l}{\mathfrak L}
\newcommand{li}{\mathfrak L^{-1}}
\newcommand{Li}{\mathcal L^{-1}}
\newcommand{const}{\text{const.}}
$$
Symmetric Groups
#
Symmetric groups
#
$\sigma: A \to A$ that is bijective is a permutation of $A$.
A permutation $\sigma$ can be represented with the following notation:
$$
\sigma=\left(\begin{array}{lll}
\alpha & \beta & \cdots \\
\sigma(\alpha)& \sigma(\beta)&\cdots
\end{array}\right)
$$
$S _ {A}$ Is the collection of all permutations of $A$. $S _ {A}$ is a group under function composition.
- $|A| = |B| \implies S _ A \simeq S _ B$.
- Suppose $A = \c{0,1, \ldots, n - 1}$. Denote $S _ n := S _ A$. Note that $S _ {n}$ has $n !$ elements.
Decompose permutations into cycles
#
Suppose $\sigma \in S _ n$. Let $A = \c{0, 1, \ldots, n - 1}$.
- Define relationship $\sim$ on $A$. $i \sim j \iff \exists k \in \N: \sigma^k(i) = j$.
- Consider the equivalent classes $A = E _ 1 + E _ 2 + \cdots + E _ k$. Where $|E _ m| = N _ m$.
- For $1 \le m \le k$, define permutation $c _ m: A \to A$ as following:
- For $a \in E _ m$, $c _ m(a) = \sigma(a)$.
- For $a \notin E _ m$, $c _ m(a) = a$.
- $c _ m: A \to A$ is called a cycle on $A$.
- Let $a _ 0 \in E _ m$ and $a _ {t + 1} = \sigma(a _ t)$ for $t \ge 0$.
- $c _ m$ can be represented with tuple $(a _ 0, \ldots, a _ {N _ m - 1})$. Since $c _ m(a _ 0) = a _ 1$, $c _ m(a _ 1) = a _ 2$, and so on...
Clearly $\sigma = c _ 1 \circ c _ 2\circ \cdots \circ c _ k$. We can decompose any permutation in $S _ n$ into composition of cycles.
- Disjoint cycles on different equivalent classes can commute.
Example: Group $S _ 3$
#
We give the table for $S _ 3$. $|S _ 3| = 6$. All elements are cycles.
$$
\begin{array}{c|cccccc}
\circ & \iota & (0,1,2) & (0,2,1) & (0,1) & (0,2) & (1,2) \\
\hline \iota & \iota & (0,1,2) & (0,2,1) & (0,1) & (0,2) & (1,2) \\
(0,1,2) & (0,1,2) & (0,2,1) & \iota & (0,2) & (1,2) & (0,1) \\
(0,2,1) & (0,2,1) & \iota & (0,1,2) & (1,2) & (0,1) & (0,2) \\
(0,1) & (0,1) & (1,2) & (0,2) & \iota & (0,2,1) & (0,1,2) \\
(0,2) & (0,2) & (0,1) & (1,2) & (0,1,2) & \iota & (0,2,1) \\
(1,2) & (1,2) & (0,2) & (0,1) & (0,2,1) & (0,1,2) & \iota
\end{array}
$$
All groups below order 6 are abelian. Thus $S _ {3}$ is the smallest group which is not abelian.
- Since $S _ 3$ is a subgroup (in isomorphic sense) of $S _ n, n \ge 3$, they are all non-abelian.
(Example: Dihedral group $D _ {n}$)
Define reflection $\mu \in S _ n$ as $\mu(i) := (n - 1) - i$.
Define rotation $\rho \in S _ n$ as $\rho(i) := i + 1 \bmod n$.
Dihedral group is generated by the two operations: $D _ n := \a{\mu, \rho} \le S _ n$.
It is not hard to see that $|D _ n| = 2n$ and
$$
D _ {n}=\left\{\iota, \rho, \rho^{2}, \rho^{3}, \cdots, \rho^{n-1}, \mu, \mu \rho, \mu \rho^{2}, \mu \rho^{3}, \cdots, \mu \rho^{n-1}\right\}
$$
- $\mu^s \rho^t$ is called the standard form of $\sigma \in D _ n$. Where $s \in \c{0, 1}$, and $0\le t < n$.
Cayley's theorem
#
Let $\a{G, \cdot}$ be a group. It is isomorphic to a subgroup of $S _ G$.
- For $g \in G$ defined permutation $\ell _ g: G \to G$ as $x \mapsto gx$.
- Define map $\phi: G \to S _ G$ as $g \mapsto \ell _ g$.
- $\phi$ is an injective homomorphism. So $G \simeq \phi[G] \le S _ G$.
- $\phi(xy) = \ell _ {xy} = \ell _ x\circ\ell _ y= \phi(x) \circ \phi(y)$.
- $\phi(x) = \phi(y) \implies \forall g \in G :xg = yg \implies x = y$.
Decompose cycles into transpositions
#
A cycle of form $(a, b)$ for $a \neq b$ is called a transposition.
Given cycle $(a _ 0, a _ 1, \ldots, a _ {n - 1})$ in $S _ A$, it can be written as a composition of transpositions:
$$
\p{a _ {0}, a _ {1}, \cdots, a _ {n - 1}}=\p{a _ {0}, a _ {n-1}}\p{a _ 0, a _ {n -2}} \cdots (a _ 0, a _ {1})
$$
Sign of permutations in $S _ n$
#
A permutation $\sigma \in S _ n$ is odd if it is the composition of an odd number of transpositions. Otherwise it is called even.
Consider sequence $a _ k = \sigma(k)$ for $0 \le k < n$. The inversion number of $\sigma \in S _ n$ is defined as following:
$$
I(\sigma) := \#\c{a _ i > a _ j: 0 \le i < j < n} \in \N
$$
$\sigma$ is odd if and only if $I(\sigma)$ is odd.
- Since compositing with a transposition changes $I(\sigma)$ by an odd integer.
Define the sign function $\sgn: S _ n \to \c{1, -1}$ as $\sgn(\sigma) := (-1)^{I(\sigma)}$.