02 循环群 对称群 置换群

循环群(Cyclic Group)

生成子群

对于任意群$G$的非空子集$A$，定义$\lang A\rang =\bigcap\limits_{i \in I}H_i$，其中$H_i$是所有包含$A$的$G$的子群。因为子群的交依然是子群，因此$\lang A\rang$是子群。我们称$\lang A\rang$是由$A$生成的子群，因为容易发现$\lang A\rang$一定是包含$A$的最小子群（最小指不存在一个真子群包含$A$，因为如果存在这样的真子群它一定是某个$H_i$，所以$\lang A\rang\subseteq H_i\subsetneq \lang A\rang$的真子集，矛盾）。

容易证明，$\lang A\rang=\{x_1\circ x_2\circ \cdots\circ x_n\mid n\in \N,x_i\in A\cup A^{-1}\}$（右边的每个元素都必须落在包含$A$的子群中，不然就不封闭。而利用子群的最后一个等价定义$a\circ b^{-1}$，右边是子群，因此这就是最小的子群了）。也就是说，由$A$生成的子群恰好是所有由$A$与$A^{-1}$中元素运算得到的全部元素。

循环群的定义

我们特别关注由单个元素生成的子群。我们把$\lang \{a\}\rang$简记为$\lang a\rang$，这样由单个元素生成的群称为循环群。从定义来看，我们并没有定义任何与“循环”有关的性质，但通过分析我们会发现，正是生成子群的性质产生了循环的性质。根据$\lang A\rang=\{x_1\circ x_2\circ \cdots\circ x_n\mid n\in \N,x_i\in A\cup A^{-1}\}$这一性质，我们立即得到$\lang a\rang=\{a^n\mid n \in \Z\}$，也就是说循环群一定能写成生成元$a$的任意整数次幂的集合的形式。此时有两种情况，要么所有的$a^n$都互不相同，这样我们就得到了一个无限的群$\{\cdots,a^{-2},a^{-1},a^0,a^1,a^2,\cdots\}$，这里依然没有看到循环的性质。但只要存在$i\neq j$使得$a^i=a^j$，循环就产生了——根据消去律，我们得到$a^{i-j}=e=a^0$，那么每经过$i-j$轮群的元素就会完全重叠，产生“循环”。如果我们找到最相邻的$i,j$使得$a^i=a^j$，记$i-j=n$，那么循环群就可以表示为$\{1,a,a^2,\cdots,a^{n-1}\}$。（由于$i,j$是最相邻的，因此这$n$个元素必定互不相同。）循环群总是只有以上两种形式，因为这两者只是生成元素中有没有重复产生的差别。

容易验证，无限循环群$\{\cdots,a^{-2},a^{-1},a^0,a^1,a^2,\cdots\}$与$(\Z,+)$同构，只需令$a^i\to i$；有限循环群$\{1,a,a^2,\cdots,a^{n-1}\}$与$(\Z_n,+_{\text{mod }n})$同构，同样令$a^i\to i$。

循环群的阶

对于有限循环群$\{1,a,a^2,\cdots,a^{n-1}\}$，我们知道$a$一定是它的一个生成元。现在要问，是否还存在别的生成元？

我们定义，对于$g\in G$，使得$g^k=1$的最小正整数$k$称为元素$g$的阶(order)，记为$|g|=k$或$\text{ord} (g)=k$（这个定义对于非循环群也适用）。如果不存在这样的正整数，则称阶为无穷大。

我们注意到，如果$|g|=t$，则一定有$\text{ord}(g^s)=\dfrac{t}{gcd(t,s)}$：Pf. $(g^s)^{\frac{t}{gcd(t,s)}}=(g^t)^{\frac{s}{gcd(t,s)}}$，而$g^t=1$，因此$(g^t)^{\frac{s}{gcd(t,s)}}=1$；而假设$\text{ord}(g^s)=m$，那么$g^{sm}=1$，因此一定有$t\mid sm$。记$t=gcd(t,s)\cdot t',s=gcd(t,s)\cdot s'$，则$gcd(t',s')=1$，所以$t'\mid s'm$，那么只能是$t'\mid m$，也即$\dfrac{t}{gcd(t,s)}\mid m$，这说明$\dfrac{t}{gcd(t,s)}$已经是最小的能使得$g^m=1$的$m$了。Qed.

