循环群与置换群

循环群(Cyclic Group)

生成子群

对于任意群\(G\)的非空子集\(A\)，定义\(\lang A\rang =\bigcap\limits_{i \in I}H_i\)，其中\(H_i\)是所有包含\(A\)的\(G\)的子群。称\(\lang A\rang\)是由\(A\)生成的子群。容易理解与证明，\(\lang A\rang\)是包含\(A\)的\(G\)的最小子群。

我们可以证明，\(\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\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}=a^0=e\)，那么每经过\(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,+)\)同构；有限循环群\(\{1,a,a^2,\cdots,a^{n-1}\}\)与\((\Z_n,+_{\text{mod }n})\)同构。

循环群的生成元

对于有限循环群\(\{1,a,a^2,\cdots,a^{n-1}\}\)，我们知道\(a\)一定是它的一个生成元。现在要问，是否还存在别的生成元？我们定义，对于\(g\in G\)，使得\(g^k=1\)的最小正整数\(k\)称为元素\(g\)的阶(order)，记为\(|g|=k\)。如果不存在这样的正整数，则称阶为无穷大。我们注意到，如果\(|g|=t\)，则一定有\(|g^s|=\dfrac{t}{gcd(t,s)}\)：\((g^s)^{\frac{t}{gcd(t,s)}}=(g^t)^{\frac{s}{gcd(t,s)}}\)，而\(g^t=1\)，因此\(\dfrac{t}{gcd(t,s)}\)一定是一个可行的指数；而假设\(|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)}\)已经是最小的可行指数了。现在我们已知\(a\)是\(\lang a\rang\)的生成元，因此\(|a|=n\)，对于任意的\(a^k\)如果它也是生成元，当且仅当\(|a^k|=n\)。而我们已经证明了\(|a^k|=\dfrac{n}{gcd(n,k)}\)，因此当且仅当\(gcd(n,k)=1\)时\(a^k\)也是生成元。这就得到了，\(\lang a\rang\)共有\(\varphi(n)\)（欧拉函数）个生成元，分别是以所有与\(n\)互质的数作为指数的那些元素。

注意，如果\(|g^t|=k\)，自然意味着\(\lang g^t\rang\)中有且仅有\(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\)更小，因此任何\(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=<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\}\)。

对于有限循环群\(G=\{1,g,\cdots,g^{n-1}\}\)，我们已经知道它有\(\varphi(n)\)个生成元，因此由这些生成元生成的循环群（\(G\)的子群）一定相等。如何写出\(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|=|g^s|=\dfrac{|g|}{gcd(|g|,s)}=\dfrac{n}{d}\)，\(|\lang g^d\rang|=|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\)，而圆的对称群为无限群。

数环与数域\(\newcommand{\F}{\mathbb{F}}\newcommand{\E}{\mathbb{E}}\)

对于复数\(\C\)上含有实数\(0,1\)的子集\(R\)，如果\(R\)对加法、减法、乘法封闭，则称\(R\)为一个数环；如果\(R\)对加法、减法、乘法、除法（非0）封闭，则称\(R\)为数域。例如，\(\Z\)是一个数环但不是数域，因为整数的除法是不封闭的；\(\Q,\R,\C\)都是数域，可以证明，\(\mathbb{Q}(\sqrt{2})=\{a+b\sqrt{2}\mid a,b\in \Q\}\)也是数域。

一般地对于数域\(\F\)，如果存在一个\(\F\)到\(\F\)的双射\(\phi\)，使得\(\phi\)满足\(\forall x,y\in \F\)始终成立\(\phi(x+y)=\phi(x)+\phi(y)\)，\(\phi(xy)=\phi(x)\phi(y)\)，则称\(\F\)是自同构(automorphic)的。显然只要取\(\phi\)为恒等映射，自同构总是成立的。而我们关注的是不同的\(\phi\)的个数，我们对\(\phi\)的要求实际上是数域对加减乘除四则运算在结构上的保持，使得自同构成立的\(\phi\)越多，说明数域\(\F\)具有更好的对称性。所有的\(\phi\)是\(\F\)到\(\F\)的双射，因此\(\phi\)的集合（记为\(Aut(\F)\)）是\(T(\F)\)的子集。容易进一步验证，\(Aut(\F)\)是满足封闭、结合律、单位元和逆元的，因此\((Aut(\F),\circ)\)实际上构成了\((T(\F),\circ)\)的一个子群，也即\((Aut(\F),\circ)\)是\(\F\)上的变换群。这个群就称为\(\F\)的自同构群，自同构群的大小反应\(\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}\)。

