置换的标准记法

我们来进一步讨论$\S 5$集合与映射提出的关于有限集一一变换的几个问题.一些重要的代数概念就是在这一基础上自然产生的.

令$\Omega$是$n$元有限集.由于元素的性质对于我们来说是非本质的，为方便起见，不妨设$\Omega =\lbrace 1,2,\cdots ,n\rbrace$.由$\Omega \to \Omega$的全体一一变换组成的集合记作$S_n =S(\Omega )$，其元素通常用小写希腊字母表示，称为置换.仅对恒等映射$e=e_{\Omega}$保留用拉丁字母.

用展开和直观的方式将任意置换$\pi :i\mapsto \pi (i)$，$i=1,2,\cdots ,n$，表示成下述形式：

$$\pi =\begin{pmatrix}
1 & 2 & \cdots & n\\
i_1 & i_2 & \cdots & i_n
\end{pmatrix} ,$$

它完全指明了所有的像：

$$\begin{array}{ccccc}
& 1 & 2 & \cdots & n \\
\pi & ↧ & ↧ & & ↧ ,\\
& i_1 & i_2 & \cdots & i_n ,\\
\end{array}\\
$$

其中$i_k =\pi (k)$，$k=1,2,\cdots ,n$是符号$1,2,\cdots ,n$的一个排列.

设置换$\sigma ,\tau \in S_n$，它们的乘法对应于映射合成的一般法则：$(\sigma \tau )(i)=\sigma (\tau (i))$.例如对于置换：

$$\sigma =\begin{pmatrix}
1 & 2 & 3 & 4\\
2 & 3 & 4 & 1
\end{pmatrix} ,\tau =\begin{pmatrix}
1 & 2 & 3 & 4\\
4 & 3 & 2 & 1
\end{pmatrix} $$

我们有

$$\sigma \tau =\begin{pmatrix}
1 & 2 & 3 & 4\\
2 & 3 & 4 & 1
\end{pmatrix} \begin{pmatrix}
1 & 2 & 3 & 4\\
4 & 3 & 2 & 1
\end{pmatrix} = \begin{array}{cccc}
1 & 2 & 3 & 4 \\
↧ & ↧ & ↧ & ↧ \\
4 & 3 & 2 & 1 \\
↧ & ↧ & ↧ & ↧ \\
1 & 4 & 3 & 2 \\
\end{array} =\begin{pmatrix}
1 & 2 & 3 & 4\\
1 & 4 & 3 & 2
\end{pmatrix} .$$

同时

$$\tau \sigma =\begin{pmatrix}
1 & 2 & 3 & 4\\
4 & 3 & 2 & 1
\end{pmatrix} \begin{pmatrix}
1 & 2 & 3 & 4\\
2 & 3 & 4 & 1
\end{pmatrix} = \begin{pmatrix}
1 & 2 & 3 & 4\\
3 & 2 & 1 & 4
\end{pmatrix} ,$$

所以$\sigma \tau \neq \tau \sigma$.

按照$\S 5$的结果，置换的乘法满足下述规律.

$i)$乘法是结合的：对任意$\alpha ,\beta ,\gamma \in S_n$，$(\alpha \beta )\gamma =\alpha (\beta \gamma )$.

$ii)~ S_n$有单位元$e$：对任意$\pi \in S_n$，$\pi e =\pi =e \pi $.

$iii)$每一个元素$\pi \in S_n$都有逆元$\pi ^{-1}:\pi \pi ^{-1} =e=\pi ^{-1}\pi$.

这三条性质，补上我们暂且不谈的一般法则(见第$4$章)，给出了称$S_n$为群的根据.准确地说，集合$S_n$连同其元素的自然乘法运算(置换的合成)，叫作$n$元对称群(或$n$个符号的对称群，或$n$个点的对称群).对于我们来说，眼下不过是术语上的约定，它将重点从集合$S_n$转向了同样重要的置换的乘法性质，即转向$S_n$中元素的合成可能表现出来的性质.对称群$S_n$是群的一般理论和$170$多年前伽罗瓦理论的源头，而且大量的数学思想正是与它相联系才得以产生.

注记 如果将术语置换当作数字$1,2,\cdots ,n$按照某种顺序摆放的代名词，$S_n$的元素有时也称为排列($\text{подстановка}$).因为$n$元有序数列与$S_n$的元素之间存在着一一对应，而“置换”一词比固定的序列使人更快地联想到运算，所以排列一词就不再使用了，我们后面还会谈到，例如将数代入多项式，但是它仅作为所指含义的另外规定.

如果还需要更多的出处，至少可以在$a)$科学文献；$b)\text{П.С.}$亚历山大罗夫的教科书《解析几何讲义》($\text{Наука}$(科学出版社)，$1968,c~767$)中找到.

我们来计算群$S_n$的阶$\mid S_n \mid$.符号$1$在置换$\sigma$的作用下变成了符号$\sigma (1)$，$\sigma (1)$有$n$种不同的取法，确定了$\sigma (1)$，$\sigma (2)$只能从剩下的$n-1$个符号中去取(所以不同的对($\sigma (1),\sigma (2)$)共计有$(n-1)+(n-1)+\cdots +(n-1)=n(n-1)$个)，而$\sigma (3)$只能从$n-2$个符号中取等等.$\sigma (1),\sigma (2),\cdots ,\sigma (n)$的所有可能的选择，也就是所有不同的置换共计$n(n-1)\cdots 2\cdot 1=n!$个.所以

$$\text{Card} S_n =\mid S_n \mid =n!$$

置换的循环结构

我们现在将$S_n$中的置换分解为更简单的置换的乘积.先用上例中的置换$\sigma ,\tau \in S_4$，能过图表(图$13$)说明分解的思路.

