置换群

贡献者： 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$ 个罐子¹，再看第二个操作把 $a$ 罐子中的球变进第 $b$ 个罐子²，那么两个操作的复合就把 $1$ 号球变进了 $2$ 号罐子。按照这个法则很容易判断，例子里的复合运算最终把 $1$ 号球变进 $2$ 号罐，$2$ 号球变进 $3$ 号罐，$3$ 号球变进 $1$ 号罐。实际上，判断出前两个球进了几号罐后，可以直接得知最后一个球进入几号罐了，因为每个罐只能进一个球。

　　如果从映射的角度来理解置换，把置换 “$n$ 号球进 $m$ 号罐” 看成 “把数字 $n$ 变为 $m$”，那么判断置换复合的结果可能更方便，如图 1 。但是要注意的是，在本小节讨论的置换的复合里，特别式接下来介绍的 “循环表示法” 里，在一个乘积里，我们是从左边开始复合的，比如说对于置换 $s_1$ 和 $s_2$，我们规定 $s_1s_2$ 是先进行 $s_1$ 再进行 $s_2$。这和一般的映射的表示不一样，一般的映射里的顺序是 $s_2\circ s_1$。

图 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$ 号罐，刚好是一个循环。我们把这样的一个循环³表示为 $(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)$，顺序没有影响。一般地，$n$ 个元素的任意置换，都可以写成相互分离的循环的乘积。如果 $s_i$ 表示一个循环⁴，那么 $s_1s_2s_3\cdots s_n$ 就表示先进行 $s_1$ 置换，然后 $s_2$、$s_3$，依次进行。

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

　　给定数字 $n$，我们把 $n$ 个元素之间所有的置换收集起来，做成一个集合，记为 $S_n$，称为 $n$ 个元素的置换群（permutation group），或者就叫 $n$阶置换群。诶，我直接称呼它为一个 “群” 了，群运算是什么呢？就是置换的复合。

习题 1　

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

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

1. ^ 例子里，第一个操作把它变进了第 $2$ 个罐子
2. ^ 例子里，第二个操作把第 $2$ 个罐子里的球变进了第 $2$ 个罐子
3. ^ 有时这样的一个循环又称为轮换（cycle）。
4. ^ 比如式 5 里可以有 $s_1=(1 2 4)$ 和 $s_2=(3 5)$

致读者：小时百科一直以来坚持所有内容免费，这导致我们处于严重的亏损状态。长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。因此，我们请求广大读者热心打赏 ，使网站得以健康发展。如果看到这条信息的每位读者能慷慨打赏 10 元，我们一个星期内就能脱离亏损，并保证在接下来的一整年里向所有读者继续免费提供优质内容。但遗憾的是只有不到 1% 的读者愿意捐款，他们的付出帮助了 99% 的读者免费获取知识，我们在此表示感谢。