现在我们已知$a$是$\lang a\rang$的生成元，因此$\text{ord}(a)=n$，对于任意的$a^k$如果它也是生成元，当且仅当$\text{ord}(a^k)=n$。而我们已经证明了$\text{ord}(a^k)=\dfrac{n}{gcd(n,k)}$，因此当且仅当$gcd(n,k)=1$时$a^k$也是生成元。这就得到了，$\lang a\rang$共有$\varphi(n)$（欧拉函数）个生成元，分别是以所有与$n$互质的数作为指数的那些元素。

关于阶还有另一个有用的结论。设$\text{ord} (a)=n,\text{ord}(b)=m$，如果$ab=ba$，$\gcd(n,m)=1$，那么有$\text{ord}(ab)=nm$。Pf. 设$\text{ord}(ab)=r$，那么$a^{rm}=a^{rm}(b^m)^r=(ab)^{rm}=1$，因此$n\mid rm$。而$n,m$互素，因此$n\mid r$。对称地，也有$m\mid r$。因此$\text{lcm}(n,m)\mid r$，因此$nm\mid r$。而$(ab)^{nm}=a^{nm}b^{nm}=1$。综上，$r=nm$。Qed.

注意，如果$\text{ord}(g^t)=k$，自然意味着$\lang g^t\rang$中有且仅有$k$个元素。也即，循环群中元素的阶等于该元素生成的循环群的大小。我们经常把循环群的大小也称为循环群的阶。

循环群的子群

循环群的子群一定也是循环群。对于循环群$G$，可以写作$G=\{g^k\mid k \in \Z\}$。对于$H\preceq G$，可以记为$H=\{g^{i_1},g^{i_2},\cdots\}$。对于$|H|=1$，显然；否则$|H|\geq 2$，我们总能在$g^{i_j}$中找到一个绝对值最小且不为零的整数$i$。容易发现，一定成立$H=\lang g^i\rang$：首先，我们有$\lang g^i\rang\subseteq H$，因为$\lang g^i\rang$定义为$G$中所有包含$g^i$的子群的交，而$H$就是这样的子群，因此肯定被交在内；其次，$\forall g^{i_j}\in H$，可以写出商式$i_j=qi+r$，那么$g^{i_j}=g^{qi}\cdot g^r$。也即$g^{i_j-qi}=g^r$。因为$H$具有封闭性，而$g^{i_j},g^i\in H$，因此有$g^{i_j-qi}\in H$，也即$g^r\in H$。而$r$的绝对值小于$i$，所以必须为0（如果不为0，则与$i$的绝对值最小矛盾）。因此任何$i_j$都一定是$i$的倍数，这说明$H\subseteq \lang g^i\rang$。综上，$H=\lang g^i\rang$。

无限循环群的子群全都是循环群，而每个循环群又必须是由群中的某个元素生成的，所以对于无限循环群$G=\{g^k\mid k\in \Z\}$，我们只需在$\{\lang g^k\rang\mid k \in \Z\}$中剔除重复的群就得到了$G$的所有子群。显然，$\forall k$，$\lang g^k\rang=\lang g^{-k}\rang$。而$\forall i> j\geq 0$，一定有$\lang g^i\rang\neq \lang g^j\rang$，因为$g^j\not \in\lang g^i\rang$。综上，无限循环群$G$的所有子群就恰好是$\{\lang g^d\rang\mid d\in \N\}$，对于每个$d$两两互不相同。

对于有限循环群$G=\{1,g,\cdots,g^{n-1}\}$，为了写出$G$的所有不同子群，我们也只需要枚举每个元素作为生成元，再去除重复的即可。如何去除重复的呢？我们发现，对于$g^s$，一定有$\lang g^s\rang=\lang g^{gcd(n,s)}\rang$。记$d=gcd(n,s)$，根据$d\mid s$，那么$g^s \in \lang g^d\rang$，因此$\lang g^s\rang\subseteq \lang g^d\rang$；而$|\lang g^s\rang|=\text{ord}(g^s)=\dfrac{n}{gcd(n,s)}=\dfrac{n}{d}$，$|\lang g^d\rang|=\text{ord}(g^d)=\dfrac{n}{gcd(n,d)}=\dfrac{n}{d}$。综上，$\lang g^s\rang\subseteq \lang g^d\rang$且$|\lang g^s\rang|=|\lang g^d\rang|$，因此$\lang g^s\rang=\lang g^d\rang$。所以对于$0<s<n$，如果$s$不是$n$的因子，那么$\lang g^s\rang$就一定与$\lang g^{gcd(n,s)}\rang$重复。而对于任何$s\mid n$，$|\lang g^s\rang|=\dfrac{n}{s}$，也即$\lang g^s\rang$互不相同。因此有限群$G$的所有子群就可以两两不同地表示为$\{\lang g^s\rang\mid 0\leq s < n,s\mid n\}$。

