在数学，特别是线性代数中，积和式是一个与行列式类似的多项式。与行列式类似，积和式可以看作是定义在一个变量矩阵上。积和式在计算机科学，特别是计算复杂性理论中有重要的地位。比如计算一个二分图（bipartite graph）的完美匹配（perfect matching）的数目可以方便的表示为计算积和式的值。

简介

在 数学，特别是 线性代数中，积和式是一个与 行列式类似的多项式。与行列式类似，积和式可以看作是定义在一个变量矩阵上。积和式在 计算机科学，特别是 计算复杂性理论中有重要的地位。比如计算一个 二分图（bipartite graph）的 完美匹配（perfect matching）的数目可以方便的表示为计算积和式的值。

定义

为了给定n阶积和式的定义，我们来定义一下几个名称：

线性函数

设f是

上的一个k元函数。如果对每一个i，

，均有

其中λ，

， η，

，则f称为 k重线性函数。规范

设

是

上的n元函数，且设 εi为第i个分量为1，其他分量为0的向量，

。如果

，则称

是 规范的。对称

设

是F^n上的n元函数，如果对于任意整数i，j，

，均有

则称

是 对称的。

于是我们得到了n阶积和式的定义：

积和式

给定一个数域F，则称数域F^n上的 规范对称n重线性函数叫做n阶积和式(permanent)。

这和n阶行列式对比：

给定一个数域F，则称数域F^n上的 规范反对称n重线性函数叫做n阶行列式(determinant)。

积和式的性质

对于一个方阵A，

，n阶积和式记为perA或者permA

不难证明，

特殊情况，当

时，

，与行列式只差个符号。因此，积和式有些性质可以类比于行列式。

组合上的解释

积和式的定义可以从如下两方面理解，即计算二分图上完美匹配的个数，以及计算一个 图上的圈复盖的权重。

与二分图完美匹配的关系

二分图上的完美匹配是算法理论和计算复杂性理论中的重要问题。对于一个

的二分图

，其中

是左边结点的集合，

是右边结点的集合， E为边的集合， G的一个完美匹配是

到

的一个双射f，使得

都在 E中出现。

对 G，我们可以建立如下

的0-1矩阵

，其中

当且仅当(i,j')属于 E。不难验证，per Ag的值即是 G中完美匹配的个数。这样，我们将积和式的值与二分图完美匹配的个数建立了联系。与图的圈复盖的关系

对于一个图

为结点集， E为边集。一个 G的圈复盖是一组 G中的不相交的圈的集合，且这些圈复盖所有的点集。由于一个 置换可以做环状分解，可以看出一个置换与一个可能的圈复盖是一一对应的。特别的， G的 邻接矩阵的积和式即是 G中圈复盖的数目。