群论 学习笔记

群论

群的定义

定义:给定集合 $G$ 和集合 $G$ 上的二元运算 $\cdot$,满足以下条件称为群:

1、封闭性(Closure):若 $a,b\in G$,则 $\exists c\in G$,使得 $a\cdot b=c$。

2、结合律(Associativity):对 $\forall a,b,c\in G$,有 $(a\cdot b)\cdot c=a\cdot(b\cdot c)$。由于结合律成立,可记作 $a\cdot b\cdot c$。

3、有单位元(Identity):$\exists e\in G$,满足对 $\forall a\in G$,有 $a\cdot e=e\cdot a=a$。

4、有逆元(Inverse):$\forall a\in G$,满足 $\exists b\in G$,使得 $a\cdot b=b\cdot a=e$,记作 $b=a^{-1}$。

一些概念

群元素的个数是有限的,是有限群;群元素的个数是无限的,是无限群。

有限群 $G$ 的元素个数叫做群的阶,记做 $|G|$。

设 $G$ 是群,$G'$ 是 $G$ 的子集,若在 $G'$ 原有的运算之下也是一个群,则称为 $G$ 的一个子群。

若群 $G$ 的任意两元素 $a,b$ 恒满足 $a\cdot b=b\cdot a$。则称 $G$ 为交换群,又称 Abel 群。

一些性质

单位元唯一:$e_1e_2=e_2=e_1$

左右逆元相等:$ab=e,ca=e\rightarrow b=c$
证明:$cab=(ca)b=eb=b, cab=c(ab)=ce=c \Rightarrow b=c$

消去律成立:$ab=ac\rightarrow b=c$
证明:$ab=ac \Rightarrow a^{-1}ab=a^{-1}ac\Rightarrow b=c$

每个元的逆元唯一:$ab=ba=e,ac=ca=e \rightarrow b=c$
证明:$e=ab=ac\Rightarrow b=c$

多个数乘积的逆元:$(ab\cdots c)^{-1}=c^{-1}\cdots b^{-1}a^{-1}$
证明:$(c^{-1}\cdots b^{-1}a^{-1})(ab\cdots c)=c^{-1}\cdots b^{-1}(a^{-1}a)b\cdots c=\cdots=e$

对于有限群,逆元存在于消去律存在等价。
证明:上面已经证明逆元存在则消去律存在,接下来证明消去律存在则逆元存在。
$ab=ac\rightarrow b=c$,则令 $G'={ax|x\in G}$,根据消去律 $ax$ 两两不同,则 $|G|=|G'|$,而根据封闭性,$G'\subseteq G$,(对有限群)故 $G=G'$,则必然存在 $e\in G'$,即 $\exists x\in G,ax=e$。

对于有限群,若 $a\in G$,则存在最小正整数 $r$,使得 $a^r=e$,且 $a^{-1}=a^{r-1}$。
证明:设 $g=|G|$,则 $a,a^2,\cdots,a^g,a^{g+1}\in G$ 中必有相同项(鸽巢原理)。
设 $a^j=a^k(1\leq j\lt k\leq g+1)$,则 $e=a^{k-j}$(消去律)。令 $r=k-j$,则 $a^r=a^{r-1}a=e$,即 $a^{-1}=a^{r-1}$。
既然存在正整数 $r$ 使得 $a^r=e$,其中必有最小者,不妨仍设为 $r$。
$r$ 称为 $a$ 的阶(和群的阶不同,这是一个元的阶),容易证明 $H={a,a^2,\cdots,a^r=e}$ 在原有运算意义下也是一个群。

置换群

置换

置换:$[1,n]$ 到自身的一一映射称为 $n$ 阶置换,共有 $n!$ 个。$S_n$ 为所有 $n$ 阶置换组成的置换群。

置换群的运算:双射的复合(不满足交换律)。

循环

循环:$p=(a_1,a_2,\cdots,a_n)$ 称为 $n$ 阶循环,$a_1\rightarrow a_2\rightarrow a_3,\cdots\rightarrow a_n\rightarrow a_1$。$p^n=(1)(2)\cdots (n)=e$。

若两个循环无共同文字,称为不相交的,不相交的循环相乘可交换。任一置换可表示成若干不相交循环的乘积。

共轭类

$P=(a_1a_2\cdots a_{k_1})(b_1b_2\cdots b_{k_2})\cdots(h_1h_2\cdots h_{k_l})$,其中 $a,b,\cdots,h$ 都是不相交循环,$k_1+k_2\cdots k_l=n$。设 $k_i=j$ 的出现次数为 $c_j$,用 $(j)^{c_j}$ 表示,$\sum_{j=1}^n j c_j=n$ 则它的格式为 $(1)^{c_1}(2)^{c_2}\cdots (n)^{c_n}$。

共轭类:$S_n$ 中所有相同格式的置换全体构成一个共轭类。

对换

任意循环都可以表示为对换的积:$(1\ 2\cdots n)=(1\ 2)(1\ 3)\cdots (1\ n)$。

每个置换的分解方式不是唯一的,但是表示成对换的个数的奇偶性是唯一的。

陪集

