抽象代数/群论/置换群

置换群

对于任何有限非空集S，A(S) 是S到S的所有一对一变换（映射）的集合，它形成一个称为置换群的群，并且A(S) 的任何元素，即从S到自身的映射，被称为置换。

对称群

定理 1： 令 $A$ 是任何集合。那么，从 $A$ 到自身的双射的集合 $S_{A}$，$f\,:,A\rightarrow A$，在函数的复合运算下形成一个群。

证明: 我们必须验证群公理。结合律成立，因为函数的复合运算总是结合的: $(f\circ g)\circ h(x)=f\circ g(h(x))=f(g(h(x)))=f(g\circ h(x))=f\circ (g\circ h)(x)$ 其中复合运算是定义的。单位元是恒等函数，由 $\mathrm {id} _{A}(a)=a$ 对所有 $a\in A$ 给出。最后，函数 $f$ 的逆函数是函数 $f^{-1}$，它将 $f(a)$ 映射到 $a$ 对所有 $a\in A$。这个函数存在并且是唯一的，因为 $f$ 是一个双射。因此，如所述，$S_{A}$ 是一个群。 ∎

$S_{A}$ 被称为 *对 $A$ 的对称群*。当 $A=\{1,2,...,n\}\,,\,n\in \mathbb {N}$ 时，我们将它的对称群写成 $S_{n}$，并将这个群称为 *对 $n$ 个字母的对称群*。它也被称为 *对 $n$ 个字母的置换群*。正如我们很快就会看到，这是一个合适的名称。

我们将使用不同的符号 $\iota$ 代替 $e$，来表示 $S_{n}$ 中的恒等函数。

当 $\sigma \in S_{n}$ 时，我们可以通过指定它将每个元素发送到哪里来指定 $\sigma$。有很多方法可以用数学方法来编码这些信息。一个显而易见的方法是将 $\sigma$ 识别为唯一 $n\times n$ 矩阵，在 $(i,\sigma (i))$ 项中具有值 $1$，而在其他地方为 $0$。然后，函数的合成对应于矩阵的乘法。实际上，对应于 $\rho$ 的矩阵在 $(i,\rho (i))$ 项中具有值 $1$，这与 $(\sigma (j),\rho (\sigma (j)))$ 相同，因此积在 $(j,\rho (\sigma (j)))$ 项中具有值 $1$。这种表示法可能看起来很笨拙。幸运的是，存在一种更方便的表示法，我们将使用它。

我们可以用 $2\times n$ 矩阵 $\left({\begin{array}{cccc}1&2&\dots &n\\\sigma (1)&\sigma (2)&\dots &\sigma (n)\end{array}}\right)$ 来表示任何 $\sigma \in S_{n}$。我们显然失去了函数合成与矩阵乘法之间的对应关系，但我们获得了更易读的符号。目前，我们将使用这种表示法。

注 2: 令 $\sigma ,\rho \in S_{n}$. 那么，积 $\sigma \rho \equiv \sigma \circ \rho$ 是首先作用 $\rho$，然后作用 $\sigma$ 所获得的函数。也就是说，$\sigma \rho (x)=\sigma (\rho (x))$. 在 $S_{n}$ 中计算积时，这一点很重要。一些教科书试图通过写类似 $(x)\rho \sigma$ 的函数（即把参数写在函数的左边）来解决经常出现的混淆。我们不会这样做，因为它不符合标准。读者应该利用下面的例子和定理来感受在 $S_{n}$ 中的积。

例 3: 我们将展示 $S_{3}$ 的乘法表。我们为 $S_{3}$ 引入特殊符号：$\iota =\rho _{0}$，$\rho _{1}=\left({\begin{array}{ccc}1&2&3\\2&3&1\end{array}}\right)$，$\rho _{2}=\left({\begin{array}{ccc}1&2&3\\3&1&2\end{array}}\right)$，$\mu _{1}=\left({\begin{array}{ccc}1&2&3\\1&3&2\end{array}}\right)$，$\mu _{2}=\left({\begin{array}{ccc}1&2&3\\3&2&1\end{array}}\right)$ 和 $\mu _{3}=\left({\begin{array}{ccc}1&2&3\\2&1&3\end{array}}\right)$。那么 $S_{3}$ 的乘法表为

