05 群在集合上的作用

给定一个群$(G,\cdot)$和一个非空集合$X$，如果我们能够定义一个$G$中元素和$X$中元素的运算$\circ$满足以下三条性质，就称群$G$作用在$X$上：① $\forall g\in G,f_g:x\to g\circ x$是一个$X$到$X$的映射；② 结合律：$\forall g,h\in G,\forall x\in X,$ $h\circ(g\circ x)=(h\cdot g)\circ x$；③ 对于$G$中的单位元$e$，$\forall x\in X,e\circ x=x$。

我们发现，这样的作用$f_g$始终是$X\to X$的双射。Pf. 先证单射，如果$g\circ x_1=g\circ x_2$，那么两边同时作用$g^{-1}$，得到$g^{-1}\circ (g\circ x_1)=g^{-1}\circ (g\circ x_2)$，根据结合律得到$(g^{-1}\cdot g)\circ x_1=(g^{-1}\cdot g)\circ x_2$，由性质三$x_1=x_2$；再证满射，对于任意的$y\in X$，由于$f_{g^{-1}}$也是$X\to X$的映射，因此$g^{-1}\circ y\in X$，于是一定有$f_g(g^{-1}\circ y)=g\circ (g^{-1}\circ y)=(g\cdot g^{-1})\circ y=y$。Qed.

可见，群在集合中的作用就是由群中的每个元素给出一个$X$到$X$的满足一定性质的双射。我们知道，$X$的对称群$S_X$中的元素是所有$X\to X$的双射，如果我们定义$\phi(g):g\to f_g$，这就是一个$X$到$S_X$的映射。而根据定义，$\phi(g\cdot h)=f_{g\cdot h}$。$\forall x\in X$，$f_{g\cdot h}(x)=(g\cdot h)\circ x=g\circ (h\circ x)=f_g(f_h(x))$，而映射的复合恰好是对称群上的运算法则，所以我们有$\phi(g\cdot h)=\phi(g)\phi(h)$——$\phi$是一个保运算的映射，也即$\phi$是$X$到$S_X$的群同态！根据同态的左子群右子群性质，我们也知道了所有映射$f_g$也构成了$S_X$的子群。

如果取$X$等于$G$，运算为群$G$中的运算，那么$\phi$是$G$到$S_X$的同态。那么，$\ker\phi=\{g\mid f_g=I\}$。而满足$f_g=I$的$g$一定有$\forall x\in G,gx=x$，由群的消去律有$g=e$，因此$\ker\phi=\{e\}$。所以$\phi$是单射！所以，$\phi$是$G$到$\phi(G)$的双射——一个同构映射。这样我们就找到了$S_X$中的一个子群与$G$同构，这正是Cayley定理描述的事实。

轨道与稳定子(Orbits and Stabilizers)

对于$X$中的任意一个元素$x$，我们用所有可能的群中元素作用在它身上得到的元素集合称为$x$的轨道(orbit)，记为$B(x)=\{g\circ x\mid g\in G\}$。我们发现，轨道实际上把$X$分划为了若干等价类。$\forall x,y\in X$，定义$x\sim y$当且仅当$y\in B(x)$。我们证明这是一个等价关系：自反性，$x\in B(x)$显然成立；对称性，如果$y\in B(x)$，那么存在$g\in G$使得$y=g\circ x$，因此$x=g^{-1}\circ y$，所以$x\in B(y)$；传递性，如果$x\in B(y),y\in B(z)$，那么存在$g_1$使得$x=g_1\circ y$，存在$g_2$使得$y=g_2\circ z$，于是$x=g_1\circ (g_2\circ z)=(g_1\cdot g_2)\circ z$，因此$x\in B(z)$。

在生成$x$的轨道$B(x)$的所有$g$当中，有一些（例如单位元）会把$x$映射到$x$本身，我们把这些$x$收集进集合$G(x)=\{g\mid g\circ x=x\}$，称为$x$的稳定子(stabilizer)。我们发现对于任意$x$，稳定子$G(x)$都形成了$G$的一个子群：只需证明$\forall g,h\in G(x),g^{-1}\cdot h\in G(x)$，其中$g\circ x=x$，因此$x=g^{-1}\circ x$，而$h\circ x=x$，因此$g^{-1}\circ (h\circ x)=x$，也即$(g^{-1}\cdot h)\circ x=x$。