置换$\sigma $叫作一个长为$4$的循环，简单地写成$\sigma=\begin{pmatrix} 1 & 2 & 3 & 4 \end{pmatrix} ,$或

$$\sigma=\begin{pmatrix} 2 & 3 & 4 & 1\end{pmatrix}=\begin{pmatrix} 3 & 4 & 1 & 2 \end{pmatrix}=\begin{pmatrix} 4 & 1 & 2 & 3 \end{pmatrix} ,$$

而置换

$$\tau=\begin{pmatrix} 1 & 4 \end{pmatrix}\begin{pmatrix} 2 & 3 \end{pmatrix} $$

是两个无关的(不相交的)长为$2$的循环$\begin{pmatrix} 1 & 4 \end{pmatrix}$和$\begin{pmatrix} 2 & 3 \end{pmatrix}$的乘积.我们指出

$$\sigma ^2=\begin{pmatrix} 1 & 3 \end{pmatrix}\begin{pmatrix} 2 & 4 \end{pmatrix} ,\sigma ^4=(\sigma ^2)^2=e ,\tau ^2 =e.$$

现在设$\pi$是$S_n$中的任意置换.其方幂$\pi ^s$归纳地定义如下(见$\S 5$定理$3$的证明)：

$$\pi ^s=\begin{cases} \pi (\pi ^{s-1}), & 若 s > 0， \\ e, & 若s = 0，\\ \pi ^{-1}((\pi ^{-1})^{-s-1}), & 若s < 0.\end{cases}$$

这时显然有

$$\pi ^s \pi ^t =\pi ^{s+t} =\pi ^t \pi ^s ,s,t \in \mathbb{Z}$$

(当$s$与$t$同号时，顺序添上$\pi$或$\pi ^{-1}$，当$s$与$t$异号时，用$e$代替$\pi \pi ^{-1}$，$\pi ^{-1}\pi$).因为$\mid \Omega \mid < \infty$，所以对于每一个置换$\pi \in S_n$，可以找到唯一确定的自然数$q=q(\pi )$，使得全部不同的方幂包含在集合$\langle \pi \rangle =\lbrace e,\pi ,\cdots ,\pi ^{q-1} \rbrace$中，且$\pi ^q =e$.该数$q$叫作置换$\pi $的阶.这样，上述置换$\sigma$和$\tau$分别有阶$4$和$2$.

称两个点$i,j\in \Omega$为$\pi$等价的，若存在某个$s\in \mathbb{Z}$，使得$j=\pi ^s(i)$.因为

$$i=\pi ^0(i),j=\pi ^s(i) \Rightarrow i=\pi ^{-s}(j),j=\pi ^s(i),k=\pi ^t(j) \Rightarrow k=\pi ^{s+t}(i),$$

我们显然得到了$\Omega$上的一个关系，它具有反身、对称、传递性(见$\S 6$第$2$段).基于等价关系的一般性质，我们有

$$\Omega =\Omega _1 \cup \cdots \cup \Omega _p .\label{1}\tag{1}$$

集合$\Omega$划分成了两两不相交的类$\Omega _1 ,\cdots ,\Omega _p$，这些类被直观地称为$\pi $轨道.这一名称是完全有根据的：因为每一个点$i\in \Omega$恰属于一个轨道，并且如果$i\in \Omega _k$，则$\Omega _k$由元素$\pi$的方幂作用在点$i$上的像组成：$i$，$\pi (i)$，$\pi ^2 (i)$，$\cdots$，$\pi ^{l_k -1}(i)$，此处$l_k =\mid \Omega _k \mid $是$\pi $轨道$\Omega _k$的长度.显然

$$l_k \leq q =\text{Card} \langle \pi \rangle ,\quad \pi ^{l_k }(i)=i,$$

并且$l_k$是具有这些性质的最小数.令

$$\pi _k =(i,\pi (i),\cdots ,\pi ^{l_k -1}(i))=\begin{pmatrix} i & \pi (i) & \cdots & \pi ^{l_k -2}(i)\\ \pi (i) & \pi ^2(i) & \cdots & \pi ^{l_k -1}(i) \end{pmatrix},$$

我们得到了一个置换，叫作长为$l_k$的循环.

将循环写成$$\begin{pmatrix} 1 & 2 & 3 & \cdots & l \end{pmatrix}$$或$$\begin{pmatrix} 1, & 2, & 3, & \cdots & ,l \end{pmatrix}$$是有趣和方便的.

循环$\pi _k$使集合$\Omega \backslash \Omega _k$中所有的点保持不变，而任取点$j\in \Omega _k$，$\pi (j) =\pi _k (j)$这一性质给我们提供了称两个循环$\pi _s ,\pi _t ,s\neq t$，是无关的或不相交的这一说法的依据.因为任取$i\in \Omega _k$，$\pi _k^{l_k }(i)=i$，所以$\pi _k^{l_k }=e$.

这样，公式$\eqref{1}$的划分对应于置换$\pi$到乘积的分解

$$\pi =\pi _1 \pi _2 \cdots \pi _p ,\label{2}\tag{2}$$

其中任意两个循环都是可换序的：$\pi =\pi _1 \pi _2 \cdots \pi _p =\pi _{l_1 } \pi _{l_2 } \cdots \pi _{l_p }$.可以假定

$$l_1 \geq l_2 \geq \cdots \geq l_m > l _{m+1 } =\cdots = l_p =1.$$

如果循环$\pi _k =(i)$的长度是$1$，那么它事实上是恒等置换.这样的循环自然可在乘积$\eqref{2}$中省略：

$$\pi =\pi _1 \pi _2 \cdots \pi _m ,l_k > 1 ,1 \leq k \leq m.\label{3}\tag{3}$$

例如我们可以将置换

