置换群

群可以有多种不同的表示. 尤其是,所有有限群都可以表示为置换群. 也就是说它们总是和一个 元素集合的自同构对称群 的一个子群同构 (Cayley 定理). 在过去的40年中,高效的处理置换群技术得到发展,使人们能够用计算机对非常大的群进行处理.
Wolfram 语言为处理范围在几千以内的中等次数的置换群提供了一套命令与算法,因而适用于元素超过 的置换群.

本教程介绍一些计算有限置换群的基本算法,这些有限群是由一系列以不相交轮换的形式给出的生成置换所确定的. 另外一个教程 "置换" 会解释如何处理轮换形式的置换.

生成集

确定一个群的一个简单而紧凑的方法是通过给出一组元素,它们的反复相乘就产生了整个群. 这些元素称为群的生成元,它们组成的集合叫生成集. 这是确定有限群的一个普遍而有力的方法. 当然,对于大型的群而言,可能很难从中获取有关群的信息.

PermutationGroup由生成元定义的置换群的头部
GroupElements群元素列表
GroupMultiplicationTable群元素所有乘积对的表格(乘法表)
CayleyGraph连接群元素的生成元的图(凯莱图)

群的表示.

采用两个置换并构造由它们生成的群.
In[1]:=
Click for copyable input
这是群中所有置换的列表.
In[4]:=
Click for copyable input
Out[4]=
In[5]:=
Click for copyable input
Out[5]=
两个生成元都保持第二个点不动,因而群中的所有置换也都是这样. 这个生成的群与集合 上具有 个置换的对称群同构.
In[6]:=
Click for copyable input
Out[6]=
In[7]:=
Click for copyable input
Out[7]=

对于小型群,可以构造更好的群表示. 它们是凯莱乘法表和凯莱图,后者既代表了整个群的信息,也代表了所用的生成元的信息.

对于小型群,所有乘积都可以用凯莱乘法表表示.
In[8]:=
Click for copyable input
Out[8]//TableForm=
每一行和每一列本身是数124的一个置换. 这个数组当且仅当群是阿贝尔的的时候是对称的. 群不是阿贝尔的.
In[9]:=
Click for copyable input
Out[9]=
In[10]:=
Click for copyable input
Out[10]=
你也可以用一个凯莱图. 用置换 的相乘表示为红色,用 的表示为蓝色.
In[11]:=
Click for copyable input
Out[11]=
从图中很清楚地看到,第一个生成元(红色)是三阶的,而第二个(蓝色)是二阶的.
In[12]:=
Click for copyable input
Out[12]=
图中任何一个闭合环路表示一种给出恒元的关系. 例如,环路 与以下对应.
In[13]:=
Click for copyable input
Out[13]=
换句话说,我们找到了一个四阶置换.
In[14]:=
Click for copyable input
Out[14]=

轨道和稳定子群

给定作用于一些点的一个集合的置换群的任何生成集,就有可能找出其它哪些点可以和给定的一个点相联系. 这被称为那个点的轨道(orbit ).

GroupOrbits计算一个群作用下点的轨道

轨道的计算.

采用两个新的置换,并用它们组成一个生成集.
In[15]:=
Click for copyable input
这是点3的轨道. 轨道是将点按字典顺序排序的形式给出的.
In[18]:=
Click for copyable input
Out[18]=
轨道上的每一个点都唯一地确定了同一个轨道.
In[19]:=
Click for copyable input
Out[19]=

点不能同时属于两条不同的轨道,因而轨道将群所作用的点的集合进行了分区.

在这个例子中,最大的支撑点是30 .
In[20]:=
Click for copyable input
Out[20]=
因此,轨道对最初的30个点进行分区.
In[21]:=
Click for copyable input
Out[21]=
也可以输入更多的点来选择轨道.
In[22]:=
Click for copyable input
Out[22]=
如果划分一个更大的范围,所有其它点将都是稳定的.
In[23]:=
Click for copyable input
Out[23]=
轨道可以高效地计算,因此有可能用于较大支撑的置换.
取一个由两个次数较大但相同的随机置换生成的群.
In[24]:=
Click for copyable input
在多数情形下,这个群是可递的,有一个单一的轨道.
In[25]:=
Click for copyable input
Out[25]=
现在取两个支撑长度相差很大的生成元.
In[26]:=
Click for copyable input
那么通常还有一个较大的轨道,但不是最长的.
In[27]:=
Click for copyable input
Out[27]=

用更一般的作用可以形成其它类型的轨道,如共轭类.

这是对称群的一个置换的共轭类.
In[28]:=
Click for copyable input
Out[28]=

轨道描述点如何运动. 作为对轨道所提供的信息的补充,也可以计算稳定子群,即保持一个或几个点不动的群元组成的子群.

GroupStabilizer保持一个或几个点不动的群元组成的子群

稳定子群的计算.

再次取出这个群.
In[29]:=
Click for copyable input
Out[29]=
这是保持点3不动的置换的子群. 轮换表示法表明它的任何一个生成元都不会移动点3.
In[30]:=
Click for copyable input
Out[30]=
已经知道,在该群作用下,点3的轨道长度是18:
In[31]:=
Click for copyable input
Out[31]=
In[32]:=
Click for copyable input
Out[32]=
根据轨道-稳定子群定理,这也一定是两个群阶数之商:
In[33]:=
Click for copyable input
Out[33]=

强生成集表示