同时，我们可以证明如果存在$a\in G$使得$y=a\circ x$，那么$G(y)=aG(x)a^{-1}$。先证$G(y)\subseteq aG(x)a^{-1}$，$\forall g\in G(y)$，$g\circ y=y$，那么$(a^{-1}ga)\circ x=(a^{-1}g)\circ y=a^{-1}\circ y=x$，因此$a^{-1}ga\in G(x)$，也即$g\in aG(x)a^{-1}$；再证$aG(x)a^{-1}\subseteq G(y)$，$\forall h\in G(x)$，$h\circ x=x$，那么$aha^{-1}\circ y=(ah)\circ x=a\circ x=y$，因此$aha^{-1}\in G(y)$。我们知道左乘或右乘一个群中元素一定是双射，因此$G(y)$与$G(x)$的大小一定相同——同一个轨道上的元素的稳定子大小都相同。

The Orbit-Stablizer Theorem

我们可以这样理解$x$的轨道：以它为中心，每个$g$中的元素都对应着一条有向边从$x$出发指向$g\circ x$，$x$的轨道就是从$x$出发可达的点集；一部分有向边是从$x$出发指向自身的，这些边就是稳定子。稳定子可能不止一条，同样地对于某个$y\in B(x)$，边$x\to y$也可能不止一条。对于某个$y\in B(x)$，假设既有$g_1\circ x=y$，又有$g_2\circ x=y$，那么$x=(g_1^{-1}g_2)\circ x$，因此$g_1^{-1}g_2$是稳定子。我们发现，$g_1\circ x=g_2\circ x\iff g_1^{-1}g_2\in G(x)$——这是陪集的性质！对于子群$G(x)$，陪集$g_1G(x)=g_2G(x)$当且仅当$g_1^{-1}g_2\in G(x)$。轨道图上指向相同终点的边一定构成稳定子的一个陪集。根据Lagrange定理，所有的陪集都有相同的大小。换言之，轨道图上任意两点之间边的条数总是相等的，且等于$|G(x)|$。进而，轨道的大小就是陪集的个数，$|B(x)|=[G:G(x)]$。这称为轨道-稳定子定理。

The Orbit-Counting Theorem

如何计算$X$中有多少个不同的轨道呢？我们可以用一种double counting的方法来得到计算轨道个数的一个简单方法。设群$G$作用在集合$X$上，把所有满足$g\circ x=x$的有序对收集进集合$T$，$T=\{(g,x)\mid g\circ x=x,g\in G,x\in X\}$。固定$x$计数，设$T_x=\{(g,x)\mid g\circ x=x,g\in G\}$，所有的$g$其实就是稳定子，$|T_x|=|G(x)|$。于是$|T|=\sum\limits_{x}|T_x|=\sum\limits_{x}|G(x)|$。另一方面，固定$g$，设$T_g=\{(g,x)\mid g\circ x=x,x\in X\}$，于是$\sum\limits_{x}|G(x)|=\sum\limits_{g}|T_g|$。两边同时除以$|G|$，那么$\sum\limits_{x}\dfrac{|G(x)|}{|G|}=\dfrac{\sum\limits_{g}|T_g|}{|G|}$。其中，$|G|/|G(x)|=[G:G(x)]=|B(x)|$，因此$\sum\limits_{x}\dfrac{|G(x)|}{|G|}=\sum\limits_{x}\dfrac{1}{|B(x)|}$，而由于同一个轨道中的$x$的$B(x)$都取相同值，因此$\sum\limits_{x}\dfrac{1}{|B(x)|}$就是轨道数。综上，轨道数就等于$\dfrac{1}{|G|}\sum\limits_{g}|T_g|$。而$|T_g|$就是函数$f_g$的“不动点”个数。

几类特殊的作用

选取$X=G$，运算定义为群的运算$f_g:x\to gx$。根据封闭性，这是$X\to X$的映射；根据群运算的结合律和单位元的性质，我们验证了这的确是一种群在集合上的作用，这里$G$作用于自身，称为正则作用(regular action)。此时对于任意的$x\in X$，对于任意的$y\in X$都有$y=(yx^{-1})x$，因此任意一个元素的轨道都覆盖了所有点；$gx=x$由消去律得$g=e$，所以稳定子大小为1，也即轨道图上不存在重边。

对于$G$和$X$，定义$f_g:x\to x$。这确实是映射，结合律和单位元都成立。这称为平凡作用(trivial action)。此时，所有$G$中元素都是任何$x$的稳定子，$\forall x,G(x)=G$。每个$x$自成一个轨道，共有$|X|$个不同轨道。