$$\pi =\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 2 & 3 & 4 & 5 & 1 & 7 & 6 & 8 \end{pmatrix}\in S_8$$

写成

$$\pi =\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \end{pmatrix} \begin{pmatrix} 6 & 7 \end{pmatrix}\begin{pmatrix} 8 \end{pmatrix}=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \end{pmatrix}\begin{pmatrix} 6 & 7 \end{pmatrix}.\label{4}\tag{4}$$

对任意$n \geq 7$，$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \end{pmatrix} \begin{pmatrix} 6 & 7 \end{pmatrix}$可以看成$S_n$的置换，这是上述记号的不便之处，可是一旦$n$确定下来，这种不确定性就不存在了.

更精确地，假设我们还有形如$\eqref{3}$式的另一种分解$\pi =\alpha _1 \alpha _2 \cdots \alpha _r$，它也是不相交循环的乘积，并设符号$i$在$\pi$的作用下改变.这时存在$\pi _1 ,\cdots ,\pi _m$中的一个(且仅有一个)循环$\pi _s$，使得$\pi _s (i)\neq i$，同时，存在$\alpha _1 ,\cdots ,\alpha _r$中的一个循环$\alpha _t$，使得$\alpha _t (i)\neq i$.我们有$\pi _s (i)=\pi (i)=\alpha _t (i)$.如果我们已经知道

$$ \pi _s^k (i)=\pi ^k(i)=\alpha _t^k (i),\label{5} \tag{5}$$

那么将置换$\pi$作用于这一等式，并运用$\pi $与$\pi _s^k$和$\alpha _t^k$的交换性，我们得到

$$ \pi \pi _s^k (i)=\pi ^{k+1}(i)=\pi \alpha _t^k (i),$$

因而$\pi _s^k \pi (i)=\pi ^{k+1}(i)=\alpha _t^k \pi (i)$，最后，

$$ \pi _s^{k+1} (i)=\pi ^{k+1}(i)=\alpha _t^{k+1} (i).$$

这就是说，等式$\eqref{5}$对任意$k=0,1,2,\cdots$成立.但循环是被它的方幂在任意一个发生改变的符号上的作用唯一确定的.因而$\pi _s =\alpha _t$.然后再对$m$或$r$用归纳法.

于是我们证明了

定理$1$ $S_n$中的每一个置换$\pi \neq e$都是长度$\geq 2$、不相交的循环的乘积.这一分解式精确到循环的顺序是唯一确定的.

将注意力转到长为$2$的循环.

定义 长为$2$的循环叫作对换.

任意对换的形状为$\pi =\begin{pmatrix} i & j \end{pmatrix}$，它不改变所有异于$i,j$的符号.从定理$1$得到

推论 每一个置换$\pi \in S_n$都是对换的乘积.

证明 事实上，循环可以写成对换的乘积，例如

$$\pi =\begin{pmatrix} 1 & 2 & \cdots & l-1 & l\end{pmatrix}=\begin{pmatrix} 1 & l \end{pmatrix}\begin{pmatrix} 1 & l-1 \end{pmatrix}\cdots \begin{pmatrix} 1 & 3 \end{pmatrix}\begin{pmatrix} 1 & 2 \end{pmatrix}.$$

而定理$1$保证了任意置换可写成对换的乘积.$\quad \quad \square$

对定理$1$及其推论中的公式说明如下.从循环$\sigma =\begin{pmatrix} i_1 & i_2 & i_3 & \cdots & i_{l-1} & i_l\end{pmatrix}$的定义得出

$$ i_1 \mapsto i_2 ,i_2 \mapsto i_3 ,\cdots ,i_{l-1} \mapsto i_l ,i_l \mapsto i_1$$

和

$$ j \mapsto j ,j\in \Omega \backslash \lbrace i_1 , i_2 , \cdots , i_{l-1} , i_l \rbrace ,$$

如果我们将$\sigma$写成$\sigma =\begin{pmatrix} i_2 & i_3 & \cdots & i_l & i_1\end{pmatrix}$，即对包含在$\sigma$中的号码循环移位，则任何事情都没有改变.这样，定理$1$的唯一性是一个本质的特性.另一方面，在推论中将置换写成对换的乘积是没有这种唯一性的.令

$$ \sigma =\begin{pmatrix} i_1 & i_2 & i_3 & \cdots & i_{l-1} & i_l\end{pmatrix} =\begin{pmatrix} i_1 & i_l \end{pmatrix}\begin{pmatrix} i_1 & i_{l-1} \end{pmatrix}\cdots \begin{pmatrix} i_1 & i_3 \end{pmatrix}\begin{pmatrix} i_1 & i_2 \end{pmatrix},$$

$$ \sigma =\begin{pmatrix} i_2 & i_3 & \cdots & i_{l-1} & i_l & i_1 \end{pmatrix} =\begin{pmatrix} i_2 & i_1 \end{pmatrix}\begin{pmatrix} i_2 & i_l \end{pmatrix}\begin{pmatrix} i_2 & i_{l-1} \end{pmatrix}\cdots \begin{pmatrix} i_2 & i_3 \end{pmatrix}.$$

置换$\sigma$的同种写法包含相同个数$l-1$个的不同的对换(仅仅$\begin{pmatrix} i_1 & i_2 \end{pmatrix}=\begin{pmatrix} i_2 & i_1 \end{pmatrix} $).此外，这些对换不是可交换的，而它们的个数也不是一成不变的.例如在$S_4$中

