跳转到内容

积和式

本页使用了标题或全文手工转换
维基百科,自由的百科全书

线性代数中,积和式(英語:permanent)是一个由方块矩阵计算得到的标量,记作。积和式的定义与行列式类似,只是在求和时不添加正负号。当矩阵包含若干变量时,积和式也可以看作是一个关于这些变量的多项式。积和式在计算机科学,特别是计算复杂性理论中有重要的地位,因为理论上的一个重要难题——计算一个二分图(bipartite graph)上完美匹配(perfect matching)的数目——等价于求某个矩阵的积和式。

定义

一个矩阵的积和式定义为

其中对称群_(n次对称群),即包含所有元排列的集合。在的特殊情形下,

从定义不难验证,积和式是多线性多项式,且置换中行(或列)后保持不变。与行列式类似,积和式也可以用拉普拉斯展开式展开。

作为比较,同一个矩阵的行列式定义为

其中符号差。可以看出,两者形式上的区别仅在于某些项前面的符号有所不同。尽管如此,它们在性质上却有诸多不同。比如,置换中两行(或列)后行列式的符号改变,而正是这一性质使我们得以利用高斯消元法高效求出行列式的值。

与组合问题的联系

积和式的定义可以从如下两方面理解,一是用于计算二分图上完美匹配的个数,二是用于计算一个上的圈覆盖的个数。

与二分图完美匹配的关系

二分图上的完美匹配是算法理论和计算复杂性理论中的重要问题。设二分图,其中是左边结点的集合,是右边结点的集合,为边的集合。如果双射满足均为中的边,那么我们称其为的一个完美匹配。

对包括二分图在内的任意图,我们定义其邻接矩阵如下:若,否则 。不难验证,的值即是中完美匹配的个数,因为乘积项与双射之间一一对应,而不满足条件的双射所对应的乘积项为零。这样,我们就将积和式的值与二分图完美匹配的个数建立了联系。

与图的圈覆盖的关系

设有向图为结点集,为边集。的一个圈覆盖定义为中一组不相交的的集合,且这些圈覆盖了。由于一个置换可以做环状分解,可以看出一个置换与一个可能的圈覆盖是一一对应的。特别地,的邻接矩阵的积和式即是中圈覆盖的数目。

积和式的计算复杂性

Valient首先证明了积和式的求值问题是#P完全的,即便矩阵各项的值仅能取0或1[1]。也就是说,任何#P复杂性类中的计数问题都能多项式归约到积和式的求值问题。而户田定理(Toda's theorem)告诉我们,因此假若能在确定性多项式时间内解决积和式求值问题,那么也能在确定性多项式时间内解决一切属于多项式谱系)的判定问题,进而导致;计算机科学家普遍相信这是不可能的。可见计算积和式的复杂性远比计算行列式高;后者易用高斯消元等算法在确定性多项式时间内解决。

虽然精确计算积和式很困难,但是的确存在近似计算积和式的高效算法。Jerrum,Sinclair和Vigoda设计出了一种多项式时间内的随机算法,能以任意精度(FPRAS)近似计算非负矩阵的积和式[2]

参考文献

  1. ^ Valiant, L.G. The complexity of computing the permanent. Theoretical Computer Science. 1979, 8 (2): 189–201 [2020-10-21]. doi:10.1016/0304-3975(79)90044-6. (原始内容存档于2021-03-08) (英语). 
  2. ^ Jerrum, Mark; Sinclair, Alistair; Vigoda, Eric. A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. Proceedings of the thirty-third annual ACM symposium on Theory of computing - STOC '01 (Hersonissos, Greece: ACM Press). 2001: 712–721. ISBN 978-1-58113-349-3. doi:10.1145/380752.380877 (英语).