群论概述

参考Introduction to graph theroy

群的公理与基本例子

核心定义与公理

一个 二元结构 (binary structure) 是一对 (G,∗)(G, *)，其中：

• $G$ 是一个集合。
• $\ast$ 是定义在 $G\times G$ 上的二元运算（binary operation）。

群 是满足下列公理的二元结构 (G,∗)：

公理	内容
闭包 (Closure)	$\forall x,y\in G$，有 $x\ast y\in G$（运算结果仍在集合内）
结合律 (Associativity)	$\forall x,y,z\in G$，$(x\ast y)\ast z=x\ast (y\ast z)$
单位元 (Identity)	存在 $e\in G$，使得 $\forall x\in G,$; $e\ast x=x\ast e=x$
逆元 (Inverse)	对每个 $x\in G$，存在$y\in G$，使得 $x\ast y=y\ast x=e$

同构与同态 (Homomorphism & Isomorphism)

• 同态 (Homomorphism)：如果 $(G,\ast )$ 与 $(H,\star )$ 是两个二元结构／群，一个函数 $\phi :G\to H$ 是同态，如果对所有 $x,y\in G$，有 $\phi (x\ast y)=\phi (x)\star \phi (y)$即运算“被保留/对应”。
• 同构 (Isomorphism)：同态之外还要是双射（bijective/invertible）。如果存在一个这样的同构 $\phi :G\to H$，我们写 $G\cong H$。同构的群是“结构上一样”的，只是名字／表示方式可能不同。
• 结构性属性 (Structural properties)：在同构关系下不变的特性，例如群的阶（元素个数，order）、是否交换群、结合律、是否有某种特性……这些都是结构性属性。查看同构有助于认出两个看起来不一样的群其实本质上是一样的。

图论基础

定义 A.2（群在集合上的作用）。设 $\mathcal{X}$ 是一个带有对称群 $\mathbb{G}$ 的集合。群 $\mathbb{G}$ 在集合 $\mathcal{X}$ 上的（左）群作用是一个映射：

$$\begin{array}{rl}(▹):\mathbb{G}\times \mathcal{X}& ⟶\mathcal{X}\\ (g,\mathbf{x})& ⟶g▹\mathbf{x}\end{array}$$

该映射与群合成运算和单位元 $e\in \mathbb{G}$ 兼容，使得以下性质成立：

$$\begin{array}{rl}\text{单位元：}& e▹\mathbf{x}=\mathbf{x},\forall \mathbf{x}\in \mathcal{X}\\ \text{结合律：}& (g_1\circ g_2)▹\mathbf{x}=g_1▹(g_2▹\mathbf{x}),\forall g_1,g_2\in \mathbb{G},\forall \mathbf{x}\in \mathcal{X}\end{array}$$

我们主要研究具有向量空间结构的集合上的对称变换。在大多数实际情况下，群在向量空间上的作用是线性的，允许将对称变换表示为线性可逆映射。一旦选择了空间的基，这些映射可以用矩阵形式表示。

定义 A.3（线性群表示）。设 $\mathcal{X}$ 是一个带有对称群 $\mathbb{G}$ 的向量空间。$\mathbb{G}$ 在 $\mathcal{X}$ 上的一个线性表示是一个映射，记为 ${\rho }_{\mathcal{X}}$，它在对称变换和 $\mathcal{X}$ 上的可逆线性映射之间建立联系（即，一般线性群 $\mathbb{GL}(\mathcal{X})$ 的元素）：

\begin{aligned} \rho_{\mathcal{X}}: \quad \mathbb{G} \quad &\longrightarrow \quad \mathbb{GL}(\mathcal{X})\\ g \quad &\longrightarrow \quad \rho_{\mathcal{X}}(g), \end{aligned}$$ 使得以下性质成立：

\begin{aligned} \text{合成：} &\quad \rho_{\mathcal{X}}(g_1 \circ g_2) = \rho_{\mathcal{X}}(g_1) \rho_{\mathcal{X}}(g_2), \quad \forall g_1, g_2 \in \mathbb{G}, \ \text{逆元：} &\quad \rho_{\mathcal{X}}(g^{-1}) = \rho_{\mathcal{X}}(g)^{-1}, \quad \forall g \in \mathbb{G}. \ \text{单位元：} &\quad \rho_{\mathcal{X}}(g \circ g^{-1}) = \rho_{\mathcal{X}}(e) = \mathbf{I}, \end{aligned}