$$ \begin{pmatrix} 1 & 2 & 3 \end{pmatrix}=\begin{pmatrix} 1 & 3 \end{pmatrix}\begin{pmatrix} 1 & 2 \end{pmatrix}=\begin{pmatrix} 2 & 3 \end{pmatrix}\begin{pmatrix} 1 & 3 \end{pmatrix}=\begin{pmatrix} 1 & 3 \end{pmatrix}\begin{pmatrix} 2 & 4 \end{pmatrix}\begin{pmatrix} 1 & 2 \end{pmatrix}\begin{pmatrix} 1 & 4 \end{pmatrix}.$$

置换的符号

给出下述重要定理：

定理$2$ 设$\pi$是$S_n$中的一个置换，将$\pi $分解成对换的乘积：

$$\pi =\tau _1 \tau _2 \cdots \tau _k ,\label{6}\tag{6}$$

称

$$\varepsilon _{\pi} =(-1)^k \label{7}\tag{7}$$

为$\pi $的符号(亦称符号差或奇偶性)，它由置换$\pi$唯一确定并不信赖于$\eqref{6}$式的分解方法，即对于给定的$\pi$，整数$k$给出的奇偶性永远是唯一的.此外任取$\alpha ,\beta \in S_n$，

$$\varepsilon _{\alpha \beta} =\varepsilon _{\alpha } \varepsilon _{\beta} .\label{8}\tag{8}$$

证明 $1)$设除$\eqref{6}$式外，我们还有一个分解

$$\pi =\tau’ _1 \tau’ _2 \cdots \tau’ _{k’} ,\label{61}\tag{6′}$$

并且数$k$与$k’$是不同的.定理的结论等价于说，整数$k+k’$是一个偶数.因为$(\tau’ _s )^2=e$，且$\eqref{6}$与$\eqref{61}$给出$\tau _1 \tau _2 \cdots \tau _k =\tau’ _1 \tau’ _2 \cdots \tau’ _{k’}$，用$\tau’ _{k’} ,\cdots ,\tau’ _2 ,\tau’ _1$从右侧顺序去乘这一等式的两边，我们得到$\tau _1 \tau _2 \cdots \tau _k \tau’ _{k’} \cdots \tau’ _2 \tau’ _1=e$.我们的问题可以归结成：设

$$e=\sigma _1 \sigma _2 \cdots \sigma _{m-1} \sigma _m ,m > 0,\label{9}\tag{9}$$

是单位置换到对换乘积的一个分解.则$m$是一个偶数.

这个目的可以用下述方法实现：将$e$的表达式$\eqref{9}$转化成$m-2$个对换的乘积.继续这一过程，如果$m$是奇数，我们就得到了一个对换$\tau$.但显然$e\neq \tau$.根据以上分析，我们只需给出将$m$个因子削减为$m-2$个的依据.

$2)$ 设$s,1 \leq s \leq n$，是任意一个包含在对换$\sigma _2 ,\cdots ,\sigma _m$中的整数.为确定起见，设

$$e=\sigma _1 \cdots \sigma _{p-1} \sigma _p \sigma _{p+1} \cdots \sigma _m ,$$

使得$\sigma _p =\sigma _{p-1} =\begin{pmatrix} s & t \end{pmatrix} $，而$\sigma _{p+1} ,\cdots ,\sigma _m $不包含$s$.对于$\sigma _{p-1} $，有下述四种可能性：

$a)$ $\sigma _{p-1} =\begin{pmatrix} s & t \end{pmatrix}$；这时$\sigma _{p-1} \sigma _{p} =\begin{pmatrix} s & t \end{pmatrix} \begin{pmatrix} s & t \end{pmatrix}$从$e$的写法中排除，我们得到了$m-2$个对换的分解式；

$b)$ $\sigma _{p-1}=\begin{pmatrix} s & r \end{pmatrix},r\neq s ,t$；则

$$\sigma _{p-1} \sigma _{p} =\begin{pmatrix} s & r \end{pmatrix}\begin{pmatrix} s & t \end{pmatrix}=\begin{pmatrix} s & t \end{pmatrix}\begin{pmatrix} r & t \end{pmatrix},$$

于是我们将$s$向左移动了一个位置，对换的个数$m$没有改变；

$c)$ $\sigma _{p-1}=\begin{pmatrix} t & r \end{pmatrix},r\neq s ,t$；则

$$\sigma _{p-1} \sigma _{p} =\begin{pmatrix} t & r \end{pmatrix}\begin{pmatrix} s & t \end{pmatrix}=\begin{pmatrix} s & r \end{pmatrix}\begin{pmatrix} t & r \end{pmatrix},$$

再次出现$b)$的情况，$s$向左位移而对换的个数$m$没有改变；

$d)$ $\sigma _{p-1}=\begin{pmatrix} q & r \end{pmatrix},\lbrace q,r\rbrace \cap \lbrace s,t\rbrace =\varnothing $；这时

$$\sigma _{p-1} \sigma _{p} =\begin{pmatrix} q & r \end{pmatrix}\begin{pmatrix} s & t \end{pmatrix}=\begin{pmatrix} s & t \end{pmatrix}\begin{pmatrix} q & r \end{pmatrix}.$$

如果出现情况$a)$，我们的目的就达到了.否则，不断重复$b)-d)$的处理方式，可以将$s$移动到左边第一个位置.归根到底，我们或者有情况$a)$，或者到达下述极限情况：$e=\sigma’ _1 \sigma’ _2 \cdots \sigma’ _m$，$\sigma’ _1 =\begin{pmatrix} s & t’ \end{pmatrix}$，且$s$不进入$\sigma’ _2 \cdots \sigma’ _m$.于是，当$k > 1$时$\sigma’ _k (s)=s$，但$s=e(s)=\sigma’ _1 (s) =t’\neq s$.这个矛盾证明了情况$a)$必须出现，从而$m$是偶数，所以关于$\varepsilon _{\pi}$不变性的论断是正确的.