${\begin{array}{c|cccccc}\circ &\rho _{0}&\rho _{1}&\rho _{2}&\mu _{1}&\mu _{2}&\mu _{3}\\\hline \rho _{0}&\rho _{0}&\rho _{1}&\rho _{2}&\mu _{1}&\mu _{2}&\mu _{3}\\\rho _{1}&\rho _{1}&\rho _{2}&\rho _{0}&\mu _{3}&\mu _{1}&\mu _{2}\\\rho _{2}&\rho _{2}&\rho _{0}&\rho _{1}&\mu _{2}&\mu _{3}&\mu _{1}\\\mu _{1}&\mu _{1}&\mu _{2}&\mu _{3}&\rho _{0}&\rho _{2}&\rho _{1}\\\mu _{2}&\mu _{2}&\mu _{3}&\mu _{1}&\rho _{1}&\rho _{0}&\rho _{2}\\\mu _{3}&\mu _{3}&\mu _{1}&\mu _{2}&\rho _{2}&\rho _{1}&\rho _{0}\end{array}}$

定理 4： $S_{n}$ 的阶为 $n!$.

证明：这可以通过计数论证得出。我们可以在 $S_{n}$ 中指定一个唯一的元素，方法是指定每个 $i\in \{1,2,...,n\}$ 映射到的位置。此外，任何排列都可以用这种方式指定。设 $\sigma \in S_{n}$。在选择 $\sigma (1)$ 时，我们完全自由，有 $n$ 种选择。然后，在选择 $\sigma (2)$ 时，我们必须从 $\{1,...,n\}-\{\sigma (1)\}$ 中选择，总共有 $n-1$ 种选择。以此类推，我们看到对于 $\sigma (i)$，我们必须从 $\{1,...,n\}-\{\sigma (1),...,\sigma (i-1)\}$ 中选择，总共有 $n+1-i$ 种选择。指定一个元素的总方法数，以及 $S_{n}$ 中元素的总数，因此为 $|S_{n}|=\prod _{i=1}^{n}(n+1-i)=n(n-1)...\cdot 2\cdot 1=n!$，证毕。 ∎

定理 5： $S_{n}$ 对于所有 $n\geq 3$ 都是非阿贝尔群。

证明：设 $\sigma =\left({\begin{array}{ccccc}1&2&3&\dots &n\\2&1&3&\dots &n\end{array}}\right)$ 为仅交换 1 和 2 的函数，$\rho =\left({\begin{array}{ccccc}1&2&3&\dots &n\\1&3&2&\dots &n\end{array}}\right)$ 为仅交换 2 和 3 的函数。那么 $\sigma \rho =\left({\begin{array}{ccccc}1&2&3&\dots &n\\2&3&1&\dots &n\end{array}}\right)$ 和 $\rho \sigma =\left({\begin{array}{ccccc}1&2&3&\dots &n\\3&1&2&\dots &n\end{array}}\right)$。由于 $\sigma \rho \neq \rho \sigma$，$S_{n}$ 不是阿贝尔群。∎

定义 6：设 $\sigma \in S_{n}$ 使得 $\sigma ^{k}=\iota$ 对于某个 $k\in \mathbb {Z}$ 成立。那么 $\sigma$ 被称为 $k$-循环，其中 $k$ 是最小的正整数。设 $\sigma ^{*}$ 是整数集 $a$，使得 $\sigma (a)\neq a$。两个循环 $\sigma ,\rho$ 被称为不相交的，如果 $\sigma ^{*}\cap \rho ^{*}=\emptyset$。另外，一个 2-循环被称为对换。