选取$X=G$，定义$f_g:x\to gxg^{-1}$。根据群的封闭性这是$X\to X$的映射，结合律成立（$h\circ (g\circ x)=h(gxg^{-1})h^{-1}=(hg)x(hg)^{-1}=(hg)\circ x$），单位元$exe^{-1}=x$。这称为元素共轭作用(conjugation on elements)。这是保运算的映射，$f_g(xy)=gxyg^{-1}=gxg^{-1}gyg^{-1}=f_g(x)f_g(y)$，因此$f_g$构成了$G\to G$的自同态，而$f_g$是双射所以是自同构。$x$的稳定子写作$G(x)=\{g\mid gxg^{-1}=x\}$，也即$\{g\mid gx=xg\}$，这些是所有与$x$相乘满足交换律的元素集合，称为$x$的中心化子(centralizer)，记为$C_G(x)$。对所有的$C_G(x)$取交，得到的是与所有$x$满足交换律的元素，这些元素称为群$G$的中心元(central element)。由于每个$G(x)$都是$G$的子群，中心元构成的集合也是子群，称为中心元群。（在Homework6中，我们证明了中心元群是正规子群。）中心元群中的每个元素的稳定子都是$G$，它们都各自自成一个轨道。对于给定的$x$，$B(x)=\{gxg^{-1}\mid g\in G\}$，对于不同的$x$它们构成$G$的partition，因此这个集合又称为$x$的共轭类(conjugacy class)。

取$X=\{H\mid H\preceq G\}$，定义$f_g:H\to gHg^{-1}$。$gHg^{-1}$是子群，因为$(gHg^{-1})(gHg^{-1})=gHHg^{-1}=gHg^{-1}$，$(gHg^{-1})^{-1}=gHg^{-1}$，因此是映射；结合律$h(gHg^{-1})h^{-1}=(hg)H(hg)^{-1}$；单位元$eHe^{-1}=H$。这称为子群共轭作用(conjugation on subgroups)。$H$的稳定子$G(H)=\{g\mid gHg^{-1}=H\}$ $=\{g\mid gH=Hg\}$。可见如果群$K$满足$K\subseteq G(H)$就有$H$是$K$的正规子群，因此$G(H)$又称为$H$的正规化子(Normalizer)，记为$N_G(H)$。正规化子同样是$G$的子群：$\forall a,b\in N_G(H)$，$(a^{-1}b)H(a^{-1}b)^{-1}=a^{-1}(bHb^{-1})a$ $=a^{-1}Ha=H$。其中最后一步是因为如果$a\in N_G(H)$，那么$aHa^{-1}=H$，所以$a^{-1}Ha=H^{-1}=H$，因此$a^{-1}\in N_G(H)$。同时显然有，$\forall h\in H$，$hHh^{-1}=H$，因此$H\subseteq N_G(H)$，也即$H\preceq N_G(H)$。综上，$N_G(H)$是$G$中最大的使得$H$在其中是正规子群的子群。

取$X=\{S\mid S\subseteq G\}$，定义$f_g:S\to gSg^{-1}$。根据封闭性，$gSg^{-1}\subseteq G$；结合律$h(gSg^{-1})h^{-1}=(hg)S(hg)^{-1}$；单位元$eSe^{-1}=S$。这称为子集共轭作用(conjugation on subsets)。$S$的稳定子$G(S)=\{g\mid gS=Sg\}$同样称为$S$的正规化子(normalizer)，记为$N_G(S)$。子集共轭显然满足$|S|=|gSg^{-1}|$（子群共轭自然也满足）。

对于$H\preceq G$，取$X=G/H=\{aH\mid a\in G\}$，定义$f_g:aH\to gaH$。显然这是映射，满足结合律和单位元。这称为陪集左乘的作用(multiplication on cosets)。作为一个应用，我们考虑如下例子：群的第二同构定理陈述了如果$H\preceq G,K\unlhd G$，那么$H/(H\cap K)\cong HK/K$。现在我们证明如果把$K\unlhd G$放弱为$K\preceq G$，结论也会相应弱化为$\dfrac{|H|}{|H\cap K|}=\dfrac{|HK|}{|K|}$。Pf. 取$X=G/K$，让$H$以陪集左乘的方式作用在$X$上（$G$可以作用，子群$H$当然也可以作用）。那么对于$K\in X$，轨道$B(K)=\{hK\mid h\in H\}$，稳定子$G(K)=\{h\in H\mid hK=K\}=H\cap K$。根据轨道-稳定子定理，$|B(K)|=|H|/|G(K)|$。而$|B(K)|=|HK|/|K|$，所以$|HK|/|K|=|H|/|H\cap K|$。Qed.