对称群(Symmetric Group)和变换群(Group of Transformation)

对于非空集合$M$，把所有$M$到$M$的双射收集到集合$T(M)$，定义运算$\circ$表示$T(M)$中一个双射与另一个双射的复合，那么可以验证$(T(M),\circ)$构成了一个群。只需验证四个条件：双射复合双射依然是双射，封闭性成立；映射的复合满足结合律；存在单位元为恒等映射；存在逆元为逆映射。我们称群$(T(M),\circ)$为$M$的对称群，称$M$的对称群的子群为$M$的变换群。

下面我们讨论几种特殊的对称群。

平面的运动群

平面$\R^2$上有一种称为保距变换的特殊双射，任意两点间的欧氏距离在映射前后都保持不变。可以证明，这样的变换只有三种基本的几何形式，分别是平移、旋转和沿轴做对称。我们称这种保距变换为“运动”，记$\R^2$上所有的运动为集合$M(\R^2)$。显然，$M(\R^2)$是对称群$T(\R^2)$的子集。我们可以进一步验证它构成群，也即平面的运动群是平面的一个变换群：两个运动的复合依然是运动，因为仍然保矩，故封闭性成立；结合律继承平面对称群的结合律；恒等映射是保矩的，因此存在单位元；逆映射也是运动，因此存在逆元。综上，$(M(\R^2),\circ)$构成群。

称$\R^2$的一个子集为平面上的一个图形，记为$K$。如果$K$经过运动后恰好完全与原来的自身重合，我们就把这样的运动收集进集合$S(K)$。用同样的方法可以验证，$(S(K),\circ)$也构成群，称为图形$K$的对称群。容易发现，一个图形的对称群规模越大，说明图形的对称性越好。例如可以证明，正三角形的对称群大小为$6$，正方形的对称群大小为$8$，而圆的对称群为无限群。

数环与数域

前置知识：环与域的定义，同构的定义

对于域$\mathbb{F}$，取所有$\mathbb{F} \to\mathbb{F}$的（自）同构映射$\phi$构成集合$Aut(\mathbb{F})$，容易发现$Aut(\mathbb{F})$是$\mathbb{F}$的对称群$T(\mathbb{F})$的子集。容易进一步验证，$Aut(\mathbb{F})$是满足封闭、结合律、单位元和逆元的，因此$(Aut(\mathbb{F}),\circ)$实际上构成了$(T(\mathbb{F}),\circ)$的一个子群，也即$(Aut(\mathbb{F}),\circ)$是$\mathbb{F}$上的变换群。这个群就称为$\mathbb{F}$的自同构群。

我们关注的是$\mathbb{F}$上不同的自同构映射$\phi$的个数，也即自同构群的大小。自同构群的大小能够反应域$\mathbb{F}$的“对称性”，因为域的自同构映射要求的实际上是域对加减乘除四则运算在结构上的保持，使得自同构成立的$\phi$越多，说明域$\mathbb{F}$的各个元素的特殊性越弱。

根据自同构的定义，对于任意满足要求的$\phi$，一定成立：$\phi(0)=0$；$\phi(1)=1$；$\phi(-x)=-\phi(x)$；$\phi(x-y)=\phi(x)-\phi(y)$；$\forall x\neq 0,\phi(x^{-1})=\phi(x)^{-1}$。