备注 3: 重要的是要认识到，如果 $a\in \sigma ^{*}$，那么 $\sigma (a)$ 也是。如果 $\sigma (a)=b\neq a$，那么如果 $\sigma (b)=b$，我们就有 $\sigma$ 不是一一映射的。

定理 7: 令 $\sigma ,\rho \in S_{n}$。如果 $\sigma ^{*}\cap \rho ^{*}=\emptyset$，那么 $\sigma \rho =\rho \sigma$。

证明: 对于任何整数 $1\leq a\leq n$ 使得 $a\in \sigma ^{*}$ 但 $a\not \in \rho ^{*}$，我们有 $\sigma \rho (a)=\sigma (\iota (a))=\sigma (a)=\iota (\sigma (a))=\rho (\sigma (a))=\rho \sigma (a)$。类似的论证适用于 $a\in \rho ^{*}$ 但 $a\not \in \sigma ^{*}$。如果 $a\not \in \sigma ^{*}\cup \rho ^{*}$，我们必须有 $\sigma \rho (a)=\sigma (a)=a=\rho (a)=\rho \sigma (a)$。由于 $\sigma ^{*}\cap \rho ^{*}=\emptyset$，我们现在已经穷尽了所有 $a\in \{1,...,n\}$，我们完成了。 ∎

定理 8: 任何置换都可以表示为不相交循环的复合。

证明：令 $\sigma \in S_{n}$。选择一个元素 $a\in \sigma ^{*}$ 并计算 $\sigma (a),\sigma ^{2}(a),...,\sigma ^{k}(a)=a$。由于 $S_{n}$ 是有限阶数 $n!$，我们知道 $k$ 存在且 $k\leq n!$。我们现在找到了一个 $k$-循环 $\sigma _{1}$ 包含 $a$。由于 $\sigma _{1}^{*}=\{a,\sigma (a),...,\sigma ^{k-1}(a)\}$，这个循环可以从 $\sigma$ 中分解出来得到 $\sigma =\sigma _{1}\sigma ^{\prime }$。重复此过程，由于 $\sigma ^{*}$ 是有限的，该过程将终止，我们已经构建了一个等于 $\sigma$ 的不相交循环的组合。 ∎

现在我们已经证明了所有置换都只是不相交循环的组合，我们可以引入置换的最终简写符号。对于一个 $n$-循环 $\sigma$，我们可以通过选择任何元素 $a\in \sigma ^{*}$ 并写成 $\sigma =\left(a\ \sigma (a)\ \sigma ^{2}(a)\ ...\ \sigma ^{n-1}(a)\right)$ 来显示它的作用。

定理 9：任何 $n$-循环可以表示为换位的组合。

证明：令 $\sigma =\left(a\ \sigma (a)\ \sigma ^{2}(a)\ ...\ \sigma ^{n-1}(a)\right)$。 那么，$\sigma =\left(a\ \sigma ^{2}(a)\ ...\ \sigma ^{n-1}(a)\right)\left(a\ \sigma (a)\right)$ （验证一下！），省略了复合符号$\circ$。重复此过程，得到$\sigma =\left(a\ \sigma ^{n-1}(a)\right)...\left(a\ \sigma ^{2}(a)\right)\left(a\ \sigma (a)\right)$。 ∎

注10：这种用对换乘积表示$\sigma$的方式不是唯一的。 然而，正如我们现在将要看到的，这种表示的“奇偶性”是明确定义的。

定义11：如果一个置换可以表示为偶数个对换的乘积，则该置换的奇偶性为偶数。 否则，它是奇数。 我们定义函数$\operatorname {sgn}(\sigma )=1$，如果$\sigma$是偶数，并且$\operatorname {sgn}(\sigma )=-1$，如果$\sigma$是奇数。

引理12：单位元$\iota$的奇偶性为偶数。