陪集:对于 $G$ 的一个子群 $G'$,它关于 $a\in G$ 的右陪集为 $G'_a={x\cdot a|x\in G'}$,左陪集为 $_aG'={a\cdot x|x\in G'}$。
根据消去律,陪集的元素两两不同,故 $G'$ 每一个陪集的大小都和 $G$ 相等。

方便起见,以下均以右陪集为例,左陪集同理。
一个性质:对于 $a,b\in G$,若 $G'_a \cap G'_b\neq \varnothing$,则 $G'_a=G'_b$。
证明:因为 $G'_a \cap G'_b\neq \varnothing$,所以 $\exists x,y\in G',x\cdot a=y\cdot b$,$y^{-1}\cdot x\cdot a=b$。
对 $\forall z\in G'_b$,设 $z=tb(t\in G')$,则 $z=tb=t\cdot y^{-1}\cdot x\cdot a=(t\cdot y^{-1}\cdot x)\cdot a$,而 $t\cdot y^{-1}\cdot x\in G'$,故 $z\in G'_a$,即 $G'_b\subseteq G'_a$。同理可以证明 $G'_a\subseteq G'_b$,故 $G'_a=G'_b$。

拉格朗日定理

拉格朗日定理(Lagrange's theorem):对任意 $G$ 的一个子群 $G'$,$|G'||G':G|=|G|$($|G':G|$ 表示 $G'$ 在 $G$ 中的陪集个数)。
证明:上面说明了 $G'$ 的陪集的大小都是 $|G'|$,而且任意两个相等或不交。
又因为 $e\in G'\Rightarrow x\in G'_x \Rightarrow \bigcup _{x\in G} G'_x=G$,所以共有 $|G':G|=\frac{|G|}{|G'|}$ 个不同的陪集。
这个定理说明了一个群的子群大小是整除该群大小的。

不动点、轨道和稳定化子

很多概念在中文翻译的描述上有差异,我们主要用不动点/轨道/稳定化子来描述。

设群 $G$ 作用在集合 $X$ 上。对于 $X$ 中的一个元素 $x$,每个 $G$ 中元素 $g$ 都把 $x$ 映射到某个 $g(x)\in X$ 上。

注意,$g(x)$ 表示将 $g$ 作用在 $x$ 上得到的结果。

不动点(fixed point):对于 $X$ 中的一个元素 $x$,如果 $x\in X$ 在任意 $g\in G$ 的作用下都不变,即 $g(x)=x$,那么称 $x$ 为该群作用的一个不动点。不动点集 $X^g={x\in X\mid g(x)=x, \forall g\in G}$。

轨道(orbit):对于 $X$ 中的一个元素 $x$,所有能被映射到的元素 $g(x)$ 构成了 $X$ 的一个子集,称为元素 $x$ 的轨道。$\mathrm{orbit}(x)={g(x)\mid g\in G}$。轨道集合 $X/G$ 为所有不同轨道的集合。
(另外的一种描述,等价类。)

稳定化子(stablizer):对于 $X$ 中的一个元素 $x$,所有满足 $g(x)=x$ 的 $g$ 构成了 $G$ 的一个子群,称为元素 $x$ 的稳定化子。$\mathrm{stab}(x)={g\in G\mid g(x)=x}$。
(另外的一种描述,$k$ 不动置换类:设 $G$ 是 $S_n$ 的一个子群。对于 $k\in [1,n]$,$G$ 中使得 $k$ 元素保持不变的置换全体,称为 $k$ 不动置换类,记作 $Z_k$。)

轨道-稳定化子定理

轨道-稳定化子定理(Orbit-stabilizer theorem):对 $\forall x\in X$,有 $|\mathrm{stab}(x)||\mathrm{orbit}(x)|=|G|$。
证明:首先我们有对于 $\forall x\in X$,满足 $\forall g,h\in G,g(x)=h(x) \Longleftrightarrow g$ 和 $h$ 在稳定化子的同一个左陪集上,证明如下 $g(x)=h(x)\Leftrightarrow (g^{-1}\cdot h)(x)=x\Leftrightarrow g^{-1}\cdot h\in \mathrm{orbit}(x)\Leftrightarrow h\in \ _g\mathrm{orbit}(x)$。
故轨道数量 $|\mathrm{orbit}(x)|$ 就是稳定化子的陪集数量 $|\mathrm{stab(x)}:G|$,根据拉格朗日定理,可以得到 $|\mathrm{stab}(x)||\mathrm{orbit}(x)|=|G|$。

Burnside 引理

伯恩赛德引理(Burnside's lemma):$|X/G|=\frac{1}{|G|}\sum_{g\in G}|X^g|$。轨道数(等价类)数量为所有置换下不动点数量的平均值。
证明:$|X/G|=\sum_{x\in X}\frac{1}{|\mathrm{orbit}(x)|}=\frac{\sum_{x\in X} |\mathrm{stab}(x)|}{|G|}=\frac{\sum_{g\in G} |X^g|}{|G|}$。
解释:第一个等号是,每个 $x$ 出现在大小为 $|\mathrm{orbit}(x)|$ 的轨道,而每个轨道应该被计算恰好一次,相当于其中每个元素贡献 $\frac{1}{|\mathrm{orbit}(x)|}$;第二个等号是轨道-稳定化子定理;第三个等号是两个分子都等于 $x\in X,g\in G,g(x)=x$ 的数量。

Pólya 定理

波利亚计数定理(Pólya enumeration theorem):对于 $n$ 阶置换群 $G$,用 $t$ 种颜色给 $n$ 个位置着色的不同方案数为 $|X/G|=\frac{1}{|G|}\sum_{g\in G}t^{c(g)}$,其中 $c(g)$ 表示置换 $g$ 拆出的不相交循环个数。
证明:只需证明 $|X^g|=t^{c(g)}$。$X^g$ 中的元素在 $g$ 作用下不变,等价于同一个循环上的颜色都相同,而不同循环间独立,故 $|X^g|=t^{c(g)}$。

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