每当向量空间是有限维的 $|\mathcal{X}| = n < \infty$ 时，线性映射可以以矩阵形式 $\rho_{\mathcal{X}}(g) \in \mathbb{R}^{n \times n}$ 表示，一旦选择了向量空间 $\mathcal{X}$ 的基集 $\mathbb{I}_{\mathcal{X}}$。在这种情况下，方程 (12b) 到 (12d) 展示了对称变换的合成和逆如何分别转化为矩阵乘法和逆。此外，$\rho_{\mathcal{X}}$ 允许将（线性）群作用（定义 A.2）表示为矩阵-向量乘法：

\begin{aligned} (\triangleright): \quad \mathbb{G} \times \mathcal{X} \quad &\longrightarrow \quad \mathcal{X} \ (g, \mathbf{x}) \quad &\longrightarrow \quad g \triangleright \mathbf{x} := \rho_{\mathcal{X}}(g) \mathbf{x} \end{aligned}

**定义 A.4（张量积表示）**。设 $\mathcal{X}$ 和 $\mathcal{Y}$ 是具有共同对称群 $\mathbb{G}$ 的（有限维）向量空间。记 $\rho_{\mathcal{X}}: \mathbb{G} \to \mathbb{GL}(\mathcal{X})$ 和 $\rho_{\mathcal{Y}}: \mathbb{G} \to \mathbb{GL}(\mathcal{Y})$ 为相应的线性表示。张量积表示通过群作用在向量空间上的表示的克罗内克积定义： $$ \begin{aligned} (\rho_{\mathcal{X}} \otimes \rho_{\mathcal{Y}}): \quad \mathbb{G} \quad &\longrightarrow \quad \mathbb{GL}(\mathcal{X} \otimes \mathcal{Y}) \\ g \quad &\longrightarrow \quad \rho_{\mathcal{X}}(g) \otimes \rho_{\mathcal{Y}}(g), \end{aligned}

注释 A.1。每当用 $({▹}_{\mathcal{X}})$ 和 $({▹}_{\mathcal{Y}})$ 表示群作用时，我们将使用符号 ${▹}_{\mathcal{X}\otimes \mathcal{Y}}$ 来表示在张量积空间 $\mathcal{X}\otimes \mathcal{Y}$ 上的群作用。使得：

$$\begin{array}{rl}{▹}_{\mathcal{X}\otimes \mathcal{Y}}:\mathbb{G}\times (\mathcal{X}\otimes \mathcal{Y})& ⟶(\mathcal{X}\otimes \mathcal{Y})\\ (g,\mathbf{x}\otimes \mathbf{y})& ⟶[{\rho }_{\mathcal{X}}(g)\otimes {\rho }_{\mathcal{Y}}(g)](\mathbf{x}\otimes \mathbf{y})\end{array}$$

定义 A.5（$\mathbb{G}$-等变和 $\mathbb{G}$-不变映射）。设 $\mathcal{X}$ 和 $\mathcal{Y}$ 是具有相同对称群 $\mathbb{G}$ 的两个向量空间，分别带有群作用 ${▹}_{\mathcal{X}}$ 和 ${▹}_{\mathcal{Y}}$。一个映射 $f:\mathcal{X}\mapsto \mathcal{Y}$ 被称为 $\mathbb{G}$-等变的，如果它与群作用可交换，使得：

$$\begin{array}{rl}g{▹}_{\mathcal{Y}}\mathbf{y}& =g{▹}_{\mathcal{Y}}f(\mathbf{x})=f(g{▹}_{\mathcal{X}}\mathbf{x}),\forall \mathbf{x}\in \mathcal{X},g\in \mathbb{G}.\\ {\rho }_{\mathcal{Y}}(g)f(\mathbf{x})& =f({\rho }_{\mathcal{X}}(g)\mathbf{x})\end{array}⟺\begin{array}{rl}\mathcal{X}& \stackrel{{▹}_{\mathcal{X}}}{\to }\mathcal{X}\\ & \downarrow f\downarrow f\\ \mathcal{Y}& \stackrel{{▹}_{\mathcal{Y}}}{\to }\mathcal{Y}\end{array}$$

$\mathbb{G}$-等变映射的一个特例是 $\mathbb{G}$-不变映射，它们与群作用可交换，并且具有平凡的输出群作用 ${▹}_{\mathcal{Y}}$，使得 ${\rho }_{\mathcal{Y}}(g)=\mathbf{I}$ 对所有 $g\in \mathbb{G}$ 成立。即：