Proof: Observe first that $\iota \neq (a\ b)$ for $a\neq b$. Thus the minimum number of transpositions necessary to represent $\iota$ is 2: $\iota =(a\ b)(a\ b)$. Now, assume that for any representation using less than $k$ transpositions must be even. Thus, let $\iota =(a_{1}\ b_{1})...(a_{k}\ b_{k})$. Now, since in particular $\iota (a_{1})=a_{1}$, we must have $a_{1}\in (a_{i}\ b_{i})^{*}$ for some $1<i\leq k$. Since disjoint transpositions commute, and $(a_{r}\ a_{s})(a_{i}\ a_{r})=(a_{i}\ a_{s})(a_{r}\ a_{s})$ where $a_{i}\neq a_{r}\neq a_{s}$, it is always possible to configure the transpositions such that the first two transpositions are either $(a_{1}\ b_{1})(a_{1}\ b_{1})=\iota$, reducing the number of transposition by two, or $(a_{1}\ b_{1})(a_{1}\ b_{2})=(a_{1}\ b_{2})(b_{1}\ b_{2})$. In this case we have reduced the number of transpositions involving $a_{1}$ by 1. We restart the same process as above. with the new representation. Since only a finite number of transpositions move $a_{1}$, we will eventually be able to cancel two permutations and be left with $k-2$ transpositions in the product. Then, by the induction hypothesis, $k-2$ must be even and so $k$ is even as well, proving the lemma. ∎

定理13：置换的奇偶性，以及$\operatorname {sgn}$函数是明确定义的。

证明：设 $\sigma \in S_{n}$，并将 $\sigma$ 写成两种不同方式的转置乘积： $\sigma =\tau _{1}...\tau _{k}=\tau _{1}^{\prime }...\tau _{k^{\prime }}^{\prime }$。那么，由于 $\iota$ 具有偶校验性，根据引理 11，以及 $\iota =\sigma \sigma ^{-1}=\tau _{1}...\tau _{k}\tau _{k^{\prime }}^{\prime }...\tau _{1}^{\prime }$。因此，$k+k^{\prime }\equiv 0\ \mathrm {mod} \ 2$，并且 $k\equiv k^{\prime }\ \mathrm {mod} \ 2$，所以 $\sigma$ 具有唯一确定的校验性，因此 $\operatorname {sgn}$ 是定义良好的。 ∎

定理 14：设 $\sigma ,\rho \in S_{n}$。然后，$\operatorname {sgn}(\sigma \rho )=\operatorname {sgn}(\sigma )\operatorname {sgn}(\rho )$。

证明：将 $\sigma$ 和 $\rho$ 分解成对换：$\sigma =\mu _{1}...\mu _{k}$，$\rho =\nu _{1}...\nu _{l}$。然后 $\sigma \rho =\mu _{1}...\mu _{k}\nu _{1}...\nu _{l}$ 的奇偶性由 $k+l$ 给出。如果两者都是偶数或奇数，$k+l$ 是偶数，实际上 $\operatorname {sgn}(\sigma )\operatorname {sgn}(\rho )=1\cdot 1=1=\operatorname {sgn}(\sigma \rho )$。如果一个是奇数，另一个是偶数，$k+l$ 是奇数，并且再次 $\operatorname {sgn}(\sigma )\operatorname {sgn}(\rho )=(-1)\cdot 1=-1=\operatorname {sgn}(\sigma \rho )$，证明了定理。∎

引理 15：$S_{n}$ 中偶排列的数量等于奇排列的数量。

证明：令 $\sigma$ 为任何偶置换， $\tau$ 为一个对换。则由定理 14 可知 $\tau \sigma$ 的奇偶性为奇。令 $E$ 为偶置换的集合， $O$ 为奇置换的集合。则由 $f(\sigma )=\tau \sigma$ 给出的函数 $f:E\rightarrow O$ 对于任何 $\sigma \in E$ 和一个固定的对换 $\tau$，是一个双射。（事实上，它是在 $S_{S_{n}}$ 中的对换！）因此 $E$ 和 $O$ 具有相同数量的元素，如所述。 ∎