$3)$ 如果$\alpha =\tau _1 \cdots \tau _k$，$\beta =\tau _{k+1} \cdots \tau _{k+l}$，则$\alpha \beta =\tau _1 \cdots \tau _k \tau _{k+1} \cdots \tau _{k+l}$，且$\varepsilon _{\alpha} =(-1)^k$,$\varepsilon _{\beta} =(-1)^l$,$\varepsilon _{\alpha \beta } =(-1)^{k+l}=(-1)^k (-1)^l=\varepsilon _{\alpha } \varepsilon _{\beta } $.$\quad \quad \square$

定义 若$\varepsilon _{\pi }=1$，则称置换$\pi \in S_n$为偶置换，若$\varepsilon _{\pi }=-1$，则称置换$\pi $为奇置换.

根据定义，所有的对换都是奇置换，而$\varepsilon _e =1$.

推论 设置换$\pi \in S_n$分解为长为$l_1 ,l_2 ,\cdots ,l_m$的互不相交的循环的乘积.则

$$ \varepsilon _{\pi }=(-1)^{\scriptsize {\displaystyle \sum_{k=1}^m (l_k -1)}}.$$

证明 事实上，根据定理$2$，我们有

$$ \varepsilon _{\pi }=\varepsilon _{\pi _1 \cdots \pi _m }=\varepsilon _{\pi _1 }\cdots \varepsilon _{\pi _m}$$

其中，$\varepsilon _{\pi _k }=(-1)^{l_k -1}$，因为$\pi _k$可以写成$l_k -1$个对换的乘积(见前述定理$1$的推论的证明).最后

$$\varepsilon _{\pi }=(-1)^{l_1 -1}\cdots (-1)^{l_m -1}=(-1)^{\scriptsize {\displaystyle \sum_{k=1}^m (l_k -1)}}.\quad \quad \square$$

例 设$\pi =\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ 5 & 4 & 6 & 7 & 2 & 9 & 1 & 3 & 8 & 11 & 10 \end{pmatrix}$.则$\pi =\begin{pmatrix} 1 & 5 & 2 & 4 & 7 \end{pmatrix}\begin{pmatrix} 3 & 6 & 9 & 8 \end{pmatrix}\begin{pmatrix} 10 & 11 \end{pmatrix}$ ，从$l_1 =5$，$l_2 =4$，$l_3 =2$得到$\varepsilon _{\pi } =(-1)^{4+3+1}=1$.

将$S_n$写成并集$S_n=A_n \cup \overline{A} _n$，其中

$$A_n =\lbrace \pi \in S_n \mid \varepsilon _{\pi }=1\rbrace$$

是偶置换的集合，$\overline{A}=S_n \backslash A_n$是奇置换的集合.设$\tau =\begin{pmatrix} i & j \end{pmatrix}$是任意对换.$S_n$到自身的映射$L_{\tau }:\pi \mapsto \tau \pi$是一个一一映射.($L_{\tau }$是单射：$\tau \alpha =\tau \beta \Rightarrow \alpha =\beta $；结论由$\S 5$定理$3$给出.不难看出$L_{\tau }^2$是恒等映射，故$L_{\tau }^{-1}=L_{\tau }$).$L_{\tau }$可以直观地表示成在集合$S_n =\lbrace \pi _1 =e ,\pi _2 ,\pi _3 ,\cdots ,\pi _N \rbrace $上的一个$N=n!$阶置换：

$$L_{\tau } =\begin{pmatrix} \pi _1 & \pi _2 & \pi _3 & \cdots & \pi _N \\ \tau \pi _1 & \tau \pi _2 & \tau \pi _3 & \cdots & \tau \pi _N \end{pmatrix}\label{10}\tag{10}$$

$$R_{\tau } =\begin{pmatrix} \pi _1 & \pi _2 & \pi _3 & \cdots & \pi _N \\ \pi _1 \tau & \pi _2 \tau & \pi _3 \tau & \cdots & \pi _N \tau \end{pmatrix}\label{101}\tag{10′}$$

也是$S_n$上的一个置换.映射$\eqref{10}$和$\eqref{101}$以后会有更广泛的应用.此刻我们指出$\varepsilon _{\tau \pi } =\varepsilon _{\tau } \varepsilon _{\pi } =-\varepsilon _{\pi }$，所以

$$L_{\tau }(A_n) =\overline{A} _n ,\quad L_{\tau }(\overline{A} _n) =A_n.$$

也就是说，$S_n$中偶置换的个数等于奇置换的个数，从而

$$\mid A_n \mid =\dfrac12 \mid S_n \mid =\dfrac{n!}2 .\label{11}\tag{11}$$

$S_n$在函数上的作用

$S_n$中任一置换$\sigma$的符号的重要意义可以在计算$\sigma$逆序数时看到(见本节最后的习题$5$).但现在不去管它，我们运用斜对称函数的概念，给出定理$2$的另一种证明，斜对称函数本身也是重要且有用的.

定义 设$\pi \in S_n$，$f$是$n$个自变量的函数.令

$$(\pi \circ f)(x_1 ,x_2 ,\cdots ,x_n )=f(x_{\pi (1)} ,\cdots ,x_{\pi (n)})\label{12}\tag{12}$$

则称函数$g= \pi \circ f$是由$\pi $作用在$f$上得到的.

引理$1$ 设$\alpha ,\beta$是$S_n$的任意置换.则

$$(\alpha \beta)\circ f=\alpha \circ (\beta \circ f).$$

证明 根据公式$\eqref{12}$，我们有

$$(\alpha \circ (\beta \circ f))(x_1 ,\cdots ,x_n )=(\beta \circ f)(x_{\alpha (1)} ,\cdots ,x_{\alpha (n)}),$$

令$y_k =x_{\alpha (k)}$，并注意到$y_{\beta (i)} =x_{\alpha (\beta (i))}$，

