算法筆記-群論

• 算法筆記目錄

群

有一個集合 $G$ 和一個二元運算子 $\cdot$，滿足以下條件，就稱 $(G,\cdot)$ 構成一個群：

• 封閉性
  • 對於 $G$ 中的任意兩個元素 $a,b$，都有 $a\cdot b\in G$。
• 結合性
  • 對於 $G$ 中的任意三個元素 $a,b,c$，都有 $a\cdot (b\cdot c)=(a\cdot b)\cdot c$。
• 單位元
  • 對於 $G$ 中的任意元素 $a$，都有存在一個元素 $e$，使得 $a\cdot e=a=e\cdot a$。
• 逆元
  • 對於 $G$ 中的任意元素 $a$，都有存在一個元素 $a^{-1}$，使得 $a\cdot a^{-1}=a^{-1}\cdot a=e$。

以加法為例，$a,b,c \in \mathbb{Z} $，$a+b+c$ 滿足上述條件，因此 $(\mathbb{Z},+)$ 構成一個群。

而因為 $+$ 滿足結合性，所以我們在做運算時不需要加括號，如果 $+$ 運算都與同一元素有關，可以變成乘法，$a+a+a=3a$

• 注意到群沒有必要滿足交換性，而如果群滿足交換性，則稱為交換群或阿貝爾群。

• 加法的逆元是負號，乘法的逆元是倒數。

如果 $G$ 中存在一個元素 $g$ 使得對 $G$ 中的任意元素 $a$ 都有 $a = g^n $，則稱 $(G,\cdot)$ 為循環群，也說 $G$ 由 $g$ 生成、$g$ 是 $G$ 的生成元，記作 $G = \langle g \rangle$，其中 $\langle g \rangle$ 稱為 $g$ 的生成集合(Span)。