定义 16：令 $S_{n}$ 中所有偶置换的集合表示为 $A_{n}$。 $A_{n}$ 被称为关于 $n$ 个字母的交错群。

定理 17： $A_{n}$是一个群，并且是 $S_{n}$ 的一个子群，其阶为 ${\frac {n!}{2}}$。

证明：我们首先证明 $A_{n}$ 在合成运算下是一个群。然后它自动成为 $S_{n}$ 的一个子群。根据定理 14，$A_{n}$ 在合成运算下是封闭的，并且结合律从 $S_{n}$ 继承而来。此外，恒等置换是偶置换，因此 $\iota \in A_{n}$。因此 $A_{n}$ 是一个群，也是 $S_{n}$ 的一个子群。根据引理 14，偶置换和奇置换的数量相等，因此我们有 $|A_{n}|={\frac {|S_{n}|}{2}}={\frac {n!}{2}}$，证明了定理。 ∎

定理 18：设 $n\geq 3$。那么 $A_{n}$ 由 $S_{n}$ 中的 3-循环生成。

证明：我们必须证明任何偶置换都可以分解成 3-循环。只要证明对一对换位成立就足够了。设 $a,b,c,d\in S_{n}$ 是不同的。那么，通过一些分类讨论，

i) $(a\ b)(a\ b)=(a\ b\ c)^{3}$,

ii) $(a\ b)(b\ c)=(c\ a\ b)$，以及

iii) $(a\ b)(c\ d)=(a\ d\ c)(a\ b\ c)$,

证明了定理。 ∎

在前面的章节中，我们证明了拉格朗日定理：任何子群的阶数都整除其母群的阶数。但是，反过来，即一个群对于其阶数的每个除数都存在一个子群，则是错误的！最小的反例是交错群 $A_{4}$，它的阶数是 12，但没有阶数为 6 的子群。它有阶数为 3 和 4 的子群，分别对应于阶数为 3 的循环群和克莱因四元群。然而，如果我们向对应于 $C_{3}$ 的子群中添加任何其他元素，它将生成整个群 $A_{4}$。我们把这一点留给读者证明。

二面体群

这些线代表正六边形的反射对称

二面体群 $D_{16}$ 的元素，作为停车标志的旋转和反射。

二面体群是正多边形的对称群。因此，它们是对称群的子群。一般来说，一个正 $n$-边形有 $n$ 个旋转对称和 $n$ 个反射对称。二面体群通过包含相关的旋转和反射来捕获这些对称性。

定义 19：阶数为 $2n$ 的二面体群，记为 $D_{2n}$，是正 $n$-边形的旋转和反射群。

定理 20：$D_{2n}$ 的阶数恰好是 $2n$。

证明: 令 $\rho$ 为一个旋转，它在 $D_{2n}$ 中生成一个阶为 $n$ 的子群。显然，$\langle \rho \rangle$ 然后捕获了所有规则 $n$-边形的纯旋转。现在设 $\mu$ 为 $D_{2n}$ 中的任何旋转。剩下的元素可以通过将 $\langle \rho \rangle$ 中的每个元素与 $\mu$ 合成来找到。我们得到一个元素列表 $D_{2n}=\{\iota ,\rho ,...,\rho ^{n-1},\mu ,\mu \rho ,...,\mu \rho ^{n-1}\}$。因此，$D_{2n}$ 的阶为 $2n$，证明了其符号并证明了定理。 ∎

备注 21: 从这个证明中我们也可以看到 $\{\rho ,\mu \}$ 是 $G$ 的生成集，并且所有元素都可以通过写出 $\rho$ 和 $\mu$ 的任意乘积，并根据规则 $\rho ^{n}=\iota$，$\mu ^{2}=\iota$ 和 $\rho \mu =\mu \rho ^{-1}$ 进行简化表达式。事实上，从图中可以看出，旋转与反射的合成是新的反射。