范德蒙行列式的一個組合解釋

孫毅

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

關鍵詞：行列式；范德蒙行列式；格路；組合解釋

一、 引言

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

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

D（x）=∏1≤j

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

二、 格路與行列式的關系

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

圖一左圖是一個有向無圈圖；右圖是簡單有向無圈圖

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

如圖一的左圖就是一個包含六個頂點的有向無圈圖，其中：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）中的元素也可以用有序點對來表示，以圖一的左圖為例，E（G）又可以表示成如下形式：E（G）={（A1，B1），（A2，A1），（A3，B3），（A3，A2），（B2，B1），（B3，B2），（B3，A1）}。

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

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

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

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

det（M）=∑P是頂點不交的路徑族sign（P）w（P）。

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

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

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

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

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

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

∏1≤j

現構造一個簡單的有向無圈圖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}，它們各自內部的點之間沒有有向邊相連，而集合之間的每一對點都有有向邊。

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