在线性代数中，积和式（）是一个由方块矩阵A计算得到的标量，记作\operatorname{perm}(A)。积和式的定义与行列式类似，只是在求和时不添加正负号。当矩阵A包含若干变量时，积和式也可以看作是一个关于这些变量的多项式。积和式在计算机科学，特别是计算复杂性理论中有重要的地位，因为理论上的一个重要难题——计算一个二分图（）上完美匹配（）的数目——等价于求某个矩阵的积和式。
定义
一个n \times n矩阵A=(a_{i,j})的积和式定义为
: \operatorname{perm}(A)=\sum_{\sigma\in S_n}\prod_{i=1}^n a_{i,\sigma(i)}.
其中S_n为 n阶对称群 (n次对称群)，即包含所有 n元排列的集合。在 n = 2的特殊情形下，
: \operatorname{perm}\begin{pmatrix}a&b \\ c&d\end{pmatrix}=ad+bc.
从定义不难验证，积和式是多线性多项式，且置换 A中行（或列）后保持不变。与行列式类似，积和式也可以用拉普拉斯展开式展开。
作为比较，同一个矩阵 A的行列式定义为
: \det(A) = \sum_{\sigma \in S_n} \sgn(\sigma) \prod_{i=1}^n a_{i,\sigma(i)}
其中\sgn(\sigma)为符号差。可以看出，两者形式上的区别仅在于某些项前面的符号有所不同。尽管如此，它们在性质上却有诸多不同。比如，置换 A中两行（或列）后行列式的符号会改变，而正是这一性质使我们得以利用高斯消元法高效求出行列式的值。
与组合问题的联系
积和式的定义可以从如下两方面理解，一是用于计算二分图上完美匹配的个数，二是用于计算一个图上的圈覆盖的个数。
与二分图完美匹配的关系
二分图上的完美匹配是算法理论和计算复杂性理论中的重要问题。设二分图G=(L, R, E)，其中L = \{1, 2, \dots, n\}是左边结点的集合，R=\{1', 2', \dots, n'\}是右边结点的集合，E为边的集合。如果双射f: L \to R满足(1, f(1)), (2, f(2)), \dots, (n, f(n))均为E中的边，那么我们称其为G的一个完美匹配。
对包括二分图在内的任意图G，我们定义其邻接矩阵 A_G = (a_{ij})_{n \times n}如下：若(i,j')\in E 则 a_{ij}=1，否则 a_{ij}=0。不难验证，\operatorname{perm}(A_G)的值即是G中完美匹配的个数，因为乘积项与双射之间一一对应，而不满足条件的双射所对应的乘积项为零。这样，我们就将积和式的值与二分图完美匹配的个数建立了联系。
与图的圈覆盖的关系
设有向图G=(V,E)，V=\{1, 2, \dots, n\}为结点集，E为边集。G的一个圈覆盖定义为G中一组不相交的圈的集合，且这些圈覆盖了V。由于一个置换可以做环状分解，可以看出一个置换与一个可能的圈覆盖是一一对应的。特别地，G的邻接矩阵A_G的积和式即是G中圈覆盖的数目。
棋
大小為 n \times n 的全 1 永久矩陣是大小為 n \times n 的棋盤上 n 個互不攻擊的車的可能排列數。
积和式的计算复杂性
Valient首先证明了积和式的求值问题是#P完全的，即便矩阵各项的值仅能取0或1。也就是说，任何#P复杂性类中的计数问题都能多项式归约到积和式的求值问题。而户田定理（Toda's theorem）告诉我们\textsf{PH} \subseteq \textsf{P}^{\# \textsf{P}}，因此假若能在确定性多项式时间内解决积和式求值问题，那么也能在确定性多项式时间内解决一切属于多项式谱系（\textsf{PH}）的判定问题，进而导致\textsf{P} = \textsf{NP} = \textsf{PH}；计算机科学家普遍相信这是不可能的。可见计算积和式的复杂性远比计算行列式高；后者易用高斯消元等算法在确定性多项式时间内解决。
虽然精确计算积和式很困难，但是的确存在近似计算积和式的高效算法。Jerrum，Sinclair和Vigoda设计出了一种多项式时间内的随机算法，能以任意精度（FPRAS）近似计算非负矩阵的积和式。
参考文献
评论 (0)