取$X=\{S\mid S\subseteq G\}$，同样可以验证$f_g:S\to gS$是作用，称为子集左乘的作用(multiplication on subsets)。

串珠染色问题

有$6$颗珠子串成一个环，要给它们用$n$种颜色染色，问有多少种不同的染色方案？其中，经过旋转和翻折后相同的方案算同一种方案。这就是串珠染色问题。

可以证明，串珠（正六边形）的运动只有$12$种，分别是依次旋转$0^\circ,60^\circ,120^\circ,180^\circ,240^\circ,300^\circ$以及沿六条不同的对称轴翻折。每一种运动对应着一个$6$阶permutation，所有的运动构成一个$6$阶置换群，也即$[6]$的对称群的一个子群。列举如下：$\tau_1=(1)(2)(3)(4)(5)(6)$，$\tau_2=(1,2,3,4,5,6)$，$\tau_3=(1,3,5)(2,4,6)$，$\tau_4=(1,4)(2,5)(3,6)$，$\tau_5=(1,5,3)(2,6,4)$，$\tau_6=(1,6,5,4,3,2)$，$\tau_7=(1,6)(2,5)(3,4)$，$\tau_8=(1,5)(2,4)(3)(6)$，$\tau_9=(1,4)(2,3)(5,6)$，$\tau_{10}=(1,3)(2)(4,6)(5)$，$\tau_{11}=(1,2)(3,6)(4,5)$，$\tau_{12}=(1)(2,6)(3,5)(4)$。把这个置换群记为$D_{12}$。

现在不考虑重复地做出$n^6$种染色方案，每个染色方案是一个长度为$6$的数字串，它们构成集合$X$。令$D_{12}$作用在$X$上，作用的方式是以$\tau_i$的方式对数字串进行顺序的重排。可见，映射、结合律、单位元都满足，因此这是群在集合上的作用。而串珠染色问题就是要问$X$的不同轨道个数，因为同一个轨道意味着同一种本质相同的染色方案。根据Orbit-Counting定理，我们只需计算每一个置换$\tau_i$在$X$上的不动点个数。假设总共可以染$n$种颜色，那么$\tau_1$的不动点是全部（$n^6$）；$\tau_2$产生不动点当且仅当旋转$60^\circ$以后不变，意味着只要有两个相邻颜色不同就不合法，因此只有所有颜色相同的方案，共$n$个。更一般地，我们发现进行不相交的轮换分解以后，不动点上每个轮换中的颜色必须相同，不同轮换可以是不同颜色。因此$\tau_i$的不动点个数就是$n^k$，其中$k$是轮换个数。这样我们就给出了串珠染色问题的多项式表达式：$\dfrac{n^6+n+n^2+n^3+n^2+n+n^3+n^4+n^3+n^4+n^3+n^4}{12}$。

正多面体的旋转变换群

将一个正多面体进行旋转变换，使得所有的面在变换后依然与原先的某个面重合，容易验证所有这样的变换构成一个旋转变换群。求出旋转变换群的大小，就求出了正多面体有多少种本质不同的旋转。这可以利用群在集合上的作用来求解。

以正十二面体为例，设群$G$是正十二面体的旋转变换群，$X=\{1,2,\cdots,12\}$，分别代表正十二面体的每个面。$G$中的一个元素是一个$12$阶的permutation，定义$\sigma\in G$作用在$x$上的映射：$f_{\sigma}:x\to \sigma(x)$。这的确是$X\to X$的映射，并且满足结合律和单位元。要求出$G$的大小，只需求出某个特定面（比如$1$）的轨道和稳定子大小的乘积。面$1$的轨道是经过所有可能旋转能够变换到的面，显然是$12$；面$1$的稳定子是所有使得其保持静止的旋转，这对应着绕穿过面$1$中心与面$1$垂直的对称轴进行的本质不同旋转，由于正十二面体表面由五边形组成，共有$5$个这样的旋转。因此群的大小为$12\times 5=60$。

也就是说我们得到了，正多面体的旋转变换群大小为面的个数乘以多边形边数。因此，正四面体为$4\times 3=12$，正六面体（立方体）为$6\times 4=24$，正八面体为$8\times 3=24$，正十二面体为$12\times 5=60$，正二十面体为$20\times 3=60$。