$$\begin{align}
& (\alpha \circ (\beta \circ f))(x_1 ,\cdots ,x_n )=(\beta \circ f)(y_1 ,\cdots ,y_n ) \\
= & f(y_{\beta (1)} ,\cdots ,y_{\beta (n)} )=f(x_{\alpha (\beta (1))} ,\cdots ,x_{\alpha (\beta (n))}) \\
= &f(x_{(\alpha \beta )(1)} ,\cdots ,x_{(\alpha \beta )(n)})=((\alpha \beta )\circ f)(x_1 ,\cdots ,x_n ).\quad \quad \square
\end{align}$$

定义 一个$n$元函数$f$叫作斜对称的，若$f(\cdots ,x_k ,x_{k+1} ,\cdots )=-f(\cdots ,x_{k+1} ,x_k ,\cdots )$，也就是说，当交换任意两个相邻变量的位置时，函数值变号.

引理$2$ 交换任意两个变量的位置，斜对称函数变号.

证明 设交换第$i,j$个自变量的位置，且$i < j$.对位于$i,j$之间的自变量的个数$l=j-i-1$作归纳.当$l=0$时，引理的条件符合斜对称函数的定义.设引理对任意$j-i-1 < l$真.则

$$\begin{align}
& f(\cdots ,x_i ,x_{i+1} ,\cdots ,x_{j-1} ,x_j ,\cdots ) =-f(\cdots ,x_{i+1} ,x_i ,\cdots ,x_{j-1} ,x_j ,\cdots )\\
= & f(\cdots ,x_{i+1} ,x_j ,\cdots ,x_{j-1} ,x_i ,\cdots ) =-f(\cdots ,x_j ,x_{i+1} ,\cdots ,x_{j-1} ,x_i ,\cdots ). \quad \square
\end{align}$$

应该指出，并非所有的斜对称函数恒等于零.下面是一个最简单的例子.

例 设

$$\Delta _n =\Delta _n (x_1 ,x_2 ,\cdots ,x_n )=\prod\limits_{1 < j < i \leq n}(x_i -x_j )$$

符号$\prod$表示乘积，正如$\sum$表示求和.指出任意两个相邻的自变量$x_k ,x_{k+1}$，我们有

$$\Delta _n =(x_{k+1} -x_k)\left[ (x_{k+1} -x_{k-1})\cdots (x_{k+1} -x_1)(x_k -x_{k-1})\cdots (x_k -x_1) \right]\cdot A\cdot B,$$

其中

$$A=\prod\limits_{1 \leq j < i < k}(x_i -x_j ),$$

$$B=\prod\limits_{s=k+2}\left[ (x_s -x_{s-1})\cdots (x_s -x_{k+1})(x_s -x_k)\cdots (x_s -x_1) \right] .$$

交换$x_k $与$x_{k+1} $的位置，因子$\left[ (x_{k+1} -x_{k-1} )\cdots (x_{k+1} -x_1 )(x_k -x_{k-1} )\cdots (x_k -x_1 ) \right] ,A$和$B$显然没有改变，可是

$$ (x_k -x_{k+1} )=-(x_{k+1} -x_k ).$$

这就意味着

$$\Delta _n (\cdots ,x_k ,x_{k+1} ,\cdots )=-\Delta _n (\cdots ,x_{k+1} ,x_k ,\cdots ),1\leq k \leq n+1.$$

$\Delta _n $是斜对称函数.根据引理$2$，我们有
$$\Delta _n (\cdots ,x_i ,\cdots ,x_j ,\cdots )=-\Delta _n (\cdots ,x_j ,\cdots ,x_i ,\cdots ).$$

此外，当$x_1 ,\cdots ,x_n$两两不同时，

$$\Delta _n (x_1 ,\cdots ,x_n )\neq 0.$$

定理$2$的第二种证明 考虑任意$n$个变元$x_1 ,\cdots ,x_n$上的斜对称函数$f$.根据定理$1$，当置换$\pi =\tau _1 \tau _2 \cdots \tau _k$分解成对换的乘积时，$\pi$在$f$上的作用归结到对换$\tau _k$，$\tau _{k-1}$，$\cdots$，$\tau _1$在$f$上的逐次作用，即$k$个$(-1)$与$f$的乘积：

$$\pi \circ f=(\tau _1 \cdots \tau _{k-1})\circ (\tau _k \circ f)=-(\tau _1 \cdots \tau _{k-1})\circ f=\cdots =(-1)^kf=\varepsilon _{\pi} f.$$

因为这一关系式的左边信赖于$\pi$，而不信赖于$\pi$的任何分解，所以由等式$\eqref{7}$指出的映射$\varepsilon :\pi \mapsto \varepsilon _{\pi}$当$f$不是零函数时由置换$\pi$完全确定.事实上，这样的函数是能够取到的，例如$f =\Delta _n$.

按照引理$1$建立的法则将置换$\alpha \beta$作用到这样的函数$f$上，

$$\varepsilon _{\alpha \beta} f=(\alpha \beta )\circ f=\alpha \circ (\beta \circ f)=\alpha \circ (\varepsilon _{\beta} f) =\varepsilon _{\beta} (\alpha \circ f)=\varepsilon _{\beta} (\varepsilon _{\alpha } f)=(\varepsilon _{\beta} \varepsilon _{\alpha} )f,$$

从而得到关系式$\eqref{8}$.$\quad \quad \square$

注记 我们将不止一次地研究$S_n$对函数的作用，在[$\text{BAⅢ}$]中可以看到这仅仅是一般规律的个别体现.我们的另一个小小的成绩在于，将口头表达式“在$f(x_1 ,\cdots ,x_n)$中交换$x_i$与$x_j$的位置”，简记作符号$\tau \circ f$，其中$\tau = \begin{pmatrix} i & j \end{pmatrix}$.

