【抽象代数】群论
zhouxianzhuo
·
·
算法·理论
前置知识
置换（Permutation）
定义
$$
\sigma=\begin{pmatrix}\alpha_1&\alpha_2&\dots&\alpha_n\\\alpha_{i_1}&\alpha_{i_2}&\dots&\alpha_{i_n}\end{pmatrix}
$$
若首行默认按照自然顺序书写，那么可以省略首行，将置换 $\sigma$ 表示为
$$
\sigma=\sigma(1)\sigma(2)\dots\sigma(n)
$$
其中 $i_1,i_2,\dots,i_n$ 是 $1,2,\dots,n$ 的一个排列，$\alpha_{i_k}$ 是 $\alpha_k$ 在置换 $\sigma$ 下的像。
**注意：置换是将元素 $\alpha_{i_k}$ 映射到元素 $\alpha_k$，而非将元素 $\alpha_k$ 映射到下标为 $\alpha_{i_k}$ 的位置。简单来说，就是将原序列的元素 $\alpha_k$ 替换成元素 $\alpha_{i_k}$。**
---
### 复合
置换的复合常常被称作置换的乘法。
给定两个置换
$$
\sigma=\begin{pmatrix}\alpha_1&\alpha_2&\dots&\alpha_n\\\alpha_{p_1}&\alpha_{p_2}&\dots&\alpha_{p_n}\end{pmatrix},\tau=\begin{pmatrix}\alpha_{p_1}&\alpha_{p_2}&\dots&\alpha_{p_n}\\\alpha_{q_1}&\alpha_{q_2}&\dots&\alpha_{q_n}\end{pmatrix}
$$
那么它们的乘积为
$$
\tau\circ\sigma=\begin{pmatrix}\alpha_{1}&\alpha_{2}&\dots&\alpha_{n}\\\alpha_{q_1}&\alpha_{q_2}&\dots&\alpha_{q_n}\end{pmatrix}
$$
即 $(\tau\circ\sigma)(x)=\tau(\sigma(x))$。
注意置换的复合的运算顺序是自右向左。
---
### 阶
置换的阶指满足如下条件的最小正整数 $a$：重复该置换 $a$ 次后，所有的元素都回到了原位。
即
$$
\mathrm{ord}_\sigma=\min\{a\in N_+:\sigma^a=\begin{pmatrix}\alpha_1&\alpha_2&\dots&\alpha_n\\\alpha_1&\alpha_2&\dots&\alpha_n\end{pmatrix}\}
$$
---
### 逆置换
给定置换
$$
\sigma=\begin{pmatrix}\alpha_1&\alpha_2&\dots&\alpha_n\\\alpha_{i_1}&\alpha_{i_2}&\dots&\alpha_{i_n}\end{pmatrix}
$$
定义它的逆置换为
$$
\sigma^{-1}=\begin{pmatrix}\alpha_{i_1}&\alpha_{i_2}&\dots&\alpha_{i_n}\\\alpha_1&\alpha_2&\dots&\alpha_n\end{pmatrix}
$$
逆置换满足
$$
\sigma\circ\sigma^{-1}=\begin{pmatrix}\alpha_1&\alpha_2&\dots&\alpha_n\\\alpha_1&\alpha_2&\dots&\alpha_n\end{pmatrix}
$$
---
# 群的基本概念
## 群（Group）
### 定义
设 $G$ 是一个非空集合，$\cdot$ 是一个二元运算，如果满足以下条件：
1. 封闭性：对于任意 $a,b\in G$，满足 $a\cdot b\in G$。
2. 结合律成立：对于任意 $a,b,c\in G$，满足 $(a\cdot b)\cdot c=a\cdot (b\cdot c)$。
3. 单位元存在：存在唯一元素 $e\in G$，使得对于任意 $a\in G$，满足 $e\cdot a=a\cdot e=a$。
4. 逆元存在：对于任意 $a\in G$，存在唯一 $a^{-1}\in G$，使得 $a\cdot a^{-1}=a^{-1}\cdot a=e$。
则称 $G$ 对 $\cdot$ 构成一个群，记作 $(G,\cdot)$。
若群 $(G,\cdot)$ 的集合元素个数有限，则称其为有限群，否则称其为无限群。
---
### 阶
有限群的集合元素个数称为有限群的阶。
---
### 运算
设有群 $(G,\cdot)$。
对于 $g\in G$ 以及 $G$ 的子集 $H$，定义 $g\cdot H=\{g\cdot h|h\in H\}$，$H\cdot g=\{h\cdot g|h\in H\}$。
对于 $G$ 的子集 $A,B$，定义 $A\cdot B=\{a\cdot b|a\in A,b\in B\}$。
对于 $G$ 的子集 $H$，定义 $H^{-1}=\{h^{-1}|h\in H\}$。
---
## 子群（Subgroup）
### 定义
设有群 $(G,\cdot)$。
对于 $G$ 的子集 $H$，若 $(H,\cdot)$ 为群，则称 $(H,\cdot)$ 为 $(G,\cdot)$ 的子群，记作 $H\le G$。
对于 $G$ 的真子集 $H$，若 $(H,\cdot)$ 为群，则称 $(H,\cdot)$ 为 $(G,\cdot)$ 的真子群，记作 $H<G$。
---
## 对称群（Symmetric Group）
### 定义
设 $G$ 为所有 $n$ 元置换构成的集合，则 $G$ 对置换的复合 $\circ$ 构成对称群 $(G,\circ)$，记作 $S_G$。
对称群 $S_G$ 满足群的定义：
1. 封闭性：两个 $n$ 元置换的复合仍是一个 $n$ 元置换。
2. 结合律成立：函数的复合满足结合律。
3. 单位元存在：存在恒等置换 $e=\begin{pmatrix}1&2&\dots&n\\1&2&\dots&n\end{pmatrix}$，使得对于任意 $n$ 元置换 $\sigma$，满足 $e\circ \sigma=\sigma\circ e=\sigma$。
4. 逆元存在：任意一个置换都存在逆置换。
---
### 性质
对称群 $S_G$ 是有限群，阶为 $n!$。
---
## 置换群（Permutation Group）