置换群及其性质

对称群及其性质

设$X=\{x_1,\ x_2, \ \cdots,\ x_n\}$, 对于$\sigma\in \mathfrak{S}(X)$, 可将其表示为

$\sigma=\left[ \begin{array}{cc} x_1 & x_2 &\cdots &x_n\\ x_{i_1} &x_{i_2} &\cdots &x_{i_n}\end{array}\right]=\left[ \begin{array}{cc} x_1 & x_2 &\cdots &x_n\\ \sigma(x_{1}) &\sigma(x_{2}) &\cdots &\sigma(x_{n})\end{array}\right]$

其含义是$\sigma(x_k)=x_{i_k},\ k=1,\ 2,\ \cdots,\ n$，也就是说，置换$\sigma$将元素$x_k$映射到$x_{i_k}$，其中$i_1,\ i_2,\ \cdots,\ i_n$是集合$\mathbb{Z_n^+}$的一个排列。

约定：

1. $n$元集$X=\mathbb{Z_n^+}$;
2. $\mathbb{Z_n^+}$上的全体置换的集合$\mathfrak{S}(\mathbb{Z_n^+})$表示为$\mathcal{S}_n$;

对于$\forall \sigma,\ \tau\in \mathcal{S_n},\ \mathcal{S}_n$上的二元运算“$\circ$”定义为：$(\sigma\circ\tau)(x)=\sigma(\tau(x)),\ x\in\mathbb{Z_n^+}$.

易知$(\mathcal{S}_n,\ \circ)$是一个群，称为$n$元集$\mathbb{Z_n^+}$上的对称群，$\mathcal{S_n}$的子群称为$n$元集$\mathbb{Z_n^+}$上的置换群.

群$(\mathcal{S}_n,\ \circ)$的单位元$\iota$是集合$\mathbb{Z}_n^+$上的恒等置换：

$\iota=\left[ \begin{array}{cc} 1 & 2 &\cdots &n\\ {1} &{2} &\cdots &{n}\end{array}\right]=(1)(2)\cdots(n)$

置换的合成运算($\sigma\circ\tau$)

先将两行矩阵表示的$\sigma$作列交换，使得$\sigma$的第一行与$\tau$的第二行元素排列完全一致，然后由$\tau$的第一行与$\sigma$的第二行构成的矩阵就是$\sigma\tau$.

逆置换

先进行列交换，后进行行交换。

对于一个给定的置换$\sigma$，如果已经得到了$\sigma$的循环分解式，只需要将$\sigma$的循环分解式中每个循环反转，即得其逆置换$\sigma^{-1}$.

置换$\sigma$的格式$\mathrm{typ}(\sigma)$

令$\lambda_k$为置换$\sigma$的循环分解式中长度为$k$的循环的个数，则：

$\mathrm{typ}(\sigma)=(\lambda_1,\ \lambda_2,\ ,\cdots,\ \lambda_n)\in \Lambda_n$.

奇偶置换

可表为奇数个对换乘积的置换：奇置换

可表为偶数个对换乘积的置换：偶置换

交错群

$\mathcal{S_n}$中全体偶置换的集合$\mathcal{A_n}$：交错群, 且有$|\mathcal{A_n}|=|\mathcal{S_n}|/2$.

定理

设$\sigma\in \mathcal{S}_n$, $C_k$是$\sigma$的循环分解式中第$k$个循环（$C_k$也表示第$k$个循环中所包含的元素之集），$|C_k|$表示循环$C_k$的长度，则有：

$\sigma^{|C_k|}(x)=x,\ \forall x\in C_k$

推论

1. 设$\sigma\in \mathcal{S}_n$, $C_k$是$\sigma$的循环分解式中第$k$个循环（$C_k$也表示第$k$个循环中所包含的元素之集），则对于$\forall l\in \mathbb{Z}^+$有$\sigma^l\big |_{C_k}=\sigma^{l \mod |C_k|}\big |_{C_k}$.
2. 设$\sigma=C_1C_2\cdots C_m\in\mathcal{S}_n$, 并令$\lambda$是$\sigma$的各循环长度的最小公倍数，即$\lambda=\mathrm{lcm} (|C_1,\ |C_2|,\ \cdots,\ |C_m|)$, 则有$\sigma^\lambda=\iota$.

