Cycli & Permutationes 轮换与置换
〔定义〕：
设有限集(1) $X$ 上的映射 $f$，若存在 $X$ 的子集 $A=\{a_1,\,a_2,\,\cdots,\,a_\ell\}$ 使得对任意 $a_i\in A$，有
$f(a_\ell)=\begin{equation} \left\{\begin{aligned}&a_{i+1},& i&\neq\ell,\\&a_1,&i&=\ell,\end{aligned} \right.\end{equation}$
并且对任意 $a\in X\setminus A$，有 $f(a)=a$，则称映射 $f$ 为 $X$ 上的轮换（cycle），其长度（length，或简称长）为 $\ell$，记为 $(a_1\;\;a_2\;\;\cdots\;\;a_\ell)$，这一记法称为单行记法（one-line notation）．简单地说，这一轮换即是将序列中的元素依次替换为序列中的下一项，最后一项替换为其原本的首项．
将轮换前后的序列分别写在上下两行形成矩阵状，这一记法称作双行记法（two-line notation）．实际上，通常选用逐次递增 $1$ 的正整数列为自然顺序（natural order）并记入上行，如 $1$ 到 $5$ 的正整数集上的轮换 $(2\;\;4\;\;3)$，以双行记法则表示为 $\begin{pmatrix}
1 & 2 & 3 & 4 & 5 \\
1 & 4 & 2 & 3 & 5
\end{pmatrix}$．双行记法中，各列的位置可以互相替换而不改变其意义，并且常常将轮换前后位置不变的元素省去，如上例可表示为 $\begin{pmatrix}
2 & 3 & 4 \\
4 & 2 & 3
\end{pmatrix}$．长为 $1$ 的轮换为恒等映射，记作 $I$．
长为 $2$ 的轮换称为对换（transposition）．长为 $\ell$ 的轮换可表示为至少 $\ell-1$ 个对换的积（积即复合运算的结果，书写为左乘的形式）．如轮换 $(2\;\;4\;\;3)$ 可以表示为 $(2\;\;3)(2\;\;4)$．若对换的元素在序列中相邻，则称如此的对换为相邻对换（adjacent transposition）．
考虑集合 $X$ 上的两个轮换 $\kappa,\,\kappa’$，若 $\kappa$ 与 $\kappa’$ 所改变位置的元素中不存在相同者，则称 $\kappa$ 与 $\kappa’$ 不交（disjoint）．显然地，不交的轮换可交换．
将轮换的单行记法中各元素按倒序改写，则得到该轮换的逆，而在双行记法中，将上下两行互换则亦然．
〔定义〕：
有限集 $\varSigma$ 到其自身的一个双射 $\sigma$ 称为 $\varSigma$ 上的一个置换（permutation）．有限集上任一置换都能表示为有限个不交的轮换之积，进而可以表示为有限个对换之积，并且无论表示方式，对换的个数总是保持为奇数或偶数其一．由此，可表示为奇数个对换之积的置换称为奇置换（odd permutation），否则称为偶置换（even permutation）．
〔定义〕：
有限集 $\varSigma$ 上的所有置换所成集合 $S(\varSigma)$ 关于复合运算（左乘）形成群，称为 $\varSigma$ 上的对称群（symmetric group），其单位元为恒等映射 $I$，且 $|S(\varSigma)|=|\varSigma|!$．$S(\varSigma)$ 的任一子群称为 $\varSigma$ 上的置换群（permutation group）．
若有限集 $\varSigma,\,\varSigma’$ 的势均为 $n$，则不难看出 $S(\varSigma)\cong S(\varSigma’)$，于是任一 $n$ 元集合上的对称群均可视作 $n!$ 阶的同一对称群，称为 $n$ 次对称群（symmetric group of degree $n$），记为 $S_n,\;\mathrm{Sym}(n)$ 或 $\mathfrak S_n$(2)（后文出于简便且避免歧义而采用后者），而其子群称为 $n$ 次置换群（permutation group of degree $n$）．需要注意的是此处的 $n$ 称为次数（degree），而其阶数为 $n!$．未特别指明的情况下，$\mathfrak S_n$ 均指 $1$ 到 $n$ 的正整数集 $\{k\in\mathbb N\mid 1\leq k\leq n\}$ 上的对称群．
〔定义〕：
同为奇（偶）置换的两个置换之积为偶置换，否则为奇置换．若置换 $\tau$ 为奇置换，记 $\operatorname{sgn}\tau=-1$，否则记 $\operatorname{sgn}\tau=1$，此处的 $\operatorname{sgn}\tau$ 称为置换 $\tau$ 的符号（sign）．
定义映射 $f:\mathfrak S_n\to(\{-1,\,1\},\,\times),\quad\tau\mapsto\operatorname{sgn}\tau$，当 $n\geq 2$，易知 $f$ 为满同态．
$\ker f$ 是 $\mathfrak S_n\;(n\geq 2)$ 上所有偶置换所成子群，称为 $n$ 次交错群（或交替群，alternating group of degree $n$），记为 $A_n,\;\mathrm{Alt}(n)$ 或 $\mathfrak A_n$（出于同样的考量，后文均用后者）．
- 由同态基本定理可知 $\mathfrak A_n\unlhd \mathfrak S_n\;(n\geq2)$，并且 $[\mathfrak A_n:\mathfrak S_n]=2$，$|\mathfrak A_n|=n!/2$．
〔定理 8.1〕：
当 $n\geq 2$，$\{(1,\,i)\mid 2\leq i\leq n\}$ 是 $\mathfrak S_n$ 的一个生成元系．
〔证明〕：
$\forall\;2\leq i,\,j\leq n,\;i\neq j,$
$(i\;\;j)=(1\;\;i)(1\;\;j)(1\;\;i)$．
■
〔定理 8.2〕：
当 $n\geq 3$，全体长为 $3$ 的轮换形成 $\mathfrak A_n$ 的一个生成元系．
〔证明〕：
任一偶置换均可表示为偶数个对换之积，从而只需证明任意两个对换之积均可表示为长度为 $3$ 的轮换（之积）．
于是对于任一偶置换 $\tau=(i\;\;j)(r\;\;s)\quad(i\neq j,\;r\neq s)$，
若 $(i\;\;j)=(r\;\;s)$，则 $\tau=I$（自然可以是两个互逆的轮换之积）；
若 $j=r,\;i\neq s$，则 $\tau=(j\;\;s\;\;i)$；
若 $i,\,j,\,r,\,s$ 彼此不等，则 $\tau=(r\;\;i\;\;s)(i\;\;j\;\;r)$．
■
〔定理 8.3〕：
任一置换均可表示为有限个不交的轮换之积，且在不计顺序的情况下这些轮换的组合是唯一的．
〔证明〕：
记 $\mathfrak S_n$ 是 $n$ 元集合 $X$ 上的对称群，对任一 $\sigma\in\mathfrak S_n$，定义等价关系 $\sim$：
$a\sim b\;\Leftrightarrow\;\exists\;k\in\mathbb Z,\quad \sigma^k(a)=b\quad$ $(a,\,b\in X)$，
则 $X=\displaystyle\bigsqcup_{i=1}^s\;[r_i]$，其中 $[r_i]$ 为 $r_i\in X$ 关于 $\sim$ 的等价类．
$k_i:=|[r_i]|$，则对于代表元 $r_i\in[r_i]$，$k_i$ 是使得 $\sigma^{k}(r_i)=r_i$ 的最小正整数 $k$，亦即 $[r_i]=\{\sigma^k(r_i)\mid 0\leq k\leq k_1\}$．
令 $\sigma_i=\displaystyle\prod_{k=0}^{k_i-1}\sigma^k(r_i)$（依次右乘），
则 $\sigma=\displaystyle\prod_{i=1}^s \sigma_i$（左乘右乘均可），且唯一性易证．
■
〔定义〕：
将 $\mathfrak S_n$ 上的置换表示为若干个轮换之积（位置不变的元素视为经历恒等变换），若其中长为 $\ell$ 的轮换共有 $\lambda_\ell$ 个（$1\leq \lambda\leq n$），则称置换的型（type）为 $1^{\lambda_1}2^{\lambda_2}\cdots n^{\lambda_n}$，特别地，若 $\lambda_i=0$，则 $i^{\lambda_i}=i^0$ 部分可略去．
〔例〕：
考虑 $\mathfrak S_7$ 中的置换 $(2\;\;3\;\;1\;\;5\;\;4\;\;6\;\;7)=(1\;\;2\;\;3)(4\;\;5)(6)(7)=(1\;\;2\;\;3)(4\;\;5)$，可知其型为 $1^22^13^1$．
〔定理 8.4〕：
设 $\sigma,\,\sigma’\in\mathfrak S_n$，则有
$\sigma$ 与 $\sigma’$ 共轭 $\Leftrightarrow$ $\sigma$ 与 $\sigma’$ 的型相同．
〔证明〕：
充分性：
若 $\sigma$ 与 $\sigma’$ 共轭，则 $\exists\;\tau\in\mathfrak S_n,\quad \sigma’=\tau\sigma\tau^{-1}$，从而可将 $\sigma$ 表示为不交的轮换之积：
$\sigma=(a\;\;b\;\;\cdots\;\;c)\cdots(\alpha\;\;\beta\;\;\cdots\;\;\gamma)$，
由于 $(\tau\sigma\tau^{-1})(\tau(a))=\tau\sigma(a)=\tau(b)$，所以
$\sigma’=\tau\sigma\tau^{-1}$ $=(\tau(a)\;\;\tau(b)\;\;\cdots\;\;\tau(c))\cdots(\tau(\alpha)\;\;\tau(\beta)\;\;\cdots\;\;\tau(\gamma))$，
于是可知 $\sigma$ 与 $\sigma’$ 的型相同．
必要性：
设 $\sigma$ 与 $\sigma’$ 的型相同，即
$\sigma=(a\;\;b\;\;\cdots\;\;c)\cdots(\alpha\;\;\beta\;\;\cdots\;\;\gamma)$，
$\sigma’=(a’\;\;b’\;\;\cdots\;\;c’)\cdots(\alpha’\;\;\beta’\;\;\cdots\;\;\gamma’)$，
又令 $\tau=\begin{pmatrix}
a & b & \cdots & c & \cdots & \alpha & \beta & \cdots & \gamma \\
a’ & b’ & \cdots & c’ & \cdots & \alpha’ & \beta’ & \cdots & \gamma’
\end{pmatrix}$，则 $\tau\sigma\tau^{-1}=\sigma’$，得证．■
- 型为 $1^{\lambda_1}2^{\lambda_2}\cdots n^{\lambda_n}$ 的置换之共轭类记为 $[1^{\lambda_1}2^{\lambda_2}\cdots n^{\lambda_n}]$．
〔例〕：
$\mathfrak S_3$ 中所有共轭类如下：
$[1^3]:\qquad I$
$[1^12^1]:\;\;\;(1\;\;2),\;(1\;\;3),\;(2\;\;3)$
$[3^1]:\quad\;\;\;(2\;\;3\;\;1),\;(3\;\;1\;\;2)$
Catervae Simplices 单群
〔定义〕：
若非平凡的群 $G$ 只有平凡的子群，则称 $G$ 为单群（simple group）．
- 除去质数阶的群（理所当然都是循环群），其余单群均为非阿贝尔群．
单群之于群论如同质数之于数论，除却平凡群，其余的群均可以以某种方式“分解”成特定的单群（这一事实称为 Jordan–Hölder 定理）．然而确定所有单群的种类并不如单群本身这么简单．上百名学者以数万页的文章，才终在 2004 年完成了所有有限单群的分类工作，而这一历程跨越了近半世纪．
相关视频推荐：
〔定理 8.5〕：
当 $n\geq 5$，交错群 $\mathfrak A_n$ 为单群．
该定理的证明较长，此处从略．
〔推论〕：
当 $n\geq 5$，$\mathfrak A_n$ 是 $\mathfrak S_n$ 的唯一非平凡正规子群．
〔证明〕：
（以下均以 $n\geq 5$ 为前提）
已知 $\mathfrak A_n\unlhd \mathfrak S_n$，
设 $N\unlhd \mathfrak S_n,\;N\neq\{e\}$，
$N\leq \mathfrak A_n\;\Rightarrow\;N\unlhd \mathfrak A_n\;\Rightarrow\;N=\mathfrak A_n$．
否则即 $N$ 包含奇置换，于是有 $N\cap\mathfrak A_n\unlhd \mathfrak A_n$，且 $\mathfrak A_n/(N\cap\mathfrak A_n)\cong (N\cdot\mathfrak A_n)/N=\mathfrak S_n/N$(3)， （第二同构定理）
从而由计数公式有 $|N\cap\mathfrak A_n|=\dfrac{|N|\cdot|\mathfrak A_n|}{|\mathfrak S_n|}=\dfrac{|N|}2$．
而又已知 $N\cap\mathfrak A_n\unlhd \mathfrak A_n$，且 $\mathfrak A_n$ 为单群，所以 $N\cap\mathfrak A_n$ 必然等同于 $\mathfrak A_n$ 或 $\{e\}$ 其一．
若为前者，则 $|N|=2|N\cap\mathfrak A_n|=2|\mathfrak A_n|=|\mathfrak S_n|$，即 $N=\mathfrak S_n$．
若为后者，则 $|N|=2$，而显然地，$\mathfrak S_n$ 中不含 $2$ 阶子群(4)，矛盾．
综上，$N$ 等于 $\mathfrak S_n$ 或 $\mathfrak A_n$，因此 $\mathfrak A_n$ 是 $\mathfrak S_n$ 的唯一非平凡正规子群．
$\mathfrak A_2=\{I\}\cong\{e\}$；
$\mathfrak A_3=\{I,\,(1\;\;2)(1\;\;3),\,(1\;\;3)(1\;\;2)\}\cong\mathbb Z_3$；
$\{I,\,(1\;\;2)(3\;\;4),\,(1\;\;3)(2\;\;4),\,(1\;\;4)(2\;\;3)\}\lhd\mathfrak A_4$ ，因此 $\mathfrak A_4$ 不是单群．
前文中曾指出关于正规子群的一个重要事实，即在 $N\leq M\leq G$ 且 $N\unlhd M,\;M\unlhd G$ 的前提下，不能保证 $N\unlhd G$ 总是成立，换言之，正规子群的关系是非传递的．其中一个典型的反例可以构造如下：
令 $A=\{I,\,(1\;\;2)(3\;\;4)\}$，该群同构于 $2$ 阶循环群．
令 $K=\{I,\,(1\;\;2)(3\;\;4),\,(1\;\;3)(2\;\;4),\,(1\;\;4)(2\;\;3)\}$，该群同构于 Klein 四元群．
由于 $K$ 是阿贝尔群，且 $A<K$，因此 $A\lhd K$，而前文已提及，$K\lhd \mathfrak A_4$，然而 $A\lhd \mathfrak A_4$ 并不成立，比如考虑 $(1\;\;2\;\;3)\in\mathfrak A_4$，则 $(1\;\;2\;\;3)A=\{(1\;\;2\;\;3),\,(1\;\;3\;\;4)\}$，而 $A(1\;\;2\;\;3)=\{(1\;\;2\;\;3),\,(2\;\;4\;\;3)\}$，$(1\;\;3\;\;4)\neq(2\;\;4\;\;3)$，所以 $(1\;\;2\;\;3)A\neq A(1\;\;2\;\;3)$．
需要注意的一点是，同构并不保持对同一群的正规性，亦即 $A\unlhd G,\;B\leq G,\;A\cong B$ 并不能保证 $B\unlhd G$．对此事实的严谨说明暂且不甚简易，而简言之即同构只保证了群的“内在”结构一致，正规性却是作为子群对于另一群而言的．作为子群时，互相同构的群并不总是具有同样的地位．如上的 $K$ 是 Klein 四元群在 $\mathfrak S_4$ 中的一种表示形式，可以证明 $K\lhd \mathfrak S_4$，然而其他表示，例如 $K’:=\{I,\,(1\;\;2),\,(3\;\;4),\,(1\;\;2)(3\;\;4)\}$ 虽然满足了 $K’\cong V,\;K’\leq\mathfrak S_4$，却不满足 $K’\lhd \mathfrak S_4$．
Annotationes 注释
(1). 轮换，以及下文的置换亦可考虑无限集上的形式，而此处只考虑有限集的情况． ↩
(2). $\mathfrak S$ 是字母 S 的 Fraktur 字体（通常也称为哥特体）形式，下文的 $\mathfrak A$ 则是字母 A 的相应形式． ↩
(3). $N$ 中包含至少一个奇置换，则可以通过 $\mathfrak A_n$ 中的偶置换相乘得到一个对换 $(i\;\;j)$，不难证明如此乘积可以得到 $1\leq n_0\leq n,\;n\neq i$ 的任一形如 $(i\;\;n_0)$ 的对换，这些对换组成了 $\mathfrak S_n$ 的生成元系（参照 Th. 8.1）． ↩
(4). 若存在 $2$ 阶子群，其必然含有恒等变换为单位元，而另一元素并非恒等变换从而必然违反可逆性． ↩