置换群、对称群

                     

贡献者： Giacomo; JierPeter

预备知识　群，矩阵及其运算

　　 本文节选自《小时百科系列教材》中的《代数学》，为了良好的阅读体验和完整的讲解内容，建议阅读原书。

1. 置换群

　　 群论的创始人伽罗华（Évariste Galois，又译作伽罗瓦）在提出 “群” 这一概念的时候，指的其实是以下介绍的置换群。

　　 取 $n$ 个罐子，分别从 $1$ 到 $n$ 进行编号，再取 $n$ 个小球，也从 $1$ 到 $n$ 依次编号。在初始状态下，每个罐子里有一个小球，并且罐子和球的编号全都一致。如果我们从初始状态开始进行一个 “置换操作”，在保证每个罐子里都只有一个小球的情况下改变每个罐子里所装的小球，那么我们可以把这个操作本身等同于操作后变换的结果。比如说，如果我有三个罐子和三个小球，那么状态 “$1$ 号罐子里装 $2$ 号球，$2$ 号罐子里装 $1$ 号球，$3$ 号罐子里装 $3$ 号球” 就相当于 “交换 $1$、$2$ 号罐子里的球” 这一操作。为了方便表示，我们可以用两排数字来表示状态或操作，方法是用第一排的数字表示小球的编号，第二排数字表示对应小球所在罐子的编号。这样，“交换 $1$、$2$ 号罐子里的球” 这一操作就可以表示为：

\begin{equation}\begin{pmatrix} 1&2&3\\2&1&3 \end{pmatrix}~.\end{equation}

　　 置换操作可以进行复合，就是先后进行操作。比如说，如果我先进行

\begin{equation}\begin{pmatrix} 1&2&3\\2&1&3 \end{pmatrix}~,\end{equation}

　　 再进行

\begin{equation}\begin{pmatrix} 1&2&3\\3&2&1 \end{pmatrix}~,\end{equation}

　　 那么结果就是

\begin{equation}\begin{pmatrix} 1&2&3\\2&3&1 \end{pmatrix}~.\end{equation}

　　 判断两个置换复合后的结果很简单。第一排的数字永远都是按顺序排列的，第 $n$ 个数字就是 $n$；而第二排的数字中，第 $n$ 个代表的是此时 $n$ 号球所在罐子的编号。这样一来，要知道 $1$ 号球最后进入了哪个罐子，只需要先看第一个操作把它变进第 $a$ 个罐子1，再看第二个操作把 $a$ 罐子中的球变进第 $b$ 个罐子2，那么两个操作的复合就把 $1$ 号球变进了 $2$ 号罐子。按照这个法则很容易判断，例子里的复合运算最终把 $1$ 号球变进 $2$ 号罐，$2$ 号球变进 $3$ 号罐，$3$ 号球变进 $1$ 号罐。实际上，判断出前两个球进了几号罐后，可以直接得知最后一个球进入几号罐了，因为每个罐只能进一个球。

　　 如果从映射的角度来理解置换，把置换 “$n$ 号球进 $m$ 号罐” 看成 “把数字 $n$ 变为 $m$”，那么判断置换复合的结果可能更方便，如图 1 。但是要注意的是，置换的复合里，我们是从右边开始复合的，比如说对于置换 $s_1$ 和 $s_2$，我们规定 $s_2 s_1$ 或者 $s_2 \circ s_1$ 是先进行 $s_1$ 再进行 $s_2$。

图
图 1：置换的复合示意图。如图所示，两个置换的箭头首尾相连就得到复合后的置换。

　　 双排数字表示法还是太累赘了，我们还有更简洁的方法。对于一个特定的置换，当 $n_1$ 号球进入了 $n_2$ 号罐之后，$n_2$ 号球就必须另寻他处，比如说进入 $n_3$ 号罐，于是 $n_3$ 号球也被鸠占鹊巢了……以此类推，$n_1$ 逼走 $n_2$，$n_2$ 逼走 $n_3$，这个链条继续下去，最后总会回到 $n_1$ 的罐子。我们看一个任意置换的例子：