取$\mathbb{F}$为有理数域$\Q$，一定成立$\forall n\in\N$，$\phi(n)=n$。进一步$\phi(-n)=-\phi(n)=-n$，$\phi(1/n)=n^{-1}=1/n$，$\phi(m/n)=m/n$。因此$Aut(\Q)$中只有恒等映射一个元素，可见有理数域的没有任何对称性。对于数域$\Q(\sqrt{2})=\{a+b\sqrt{2}\mid a,b\in \Q\}$，按照相同的推导，所有有理数上的映射只能到自身。对于$\phi(a+b\sqrt{2})$，它必须等于$a+b\phi(\sqrt{2})$。而对于$\phi(\sqrt{2})$，必然满足$\phi(2)=\phi(\sqrt{2})^2$，因此只能有$\phi(\sqrt{2})=\pm \sqrt{2}$。可以验证，这两种取值都是可行的。因此$\Q(\sqrt{2})$的自同构群有两个元素，它的对称性略好于$\Q$。同理，$\Q(\sqrt{2},\sqrt{3})=\{a+b\sqrt{2}+c\sqrt{3}+d\sqrt{2}\sqrt{3}\}$的自同构群有$4$个元素，分别是$\phi(\sqrt{2})=\pm\sqrt{2}$与$\phi(\sqrt{3})=\pm\sqrt{3}$（事实上，是一个大小为4的非循环群），它的对称性又略好于$\Q(\sqrt{2})$。

对于域$\mathbb{E}$，取$\mathbb{E}$的子集$\mathbb{F}$，定义$Aut(\mathbb{E}:\mathbb{F})=\{\phi\in Aut(\mathbb{E})\mid \forall x\in\mathbb{F},\phi(x)=x\}$。这称为$\mathbb{E}$在$\mathbb{F}$上的对称群，其中的映射在$\mathbb{E}$上自同构，还要求在$\mathbb{F}$上保持恒等。刚才我们实际上已经验证了，$Aut(\Q(\sqrt{2}):\Q)=Aut(\Q(\sqrt{2}))$。

对称多项式

一个数域$\mathbb{F}$上的$n$元多项式可以记为$f(x_1,\cdots,x_n)=\sum\limits_{\alpha}a_\alpha x_1^{\alpha_1}\cdots x_n^{\alpha_n}$，其中$\alpha_1,\cdots,\alpha_n$取正整数，$a_\alpha$取$\mathbb{F}$中的元素。记$\mathbb{F}$上所有可能的$n$元多项式全体为集合$\mathbb{F}[x_1,\cdots,x_n]$。系数决定了一个多项式的特性，因为我们总是可以把各个项按照指数的某种规律排列整齐的。而系数的选择可以是$\mathbb{F}$中的所有元素。$\mathbb{F}[x_1,\cdots,x_n]$中有无穷多个元素，因此自然$T(\mathbb{F}[x_1,\cdots,x_n])$中也有无穷多个双射。

对于$n$个元素的集合$M=\{x_1,\cdots,x_n\}$，它对应的双射集合$T(M)$中恰好共有$n!$个双射，也即$M$的对称群大小为$n!$。这个群里的任何一个双射本质上对应着一个$n$阶的permutation。对于每一个permutation $\sigma=(i_1,i_2,\cdots,i_n)$，我们都可以构造一个$n$元多项式的映射$\phi_\sigma:f(x_1,\cdots,x_n)\to f(x_{i_1},\cdots,x_{i_n})$。我们发现，$\phi_\sigma$是$\mathbb{F}[x_1,\cdots,x_n]$上的一个双射（又是单射，又是满射）。如果把所有可能的$\sigma$对应的双射$\phi_\sigma$收集起来，我们就得到了$T(\mathbb{F}[x_1,\cdots,x_n])$的一个子集，并且我们可以进一步验证对于$T_n=\{\phi_{\sigma_i}\}$，$(T_n,\circ)$是一个群（封闭，结合律，单位元，逆元）。也即我们找到了一个$\mathbb{F}[x_1,\cdots,x_n]$上的变换群（对称群的子群），称为$\mathbb{F}[x_1,\cdots,x_n]$的$n$元对称群。

对于$\mathbb{F}[x_1,\cdots,x_n]$的一个多项式$f$，定义$S_f=\{\phi_{\sigma}\in T_n\mid \phi_\sigma(f)=f\}$，也即经过变元的轮换后保持多项式完全不变的映射集合。我们容易发现$(S_f,\circ)$也是群，这称为多项式$f(x_1,\cdots,x_n)$的对称群。我们容易把多项式的对称群与平面图形的对称群类比，对称一词本质上描述的是在某种变化下的不变性。多项式的对称群描述了变元的轮换下多项式保持不变的性质。

Cayley's Theorem

