算法数学笔记-五、群论入门

标签：入门 #### Hb 算法 群论 子群 集合 陪集 Hg

# 五、群论入门

#### 群的定义

可以理解为： $群G(S, *) = 集合（S）+ 运算（*）$

群的4个条件：
在运算$*$作用下：

1.封闭性 2.存在单位元 3.逆元存在 4.$*$ 运算满足结合律

 

#### 子群与陪集

##### 子群

如果 $H$ 为 $G $ 的一个子集，且（$H$, $*$）满足一个群，则（$H$, $*$）为（$G$, $*$）的一个子群。

##### 陪集

若有$g \in G$

左陪集: $gH\ = g* h\ (h \in H)$

右陪集: $Hg\ = h* g\ (h \in H)$

陪集的性质（以右陪集为例， 左陪集同理）：

1. $\forall g \in G, |H| = |Hg|$
2. $\forall g \in G , g \in Hg$
3. $Hg = H \Longleftrightarrow g \in H$
4. $Ha = Hb \Longleftrightarrow a * b^{-1} \in H$
5. $Ha \cap Hb \not = \emptyset \implies Ha = Hb $
6. $H$ 的全体右陪集的并集为$G$
7. 所有关于$H$的本质不同的陪集构成$G$的划分

$G / H$ 代表$G$的所有左陪集

$[G:H]$ 代表$G$中$H$的本质不同陪集的数量

 

#### 拉格朗日定理

若$G$是有限群:

则$|H|\ \big |\ |G| $，进一步：$|H| * [G:H] = |G|$

 

#### 轨道-稳定化子定理

考虑$G$作用于集合$X$：

轨道：

$x\in X$, 在$G$ 的作用下，$x$ 能到达的元素的集合$G(x)$

稳定化子:

$G^x = \{g\ |\ g\in G, g(x) = x\}$ （可知$G^x$是$G$的一个子群）

使用语言描述，便是群$ G$ 中满足 $g(x)=x$ 的所有元素 $g$ 所构成的集合

轨道-稳定子定理：
$$
|G^x | * |G(x)| = |G|
$$

#### Burnside定理

定义一个置换群$G$, 作用于集合$X$：

等价类:如果$x,y \in X$ 且存在$f \in G$使得$f(x) = y$ , 则$x,y$属于一个等价类

不同等价类的数量：
$$
|X / G| = \frac{1}{|G|} \sum _{g \in G} X^g
$$
$X^g$表示在$g$的作用下不定点的数量，即满足$g(x) = x$的$x $的数量

 

标签：入门,####,Hb,算法,群论,子群,集合,陪集,Hg
From： https://www.cnblogs.com/lyhy/p/16809800.html