置换的奇偶性

                     

贡献者： zhaojiayu; JierPeter; Giacomo

预备知识　对称群

　　 对在置换群、称群中，我们已经简单的介绍了由一个固定的有限集合 $\{1, 2, ..., n\}$ 上所有置换组成的集合连同映射的符合所构成的群：对称群。在这一节我们将更加深入的讨论对称群的一些基本结构和性质。

1. 置换的表示方式

　　 一个置换实际上就是一个函数，要把一个函数表示出来要么给出表达式（一个通用的对应关系），要么把所有的点对应的函数值一一列举出来。对于置换来说我们通常采用后者。

例 1　

　　 在 $S_4$ 中设一个置换 $\sigma=\begin{pmatrix} 1\ 2\ 3\ 4\\ 2\ 1\ 4\ 3 \end{pmatrix}$

　　 这个写法的意思是，作为一个置换。$\sigma$ 把 $1$ 对应到了 $2$，$2$ 对应到 $1$，$3$ 对应到 $4$，$4$ 对应到 $3$. 值得注意的是，第一行虽然习惯于按照大小来排列从 $1$ 到 $n$ 这些数，但是实际上只要每个数字都出现一次就够了，不按照大小顺序来排列同样也可以表达出一个函数所包含的全部信息。另外，把两行换位置互换所得到的置换 $\begin{pmatrix} 2\ 1\ 4\ 3\\ 1\ 2\ 3\ 4 \end{pmatrix}$ 就是 $\sigma$ 的逆元。

　　 对于一些比较特殊的置换，我们有更简便的表示方法。

例 2　

　　 仍然考虑 $S_4$，设 $\tau=\begin{pmatrix} 1\ 2\ 3\ 4\\ 2\ 3\ 1\ 4 \end{pmatrix}$ 在这个置换下，$1$，$2$，$3$ 进行了 “轮换"，即每个数字都被对应到它们中的下一个。4 被保持不动。这个 $\tau$ 简记为 $(1\ 2\ 3)$，它的意思是，每个数字在这个置换下被替换成后一个数字，最后一个被替换成第一个，也因此 $(1\ 2\ 3)=(3\ 1\ 2)=(2\ 3\ 1)$。那些不受这个置换影响的数字则不出现在这个记法当中。一个轮换中出现的数字的个数被称为这个轮换的长度。长度为 $2$ 的轮换一般叫做对换，即两个数字对换位置，其他的保持不动。单位置换记为 $(1)$.

定义 1　

　　 两个轮换中出现的数字（或者说被两个轮换改动位置的点）的集合若是不相交，则称这两个轮换不相交。

引理 1　

　　 不相交的轮换的乘积是交换的：设 $\tau_1=(i_1\ i_2...i_k), \tau_2=(j_1\ j_2...j_s)$，则 $\tau_1\tau_2=\tau_2\tau_1$.

　　 这个证明思路很简单，因为这两个轮换不相交，可以把它们看成是两个不同的集合重新排列。因此先对哪一个集合重排不影响最终结果。感兴趣的读者可以尝试把证明写出来。

　　 一般来说，不是所有的置换都可以简记成一个轮换，换句话说，能写成轮换的只是一小部分置换。例 1 中的 $\sigma$ 就不是一个轮换。但是，下面的定理表明，每个置换都可以唯一的表达成轮换的乘积：

定理 1　

　　 $S_n$ 中每一个非单位的置换 $\sigma$ 都可以写成不相交的长度大于等于 $2$ 的轮换的乘积。并且这个分解在不计次序的情况下是唯一的。