定理

置换与其逆置换具有相同的格式，即$\forall\ \sigma\in\mathcal{S_n}$, 有$\mathrm{typ}(\sigma)=\mathrm{typ}(\sigma^{-1})$.

共轭置换

对于$\forall\ \sigma,\ \tau\in \mathcal{S_n}$，如果$\exists \pi\in \mathcal{S_n}$，使得$\sigma=\pi\tau\pi^{-1}$，则称置换$\sigma$和$\tau$是互相共轭的置换。

定理1

互相共轭与相同格式等价，即对$\forall \ \sigma,\ \tau\in \mathcal{S_n},\ \sigma$和$\tau$共轭，当且仅当$\mathrm{typ}(\sigma)=\mathrm{typ}(\tau)$.

定理2

共轭类及其元素的性质

设$\mathcal{S_n}$是$n$元集$\mathbb{Z_n^+}$上的对称群，则有：

1. $\mathcal{S_n}$中同一共轭类的每个元素具有同样的周期；
2. 如果$\sigma$与$\tau$共轭，则$\sigma^k$与$\tau^k$共轭;
3. 单位元$\iota$（恒等置换）所在的共轭类为$\{\iota\}$;
4. $\mathcal{S_n}$中不同共轭类的个数等于正整数$n$的拆分数$p(n)$，也等于方程$\lambda_1+2\lambda_2+\cdots+n\lambda_n$非负整数解的个数$|\Lambda_n|$.

稳定子、轨道

稳定子

设$G$是$n$元集$X$上的置换群，对于给定的$x\in X$, 令

$\mathrm{Sta}(x)=\{\sigma|\sigma\in G,\ \sigma(x)=x\}$

则称$\mathrm{Sta}(x)$是$x$的不动置换类或$x$的稳定子。

定理

稳定子是子群.

设$G$是$n$元集$X$上的置换群，则对于$\forall x\in X,\ \mathrm{Sta}(x)\leqslant G$.

置换群导出的二元关系

$R=\left\{(a,\ b)|a,\ b\in X且\exists \ \sigma\in G使得\sigma(a)=b \right\}$

定理

置换群导出的二元关系是等价关系。

记：$n$元集$X$上由置换群$G$导出的等价关系$R$：$\mathbf{\stackrel{G}{\thicksim}}$.

轨道

$X$ 上由等价关系$\mathbf{\stackrel{G}{\thicksim}}$所确定的等价类称为置换群$G$的轨道。

对$\forall x\in X$, $x$所在的等价类或轨道，记为$\mathbf{Orb(x)}$.

轨道集

设$G$是$n$元集$X$上的置换群，则$G$的所有不同轨道形成的集合称为$G$的轨道集，记为$X/G$，即$X/G=\{\mathrm{Orb(x)|x\in X}\}$.

$G$的轨道集是$X$的子集，且有：$X=\bigcup_{\mathrm{Orb}(x)\in X/G}\mathrm{Orb}(x)$.

轨道集是集合$X$的一个无序拆分，即$X/G\in \Pi(X)$.

定理1

设$G$是$n$元集$X$上的置换群，$x\in X$,$\mathrm{Orb}(x)$是$G$的一条包含$x$的轨道，则对$\forall a,\ b\in \mathrm{Orb}(x)$, 有$|\mathrm{Sta}(a)|=|\mathrm{Sta}(b)|$.

定理2

$[G:\mathrm{Sta}(x)]=|\mathrm{Orb}(x)|$

$|G|=|\mathrm{Sta}(x)|\ |\mathrm{Orb}(x)|$

有限群的Cayley表示

设$(G,\ \ast)$是一个有限群，则其与$G$上的一个置换群$(H,\ \circ)$同构。