对于较大的置换群,对所有元素进行列表或画图会变得越来越不方便. 这种情况下,有必要寻求别的方法,以便可以从群的生成集中获取群的信息,而不必去计算所有的置换. 该方法的关键思想是六十年代后期发展起来的,其基础是对同一个群构造一个新的等价的生成集,但从该生成集很容易形成一个子群层级,使得对整个群能够进行快速操作. 这个特殊形式的生成集叫强生成集(strong generating set).

GroupOrder群元数
GroupElementQ检验一个置换是否属于一个给定的群

强生成集的基本功能.

采用由支撑为 的两个置换生成的群.
In[34]:=
Click for copyable input
轨道的计算可以通过标准的生成元来直接完成. 然而,为了计算群的阶数,Wolfram 语言在内部计算的是群的强生成集.
In[37]:=
Click for copyable input
Out[37]=
该表示被储存了起来,以避免针对初始的那个相同的生成元集合对其进行重复计算.
In[38]:=
Click for copyable input
Out[38]=
现在就有可能做成员的验证了.
In[39]:=
Click for copyable input
Out[39]=
In[40]:=
Click for copyable input
Out[40]=
任何生成元的积一定属于群.
In[41]:=
Click for copyable input
Out[41]=
In[42]:=
Click for copyable input
Out[42]=

现在返回来看看强生成集的性质. 强生成元是根据基(base)来定义的: 这是群作用的区域上的点的一个有序子集,对该子集,恒元是唯一保持其所有点不变的群元. 这意味着,知道置换下一个基中的点的像,就可唯一地确定这个置换. 对于已知一个较短的基的群,操作起来会是很高效的. 基定义了一个非常有用的稳定子群的层级,被称为稳定子群链. 它在置换群操作中起核心的作用,与线性代数中矢量空间的高斯-消去分层非常相似. 最后,使一个生成元的集合对于一个基具有强 (strong)的特征的条件是它包含相应稳定子群链中所有子群的生成子集.

GroupStabilizerChain一个置换群的稳定子群链
GroupActionBase指定一个群的一个基的选项

稳定子群链、基和强生成元.

这是前面的群相对于基 的一个稳定子群链,它是 Wolfram 语言自动选取的 .
In[43]:=
Click for copyable input
Out[43]=
这是该稳定子群链中子群的阶数.
In[44]:=
Click for copyable input
Out[44]=
链的基和强生成元的获取如下.
In[45]:=
Click for copyable input
Out[45]=
In[46]:=
Click for copyable input
Out[46]=
这些仍然是原群的生成元.
In[47]:=
Click for copyable input
Out[47]=
链中的第二个群是1的稳定子群,它是一个阶数为253的子群.
In[48]:=
Click for copyable input
Out[48]=
In[49]:=
Click for copyable input
Out[49]=
该稳定子群只少一个置换,该置换移动点1.
In[50]:=
Click for copyable input
Out[50]=
强生成集中的其它置换不移动点1.
In[51]:=
Click for copyable input
Out[51]=
可以对基中的前两点重复稳定化操作.
In[52]:=
Click for copyable input
Out[52]=
In[53]:=
Click for copyable input
Out[53]=
最后,第三个稳定子是平凡群,因为它是整个基的稳定子群.
In[54]:=
Click for copyable input
Out[54]=
通过证明群的阶数总能被子群的阶数整除来验证拉格朗日定理.
In[55]:=
Click for copyable input
Out[55]=
In[56]:=
Click for copyable input
Out[56]=
这些数的积即原群的阶数.
In[57]:=
Click for copyable input
Out[57]=
In[58]:=
Click for copyable input
Out[58]=
GroupActionBase 选项容许用户指定另外一个基. 如果它不是一个真正的基, Wolfram 语言将通过增加点来使其成为基.
In[59]:=
Click for copyable input
Out[59]=

示例:Rubik 魔方群

一个最著名的置换群与魔方(Rubik)的转动相关. 在下面的图形中,移动魔块儿用数字1到48表示. 中心的魔块儿不动,分别定义了六个基本转动:

这是六个基本转动.
In[60]:=
Click for copyable input
这是群元数目.
In[67]:=
Click for copyable input
Out[67]=
在内部构造了如下的稳定子群链. 并指出了保持相应的一列点不变的置换的数目. 最后一行给出了群的一个基,因为只有一个置换(即恒元)保持给定的18个点不变.
In[68]:=
Click for copyable input
In[69]:=
Click for copyable input
Out[69]=
位于链中第一行的群给出了一个强生成元的集合.
In[70]:=
Click for copyable input
Out[70]=
现在可以检验某些移动是不是群的成员. 例如,将相邻的两个棱魔块儿对换是不允许的.
In[71]:=
Click for copyable input
Out[71]=
然而同时进行这样的两个对换是允许的.
In[72]:=
Click for copyable input
Out[72]=
这是一个超翻(superflip)移动, 即同时进行所有这样的对换.
In[73]:=
Click for copyable input
Out[73]=
In[74]:=
Click for copyable input
Out[74]=

其它示例

这是两个具有较大支撑,但有很短的基的群的例子.

有限群图集ATLAS of Finite Groups)中给出的最大辛群是 ,表示为496个点上的置换.
In[75]:=
Click for copyable input
In[78]:=
Click for copyable input
Out[78]=
In[79]:=
Click for copyable input
Out[79]=
这些是它的稳定子群链中子群的阶数.
In[80]:=
Click for copyable input
Out[80]=
这是例外扭群 ,表示为819个点上的置换.
In[81]:=
Click for copyable input
In[84]:=
Click for copyable input
Out[84]=
它也具有很短的基.
In[85]:=
Click for copyable input
Out[85]=