[科普中國(guó)]-積和式

定義

為了給定n階積和式的定義，我們來(lái)定義一下幾個(gè)名稱：

線性函數(shù)設(shè)f是F^n上的一個(gè)k元函數(shù)。如果對(duì)每一個(gè)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重線性函數(shù)。

規(guī)范設(shè)f(ξ1,ξ2,...,ξn)是F^n上的n元函數(shù)，且設(shè)εi為第i個(gè)分量為1，其他分量為0的向量，i=1,2，...,n。如果f(ε1,ε2,...,εn)=1，則稱f(ξ1,ξ2,...,ξn)是規(guī)范的。

對(duì)稱設(shè)f(ξ1,ξ2,...,ξn)是F^n上的n元函數(shù)，如果對(duì)于任意整數(shù)i，j，1≤i,j≤n，均有

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

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

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

積和式定義給定一個(gè)數(shù)域F，則稱數(shù)域Fn上的規(guī)范對(duì)稱n重線性函數(shù)叫做n階積和式(permanent)。2

這和n階行列式對(duì)比：

給定一個(gè)數(shù)域F，則稱數(shù)域Fn上的規(guī)范反對(duì)稱n重線性函數(shù)叫做n階行列式(determinant)。

性質(zhì)對(duì)于一個(gè)方陣A，A=(aij)，n階積和式記為perA或者permA2

不難證明，

特殊情況，當(dāng)n=2時(shí)，perA=a11a22+a21a12，與行列式只差個(gè)符號(hào)。因此，積和式有些性質(zhì)可以類比于行列式。

組合上的解釋積和式的定義可以從如下兩方面理解，即計(jì)算二分圖上完美匹配的個(gè)數(shù)，以及計(jì)算一個(gè)圖上的圈覆蓋的權(quán)重。

二分圖二分圖上的完美匹配是算法理論和計(jì)算復(fù)雜性理論中的重要問(wèn)題。對(duì)于一個(gè)n×n的二分圖G=(L, R, E)，其中L={1, 2,..., n}是左邊結(jié)點(diǎn)的集合，R={1', 2', ..., n'}是右邊結(jié)點(diǎn)的集合，E為邊的集合，G的一個(gè)完美匹配是{1, 2, ..., n}到{1', 2', ..., n'}的一個(gè)雙射f，使得(1, f(1)), (2, f(2)), ..., (n, f(n))都在E中出現(xiàn)。

對(duì)G，我們可以建立如下n×n的0-1矩陣Ag=(aij)，i,j∈{1,2,...,n}，其中aij=1當(dāng)且僅當(dāng)(i,j')屬于E。不難驗(yàn)證，perAg的值即是G中完美匹配的個(gè)數(shù)。這樣，我們將積和式的值與二分圖完美匹配的個(gè)數(shù)建立了聯(lián)系。

圖的圈覆蓋對(duì)于一個(gè)圖G=(V,E)，V={1, 2, ..., n}為結(jié)點(diǎn)集，E為邊集。一個(gè)G的圈覆蓋是一組G中的不相交的圈的集合，且這些圈覆蓋所有的點(diǎn)集。由于一個(gè)置換可以做環(huán)狀分解，可以看出一個(gè)置換與一個(gè)可能的圈覆蓋是一一對(duì)應(yīng)的。特別的，G的鄰接矩陣的積和式即是G中圈覆蓋的數(shù)目。

計(jì)算復(fù)雜性積和式的計(jì)算是#P完全的。相對(duì)的，行列式可以用高斯消元法等算法在多項(xiàng)式時(shí)間內(nèi)解決。