Permutation Group

官方信息技术老师·15 页·深入(追求细节与边界)·0 次浏览·2 天前
对称群群作用轮换分解抽象代数

置换群

用群作用视角重解置换:从轮换分解、奇偶性到轨道稳定子定理一次打通

按 空格/→ 演示下一步

1 / 15 页

全部页面点击任意一页,跳回舞台从这页播放

对称群群作用轮换分解抽象代数

置换群

用群作用视角重解置换:从轮换分解、奇偶性到轨道稳定子定理一次打通

1第 1 页 · 置换群

什么是置换

上一节我们看到,置换群研究的是「重排」的整体结构。现在往回走一步:到底什么是「置换」?它和中学数学里的「排列」是什么关系?

双射本质
置换是集合到自身的一一对应,每个元素恰好出现一次在像中
从计数到操作
排列关心「有几种排法」,置换关心「这次怎么排」的动作本身
两种记法
两行记法直观但冗长;轮换记法体现结构,是群论标准语言
抽象的关键
元素是谁不重要,重排的「形状」(轮换类型)才是研究对象
调换座位对应 →置换是一次具体换座

排列是「一共能排出多少种坐法」,置换是「谁坐到哪」的对应关系本身

$\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 1 & 3 \end{pmatrix}$
2第 2 页 · 什么是置换

置换的表示法

前页我们用箭头 σ(1)=3 描述置换,但一条条写零散。置换是整体对象——怎么'一次性写下来'?两套主流记号:表格化的两行法,和轨迹化的循环法。这一页学互译。

两行表示法
上行写元素本身,下行对齐写像的位置,映射关系一目了然
循环表示法
从某元素出发沿映射链写下所经元素,回到起点时闭合;1-循环(不动点)常省略
两行 → 循环
挑未处理元素作起点,沿下行持续追踪直到回到起点,记为一个循环;重复直至全部覆盖
循环 → 两行
把每个循环 (a₁ a₂ … aₖ) 拆为 a₁→a₂→…→aₖ→a₁,按此填入下排;未出现元素保持对自身映射
接力赛的传棒顺序对应 →循环表示法

1棒→2棒→3棒→…→最后一棒传回起点,闭环就是一个循环

σ=(1234531254)=(1 3 2)(4 5)\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 1 & 2 & 5 & 4 \end{pmatrix} = (1\ 3\ 2)(4\ 5)
3第 3 页 · 置换的表示法

置换的乘法运算

置换相乘不是数相乘,而是函数复合。关键是顺序:从右往左依次作用。

1
乘法=复合
两个置换相乘等于把右边的置换先作用、再用左边的置换接上
2
从右往左读
στ 中 τ 先作用,σ 后作用;像先穿内衣再穿外套
3
追踪元素轨迹
对每个 x,先看 τ 把 x 送到哪,再看 σ 把那个值送到哪
4
写出合成置换
把每个 x 的最终落点整理成新的置换,记作 στ
4第 4 页 · 置换的乘法运算

换位的定义

前面我们学过,任意置换都可以由若干置换复合而成。那有没有最简单、最'原子'的置换?——只交换两个、其余不动的置换,就是一切的'积木'。

换位的定义
仅交换两个不同元素、其他元素全部保持不动的置换
标准记号 (i j)
表示交换 i 和 j;记号中元素顺序无影响:(i j)=(j i)
与恒等的边界
必须 i≠j;若 i=j,(i i) 退化为恒等置换 e,不再是换位
数组排序中的 swap对应 →换位 (i j)

排序反复调 swap,每次只动两个位置,其余不变

(i j)=(1ijn1jin)(i\ j) = \begin{pmatrix} 1 & \cdots & i & \cdots & j & \cdots & n \\ 1 & \cdots & j & \cdots & i & \cdots & n \end{pmatrix}
5第 5 页 · 换位的定义

换位的性质

上页我们把换位定义为只交换两个元素的最小积木。这页回答:一个置换究竟是「奇」还是「偶」,怎么判定?

