積和式

在數學，特別是線性代數中，積和式是一個與行列式類似的多項式。與行列式類似，積和式可以看作是定義在一個變數矩陣上。積和式在計算機科學，特別是計算複雜性理論中有重要的地位。比如計算一個二分圖（bipartite graph）的完美匹配（perfect matching）的數目可以方便的表示為計算積和式的值。

基本介紹

• 中文名：積和式
• 外文名：permanent
• 套用學科：線性代數
• 適用領域範圍：計算機科學
• 屬性：一個與行列式類似的多項式
• 相關術語：行列式

定義

為了給定n階積和式的定義，我們來定義一下幾個名稱：

線性函式

設f是F^n上的一個k元函式。如果對每一個i，1≤i≤k，均有

f(ξ1,...,ξ(i-1),λη+μζ,ξ(i+1),...,ξk)=λf(ξ1,...,ξ(i-1),η,ξ(i+1),...,ξk)+μf(ξ1,...,ξ(i-1),ζ,ξ(i+1),...,ξk)

其中λ，μ∈F，η，ζ∈F^n，則f稱為k重線性函式。

規範

設f(ξ1,ξ2,...,ξn)是F^n上的n元函式，且設εi為第i個分量為1，其他分量為0的向量，i=1,2，...,n。如果f(ε1,ε2,...,εn)=1，則稱f(ξ1,ξ2,...,ξn)是規範的。

對稱

設f(ξ1,ξ2,...,ξn)是F^n上的n元函式，如果對於任意整數i，j，1≤i,j≤n，均有

f(ξ1,...,ξi,...,ξj,...,ξk)=f(ξ1,...,ξj,...,ξi,...,ξk)

則稱f(ξ1,ξ2,...,ξn)是對稱的。

於是我們得到了n階積和式的定義：

積和式定義

給定一個數域F，則稱數域Fⁿ上的規範對稱n重線性函式叫做n階積和式(permanent)。

這和n階行列式對比：

給定一個數域F，則稱數域Fⁿ上的規範反對稱n重線性函式叫做n階行列式(determinant)。

性質

對於一個方陣A，A=(a_ij)，n階積和式記為perA或者permA

不難證明，

特殊情況，當n=2時，perA=a₁₁a₂₂+a₂₁a₁₂，與行列式只差個符號。因此，積和式有些性質可以類比於行列式。

組合上的解釋

積和式的定義可以從如下兩方面理解，即計算二分圖上完美匹配的個數，以及計算一個圖上的圈覆蓋的權重。

二分圖

二分圖上的完美匹配是算法理論和計算複雜性理論中的重要問題。對於一個n×n的二分圖G=(L, R, E)，其中L={1, 2,..., n}是左邊結點的集合，R={1', 2', ..., n'}是右邊結點的集合，E為邊的集合，G的一個完美匹配是{1, 2, ..., n}到{1', 2', ..., n'}的一個雙射f，使得(1, f(1)), (2, f(2)), ..., (n, f(n))都在E中出現。

對G，我們可以建立如下n×n的0-1矩陣Ag=(aij)，i,j∈{1,2,...,n}，其中aij=1若且唯若(i,j')屬於E。不難驗證，perAg的值即是G中完美匹配的個數。這樣，我們將積和式的值與二分圖完美匹配的個數建立了聯繫。

圖的圈覆蓋

對於一個圖G=(V,E)，V={1, 2, ..., n}為結點集，E為邊集。一個G的圈覆蓋是一組G中的不相交的圈的集合，且這些圈覆蓋所有的點集。由於一個置換可以做環狀分解，可以看出一個置換與一個可能的圈覆蓋是一一對應的。特別的，G的鄰接矩陣的積和式即是G中圈覆蓋的數目。

計算複雜性

積和式的計算是#P完全的。相對的，行列式可以用高斯消元法等算法在多項式時間內解決。