\begin{equation}\begin{pmatrix} 1&2&3&4&5\\2&4&5&1&3 \end{pmatrix}~.\end{equation}

　　 从 $1$ 开始，$1$ 号球进入 $2$ 号罐，$2$ 号球进入 $4$ 号罐，$4$ 号球又占了 $1$ 号罐，刚好是一个循环。我们把这样的一个循环3表示为 $(1 2 4)$。在这个例子里还有另一个分离的循环，就是 $(3 5)$——之所以叫分离，是因为它们涉及的数字没有交集，互不干扰。按照这样的定义，循环中领头元素是可以改变的，比如 $(1 2 4)$、$(2 4 1)$ 和 $(4 1 2)$ 都表示同一个循环，但是循环次序改变后有可能是不同的操作，比如 $(1 2 4)$ 和 $(1 4 2)$ 就不一样，不过有一个例外，那就是 $(3 5)$。像 $(3 5)$ 这样两个元素之间的循环，我们特别称为对换（exchange）。

　　 用循环的表示法，式 5 表示的置换就可以写成两个互相分离的循环的复合：$(1 2 4)(3 5)$，也可以写成 $(3 5 )(1 2 4)$，顺序没有影响。一般地，任意置换，都可以写成相互分离的循环的复合 $s_1s_2s_3\cdots s_k$。

　　 事实上，任何循环都可以写成对换的复合，比如 $(1 2 4) = (2 4)(4 1)$。我想在这里就没必要长篇大论地证明这一点了，给一个例子应该就能表达清楚该如何把循环拆成对换的复合：$(1 2 3 4 5 6) = (2 3)(3 4)(4 5)(5 6)(6 1)$。注意这些对换就不是彼此分离的了，因此不能随便交换次序。

　　 以置换为元素（以复合为乘积）的群被称为置换群（permutation group）；给定数字 $n$，我们把 $1, \dots, n$ 之间所有的置换构成的集合，记为 $S_n$，称为 $n$ 个元素的对称群（symmetric group），或者就叫 $n$阶对称群。

习题 1　

　　 证明 $S_n$ 配合置换的复合构成一个群。举例说明这个群在 $n>2$ 的时候不是阿贝尔群。

　　 在 “群论” 章节中，我们会看到置换群可以用来表示任意的群，因此置换群对群论有很好的代表意义。

置换矩阵

　　

未完成：置换矩阵的行列式 和 置换的奇偶性 的关系
我们也可以用矩阵来理解置换。

定义 1　置换矩阵

　　 置换矩阵是一个每行每列有且只有一个 $1$ 矩阵元，其他都为 $0$ 的方矩阵。

定理 1　

　　 全体 $n \times n$ 的置换矩阵的同构于 $n$ 阶对称群 $S_n$。

例 1　

\begin{equation} \begin{bmatrix}0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0\end{bmatrix} \begin{bmatrix}v_1 \\ v_2 \\ v_3 \\ v_4\end{bmatrix} = \begin{bmatrix}v_3 \\ v_2 \\ v_4 \\ v_1\end{bmatrix} ~ \end{equation}
这个置换矩阵对应
\begin{equation} \begin{pmatrix}1&2&3&4\\3&2&4&1\end{pmatrix}~ \end{equation}
或者记做 $(1 3 4)$。

　　 考虑一个置换 $\pi$，定义它对应的矩阵 $R_\pi$ 满足

\begin{equation} R_\pi v_i = v_{\pi(i)}~, \end{equation}
更具体的定义为 $R_\pi = (r_{i j})$，其中 $i$ 行 $j$ 列的矩阵元
\begin{equation} r_{i j} = \begin{cases} 1 \text{ 如果 } \pi(i) = j, \\ 0 \text{ 其余情况。}~ \end{cases}~ \end{equation}

例 2　

　　 证明定理 1 。

1. ^ 例子里，第一个操作把它变进了第 $2$ 个罐子
2. ^ 例子里，第二个操作把第 $2$ 个罐子里的球变进了第 $2$ 个罐子
3. ^ 有时这样的一个循环又称为轮换（cycle）。

                     

© 小时科技 保留一切权利