任何一个群$(G,\cdot)$作为集合$G$都有对应的对称群$T(G)$。Cayley定理指出，总是存在一个$T(G)$的子群（即$G$的某个变换群）与$G$同构。

如何来构造这个子群呢？首先这个子群应当与$G$有双射。我们在验证群上的消去律的时候提到过群中元素的左乘会引发双射。我们依次取$G$中的每个元素$g\in G$，构造双射$\psi_g:x\to g\cdot x$。把所有的$\psi_g$收集到一起构成集合$U=\{\psi_g\mid g\in G\}$，$U$是$T(G)$的一个子集。现在，构造$G$与$U$的映射$f:g\to \psi_g$。注意到$f$是单射，因为假如$\psi_g=\psi_h$，说明对任意的$x$都有$g\cdot x=h\cdot x$，根据右消去律得到$g=h$。同时，$f$是满射，因为任何一个$\psi_g$都是由$g\in G$引发的。综上，$f$是双射。并且$f$保持运算：$f(g_1\cdot g_2)=\psi_{g_1\cdot g_2}=\psi_{g_1}\circ \psi_{g_2}$。综上，$(G,\cdot)\cong (U,\circ)$。可见，$(U,\circ)$就是我们要找的同构的变换群。（这里我们可以根据定义验证群的四个条件证明$(U,\circ)$是群，也可以由同态的左子群右子群性质直接得到）

置换群(Permutation Groups)

集合$\{1,2,\cdots,n\}$的对称群就是所有$n$阶permutation构成的群。我们把它记为$S_n$，它的大小为$n!$。我们把$S_n$的子群称为置换群。由于我们总可以把任何有限群都看作是集合$\{1,2,\cdots,n\}$，而根据Cayley定理，任何一个群都与其对称群的一个子群同构。那么我们总可以说，任何一个$n$阶有限群都与一个$n$阶置换群同构。因此研究置换群就是在研究所有有限群的结构。

排列的不相交轮换分解

对于任何一个$n$阶permutation $\pi=(i_1,i_2,\cdots,i_n)$，我们总是可以把它拆解为若干个轮换(cycles)。从某个元素$i$出发，$i,\pi(i),\pi(\pi(i)),\cdots$，最后总会回到起点$i$，因为我们总共只有$n$个互不相同的元素。这样，任何一个permutation本质上就可以写作若干个不相交的轮换，例如$3 \ 5\ 4\ 1\ 2\ 6$就可以写作$(1,3,4)(2,5)(6)$：从第一个位置出发，我们发现$3$占据了原本$1$所在的位置，那么我们继续寻找谁占了$3$的位置，发现是$4$，而占据$4$的恰好是最先的$1$。这样$(1,3,4)$这三个位置上恰好是后一个顶替前一个做了一个平移。剔除这三个位置以后，我们继续寻找别的这样的cycle。最终一个permutation一定会被分解成若干个互不相交的cycle。由此可见，轮换实际上是permutation的另一种表示法。大小为偶数的轮换称为偶轮换(even cycle)，大小为奇数的轮换称为奇轮换(odd cycle)，大小为2的轮换称为一个对换(transposition)。（轮换的大小就是一个轮换中不同元素的个数，例如$(1,3,4)$的大小为3）

我们不关心每个轮换的起点是什么，每个轮换的起点可以是任意的，而起点一旦确定轮换中的排列顺序也随之确定。对于不相交的轮换，我们也不在意不同轮换的先后顺序，因为各个轮换是独立的。在忽略了起点与轮换的顺序后，我们可以说轮换的分解方式是唯一的。

在轮换的分解中，我们总可以忽略大小为1的轮换。进而，如果一个permutation $\pi$分解后只留下一个大小为$r$的轮换$\sigma$（忽略了所有大小为1的以后），那么$\sigma$与自身复合$r$次就相当于恒等映射，因为这相当于沿着cycle转了一整圈回到了初始的地方。并且这是能够使得映射回到自身的所需要的最小的复合次数。仿照循环群中的记号，我们称permutation $\pi$的阶(order)（或轮换$\sigma$的阶）为$r$，记为$\text{ord}(\pi)=\text{ord}(\sigma)=r$。更一般的，如果一个permutation $\pi$被分解为了$t$个不相交的轮换$\sigma_1\cdots \sigma_t$，那么总是成立$\text{ord}(\pi)=\text{lcm}(\text{ord}(\sigma_1),\cdots,\text{ord}(\sigma_t))$，因为只有到轮转的次数到达所有轮换的最小公倍数时排列才会第一次回到自身。

