中科诚建建设工程有限公司网站,手机怎么样做网站,可以做视频创收的网站,产品研发的流程和步骤文章目录前言群基本定义#xff1a;子群陪集拉格朗日定理正规子群交换群商群阶置换定义置换的乘法循环置换群群作用等价类不动点Burnside引理内容证明法1 轨道-稳定子定理法2Polya 定理所谓群论#xff0c;就是对群体行为问题的讨论。 #xff08;逃#xff09;
前言
个人…
文章目录前言群基本定义子群陪集拉格朗日定理正规子群交换群商群阶置换定义置换的乘法循环置换群群作用等价类不动点Burnside引理内容证明法1 轨道-稳定子定理法2Polya 定理所谓群论就是对群体行为问题的讨论。 逃
前言
个人学起来比较困难的一部分。 主要的难点在于抽象常常会陷入虚空… 但当发现理论推出来的花里胡哨的东西和事实相符时还是挺爽的。 行文中如果有错误或者不严谨的地方欢迎指正感谢。 没怎么看懂但也许有用的网站
群
基本定义
群是由非空集合 GGG 和关于 GGG 的二元运算 ⋅\cdot⋅ 组成的代数结构满足如下性质
封闭性。a,b∈G⇒a⋅b∈Ga,b\in G\Rightarrow a\cdot b\in Ga,b∈G⇒a⋅b∈G结合律。(a⋅b)⋅ca⋅(b⋅c)(a\cdot b)\cdot ca\cdot(b\cdot c)(a⋅b)⋅ca⋅(b⋅c)标识元单位元。GGG 中存在一个元素 eee使得 ∀a∈G,a⋅ee⋅aa\forall a\in G,a\cdot ee\cdot aa∀a∈G,a⋅ee⋅aa这样的元素是独一无二的。逆元。∀a∈G,∃b∈G,a⋅be\forall a\in G,\exists b\in G,a\cdot be∀a∈G,∃b∈G,a⋅be。此时称 bbb 为 a−1a^{-1}a−1。
子群
对于一个群 (G,×)(G,\times)(G,×)若 HHH 为 GGG 的一个子集且 (H,×)(H,\times)(H,×) 也构成一个群则称 (H,×)(H,\times)(H,×) 为 (G,×)(G,\times)(G,×) 的一个子群。记为 H≤GH\le GH≤G。 GGG 和 {e}\{e\}{e} 称为 GGG 的两个平凡子群。 子群检验法H≤G⇔∀h,g∈H,h⋅g−1∈HH\le G\Leftrightarrow \forall h,g\in H,h\cdot g^{-1}\in HH≤G⇔∀h,g∈H,h⋅g−1∈H。
陪集
若 H≤G,g∈GH\le G,g\in GH≤G,g∈G则称 Hg{h⋅g,h∈H}Hg\{h\cdot g,h\in H\}Hg{h⋅g,h∈H} 为 HHH 在 GGG 内关于 ggg 的右陪集左陪集就是在左边同理 陪集具有如下性质 ∣Hg∣∣H∣|Hg||H|∣Hg∣∣H∣ 因为对于 h1,h2∈H,h1≠h2h1,h2\in H,h1\ne h2h1,h2∈H,h1h2都有 g⋅h1≠g⋅h2g\cdot h1\ne g\cdot h2g⋅h1g⋅h2。 g∈Hgg\in Hgg∈Hg 因为 e∈He\in He∈H。 HgH⇔g∈HHgH\Leftrightarrow g\in HHgH⇔g∈H 左往右由于性质二g∈Hgg\in Hgg∈Hg若 g∉Hg\notin Hg∈/H不可能有 HgHHgHHgH。 右往左由于封闭性HgHgHg 不可能取到 HHH 之外的元素对于 ∀h1∈H\forall h1\in H∀h1∈H设 h1⋅g−1h2∈Hh1\cdot g^{-1}h2\in Hh1⋅g−1h2∈H。则有 h1h2⋅gh1h2\cdot gh1h2⋅g所以 h1∈Hgh1\in Hgh1∈Hg。 HaHb⇔a⋅b−1∈HHaHb\Leftrightarrow a\cdot b^{-1}\in HHaHb⇔a⋅b−1∈H 左往右因为 ∀h1∈H,∃h2∈H,h1⋅ah2⋅b\forall h1\in H,\exist h2\in H,h1\cdot ah2\cdot b∀h1∈H,∃h2∈H,h1⋅ah2⋅b也就有 a⋅b−1h2⋅h1−1a\cdot b^{-1}h2\cdot h1^{-1}a⋅b−1h2⋅h1−1而 h2⋅h1−1∈Hh2\cdot h1^{-1}\in Hh2⋅h1−1∈H。 右往左∀h1∈H,h1⋅a∈Ha,∃h2h1⋅(a⋅b−1)∈H→h1⋅ah2⋅b,h2⋅b∈Hb\forall h1\in H,h1\cdot a\in Ha,\exist h2h1\cdot(a\cdot b^{-1})\in H\to h1\cdot ah2\cdot b,h2\cdot b\in Hb∀h1∈H,h1⋅a∈Ha,∃h2h1⋅(a⋅b−1)∈H→h1⋅ah2⋅b,h2⋅b∈Hb。其实就是左往右反过来推 Ha∩Hb≠∅→HaHbHa\cap Hb\ne \emptyset\to HaHbHa∩Hb∅→HaHb Ha∩Hb≠∅→∃h1,h2∈H,h1⋅ah2⋅b→a⋅b−1h2⋅h1−1∈H→HaHbHa\cap Hb\ne \emptyset\to\exist h1,h2\in H,h1\cdot ah2\cdot b\to a\cdot b^{-1}h2\cdot h1^{-1}\in H\to HaHbHa∩Hb∅→∃h1,h2∈H,h1⋅ah2⋅b→a⋅b−1h2⋅h1−1∈H→HaHb HHH 的所有右陪集的并集为 GGG。 由于封闭性不可能取到 GGG 之外的元素。 由于 e∈He\in He∈Hggg 取遍 GGG 的所有元素就可以保证 GGG 的所有元素都被取到。
拉格朗日定理 H≤G⇒∣H∣H\le G\Rightarrow |H|H≤G⇒∣H∣ 整除 ∣G∣|G|∣G∣。 结合陪集的性质即可得。由性质 1,5,61,5,61,5,6HHH 所有本质不同的陪集互不相交大小均为 ∣H∣|H|∣H∣共同组成了 GGG。∣G∣∣H∣\dfrac{|G|}{|H|}∣H∣∣G∣ 也就是 HHH 本质不同陪集的数量。
正规子群
若 H≤GH\le GH≤G且 ∀a∈G,aHHa\forall a\in G,aHHa∀a∈G,aHHa则称 HHH 是 GGG 的正规子群。平凡子群总是正规子群。
交换群
又称为阿贝尔群简单说就是在满足群基本性质的基础上运算又满足交换律的群。 交换群的所有子群都是正规子群。
商群
设 HHH 是 GGG 的正规子群定义 G/H{gH,g∈G}G/H\{gH,g\in G\}G/H{gH,g∈G}。 商群可以理解为一种划分由拉格朗日定理G/HG/HG/H 由 ∣G∣∣H∣\dfrac{|G|}{|H|}∣H∣∣G∣ 个大小为 ∣H∣|H|∣H∣互不相交的群组成。
阶
群 GGG 中元素 xxx 的阶等于最小的正整数 ddd使得 xdex^dexde有限群中元素的阶一定存在。 有限群的阶定义为群内元素的个数无限群的阶规定为 000。 阶的一些性质 群 GGG 中元素 xxx 的阶整除 GGG 的阶。 构造一个 GGG 的子群 H{e,x,x2,...,xd−1}H\{e,x,x^2,...,x^{d-1}\}H{e,x,x2,...,xd−1}∣H∣d|H|d∣H∣d由拉格朗日定理 ddd 整除 ∣G∣|G|∣G∣。 若 GGG 中两个元素 a,ba,ba,b 的阶 m,nm,nm,n 互素则 asbte⇒asebtea^s b^te\Rightarrow a^se\b^teasbte⇒asebte。 由条件有 asb−ta^sb^{-t}asb−t同时 mmm 次方b−tmasm(am)seb^{-tm}a^{sm}(a^{m})^seb−tmasm(am)se由于 gcd(m,n)1\gcd(m,n)1gcd(m,n)1就有 b−teb^{-t}eb−te即 bteb^tebte。asea^sease 同理。 若 g1,g2∈Gg1,g2\in Gg1,g2∈G 的阶分别为 d1,d2d1,d2d1,d2则存在一个元素 g∈Gg\in Gg∈G其阶为 lcm(d1,d2)lcm(d1,d2)lcm(d1,d2)。 设 gcd(d1,d2)d\gcd(d1,d2)dgcd(d1,d2)d。考虑元素 g1d⋅g2g1^d\cdot g2g1d⋅g2。其中 g1dg1^dg1d 和 g2g2g2 的阶数互质。由性质二g1d⋅g2g1^d\cdot g2g1d⋅g2 的阶数就是 d1d×d2lcm(d1,d2)\dfrac{d1}{d}\times d2lcm(d1,d2)dd1×d2lcm(d1,d2)。
置换
定义
有限集合到自身的双射即一一对应称为置换。 可以表示为(1,2,3,…,na1,a2,a3,…,an)\begin{pmatrix}1,2,3,\dots,n\\a_1,a_2,a_3,\dots,a_n\end{pmatrix}(1,2,3,…,na1,a2,a3,…,an)表示把第 aia_iai 个元素映射到位置 iii。在第一行为 1,2,3...1,2,3...1,2,3... 时可以省去第一行。 置换 fff 作用与状态 aaa写作 f∗af*af∗a。这个写法似乎各处并不一样 例 (3,2,1,4)∗(a,b,c,d)(c,b,a,d)(3,2,1,4)*(a,b,c,d)(c,b,a,d)(3,2,1,4)∗(a,b,c,d)(c,b,a,d)
置换的乘法
定义 f1∗f2f1*f2f1∗f2 表示先进行 f2f2f2再进行 f1f1f1。 (a1,a2,...,an)∗(b1,b2,...,bn)(ba1,ba2,...,ban)(a_1,a_2,...,a_n)*(b_1,b_2,...,b_n)(b_{a_1},b_{a_2},...,b_{a_n})(a1,a2,...,an)∗(b1,b2,...,bn)(ba1,ba2,...,ban) 例 (3,2,1,4)∗(2,1,3,4)(3,1,2,4)(3,2,1,4)*(2,1,3,4)(3,1,2,4)(3,2,1,4)∗(2,1,3,4)(3,1,2,4)
循环
如果一个置换形如 (a1,a2,a3,...,an−1,ana2,a3,a4,...,an,a1)\begin{pmatrix}a_1,a_2,a_3,...,a_{n-1},a_n\\a_2,a_3,a_4,...,a_n,a_1\end{pmatrix}(a1,a2,a3,...,an−1,ana2,a3,a4,...,an,a1)则称其为一个循环。 如果两个循环不包含相同元素则称它们为不相交的。 任何置换都由若干个不相交置换的乘积。
置换群
元素个数为 nnn 的所有排列的集合 NNN 与置换乘法组成一个群 (N,∗)(N,*)(N,∗)。 其子群称为置换群。 其中的单位元又叫做恒等置换 III。
群作用
对于一个群 (G,∗)(G,*)(G,∗) 和集合 NNN给出一个二元函数 φ(g,n)\varphi(g,n)φ(g,n)满足如下性质
φ(e,n)n\varphi(e,n)nφ(e,n)nφ(a,φ(b,n))φ(a∗b,n)\varphi(a,\varphi(b,n))\varphi(a*b,n)φ(a,φ(b,n))φ(a∗b,n)
则称群 GGG 作用于集合 NNN。 如果你没明白这个定义想干什么可以把 GGG 想成置换群把 NNN 想成状态
等价类
若一个状态可以通过置换群内的某个置换到达另一个状态则称它们属于同一个等价类也就是本质相同。
不动点
若 f∗xxf*xxf∗xx则称 xxx 为 fff 的一个不动点。
Burnside引理
重头戏来勒
内容
对于作用于集合 XXX 的群 GGG。 设 X/GX/GX/G 为在 GGG 作用下等价类的集合。这里虽然并不满足商群的定义但是写成形式化语言后长的非常像即 {Gx,x∈X}\{Gx,x\in X\}{Gx,x∈X} 则有 ∣X/G∣1∣G∣∑g∈G∣Xg∣|X/G|\frac{1}{|G|}\sum_{g\in G}|X^g|∣X/G∣∣G∣1g∈G∑∣Xg∣ 其中 Xg{x∣g∗xx,x∈X}X^g\{x|g*xx,x\in X\}Xg{x∣g∗xx,x∈X}
证明
法1 轨道-稳定子定理
对于一个置换群 GGG 和状态 xxx定义 G(x){g∗x,g∈G}G(x)\{g*x,g\in G\}G(x){g∗x,g∈G} 为 xxx 的轨道其实就是等价类Gx{g∣g∗xx,g∈G}G^x\{g|g*xx,g\in G\}Gx{g∣g∗xx,g∈G} 为 xxx 的稳定子其实就是不动点。 轨道-稳定子定理∣G∣∣Gx∣∣G(x)∣|G||G^x||G(x)|∣G∣∣Gx∣∣G(x)∣ 证明 首先GxG^xGx 是一个 GGG 的子群我们按照定义逐条验证
封闭性f∗xx,g∗xx→(f∗g)∗xf∗(g∗x)xf*xx,g*xx\to(f*g)*xf*(g*x)xf∗xx,g∗xx→(f∗g)∗xf∗(g∗x)x即 f∈Gx,g∈Gx→f∗g∈Gxf\in G^x,g\in G^x\to f*g\in G^xf∈Gx,g∈Gx→f∗g∈Gx。结合律置换乘法本身始终有结合律。单位元显然 e∗xxe*xxe∗xx。逆元f∗xx→xf−1∗xf*xx\to xf^{-1}*xf∗xx→xf−1∗x
既然是子群根据拉格朗日定理就有 ∣G∣∣Gx∣∣G:Gx∣|G||G^x||G:G^x|∣G∣∣Gx∣∣G:Gx∣ 其中 ∣G:Gx∣|G:G^x|∣G:Gx∣ 表示 GxG^xGx 在 GGG 中本质不同的陪集数量。 那么现在只需要证明 ∣G:Gx∣∣G(x)∣|G:G^x||G(x)|∣G:Gx∣∣G(x)∣。
尝试在 GxG^xGx 的陪集和 xxx 的轨道之间建立双射关系。
若 f∗xg∗xf*xg*xf∗xg∗x两个置换在 xxx 轨道的同一位置则有 (g−1∗f)∗xx(g^{-1}*f)*xx(g−1∗f)∗xx即 g−1∗f∈Gxg^{-1}*f\in G^xg−1∗f∈Gx由前面陪集的性质四也就有 fGxgGxfG^xgG^xfGxgGx。若 fGxgGxfG^xgG^xfGxgGx两个置换生成的陪集相同由于第一条使用的均为充要条件反过来推依然成立也就有 f∗xg∗xf*xg*xf∗xg∗x。
所以我们得到如果轨道相同则陪集相同如果陪集相同则轨道相同建立起了双射关系命题得证。
有了轨道-稳定子定理证明 Burnside 引理就不难了。 ∑g∈GXg∑x∈XGx∑x∈X∣G∣∣G(x)∣∣G∣∑x∈X1G(x)∣G∣∑Y∈X/G∑x∈Y1∣Y∣∣G∣∑Y∈X/G1∣G∣∣X/G∣\sum_{g\in G}X^g\sum_{x\in X}G^x\\\sum_{x\in X}\frac{|G|}{|G(x)|}\\|G|\sum_{x\in X}\frac{1}{G(x)}\\|G|\sum_{Y\in X/G}\sum_{x\in Y}\frac{1}{|Y|}\\|G|\sum_{Y\in X/G}1\\|G||X/G|g∈G∑Xgx∈X∑Gxx∈X∑∣G(x)∣∣G∣∣G∣x∈X∑G(x)1∣G∣Y∈X/G∑x∈Y∑∣Y∣1∣G∣Y∈X/G∑1∣G∣∣X/G∣ 得证。
法2
一本通上的魔法操作。 被中间一大堆莫名其妙啰哩啰嗦的过程以及横空出世的“显然”整蒙了好久 但看明白了确实还是挺优雅的。
考虑一个大小为 kkk 的等价类 SSS。 从里面任选一个状态 a1a_1a1。 那么设 g1g_1g1 为满足 g1∗a1a1g_1*a_1a_1g1∗a1a1 的任意一个置换。必然存在至少可以是恒等置换 III 那么对于 SSS 中任意元素 aia_iai设 fif_ifi 为满足 fi∗a1aif_i*a_1a_ifi∗a1ai 的任意一个置换那么 Wi{g∣g∗a1ai,g∈G}W_i\{g|g*a_1a_i,g\in G\}Wi{g∣g∗a1ai,g∈G} 也就可以写成 {fi,fi∗g1,fi∗g12,...,fi∗g1d−1}\{f_i,f_i*g_1,f_i*g_1^2,...,f_i*g_1^{d-1}\}{fi,fi∗g1,fi∗g12,...,fi∗g1d−1}其中 ddd 为 g1g_1g1 的阶数。 那么可以看出所有的 ∣Wi∣|W_i|∣Wi∣ 都是相等的且由于 WiW_iWi 必然互不相交并集为全集就有 ∣W1∣∣W2∣...∣Wk∣∣G∣k|W_1||W_2|...|W_k|\dfrac{|G|}{k}∣W1∣∣W2∣...∣Wk∣k∣G∣。 也就是说对于 SSS 中每个元素 aia_iaiGai{g∣g∗aiai,g∈G}G^{a_i}\{g|g*a_ia_i,g\in G\}Gai{g∣g∗aiai,g∈G} 的大小均为 ∣G∣k\dfrac{|G|}{k}k∣G∣SSS 中一共有 kkk 个元素那么总共就贡献了 ∣G∣|G|∣G∣ 个不动点。 每个等价类都贡献 ∣G∣|G|∣G∣ 个不动点那么 Burnside 引理中的式子也就自然可得了。
Polya 定理
个人感觉 Polya 定理根本不配叫个定理 Burnside 给了我们计算本质不同方案的公式 ∣X/G∣1∣G∣∑g∈G∣Xg∣|X/G|\frac{1}{|G|}\sum_{g\in G}|X^g|∣X/G∣∣G∣1g∈G∑∣Xg∣ 而 Polya 的用途就是快速计算 Burnside 的式子。 关键就是计算这个 ∣Xg∣|X^g|∣Xg∣。 以染色问题为例假设每个点可以染 mmm 中颜色或者说a1...na_{1...n}a1...n 都可以在 [1,m][1,m][1,m] 中取值。 对于一个置换 ggg设其循环的个数为 c(g)c(g)c(g)要想成为不动点显然每个循环的颜色必须相同而不同循环的颜色相互独立因此不动点个数为 mc(g)m^{c(g)}mc(g)。 那么 Burnside 的式子也就可以写为 ∣X/G∣1∣G∣∑g∈Gmc(g)|X/G|\frac{1}{|G|}\sum_{g\in G}m^{c(g)}∣X/G∣∣G∣1g∈G∑mc(g) 然后嘞 没了。 没了 没了 Polya 就这 Polya 就这 你上你也行 个人实在感觉这个东西和 Burnside 引理放在一起是对 Burnside 的侮辱… 也可能是我对 Polya 的理解还不太到位吧。
