范德蒙行列式的一個(gè)組合解釋

孫毅

摘要：在《線性代數(shù)》的教學(xué)中，范德蒙行列式是一類非常重要的行列式，在很多數(shù)學(xué)結(jié)論的證明中起著關(guān)鍵性的作用。有關(guān)范德蒙行列式的證明方法有很多種，但一直沒有一種直觀的方法。本文將利用格路這種組合結(jié)構(gòu)，從組合的角度對范德蒙行列式給出一個(gè)組合解釋。

關(guān)鍵詞：行列式；范德蒙行列式；格路；組合解釋

一、 引言

在《線性代數(shù)》的教學(xué)過程中以及同學(xué)們在考試和解題的過程中，常常會遇到范德蒙行列式。范德蒙行列式已成為眾多《線性代數(shù)》教材中不可缺少的一部分，并且在很多學(xué)科中都有重要的應(yīng)用，如組合學(xué)中的對稱函數(shù)理論、代數(shù)學(xué)中行列式的計(jì)算以及線性變換的相關(guān)理論等。后來，人們又根據(jù)實(shí)際需要給出了各種各樣的范德蒙行列式的推廣形式及其具有的其他性質(zhì)和結(jié)果，具體可以參考文獻(xiàn)[1]。關(guān)于范德蒙行列式的值，利用數(shù)學(xué)歸納法可以得出如下結(jié)論：

定理1設(shè)x1，x2，…，xn-1，xn是任意n個(gè)實(shí)數(shù)，D（x）=|xi-1j|i，j=0，1，…，n是范德蒙行列式，則

D（x）=∏1≤j

到目前為止，人們給出了很多證明定理1的方法，除了前面提到的數(shù)學(xué)歸納法之外，還有數(shù)學(xué)構(gòu)造法、遞推公式法等，更多方法可以參考文獻(xiàn)[2]。但是，以上所有的方法并不能從直觀上對范德蒙行列式給出一個(gè)組合解釋。本文將利用組合學(xué)中格路徑與行列式的關(guān)系對范德蒙行列式給出一種比較直觀的組合解釋。

二、 格路與行列式的關(guān)系

為了說明行列式與格路徑之間的關(guān)系，我們需要定義有向無圈圖的概念。

圖一左圖是一個(gè)有向無圈圖；右圖是簡單有向無圈圖

定義1一個(gè)有向無圈圖G是指一個(gè)不包含閉合有向圈的有序三元組G=（V，E），其中V=V（G），E=E（G）分別稱為是圖G的頂點(diǎn)集、有向邊集。

如圖一的左圖就是一個(gè)包含六個(gè)頂點(diǎn)的有向無圈圖，其中：V（G）={A1，A2，A3，B1，B2，B3}，

E（G）={A1→B1，A2→A1，A3→B3，A3→A2，B2→B1，B3→B2，B3→A1}，

通常情況下，E（G）中的元素也可以用有序點(diǎn)對來表示，以圖一的左圖為例，E（G）又可以表示成如下形式：E（G）={（A1，B1），（A2，A1），（A3，B3），（A3，A2），（B2，B1），（B3，B2），（B3，A1）}。

為了解釋行列式與格路之間的關(guān)系，我們給有向無圈圖G的任意兩個(gè)頂點(diǎn)Ai和Bj的有向邊賦予一個(gè)權(quán)重ω（Ai→Bj），并且當(dāng)Ai和Bj相等時(shí)，規(guī)定ω（Ai→Bj）=1。如果p表示從有向圖G的點(diǎn)A出發(fā)到點(diǎn)B的一條有向格路，簡記為p：A→B。此時(shí)，我們定義格路p的權(quán)重為

ω（p）=∏e∈pω（e），這里的e∈p是指e是格路p上一條有向邊。我們令Α={A1，A2，…，An}和Β={B1，B2，…，Bn}是兩組頂點(diǎn)集，并且允許兩集合相交非空。定義矩陣M=（mij）n×n使得

