第 40A 章 积和式 (Permanent)¶
前置：行列式 (Ch03) · 双随机矩阵 (Ch31) · 组合数学基础
本章脉络：从行列式到积和式（去掉符号项） \(\to\) 积和式 (Permanent) 的定义 \(\to\) 与行列式的形式对比与性质差异 \(\to\) 计算复杂性：#P-完全性与 Valiant 定理 \(\to\) Ryser 容斥公式（指数级算法） \(\to\) 双随机矩阵的积和式：van der Waerden 定理（下界） \(\to\) Minc 猜想（上界） \(\to\) 应用：二部图完美匹配计数、统计力学、量子光学（玻色采样）
延伸：积和式是连接代数与组合难题的桥梁；它在形式上只比行列式少了一个“符号”，但这种微小的差异导致了计算复杂性从多项式级到指数级的巨大鸿沟，是理解算子与计数关系的终极课题
如果说行列式是线性代数的“体积”，那么积和式（Permanent）就是线性代数的“计数器”。它在形式上与行列式惊人地相似，但去掉了排列的符号项。这一微小的改动使得积和式不再具有转置不变性（对非方阵而言）或乘法性质，却成为了解决图论中完美匹配计数问题的终极工具。本章将深入这一兼具代数形式与组合难度的领域。
40A.1 定义与形式对比¶
定义 40A.1 (积和式)
\(n\) 阶方阵 \(A\) 的积和式定义为： $\(\operatorname{perm}(A) = \sum_{\sigma \in S_n} a_{1,\sigma(1)} a_{2,\sigma(2)} \cdots a_{n,\sigma(n)}\)$ 对比：行列式 \(\det(A) = \sum \operatorname{sgn}(\sigma) a_{1,\sigma(1)} \cdots a_{n,\sigma(n)}\)。
性质差异
- 非乘法性：\(\operatorname{perm}(AB) \neq \operatorname{perm}(A)\operatorname{perm}(B)\)（这是积和式最严重的代数缺陷）。
- 多重线性：与行列式一样，积和式关于行（或列）是线性的。
- 计算难度：计算积和式是 #P-完全的，这意味着不存在已知的多项式时间算法。
40A.2 van der Waerden 定理与界限¶
定理 40A.1 (van der Waerden 定理)
对于 \(n\) 阶双随机矩阵 \(P\)（元素非负且行/列和为 1）： $\(\operatorname{perm}(P) \ge \frac{n!}{n^n}\)$ 等号成立当且仅当 \(P = J_n/n\)（即所有元素均为 \(1/n\) 的矩阵）。
40A.3 计算技术：Ryser 公式¶
算法 40A.1 (Ryser 公式)
基于容斥原理，积和式可以表示为： $\(\operatorname{perm}(A) = (-1)^n \sum_{S \subseteq \{1,\ldots,n\}} (-1)^{|S|} \prod_{i=1}^n \left( \sum_{j \in S} a_{ij} \right)\)$ 意义：该公式将复杂度从 \(O(n!)\) 降至 \(O(n 2^n)\)，是中等规模矩阵积和式计算的标准方法。
练习题¶
1. [基础] 计算 \(\begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}\) 的积和式。
参考答案
计算步骤： 1. 枚举所有排列：\(\sigma_1 = (1, 2), \sigma_2 = (2, 1)\)。 2. 第一项：\(a_{11}a_{22} = 1 \cdot 4 = 4\)。 3. 第二项：\(a_{12}a_{21} = 2 \cdot 3 = 6\)。 4. 求和：\(4 + 6 = 10\)。 结论：\(\operatorname{perm} = 10\)。（注：行列式为 -2）。
2. [性质] 对于对角阵，其积和式与行列式有什么关系？
参考答案
结论： 对于对角阵，二者相等。 理由：在积和式与行列式的定义式中，非零项只有主对角线对应的一个排列（恒等排列 \(\sigma=id\)）。而恒等排列的符号 \(\operatorname{sgn}(id) = 1\)，故结果均为对角元之积。
3. [二部图] 若 \(A\) 是二部图的 (0,1)-邻接矩阵，\(\operatorname{perm}(A)\) 的物理意义是什么？
参考答案
结论： 它代表该二部图的完美匹配（Perfect Matching）的总数。 理由：积和式中的每一项非零项都对应于从第 \(i\) 行选出一个第 \(\sigma(i)\) 列的元素，这在二部图中恰好对应于一条边。如果整个乘积非零，说明这 \(n\) 条边覆盖了所有顶点且互不冲突。
4. [van der Waerden] 计算 \(2 \times 2\) 全 1 均值阵 \(J_2/2 = \begin{pmatrix} 0.5 & 0.5 \\ 0.5 & 0.5 \end{pmatrix}\) 的积和式，验证下界。
参考答案
计算： \(\operatorname{perm} = 0.5 \cdot 0.5 + 0.5 \cdot 0.5 = 0.25 + 0.25 = 0.5\)。 验证下界：\(n!/n^n = 2!/2^2 = 2/4 = 0.5\)。 结论：等号成立，符合 van der Waerden 定理。
5. [多重线性] 证明：若将矩阵 \(A\) 的第一行乘以标量 \(k\)，则其积和式也变为原来的 \(k\) 倍。
参考答案
证明： 根据定义，\(\operatorname{perm}(A)\) 的每一项乘积中都包含且仅包含来自第一行的一个元素 \(a_{1,\sigma(1)}\)。 若 \(a_{1,j} \to k a_{1,j}\)，则每一项乘积都会带上因子 \(k\)。 由分配律，总和也提取出公因子 \(k\)。
6. [上界] 什么是 Minc 猜想（现为定理）？
参考答案
描述： 对于行和为 \(r_i\) 的 (0,1)-矩阵 \(A\)，其积和式的上界为： $\(\operatorname{perm}(A) \le \prod_{i=1}^n (r_i !)^{1/r_i}\)$ 这限制了具有固定稀疏度的矩阵所能包含的最大匹配数量。
7. [矩阵幂] 证明：对于 \(A = \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}\)，\(\operatorname{perm}(A^2) \neq (\operatorname{perm} A)^2\)。
参考答案
计算： 1. \(\operatorname{perm} A = 1+1 = 2\)，故 \((\operatorname{perm} A)^2 = 4\)。 2. \(A^2 = \begin{pmatrix} 2 & 2 \\ 2 & 2 \end{pmatrix}\)。 3. \(\operatorname{perm}(A^2) = 2 \cdot 2 + 2 \cdot 2 = 8\)。 结论：\(8 \neq 4\)。这展示了积和式在处理矩阵相乘时的不协调性。
8. [反对称] 证明：对于奇数阶反对称矩阵 \(A\)，其积和式是否一定为 0？
参考答案
结论：不一定。 理由：奇数阶反对称矩阵的行列式必为 0。但积和式没有交错符号。 例如 \(A = \begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix}\)（虽然是偶数阶）， \(\det = 1\) 而 \(\operatorname{perm} = -1\)。对于奇数阶，例如 \(\begin{pmatrix} 0 & 1 & 1 \\ -1 & 0 & 1 \\ -1 & -1 & 0 \end{pmatrix}\)，其积和式通常不为 0。
9. [不变量] 积和式在哪些矩阵操作下保持不变？
参考答案
结论： 1. 置换变换：\(A \to P A Q\)（其中 \(P, Q\) 为置换矩阵）。交换行或列不改变积和式。 2. 转置：\(\operatorname{perm}(A) = \operatorname{perm}(A^T)\)（针对方阵）。 注意：它不满足在行加减变换下的不变性。
10. [应用] 什么是量子计算中的“玻色采样”（Boson Sampling）问题？
参考答案
联系： 玻色采样是一个计算难题，它证明了即使是简单的光子干涉实验，其概率分布也由转移矩阵子块的积和式决定。由于积和式计算是 #P-完全的，这意味着经典计算机很难模拟量子光学系统的行为，从而为“量子优越性”提供了证据。
本章小结¶
积和式是连接代数与组合难题的纽带：
- 对称性的代价：去掉行列式的交错符号后，积和式失去了绝大部分优秀的代数性质（如乘法法则），这直接导致了其计算上的“灾难性”复杂度。
- 组合的计数器：通过将组合约束编码进 (0,1)-矩阵，积和式成为了解决排列与匹配问题的万能钥匙，证明了代数形式可以完美封装离散逻辑。
- 计算的边界：Ryser 公式与 van der Waerden 定理分别从算法和理论层面划定了积和式的可操作界限，是现代复杂性理论研究的重要对象。