$$\begin{array}{rl}\mathbf{y}& =g{▹}_{\mathcal{Y}}f(\mathbf{x})=f(g{▹}_{\mathcal{X}}\mathbf{x}),\forall \mathbf{x}\in \mathcal{X},g\in \mathbb{G}.\\ \mathbf{y}& ={\rho }_{\mathcal{Y}}(g)f(\mathbf{x})=f({\rho }_{\mathcal{X}}(g)\mathbf{x})\end{array}⟺\begin{array}{rl}\mathcal{X}& \stackrel{{▹}_{\mathcal{X}}}{\to }\mathcal{X}\\ & \searrow f\downarrow f\\ & \mathcal{Y}\stackrel{{▹}_{\mathcal{Y}}}{\to }\mathcal{Y}\end{array}$$

定义 B.1（对称 POMDP）。一个 POMDP $(\mathcal{S},\mathcal{A},r,\tau ,{\rho }_0,\gamma ,\mathcal{O},\sigma )$ 具有对称群 $\mathbb{G}$，当状态空间 $\mathcal{S}$ 和动作空间 $\mathcal{A}$ 承认群作用 $({▹}_{\mathcal{S}})$ 和 $({▹}_{\mathcal{A}})$，且 $(r,\tau ,{\rho }_0)$ 都是 $\mathbb{G}$-不变的。也就是说，对于每一个 $g\in \mathbb{G}$，$s,s^{\prime }\in \mathcal{S}$，和 $a\in \mathcal{A}$，我们有：

$$\begin{array}{rl}\tau (g{▹}_{\mathcal{S}}{s}^{\prime }\mid g{▹}_{\mathcal{S}}s,g{▹}_{\mathcal{A}}a)& =\tau (s^{\prime }\mid s,a),\\ {\rho }_0(g{▹}_{\mathcal{S}}s)& ={\rho }_0(s),\\ r(g{▹}_{\mathcal{S}}s,g{▹}_{\mathcal{A}}a)& =r(s,a).\end{array}$$

满足方程 (2) 的 POMDP 被约束为具有最优策略和价值函数，它们满足：

$$\begin{array}{rl}\underset{\text{Policy }\mathbb{G}\text{-equivariance}}{\underbrace{g{▹}_{\mathcal{A}}{\pi }^{\ast }(\sigma (s))}}& ={\pi }^{\ast }(\sigma (g{▹}_{\mathcal{S}}s)),\\ \underset{\text{Value function }\mathbb{G}\text{-invariance}}{\underbrace{V^{\ast }(\sigma (s))}}& =V^{\ast }(\sigma (g{▹}_{\mathcal{S}}s)),\end{array}\forall s\in \mathcal{S},g\in \mathbb{G}.(\text{参见 [20]})$$

命题 B.1（最优性条件 ）。给定在最优策略 ${\pi }^{\ast }$ 上的 $\mathbb{G}$-等变约束和在最优价值函数 $V^{\ast }$ 上的 $\mathbb{G}$-不变约束（如方程 (17) 中所示）的对称 POMDP，任何参数化策略 ${\pi }_{\theta }:\mathcal{O}\to \mathcal{A}$ 和价值函数 $V_{\theta }:\mathcal{O}\to \mathbb{R}$ 可以分别被构造为 $\mathbb{G}$-等变和 $\mathbb{G}$-不变的，如果观察函数 $\sigma$ 是 $\mathbb{G}$-等变的，从而赋予观察空间相同的对称群 $\mathbb{G}$ 和群作用 ${▹}_{\mathcal{O}}$。 这是因为两个函数的复合要成为 $\mathbb{G}$-等变（${\pi }_{\theta }\circ \sigma :\mathcal{S}\to \mathcal{A}$）或 $\mathbb{G}$-不变（$V_{\theta }\circ \sigma :\mathcal{S}\to \mathbb{R}$），这两个函数都必须是 $\mathbb{G}$-等变的，使得：

$$\begin{array}{rl}g{▹}_{\mathcal{A}}{\pi }_{\theta }(\sigma (s))& ={\pi }_{\theta }(g{▹}_{\mathcal{O}}\sigma (s))={\pi }_{\theta }(\sigma (g{▹}_{\mathcal{S}}s)),\\ V_{\theta }(\sigma (s))& =V_{\theta }(g{▹}_{\mathcal{O}}\sigma (s))=V_{\theta }(\sigma (g{▹}_{\mathcal{S}}s)),\end{array}\forall s\in \mathcal{S},g\in \mathbb{G}.$$