不同描述可以代表同一对象
圆形排列没有必须选作起点的位置。例如旋转四位二进制环可能改变写出的字符串,却不改变同一个圆形排列。先计算字符串数再除以四看似合理,但不同排列的不同旋转数目可能不同。我们会精确计算等价类,而不假设每个等价类一样大。
定义 1.2.1
(群作用、轨道、稳定子与不动点集)
令 为有限群, 为有限集合。若每个 把每个 变成 中的元素 ,单位元素保持每个构型不变,且 (先后施行两个变换与施行它们的群乘积一致),就说 作用于 。
- 的轨道是 。各轨道划分 ;同一轨道中的构型在指定对称下代表同一对象。
- 的稳定子是 ,即保持这一个构型不变的变换。
- 的不动点集是 ,即被这一个变换保持不变的构型。
稳定子按构型索引,不动点集按变换索引;下面的证明会用两种方式计算同一批配对。我们先需要轨道与稳定子大小之间的关系。
引理 1.2.2
(轨道大小乘以稳定子大小)
对每个 ,
证明
(映射 g 到 g 作用于 x 的纤维)
定义 ,。按轨道的定义,它是满射。固定轨道中的 ,并令 。若 ,则 ,所以 属于 ,且 。反过来,对每个 有 。因此纤维 等于 。左乘 是单射,所以每条纤维恰有 个元素。各纤维划分 ,故 。
定理 1.2.3
(不动点数目的平均)
轨道数目为
证明
(计算被变换保持不变的配对)
令 。按 计数,得 ;按 计数,得 。把第二个和按轨道分组。对轨道 中任一 ,引理给出 ,所以 的全部元素共贡献 个配对。各轨道划分 ,因此 。除以 即得公式; 为空时两边都为零。
对同一批配对作两种计数
这个证明无须知道个别的稳定子,只需要一个事实:逐个轨道计算,配对的数目加起来都是同一个数。
证明透视
为何平均值给出轨道数
关键一步是把 计数两次:按变换计数,是我们能够计算的量;按构型计数,它可按轨道拆开。无论稳定子大小如何,每个轨道都恰好贡献 个配对:大的轨道稳定子小,小的轨道稳定子大,而引理使两者之积保持不变。正是这个不变性,把稳定子大小之和变成轨道的个数。
假设在哪里使用:纤维的计算用到逆元 与相容规则 。若变换没有逆元,“在同一轨道”就不一定对称,轨道也不再划分 。 有限使我们可以除以 , 有限使各个和为有限。论证能够完结,是因为轨道划分 :每个轨道贡献 之后,总数就是 乘以轨道数。若没有引理,我们只剩下 ,却无法求值。
环上的四个二进制位置
例题 1.2.4
(四种旋转,六个轨道)
令 为全部四位二进制字符串, 包含旋转 格。共有 个字符串。单位变换固定全部 个;旋转一格只固定 和 ,旋转三格也固定 个。旋转两格固定 个,因为相对位置必须相同。旋转轨道数为
每个轨道取一个代表,可选 。这里的作用只有旋转;若也允许反射,便是另一个等价关系,需要重新计算不动点。
例题 1.2.5
(三种旋转,四个轨道)
令 为全部三位二进制字符串, 为旋转 格,所以 ,。单位变换固定全部 个字符串。旋转一格固定某字符串,当且仅当三个比特全部相同,所以只固定 和 ;旋转两格也是如此。因此
列出轨道可以核对:、、、,大小 。 不是整数,所以这里不能把 除以 ;不动点数目的平均却是正确的。
例题 1.2.6
(自由作用不需要修正)
令 为四个旋转, 为环上的位置,旋转 格把位置 送到 。单位变换固定全部 个位置;每个非零旋转都没有固定位置,因为 迫使 。于是
只有一个轨道:每个位置都可以旋转到其他任何位置。这里每个稳定子都是平凡的,每个轨道有 个元素, 给出相同答案。这就是捷径成立的特殊情形。
反例模式
为何把字符串数直接除以四会失败
直接算 是假设每个轨道都有四个成员。但 只有一个不同旋转, 有两个,而 有四个。由于某些构型具有非单位的对称,轨道大小会不同。不动点平均考虑了这些稳定变换,而不是把所有轨道当作相同大小。
用法与限制
计数前必须指定群及其作用:只列出一些变换而没有封闭性和逆元,不能直接使用以上证明。不动点是被某一指定变换保持不变的构型,不是指没有对称的构型。平均值必为整数,因为它计算的是轨道数,尽管各个不动点数目可能不同。
若只有单位变换会固定任何构型,则每个稳定子大小为一,每个轨道大小均为 ;此特殊情况可以用 。对一般作用则未必可以。定理计算等价类数目,但不会自动给出高效率的方法,为每一类生成规范代表。
概念视角代数
把轨道看成不变函数
让 通过置换自变量,作用在 上的实值函数之上。函数被每个 保持不变,当且仅当它在每条轨道上取常值,所以这些不变函数构成的空间,维数就是轨道数。算子 是到这个空间的投影,而投影的迹等于它的秩。每个 作为置换矩阵,迹为 ,因此这个迹正好是不动点个数的平均。
常见错误
(漏掉单位变换或除错除数)
和式要遍历 的每个元素,包括单位变换,而除数是 。对四位环,漏掉单位变换会得 ,把完整的和除以 则得 ;两者都不是轨道数,正确答案是 。单位变换通常贡献最大的一项 。
常见错误
(加入反射却仍然除以四)
允许反射会把群扩大到 个元素,所以除数必须改为 。在四个位置 上,固定两个相对位置的两个反射各固定 个字符串(两个固定位置加一对互换位置,共三个独立比特),而互换相邻位置的两个反射各固定 个字符串。总和是 ,轨道数为 。若沿用除数四,会得到 ,这是不可能的:多认同一些字符串,不可能得出比旋转的 个类更多的类。
练习
快速检查
(计算长度为五的二进制字符串按五个旋转分类的数目,并为每个轨道列一个代表。)
当 是素数时,非零旋转固定哪些字符串?
解答 · 答案
单位变换固定 个字符串。四个非零旋转中,每个只有在五个比特全部相同时才固定字符串(长度为五的环上,非零旋转会把位置 依次送到全部五个位置),所以各固定 个。轨道数为 。代表可取 ;它们的轨道大小 之和为 。
快速检查
(对四位环,为何旋转两格恰好固定四个字符串?)
写出旋转互换了哪些位置。
解答 · 答案
第一与第三位置必须相同,第二与第四位置必须相同;两对各自选一位,得 个字符串。
快速检查
(在四位例子中,、 和 的轨道大小分别是多少?)
对它们施行全部四个旋转,数出不同的结果。
解答 · 答案
依次为 : 不变; 与 交替出现; 是四个不同的字符串。
快速检查
(为何加入反射必须视为新的计数问题?)
比较加入前后的作用群。
解答 · 答案
反射可能把单靠旋转不等价的构型视为相同,作用的群及其不动点项也会改变;只算旋转的结果没有包括这些变换。