允许相交的轮换分解

我们可以这样来更广义地理解轮换的分解：每一个轮换就好像作用在permutation上的一个变换（映射），因此我们规定总是从右到左依次作用轮换的变换（顺着轮换走一步），就好像映射的复合一样。容易发现，在轮换不相交时我们用这样的方式来理解permutation总是正确的。在一原始排列的基础上，我们从右到左依次顺着每个轮换走一步，从效果上就相当于完成了一次permutation。这种复合的效果对于多个permutation的复合也是满足的，当两个permutation复合时，我们先做一遍右边的permutation，再做一遍左边的permutation。进一步，如果两个permutation都分别写成不相交的轮换分解的乘积的形式，我们只需要从右到左依次做所有的轮换即可。在这样的定义下，我们可以允许轮换之间有元素相交了。

我们发现，任何一个轮换总可以拆解成一系列对换的复合：$(i_1 \ i_2 \ \cdots \ i_n)=(i_1 \ i_2) \cdots (i_{n-1} \ i_n)$。因为左边描述了$i_2$落在原本$i_1$的位置上，$i_3$落在原本$i_2$的位置上，...，$i_n$落在原本$i_{n-1}$的位置上，$i_1$落在原本$i_n$的位置上这一过程。在右边的过程中，最先发生的是$(i_{n-1},i_n)$，此后再也没有人与$i_n$对换，因此最终$i_n$一定落在原本$i_{n-1}$的位置上不动；接着，$i_{n-1}$会落在原本$i_{n-2}$的位置上，此后也再也不发生变化……以此类推，$i_n,\cdots,i_2$都将落在正确的位置上，最后的一个位置留给$i_1$，这只能是正确的位置。对于恒等映射，它也可以写成一些无意义的对换$(1 \ 2)(1 \ 2)$等等。由此可以看到，任何一个permutation都可以写成一系列轮换的复合。

我们总是可以给出以下等价的轮换分解：$(k \ a \ \cdots \ b \ l \ c \ \cdots \ d)=(k \ l)(k \ a \ \cdots \ b)(l \ c \ \cdots \ d)$（不同的字母代表不同的元素）。因为根据我们的轮换复合规则，首先在$(l \ c \ \cdots \ d)$与$(k \ a \ \cdots \ b)$中独立地进行一步轮转，而后对换此时位于各自末尾的$k,l$，恰好等价于依照$(k \ a \ \cdots \ b \ l \ c \ \cdots \ d)$进行了一步轮转。反之，$(k \ l)(k \ a \ \cdots \ b \ l \ c \ \cdots \ d)=(k \ a \ \cdots \ b)(l \ c \ \cdots \ d)$，因为对前后两部分分别做一步轮转相当于整体做一步轮转再对换各自的开头。

奇置换与偶置换

根据允许相交的轮换分解的规则，我们总可以把一个大的轮换拆分成小的轮换，直到所有轮换的大小都是2。而在上一段讨论的两条拆分规则中，第一条使得总的轮换个数增加了2，第二条没有改变总的轮换个数。换言之，只要我们只运用以上两条规则来拆分轮换（并且我们总是可以进行到最后全都只剩下对换这一步），那么轮换个数的奇偶性一定不变。那么，既然任何一个permutation都可以写成一系列对换的复合，那么是不是所有可能的对换分解中对换个数的奇偶性总是唯一的？从拆分的角度我们并不能直观保证能拆分出所有可能的对换分解，因此我们从复合的角度严格地证明这一事实。