mij=∑p：Ai→Bjω（p）。那么，從集合A到集合B的格路徑族P中包含一個(gè)置換σ以及n個(gè)格路 pi=Ai→Bσ（i），其中i=1，2，…，n。令sign（P）=signσ，格路徑族P的權(quán)重是各格路徑的權(quán)重之積，即ω（P）=∏ni=1ω（pi）。有了上面的準(zhǔn)備，我們就可以得出以下結(jié)論：

定理2設(shè)G=（V，E）是有限加權(quán)的有向圖，Α={A1，A2，…，An}和Β={B1，B2，…，Bn}是兩組基數(shù)為n的頂點(diǎn)集，且M是從Α到B的路徑矩陣，則

det（M）=∑P是頂點(diǎn)不交的路徑族sign（P）w（P）。

這里的頂點(diǎn)不交的路徑族是指格路徑族P中的任何兩條格路徑都是頂點(diǎn)不相交的，也就是說任何兩條格路徑都沒有公共點(diǎn)。該定理的詳細(xì)證明請參考文獻(xiàn)[4]。有了上面的定理，我們便可以對范德蒙行列式給出一個(gè)組合解釋。

三、 范德蒙行列式的組合解釋

現(xiàn)設(shè)M=（mij）n×n是n×n的方陣，其中矩陣中的每一個(gè)元素mij（i，j=1，2，…，n）都是實(shí)數(shù)。那么，根據(jù)行列式的定義，則有：

det（M）=∑σsign（σ）m1σ（1）m2σ（2）…mnσ（n）（*）

這里的σ是取遍n次對稱群Sn上的所有元素，符號函數(shù)sign（σ）的值與置換σ的奇偶性有關(guān)。如果σ是偶數(shù)個(gè)輪換的乘積，則sign（σ）=1，否則sign（σ）=-1。

另外，為了給范德蒙行列式一個(gè)組合解釋，我們注意到定理1中的乘積式可以化為如下等式右邊的和式（利用數(shù)學(xué)歸納法也可以證明）：

∏1≤j

現(xiàn)構(gòu)造一個(gè)簡單的有向無圈圖D=（V，E）如下：

V（D）={A1，A2，…，An，B1，B2，…，Bn}，E（D）={（Ai，Bj）|i，j=1，2，…，n}，也就是說集合Α={A1，A2，…，An}和Β={B1，B2，…，Bn}，它們各自內(nèi)部的點(diǎn)之間沒有有向邊相連，而集合之間的每一對點(diǎn)都有有向邊。

如果假設(shè)頂點(diǎn)A1，A2，…，An代表n階方陣的行標(biāo)，B1，B2，…，Bn代表n階方陣的列標(biāo)，對每對正整數(shù)i，j，我們畫一條從Ai到Bj的有向邊并賦予權(quán)重mij，如圖一右圖所示。根據(jù)定理 2，公式（*）就可以簡單地解釋為：（a）公式（*）的左邊就可以看做是格路徑矩陣的行列式，其中矩陣的（i，j）-元是從Ai到Bj的唯一有向格路的權(quán)重；（b）公式（*）的右邊就是從集合Α={A1，A2，…，An}到集合Β={B1，B2，…，Bn}的所有頂點(diǎn)的不交路徑族的帶符號的權(quán)重和。如果我們記Pσ={A1→Bσ（1），A2→Bσ（2），…，An→Bσ（n）}，則ω（Pσ）=ω（A1→Bσ（1））ω（A2→Bσ（2））…ω（An→Bσ（n）），從而公式（*）又可以寫成detM=∑σsign（σ）ω（Pσ）。特別地，當(dāng)ω（Ai→Bj）=xi-1j，即在圖一右圖中給每一條從Ai到Bj的有向邊賦予權(quán)重xi-1j時(shí)，就得到了范德蒙行列式的組合解釋。