　　 这里简单说一下证明思路，具体的证明只需补充细节即可。考虑 $\sigma$ 的一个动点（被其改变位置的一个数字）：$i_1$. 记 $i_2=\sigma(i_1)...i_n=\sigma(i_{n-1})$ 直到出现某个 $i_k=i_1$ 为止（因为一共只有有限多个数字，这种情况必定发生）。我们得到一个轮换 $\sigma_1=(i_1\ i_2...i_k)$. $\sigma$ 与 $\sigma_1$ 在 $i_1$ 到 $i_k$ 这些数上的作用是完全相同的，而 $\sigma_1$ 保持其他数字不动，可以理解为 $\sigma_1$ 是 $\sigma$ 的一部分。显然 $\sigma_1$ 的长度至少是 2（否则 $i_1$ 将是不动点）。现在考虑 $\sigma\sigma_1^{-1}$. 这个置换就是 $\sigma$ 相比于 $\sigma_1$ 多出的部分。它的动点显然少于 $\sigma$,对动点个数做归纳（或者重复上述步骤）可以得到定理中 $\sigma$ 的轮换分解。

例 3　

　　 例 1 中的 $\sigma=\begin{pmatrix} 1\ 2\ 3\ 4\\ 2\ 1\ 4\ 3 \end{pmatrix}$ 可以分解成 $(1\ 2)(3\ 4)$

2. 置换的奇偶性

引理 2　

　　 任意一个轮换 $(i_1\ i_2...i_k)$ 都可以写成对换的乘积。因此根据定理 1，任意置换也可以写成对换的乘积。

　　 证明：$(i_1\ i_2...i_k)=(i_1\ i_k)(i_1\ i_{k-1})...(i_1\ i_2)$。

例 4　

　　 上述分解并不唯一，例如在 $S_3$ 中， $(1\ 2\ 3)=(1\ 3)(1\ 2)=(2\ 3)(1\ 3)$.

　　 不仅分解的方式不唯一，不同的分解用到的对换的个数甚至也是不同的。但是尽管如此，不同分解所需对换个数的奇偶性是一致。

定理 2　置换的奇偶性

　　 设 $\sigma\in S_n$,且有分解 $\sigma=\tau_1\tau_2...\tau_k=\pi_1\pi_2...\pi_s$.其中 $\tau_j, \pi_l$ 均为对换。则 $k$ 与 $s$ 有相同的奇偶性。

　　 设 $\sigma$ 是一个 $n$ 阶置换，其可以写成 $s$ 个不相交的轮换的积，$\sigma=\tau_1\tau_2\cdots\tau_n$，我们定义一个函数 $N(\sigma)=(-1)^{n-s}$。设 $(a\ b)$ 为任意对换，则不难验证 $N((a\ b)\sigma)=-1N(\sigma)$1，同理有 $N(\sigma)=(-1)^sN(I)$，这就说明 $k,s$ 的奇偶性相同。

　　 从定理中可以看出，任意的两个分解中用到的对换个数要么同时是奇数，要么同时是偶数。换句话是，这个奇偶性不依赖于分解，只与对换 $\sigma$ 本身有关。

定义 2　

　　 若一个置换 $\sigma\in S_n$ 可以写成偶数个对换的乘积，则称 $\sigma$ 为偶置换。若可以写成奇数个对换的乘积，则称 $\sigma$ 为奇置换。

习题 1　

　　 证明对于任意 $\sigma\in S_n$，$\sigma$ 与 $\sigma^{-1}$ 有相同的奇偶性。

习题 2　

　　 证明在 $S_n$ 当中，奇置换与偶置换各占一半。（提示，固定一个对换 $\tau$，考虑映射：奇置换 $\to$ 偶置换，$\sigma\mapsto\sigma\tau$

　　 由引理 2 、定理 2 和定义 2 可知，$S_n$ 的全体偶置换构成一个正规子群。

定义 3　交错群

　　 $S_n$ 的全体偶置换构成的子群，称为 $S_n$ 的交错群（alternating group），记为 $A_n$。

1. ^ 只需注意到 $(a\ b)(a\ c\cdots\ d\ b\ e\cdots\ f)=(a\ c\ \cdots\ d)(b\ e\ \cdots f)$ 和 $(a\ b)(a\ c\ \cdots\ d)(b\ e\ \cdots\ f)=(a\ c\ \cdots\ d\ b\ e\cdots\ f)$，则 $N(\sigma)=N(\tau_1\cdots \tau_k)I)=(-1)^kN(I)$。


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

                     

友情链接： 超理论坛　|　©小时科技 保留一切权利