对于有理数域\(\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})\)，按照相同的推导，所有有理数上的映射只能到自身。对于\(\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(\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的非循环群）。

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

对称多项式

一个数域\(\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\)取\(\F\)中的元素。记\(\F\)上所有可能的\(n\)元多项式全体为集合\(\F[x_1,\cdots,x_n]\)。系数决定了一个多项式的特性，因为我们总是可以把各个项按照指数的某种规律排列整齐的。而系数的选择可以是\(\F\)中的所有元素。\(\F[x_1,\cdots,x_n]\)中有无穷多个元素，因此自然\(T(\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\)是\(\F[x_1,\cdots,x_n]\)上的一个双射（又是单射，又是满射）。如果把所有可能的\(\sigma\)对应的双射\(\phi_\sigma\)收集起来，我们就得到了\(T(\F[x_1,\cdots,x_n])\)的一个子集，并且我们可以进一步验证对于\(T_n=\{\phi_{\sigma_i}\}\)，\((T_n,\circ)\)是一个群（封闭，结合律，单位元，逆元）。也即我们找到了一个\(\F[x_1,\cdots,x_n]\)上的变换群（对称群的子群），称为\(\F[x_1,\cdots,x_n]\)的\(n\)元对称群。

对于\(\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:x\to g\cdot x\)。（为什么这是双射呢？先验证单射，假如\(g\circ x_1= g\circ x_2\)，那么根据消去律就得到\(x_1=x_2\)；再验证满射，对于任意的\(y\in G\)，总存在\(x=g^{-1}\cdot y\in G\)使得\(g\cdot x=y\)。事实上，这是一个群的普遍的性质。由群中的一个特定元素左乘（或右乘）而构造而成的映射总是一个双射）。把所有的\(\psi\)收集到一起构成集合\(U=\{\psi_g\mid g\in G\}\)，\(U\)是\(T(G)\)的一个子集。注意到，\(U\)是\(G\)到\(T(G)\)的单射，因为假如\(\psi_g=\psi_h\)，说明对任意的\(x\)都有\(g\cdot x=h\cdot x\)，根据右消去律得到\(g=h\)。换言之，我们找到了\(G\)与\(U\)的一个双射\(f:g\to \psi_g\)。验证四条性质容易证明，\((U,\circ)\)构成了一个群（也即\((U,\circ)\)是\(G\)的一个变换群），并且\(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)\)。

置换群(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的轮换。进而，如果一个permutation \(\pi\)分解后只留下<u\rang一个</u\rang大小为\(r\)的轮换\(\sigma\)（忽略了所有大小为1的以后），那么\(\sigma\)与自身复合\(r\)次就相当于恒等映射（什么都不做），因为这相当于沿着cycle转了一整圈回到了初始的地方。并且这是能够使得映射回到自身的所需要的最小的复合次数。仿照循环群中的记号，我们称permutation \(\pi\)的阶(order)（或轮换\(\sigma\)的阶）为\(r\)，记为\(|\pi|=|\sigma|=r\)，因为\(\sigma^r=\pi^r=I\)。更一般的，如果一个permutation \(\pi\)被分解为了\(t\)个<u\rang不相交</u\rang的轮换\(\sigma_1\cdots \sigma_t\)，那么总是成立\(|\pi|=\text{lcm}(|\sigma_1|,\cdots,|\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，第二条没有改变总的轮换个数。换言之，只要我们只运用以上两条规则来拆分轮换（并且我们总是可以进行到最后全都只剩下对换这一步），那么<u\rang轮换个数的奇偶性一定不变</u\rang。从这里我们已经可以直观地期待，既然任何一个permutation都可以写成一系列对换的复合，那么<u\rang对换个数的奇偶性总是唯一的</u\rang。由于从拆分的角度我们并不能直观保证能拆分出所有可能的对换，我们从复合的角度严格地证明这一事实：设一个\(n\)阶permutation \(\sigma\)有<u\rang不相交</u\rang的轮换分解\(\sigma=\tau_1\tau_2\cdots\tau_s\)（<u\rang包含大小为1的轮换</u\rang），由于这样的分解是唯一的，我们可以定义函数\(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中，对换个数的奇偶性一定是唯一确定的。这是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的轮换）有偶数个偶轮换，奇置换等价于不相交轮换分解中有奇数个偶轮换。

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

对于\(n\)阶对称群\(S_n\)，其中所有的偶置换构成子群（一个置换群！）\(A_n\)，群的运算是映射的复合。\(A_n\)称为交错群(Alternating Group)。因为偶置换与偶置换的复合依然是偶置换，满足封闭性；结合律与单位元显然；偶置换的逆变换依然是偶置换，只需把轮换反向进行，并不改变对换的奇偶性。我们进一步发现，\(|A_n|=\dfrac{n!}{2}\)，也即偶置换与奇置换的数量总是相同的：我们取唯一轮换分解中只包含一个对换的permutation，不妨取\((1,2)\in S_n\)。我们知道群中特定元素做左乘构成一个双射，因此\(f:\sigma\to (1,2)\circ \sigma\)构成了一个\(S_n\)到\(S_n\)的双射。而根据奇偶置换的唯一性，这样的映射一定把每个偶置换映射为了奇置换，而把每个奇置换映射为了偶置换。所以奇偶置换势必有着相同的数量。