习题

$1$.在数学分析教科书中证明了斯特林公式

$$n!\sim \sqrt{2\pi n} n^n e^{-n},$$

此处$e=2.718281\cdots$是自然对数底，$\pi =3.141592\cdots $；符号$\sim$指当$n\to \infty$时，$\dfrac{\sqrt{2\pi n}n^n e^{-n}}{n!}$趋近于$1$.借助阶乘公式检验近似估计$100! > (9.33\cdots )10^{157}$.在$S_{100}$中有多少长为$100$的循环？

解：$100!=93326215443944152681699238856266700490715968264381621468592963895217599993229915$ $608941463976156518286253697920827223758251185210916864000000000000000000000000.$

$$\sqrt{2\pi \times 100} 100^{100} e^{-100} \approx (9.324848\cdots )10^{157}.$$

在$S_{100}$中，长为$100$的循环一共有$(100-1)!=99!$个.参考图$13$左图和其相关说明，思路是对于围成圆圈的$100$个数字，同时按同一方向旋转，即每个数字都向左（或向右）转动一个位置，虽然数字的绝对位置发生了变化，但相对位置未变，即数字间的相邻关系未变，这样的圆排列认为是同一种，否则便是不同的圆排列.可先令$100$个相异数字任意排成一行（称为线排列），共有$(100)!$种排法，再将其首尾相接围成一圈，当圆转动一个角度时，对应另一个线排列，当每个元素又转回到原先的位置时，相当于$100$个不同的线列列，故圆排列数为$\dfrac{P(100,100)}{100} =(100-1)!=99!$.

参考资料：组合数学中的圆排列-邓秀芬

$2$.求置换$\eqref{4}$和置换

$$\pi = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 3 & 6 & 8 & 2 & 1 & 4 & 5 & 7\end{pmatrix}$$

的阶.

解：因为置换$\eqref{4}$为$\pi = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 2 & 3 & 4 & 5 & 1 & 7 & 6 & 8\end{pmatrix}$，故

$$\pi ^2= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 3 & 4 & 5 & 1 & 2 & 6 & 7 & 8\end{pmatrix} ,\pi ^4= (\pi ^2)^2 =\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 3 & 4 & 5 & 1 & 2 & 6 & 7 & 8\end{pmatrix} ,$$

$$\pi ^5=(\pi ^4)\pi =\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 1 & 2 & 3 & 4 & 5 & 7 & 6 & 8\end{pmatrix} ,\pi ^{10}=(\pi ^5)^2 =\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\end{pmatrix} =e.$$

因此，置换$\eqref{4}$的阶为$10$.

对于置换$\pi = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 3 & 6 & 8 & 2 & 1 & 4 & 5 & 7\end{pmatrix}$，有

$$\pi ^2= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 8 & 4 & 7 & 6 & 3 & 2 & 1 & 5\end{pmatrix} ,\pi ^4= (\pi ^2)^2 =\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 5 & 6 & 1 & 2 & 7 & 4 & 8 & 3\end{pmatrix} ,$$

$$\pi ^5=(\pi ^4)\pi =\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 1 & 4 & 3 & 6 & 5 & 2 & 7 & 8\end{pmatrix} ,\pi ^{10}=(\pi ^5)^2 =\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 1 & 6 & 3 & 2 & 5 & 4 & 7 & 8\end{pmatrix},$$

$$\pi ^{15}=(\pi ^5)\pi ^{10} =\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \end{pmatrix} =e.$$

因此，置换$\pi = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 3 & 6 & 8 & 2 & 1 & 4 & 5 & 7\end{pmatrix}$的阶为$15$.

$3$.形如$\eqref{3}$的置换$\pi$含有$m$个互不相交的循环，令

$$m’ =n-\sum_{k=1}^m l_k ,$$

则$\pi$使$m’$个符号(或点)保持不变.数$d(\pi )=n-(m+m’)$叫作置换$\pi$的减量.验证$\varepsilon _{\pi} =(-1)^{d(\pi)}$.

证明：可利用定理$2$推论的证明思路.设形如$\eqref{3}$的置换$\pi =\pi _1 \pi _2 \cdots \pi _m ,l_k > 1 ,1 \leq k \leq m $含有$m$个互不相交的循环，其长分别为$l_1 ,l_2 ,\cdots ,l_m$，我们有

$$ \varepsilon _{\pi }=\varepsilon _{\pi _1 \cdots \pi _m }=\varepsilon _{\pi _1 }\cdots \varepsilon _{\pi _m}$$

其中，$\varepsilon _{\pi _k }=(-1)^{l_k -1}$，因为$\pi _k$可以写成$l_k -1$个对换的乘积(见前述定理$1$的推论的证明).最后

$$\begin{align}
\varepsilon _{\pi } & =(-1)^{l_1 -1}\cdots (-1)^{l_m -1} \\
& =(-1)^{\scriptsize {\displaystyle \sum_{k=1}^m l_k -m}} \\
& =(-1)^{ { n-n+{\scriptsize \displaystyle \sum_{k=1}^m l_k }-m}} \\
& =(-1)^{\scriptsize {\displaystyle n-(n-\sum_{k=1}^m l_k +m)}} \\
& =(-1)^{\scriptsize {\displaystyle n-(m’ +m)}} \\
& =(-1)^{d(\pi )} .
\end{align}$$

$4$.计算置换

$$\pi = \begin{pmatrix} 1 & 2 & 3 & \cdots & n-1 & n \\ n & n-1 & n-2 & \cdots & 2 & 1 \end{pmatrix}$$

的符号.

解：当$n=1$时，依定义有$\varepsilon _e =1$.