偶置换与奇置换
能拆成偶数个换位之积的是偶置换,能拆成奇数个换位之积的是奇置换
判定法一:换位分解
把置换显式写成换位之积,统计换位个数定奇偶
判定法二:逆序数
数满足 i<j 但 σ(i)>σ(j) 的对数,奇数对应奇置换,偶数对应偶置换
良定义性
同一置换的换位分解方式不唯一,但奇偶性始终唯一确定
sgn 符号函数
把置换 σ 映到 +1(偶置换)或 −1(奇置换),得到乘法群 {±1}
反复开关灯对应 →换位分解的奇偶性

灯的开关态只取决于按的次数奇偶,与顺序无关;分解方式可变,奇偶性不变

sgn(σ)=(1)k,  k 为任意一组换位分解中的换位个数\operatorname{sgn}(\sigma)=(-1)^{k},\;k\text{ 为任意一组换位分解中的换位个数}
6第 6 页 · 换位的性质

置换分解为换位

把任意置换拆成换位的乘积,按一个固定算法一步步推进。

1
化为循环
先把置换写成不相交循环的乘积形式
2
拆长循环
对每个长度k≥3的循环,展开成k-1个换位
3
保留换位
长度为2的循环本身已是换位,无需再拆
4
连乘输出
把所有换位依次相乘,得到最终分解
7第 7 页 · 置换分解为换位

共轭的定义

前面我们学了置换的乘法,也学会了把任意置换拆成换位。现在摆在你面前两个置换 τ 和 π:先用 π⁻¹ 改一下标签、再让 τ 作用、最后用 π 把标签还原回来——得到的这个新置换 σ,就叫 τ 的共轭。

共轭的代数形式
σ = πτπ⁻¹:先做 π⁻¹,再做 τ,最后做 π
换视角观察
等价于站在 π 重排后的世界里看 τ 的作用
等价关系
满足自反、对称、传递,把群分成若干共轭类
循环结构不变
若 σ 与 τ 共轭,则二者循环类型完全相同
线性代数的换基底对应 →置换的共轭 πτπ⁻¹

矩阵作用在向量空间,置换作用在集合;P⁻¹AP 换坐标系,π 相当于给元素重命名

σ=πτπ1\sigma = \pi \tau \pi^{-1}
8第 8 页 · 共轭的定义

共轭类的构造

上一页我们用 gσg⁻¹ 定义了共轭——把 σ 里每个元素 a 换成 g(a)。问题来了:变换之后,什么被保留、什么被丢掉?答案是:循环的'形状'不变,循环型才是决定共轭关系的真正指纹。

循环型
σ 拆成不相交循环后,各循环长度组成多重集,如 {3,2,2}
共轭保持循环型
若 σ=(a₁…aₖ),则 gσg⁻¹=(g(a₁)…g(aₖ)),长度不变
同型 ⇒ 共轭
两个置换若循环型相同,就一定能找到 g 使 gσg⁻¹=τ
不同型 ⇒ 不共轭
循环型是共轭的不变量,不同循环型的置换必分属不同类
给座位上的学生重新编号对应 →置换的共轭

学生位置不变、只换名牌,循环形状就不变;只要形状相同,总能换名牌让两套排列对应

g(a1a2ak)g1=(g(a1)g(a2)g(ak))g(a_1\,a_2\,\ldots\,a_k)g^{-1}=\bigl(g(a_1)\,g(a_2)\,\ldots\,g(a_k)\bigr)
9第 9 页 · 共轭类的构造

共轭类的判定定理

图示共轭作用的流程:ρ → 类型 3+2 → 经 σ 共轭 → 类型不变 → 同型 ⇔ 共轭。横向阅读,从左到右推进。

图解渲染中…
a1具体如 ρ = (1 2 3)(4 5) ∈ S₅c1σ⁻¹ 重标 → ρ 作用 → σ 还原,三步合成c2形如 (σ1 σ2 σ3)(σ4 σ5),长度分布保留d1Sₙ 中共轭类 ↔ 整数分拆 λ ⊢ n
10第 10 页 · 共轭类的判定定理

