参考Introduction to graph theroy
群的公理与基本例子
核心定义与公理
一个 二元结构 (binary structure) 是一对 (G,∗)(G, *)，其中：
- 是一个集合。
- 是定义在 上的二元运算（binary operation）。
群 是满足下列公理的二元结构 (G,∗)：
| 公理 | 内容 |
|---|---|
| 闭包 (Closure) | ，有 （运算结果仍在集合内） |
| 结合律 (Associativity) | ， |
| 单位元 (Identity) | 存在 ，使得 ; |
| 逆元 (Inverse) | 对每个 ，存在，使得 |
同构与同态 (Homomorphism & Isomorphism)
- 同态 (Homomorphism)：如果 与 是两个二元结构／群，一个函数 是同态，如果对所有 ，有 即运算“被保留/对应”。
- 同构 (Isomorphism)：同态之外还要是双射（bijective/invertible）。如果存在一个这样的同构 ，我们写 。同构的群是“结构上一样”的，只是名字／表示方式可能不同。
- 结构性属性 (Structural properties)：在同构关系下不变的特性，例如群的阶（元素个数，order）、是否交换群、结合律、是否有某种特性……这些都是结构性属性。查看同构有助于认出两个看起来不一样的群其实本质上是一样的。
图论基础
定义 A.2（群在集合上的作用）。设 是一个带有对称群 的集合。群 在集合 上的（左）群作用是一个映射： 该映射与群合成运算和单位元 兼容，使得以下性质成立：
\begin{aligned} \text{单位元：} &\quad e \triangleright \mathbf{x} = \mathbf{x}, \quad \forall \mathbf{x} \in \mathcal{X} \\ \text{结合律：} &\quad (g_1 \circ g_2) \triangleright \mathbf{x} = g_1 \triangleright (g_2 \triangleright \mathbf{x}), \quad \forall g_1, g_2 \in \mathbb{G}, \forall \mathbf{x} \in \mathcal{X} \end{aligned} $$我们主要研究具有向量空间结构的集合上的对称变换。在大多数实际情况下，群在向量空间上的作用是线性的，允许将对称变换表示为线性可逆映射。一旦选择了空间的基，这些映射可以用矩阵形式表示。 **定义 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。每当用 $(\triangleright_{\mathcal{X}})$ 和 $(\triangleright_{\mathcal{Y}})$ 表示群作用时，我们将使用符号 $\triangleright_{\mathcal{X} \otimes \mathcal{Y}}$ 来表示在张量积空间 $\mathcal{X} \otimes \mathcal{Y}$ 上的群作用。使得： $$ \begin{aligned} \triangleright_{\mathcal{X} \otimes \mathcal{Y}}: \quad \mathbb{G} \times (\mathcal{X} \otimes \mathcal{Y}) \quad &\longrightarrow \quad (\mathcal{X} \otimes \mathcal{Y}) \\ (g, \mathbf{x} \otimes \mathbf{y}) \quad &\longrightarrow \quad [\rho_{\mathcal{X}}(g) \otimes \rho_{\mathcal{Y}}(g)](\mathbf{x} \otimes \mathbf{y}) \end{aligned} $$ **定义 A.5（$\mathbb{G}$-等变和 $\mathbb{G}$-不变映射）**。设 $\mathcal{X}$ 和 $\mathcal{Y}$ 是具有相同对称群 $\mathbb{G}$ 的两个向量空间，分别带有群作用 $\triangleright_{\mathcal{X}}$ 和 $\triangleright_{\mathcal{Y}}$。一个映射 $f: \mathcal{X} \mapsto \mathcal{Y}$ 被称为 $\mathbb{G}$-等变的，如果它与群作用可交换，使得： $$ \begin{aligned} g \triangleright_{\mathcal{Y}} \mathbf{y} &= g \triangleright_{\mathcal{Y}} f(\mathbf{x}) = f(g \triangleright_{\mathcal{X}} \mathbf{x}), \quad \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{aligned} \quad \iff \quad \begin{aligned} \mathcal{X} &\xrightarrow{\triangleright_{\mathcal{X}}} \mathcal{X} \\ &\downarrow f \qquad \downarrow f \\ \mathcal{Y} &\xrightarrow{\triangleright_{\mathcal{Y}}} \mathcal{Y} \end{aligned} $$ $\mathbb{G}$-等变映射的一个特例是 $\mathbb{G}$-不变映射，它们与群作用可交换，并且具有平凡的输出群作用 $\triangleright_{\mathcal{Y}}$，使得 $\rho_{\mathcal{Y}}(g) = \mathbf{I}$ 对所有 $g \in \mathbb{G}$ 成立。即： $$ \begin{aligned} \mathbf{y} &= g \triangleright_{\mathcal{Y}} f(\mathbf{x}) = f(g \triangleright_{\mathcal{X}} \mathbf{x}), \quad \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{aligned} \quad \iff \quad \begin{aligned} \mathcal{X} &\xrightarrow{\triangleright_{\mathcal{X}}} \mathcal{X} \\ &\searrow f \qquad \downarrow f \\ &\mathcal{Y} \xrightarrow{\triangleright_{\mathcal{Y}}} \mathcal{Y} \end{aligned} $$ **定义 B.1（对称 POMDP）**。一个 POMDP $(\mathcal{S}, \mathcal{A}, r, \tau, \rho_0, \gamma, \mathcal{O}, \sigma)$ 具有对称群 $\mathbb{G}$，当状态空间 $\mathcal{S}$ 和动作空间 $\mathcal{A}$ 承认群作用 $(\triangleright_{\mathcal{S}})$ 和 $(\triangleright_{\mathcal{A}})$，且 $(r, \tau, \rho_0)$ 都是 $\mathbb{G}$-不变的。也就是说，对于每一个 $g \in \mathbb{G}$，$s, s' \in \mathcal{S}$，和 $a \in \mathcal{A}$，我们有： $$ \begin{aligned} \tau(g \triangleright_{\mathcal{S}} s' \mid g \triangleright_{\mathcal{S}} s, g \triangleright_{\mathcal{A}} a) &= \tau(s' \mid s, a), \\ \rho_0(g \triangleright_{\mathcal{S}} s) &= \rho_0(s), \\ r(g \triangleright_{\mathcal{S}} s, g \triangleright_{\mathcal{A}} a) &= r(s, a). \end{aligned} $$ 满足方程 (2) 的 POMDP 被约束为具有最优策略和价值函数，它们满足： $$ \begin{aligned} \underbrace{g \triangleright_{\mathcal{A}} \pi^*(\sigma(s))}_{\text{Policy } \mathbb{G}\text{-equivariance}} &= \pi^*(\sigma(g \triangleright_{\mathcal{S}} s)), \\ \underbrace{V^*(\sigma(s))}_{\text{Value function } \mathbb{G}\text{-invariance}} &= V^*(\sigma(g \triangleright_{\mathcal{S}} s)), \end{aligned} \quad \forall s \in \mathcal{S}, \; g \in \mathbb{G}. \quad (\text{参见 [20]}) $$ **命题 B.1（最优性条件 ）**。给定在最优策略 $\pi^*$ 上的 $\mathbb{G}$-等变约束和在最优价值函数 $V^*$ 上的 $\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}$ 和群作用 $\triangleright_{\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{aligned} g \triangleright_{\mathcal{A}} \pi_\theta(\sigma(s)) &= \pi_\theta(g \triangleright_{\mathcal{O}} \sigma(s)) = \pi_\theta(\sigma(g \triangleright_{\mathcal{S}} s)), \\ V_\theta(\sigma(s)) &= V_\theta(g \triangleright_{\mathcal{O}} \sigma(s)) = V_\theta(\sigma(g \triangleright_{\mathcal{S}} s)), \end{aligned} \quad \forall s \in \mathcal{S}, \; g \in \mathbb{G}. $$