孙毅
摘要：在《线性代数》的教学中，范德蒙行列式是一类非常重要的行列式，在很多数学结论的证明中起着关键性的作用。有关范德蒙行列式的证明方法有很多种，但一直没有一种直观的方法。本文将利用格路这种组合结构，从组合的角度对范德蒙行列式给出一个组合解释。
关键词：行列式；范德蒙行列式；格路；组合解释
一、 引言
在《线性代数》的教学过程中以及同学们在考试和解题的过程中，常常会遇到范德蒙行列式。范德蒙行列式已成为众多《线性代数》教材中不可缺少的一部分，并且在很多学科中都有重要的应用，如组合学中的对称函数理论、代数学中行列式的计算以及线性变换的相关理论等。后来，人们又根据实际需要给出了各种各样的范德蒙行列式的推广形式及其具有的其他性质和结果，具体可以参考文献[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时，就得到了范德蒙行列式的组合解释。
