積和式

在線性代數中，積和式（英語：permanent）是一個由方塊矩陣$A$計算得到的標量，記作$\operatorname {perm} (A)$。積和式的定義與行列式類似，只是在求和時不添加正負號。當矩陣$A$包含若干變量時，積和式也可以看作是一個關於這些變量的多項式。積和式在計算機科學，特別是計算複雜性理論中有重要的地位，因為理論上的一個重要難題——計算一個二分圖（bipartite graph）上完美匹配（perfect matching）的數目——等價於求某個矩陣的積和式。

定義

一個$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}}\operatorname {sgn}(\sigma )\prod _{i=1}^{n}a_{i,\sigma (i)}$

其中$\operatorname {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$中圈覆蓋的數目。

積和式的計算複雜性

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）近似計算非負矩陣的積和式。