Pf. 设一个$n$阶permutation $\sigma$有不相交的轮换分解$\sigma=\tau_1\tau_2\cdots\tau_s$（包含大小为1的轮换），由于这样的分解是唯一的，我们可以定义函数$f(\sigma)=(-1)^{n-s}$，它是一个奇偶计数器，表示一个permutation在经过不相交的轮换分解后轮换个数的奇偶性（这个函数是良定义的，它是从permutation出发的映射，而不是某个轮换分解出发的映射。$f$是permutation本身的性质）。下面我们证明$f((a \ b)\sigma)=(-1)f(\sigma)$。由于$\tau_1,\cdots,\tau_s$中已经包含了$[n]$中所有元素，因此只需分两类讨论：$a,b$在同一个$\tau$中，或分散在两个$\tau$中。对于前者，不妨设$a,b\in \tau_1$（因为$\tau$中的分解不相交因此可以交换顺序），此时可以记$\tau_1=(a \ c_1 \ \cdots c_k \ b \ d_1 \cdots d_h),k,h\geq 0$，那么有等价分解$\tau_1=(a \ b)(a \ c_1 \ \cdots \ c_k)(b \ d_1 \ \cdots \ d_h)$。于是在$(a \ b)\sigma$中，$(a,b)$经过两次复合约去，余下的轮换互不相交，而相比原来恰好多出了一个轮换，因此要乘上因子$-1$；若$a,b$分散在两个轮换中，我们类似地套用第二条分解规则，记$\tau_1=(a \ c_1 \ \cdots \ c_k)$，$\tau_2=(b \ d_1 \ \cdots \ d_h)$，于是$(a \ b)\tau_1\tau_2=(a \ c_1 \ \cdots c_k \ b \ d_1 \cdots d_h)$，余下的依然是互不相交的完整轮换，相比原来少了一个，因此也要乘上因子$-1$。现在我们证明了，在复合一个对换后，permutation在唯一分解后轮换个数的奇偶性总会变化。因此假若一个permutation被以任何方式分解为（从恒等映射出发的）一系列对换的复合，其$f$的值一定只取决于对换的个数。而$f$的值又是唯一被permutation本身决定的，因此我们证明了任何方式用对换复合而成的permutation中，对换个数的奇偶性一定是唯一确定的。 Qed.

由此可见，对换分解后对换的个数是permutation本身的性质！我们把对换个数为偶数的permutation称为偶置换，把对换个数为奇数的permutation称为奇置换。

我们发现，偶置换在不相交的轮换分解中必定只有偶数个偶轮换。假如它有奇数个偶轮换，那么由于每个偶轮换都能运用$(i_1 \ i_2 \ \cdots \ i_n)=(i_1 \ i_2) \cdots (i_{n-1} \ i_n)$这种分解方式分解成奇数个对换，而每个奇轮换都会被分解成偶数个对换，最终对换的个数将会是奇数；同理，奇置换的不相交轮换分解中只能由奇数个偶轮换。反过来，如果一个置换有偶数个偶轮换，运用$(i_1 \ i_2 \ \cdots \ i_n)=(i_1 \ i_2) \cdots (i_{n-1} \ i_n)$这种分解方式所有偶轮换都能被写成奇数个对换，所有奇置换都能被写成偶数个对换，而对换个数的奇偶性永远是唯一的，因此它是一个偶置换；同理，奇数个偶轮换的置换一定是奇置换。所以我们证明了，偶置换等价于不相交轮换分解中（包括大小为1的轮换）有偶数个偶轮换，奇置换等价于不相交轮换分解中有奇数个偶轮换。

容易验证，两个奇偶性相同的置换复合得到偶置换，奇偶性不同的两个置换复合得到奇置换。因为把二者各自的对换分解从右到左合并到一起我们就得到了一个复合后的置换的对换分解，因此置换的奇偶就转化为了对换的奇偶，满足奇偶运算的规律。

交错群(Alternating Group)

对于$n$阶对称群$S_n$，其中所有的偶置换构成子群（一个置换群！）$A_n$，群的运算是映射的复合。因为偶置换与偶置换的复合依然是偶置换，满足封闭性；结合律与单位元显然；偶置换的逆变换依然是偶置换，只需把轮换反向进行，并不改变对换的奇偶性。我们把$A_n$称为$n$阶交错群。

我们进一步发现，$|A_n|=\dfrac{n!}{2}$，也即偶置换与奇置换的数量总是相同的：我们任取一个唯一轮换分解中只包含一个对换的permutation，比如取$(1,2)\in S_n$。我们知道群中特定元素做左乘构成一个双射，因此$f:\sigma\to (1,2)\circ \sigma$构成了一个$S_n$到$S_n$的双射。而根据奇偶置换的唯一性，这样的映射一定把每个偶置换映射为了奇置换，而把每个奇置换映射为了偶置换。所以奇偶置换势必有着相同的数量。