当$n=2k$时，置换$\pi = \begin{pmatrix} 1 & 2 & 3 & \cdots & n-1 & n \\ n & n-1 & n-2 & \cdots & 2 & 1 \end{pmatrix}$等价于$\begin{pmatrix} 1 & n \end{pmatrix} \begin{pmatrix} 2 & n-1 \end{pmatrix} \cdots \begin{pmatrix} k & k+1 \end{pmatrix}$，故$\pi $的符号$\varepsilon _{\pi} =(-1)^{\frac{2k}{2}} =(-1)^k$.可知当$k$为奇数时，$\varepsilon _{\pi } =-1$；当$k$为偶数时，$\varepsilon _{\pi } =1$.

当$n=2k+1$时，置换$\pi = \begin{pmatrix} 1 & 2 & 3 & \cdots & n-1 & n \\ n & n-1 & n-2 & \cdots & 2 & 1 \end{pmatrix}$等价于$\begin{pmatrix} 1 & n \end{pmatrix} \begin{pmatrix} 2 & n-1 \end{pmatrix} \cdots \begin{pmatrix} k & k+2 \end{pmatrix}$，故$\pi$的符号$\varepsilon _{\pi} =(-1)^{\frac{2k+1-1}{2}} =(-1)^k$.可知当$k$为奇数时，$\varepsilon _{\pi } =-1$；当$k$为偶数时，$\varepsilon _{\pi } =1$.

$5$.设$\Omega =\lbrace 1,2,\cdots ,n\rbrace$，$\Omega \times \Omega$是笛卡儿积.称元素对$\begin{pmatrix} i & j \end{pmatrix} \in \Omega \times \Omega$是置换$\sigma \in S_n$的逆序关系(或简称$\sigma$逆序)，若$i < j$，但$\sigma (i) > \sigma (j)$.令

$$\text{sgn} (\sigma )=\prod\limits_{1\leq i < j \leq n}\dfrac{\sigma (j) -\sigma (i)}{j-i}.$$

因为非零有理数$\dfrac{\sigma (j) -\sigma (i)}{j-i}$取负号.当且仅当$\begin{pmatrix} i & j \end{pmatrix}$是$\sigma$逆序，又因为$\sigma :\Omega \to \Omega$是一一映射，所以$\text{sgn} (\sigma )=(-1)^k$，其中$k$是$\sigma$逆序的总数.易见

$$\begin{align}
(\sigma (j)\sigma (i))\sigma & =\begin{pmatrix} \cdots & \sigma (j） & \cdots & \sigma (i） & \cdots \\ \cdots & \sigma (i） & \cdots & \sigma (j） & \cdots \end{pmatrix}\begin{pmatrix} \cdots & i & \cdots & j & \cdots \\ \cdots & \sigma (i） & \cdots & \sigma (j）& \cdots \end{pmatrix} \\
& =\begin{pmatrix} \cdots & i & \cdots & j & \cdots \\ \cdots & \sigma (j） & \cdots & \sigma (i） & \cdots \end{pmatrix}.
\end{align}$$

这样，$\sigma $逆序$\begin{pmatrix} i & j\end{pmatrix}$在作为置换$\tau \sigma$的逆序时中止了，其中$\tau =(\sigma (j) ,\sigma (i))$是一个对换.

证明可以找到$k$个对换$\tau _1 ,\cdots ,\tau _k$，使得

$$\tau _k \tau _{k-1} \cdots \tau _1 \sigma =e,$$

其中$e$是单位置换.则$\sigma =\tau _1 \cdots \tau _{k-1} \tau _k$，而$\text{sgn} \sigma =(-1)^k=\varepsilon _{\sigma}$，这两种记号代表置换的同一个不变量；(从拉丁文$\text{signum}$引出的)记号$\text{sgn}$就是符号的意思.我们得到了另一种便利的方法来确定置换的符号.例如对应于置换$\eqref{4}$的逆序的集合由五个数对$\begin{pmatrix} 1 & 5 \end{pmatrix}$，$\begin{pmatrix} 2 & 5 \end{pmatrix}$，$\begin{pmatrix} 3 & 5 \end{pmatrix}$，$\begin{pmatrix} 4 & 5 \end{pmatrix}$，$\begin{pmatrix} 6 & 7 \end{pmatrix}$组成，那么$\text{sgn}\pi =-1$.事实上，事情归结为计算置换$\pi$的下面一行中比$i$大却位于$i$的前面的数字$j$的个数，$i=1,2,\cdots ,n-1$.

证明：根据定理$1$，可将置换$\sigma$分解成对换的乘积：

$$\sigma =\sigma _1 \sigma _2 \cdots \sigma _k ,$$

对于每个对换$\sigma _i $来说，我们可以找到与之对应的对换$\tau _i $，使得$\tau _i \sigma $等于的单位置换$e$.

故有

$$\tau _1 \sigma =\tau _1 \sigma _1 \sigma _2 \cdots \sigma _k =e\sigma _2 \sigma _3 \cdots \sigma _k $$

成立.

接着，对上式依次取$\tau _2 ,\tau _3 ,\cdots ,\tau _k$，有

$$\tau _2 \tau _1 \sigma =\tau _2 \sigma _2 \sigma _3 \cdots \sigma _k = \sigma _3 \tau _4 \cdots \sigma _k ,$$

$$\cdots \cdots \cdots \cdots $$

$$\tau _k \cdots \tau _2 \tau _1 \sigma =\tau _k \sigma _k = e.$$

于是，对于置换$\sigma \in S_n $来说，可以找到$k$个对换$\tau _1 ,\cdots ,\tau _k$，使得

$$\tau _k \tau _{k-1} \cdots \tau _1 \sigma =e,$$

其中$e$是单位置换.