共轭类与对称分类

盯着 NH₃,绕 C₃ 轴转 120°——三个 H 互换位置,N 没动。这是一次 4 元置换里的 3-循环。把分子所有「形状不变」的操作按循环结构分堆,每堆就是一个共轭类——这正是构造特征标表的起点。

母群分类定理
Sₙ 中同循环型 ⟺ 共轭等价;类型 (1^{a₁}2^{a₂}⋯) 完全决定一个共轭类。
操作 ↔ 循环
Cₖ 旋转 = 一个 k-循环;只动两原子的反映 σᵥ = 一个 2-循环。
类大小公式
型 (1^{a₁}2^{a₂}⋯) 的共轭类,其大小 = n! / (∏_{k} k^{aₖ}·aₖ!)。
子群会拆类
该定理在 Sₙ 母群成立;进入真子群(如 Cₙᵥ、Dₙₕ)后同型可能裂为多类。
通往特征标
同一类所有操作在所有不可约表示下响应相同,故特征标定义为类上的函数。
化学按官能团分有机物对应 →置换按循环型分共轭类

同官能团同类;但放进特定反应条件(子群约束)下,等价类可能再拆分。

$$|C| = \frac{n!}{\prod_{k=1}^{n} k^{a_k} \, a_k!}$$
11第 11 页 · 共轭类与对称分类

Burnside引理初步

上节我们收在「共轭类内循环类型一致」。这一节把它接上 Burnside 引理:能不能用共轭类当颗粒度去数轨道?答案是可以——同类元素不动点相同,求和就能按类合并。

Burnside 引理
轨道数 = (1/|G|) Σ |Fix(g)|,即不动点数的平均
同类不动点一致
g 与 hgh⁻¹ 作用同构,故 |Fix(g)| 在共轭类内为常数
按类合并求和
把 Σ 改写为对共轭类求和,每类贡献 |C|·|Fix(g_C)|
类大小作权重
|C| = |G|/|Z_G(g)|,决定该类在最终结果里的权重
超市按品类批量结账对应 →Burnside 按共轭类合并

同类商品单价相同;总价 = Σ 类(数量 × 单价),不必逐件算

X/G=1GCCFix(gC)|X/G|=\frac{1}{|G|}\sum_{C}|C|\cdot|\mathrm{Fix}(g_C)|
12第 12 页 · Burnside引理初步

置换群的编程实现

python

用一段 Python 把置换表示为字典,演示乘法、共轭运算与循环型判定——共轭 ⇔ 循环型相同。

代码高亮加载中…

字典即映射;compose 用推导式实现函数复合;conjugate 把 g·p·g⁻¹ 写成三步;cycle_type 沿轨道走得到循环结构;同循环型即共轭(在 S_n 中)。

13第 13 页 · 置换群的编程实现

核心概念自测

点击作答

两个置换在 S_n 中共轭,当且仅当它们具有相同的______。

14第 14 页 · 核心概念自测

课后思考

先自己想,再看参考答案——好的问题比答案更值得琢磨。

1为什么任何置换都能唯一分解为不相交轮换的乘积?这里的唯一性为什么重要?

参考答案从恒等置换出发逐步搬运元素,每步都是换位;不相交轮换彼此独立、交换顺序不影响结果,所以唯一。

2把置换群作用在魔方上,旋转操作构成的群是什么?它和S₄有什么关系?

参考答案立方体有4条主对角线,旋转正好置换它们——旋转群同构于S₄,这给置换群一个直观模型。

3无限群(比如全体平移变换)能用置换群的方法研究吗?为什么?

参考答案看作用对象:作用于无穷集合上一般不行;但只要让无限群作用在有限集合上,仍可化为置换群讨论。

15第 15 页 · 课后思考
Permutation Group · 知识图解