Vandermonde矩阵的行列式

Vandermonde矩阵是形如:
 V_n= \begin{bmatrix} 1 & z_1 & z_1^2 & \cdots & z_1^{n-1} \\ 1 & z_2 & z_2^2 & \cdots & z_2^{n-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & z_n & z_n^2 & \cdots & z_n^{n-1}  \end{bmatrix}
的矩阵。

观察V_2,V_3,V_4

 V_2 = \begin{bmatrix} 1 & z_1 \\ 1 & z_2 \end{bmatrix} \\ V_3 = \begin{bmatrix} 1 & z_1 & z_1^2 \\ 1 & z_2 & z_2^2 \\ 1 & z_3 & z_3^2 \end{bmatrix} \\V_4 = \begin{bmatrix} 1 & z_1 & z_1^2 & z_1^3\\ 1 & z_2 & z_2^2 & z_2^3\\ 1 & z_3 & z_3^2 & z_3^3 \\ 1 & z_4 & z_4^2 & z_4^3 \end{bmatrix}

尝试计算V2,V3,V4的行列式。

对于V2与V3,很容易可以通过对角线法则计算行列式,不过,我们以V4为例计算一下行列式,看是否能得到一个比较简洁的行列式形式。

 det(V_4) = \begin{vmatrix} 1 & z_1 & z_1^2 & z_1^3\\ 1 & z_2 & z_2^2 & z_2^3\\ 1 & z_3 & z_3^2 & z_3^3 \\ 1 & z_4 & z_4^2 & z_4^3 \end{vmatrix}

按照定义来计算未免过于繁琐,注意到第一列都是1,在这里我选择将第2,3,4行全部减去第一列,得到:

 \begin{vmatrix} 1 & z_1 & z_1^2 & z_1^3\\ 0 & z_2 - z_1 & z_2^2 - z_1^2 & z_2^3 - z_1^3\\ 0 & z_3 - z_1 & z_3^2 - z_1^2 & z_3^3 - z_1^3 \\ 0 & z_4 - z_1 & z_4^2 - z_1^2 & z_4^3 - z_1^3 \end{vmatrix}
按照第一列展开则得到:
 \begin{vmatrix} z_2 - z_1 & z_2^2 - z_1^2 & z_2^3 - z_1^3\\ z_3 - z_1 & z_3^2 - z_1^2 & z_3^3 - z_1^3 \\ z_4 - z_1 & z_4^2 - z_1^2 & z_4^3 - z_1^3 \end{vmatrix}
请出我们的好朋友平方差公式和立方差公式:a^2 - b^2 = (a+b)(a-b)a^3 - b^3 = (a-b)(a^2 + ab + b^2),将每一行都提出来一个公因式。
 aws = (z_2 - z_1)(z_3 - z_1)(z_4 - z_1)\begin{vmatrix} 1 & z_2 + z_1 & z_2^2 + z_1^2 + z_2z_1\\ 1 & z_3 + z_1 & z_3^2 + z_1^2 + z_3z_1 \\ 1 & z_4 + z_1 & z_4^2 + z_1^2 + z_4z_1 \end{vmatrix}

第三列真是让人看着不爽(#`O′),和完全平方公式就差了一项。

但是第三列中每个元素带着的小尾巴分别是z2z1,z3z1,z4z1,既没法把它们一起都减掉,也没法把他们都转化为2倍,真是块疙瘩卡在了人喉咙里。

等等,真的没法解决掉这个可恶的小尾巴么?

第三列从上到下分别是z2,z3,z4与z1的积,而把视线挪到旁边的第二行……

刚巧从上到下也有z2,z3,z4

那事情就很简单了,拿第三列减去第二列的z1倍。

通过这样做,还能把第三列的z12也消去,真是一举两得(

再将第二列减去第一列的z1倍的话,似乎出现了吊诡的事情呢。

 aws = (z_2 - z_1)(z_3 - z_1)(z_4 - z_1)\begin{vmatrix} 1 & z_2 & z_2^2 \\ 1 & z_3 & z_3^2  \\ 1 & z_4 & z_4^2  \end{vmatrix}

式子里似乎出现了一个V3的行列式。

如果一开始用了对角线法则来计算det(V3),那大概率得到的是一堆很乱的式子,充斥着各种平方和积,要因式分解真是让人头皮发麻。不过通过对det(V4)的计算,估摸着V3的行列式应该也是可以写成一个连乘的形式——这个形式并不难猜,因为V2一眼就能看出来,括号里一定是一个差的式子。

实际上:
 V_2 = z_2 - z_1 \\ V_3 = (z_3 - z_2)(z_3 - z_1)(z_2 - z_1) \\ V_4 = (z_4 - z_3)(z_4 - z_2)(z_4 - z_1)(z_3 - z_2)(z_3 - z_1)(z_2 - z_1)

这个规律很好总结,但要转化为数学语言似乎就有点难了。从V2到V4能看出,答案是一个连乘,连乘的项是Vandermonde矩阵中不同列元素的差,按顺序似乎是从下标最大的元素一直减到最小的元素,被减数也是按照下标递减的顺序来的,此外,被减数的下标永远大于减数的下标。

另一个规律是,det(Vn)是 (zn – zn-1)(zn – zn-2)……(zn – z1)与det(Vn-1)的积。也就是说,第n阶Vandermonde矩阵行列式的值与第n-1阶Vandermonde矩阵行列式的值是相关的,类似于阶乘一样,含有递归的部分。

那么我们估摸着猜一下Vn的答案吧,我们把连乘分为几部分:第一部分是zn与比它下标小的项的差的积,也就是:

 \prod\limits_{1 \le i <n}{(z_n - z_i)}
然后是z_{n-1}与比它下标小的项的乘积:
 \prod\limits_{1 \le j<(n-1)}{(z_{n-1} - z_j)}
也就是说,答案应该是这样的:
 \prod\limits_{1 \le i <n}{(z_n - z_i)} \prod\limits_{1 \le j<(n-1)}{(z_{n-1} - z_j)} \cdots
合起来写的话形式会稍微变化一下,不过仔细想想,其实意义是一样的:
aws =  \prod\limits_{1 \le j<i \le n}{(z_i - z_j)}

写到这里,废了这么多力气,我们也只是得到了一个……猜想的答案。

那接下来就开证!用大家喜闻乐见的数学归纳法。

再瞅一眼这个矩阵:

 V_n= \begin{bmatrix} 1 & z_1 & z_1^2 & \cdots & z_1^{n-1} \\ 1 & z_2 & z_2^2 & \cdots & z_2^{n-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & z_n & z_n^2 & \cdots & z_n^{n-1}  \end{bmatrix}

首先对于 n = 2 的情形,我们猜想的答案显然是正确的。

那么我们假设对于Vn-1,我们的aws是成立的。

接下来的问题是,对于Vn来说,aws成立吗?

我们先把假设的条件写出来看看:

 det(V_n)= \begin{vmatrix} 1 & z_1 & z_1^2 & \cdots & z_1^{n-2} \\ 1 & z_2 & z_2^2 & \cdots & z_2^{n-2} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & z_{n-1} & z_{n-1}^2 & \cdots & z_{n-1}^{n-2}  \end{vmatrix} = \prod\limits_{1 \le j<i \le (n-1)}{(z_i - z_j)}

唔,说到底,Vn和Vn-1也就差了一阶不是么,所以我们想办法降阶就好了?

降阶?

刚刚在计算V4的时候,过程中是不是出现了V3

那我们就照葫芦画瓢,对Vn也执行类似的变换好了。

老样子,我们将V_n的从第二行开始,每一行都减去第一行,为了后面方便,这里写的详细一些:
 det(V_n)= \begin{vmatrix} 1 & z_1 & z_1^2 & \cdots & z_1^{n-2} & z_1^{n-1} \\ 0 & z_2 - z_1 & z_2^2 - z_1^2 & \cdots & z_2^{n-2} -z_1^{n-2} & z_2^{n-1} - z_1^{n-1} \\ 0 & z_3 -z_1 & z_3^2 - z_1^2 & \cdots & z_3^{n-2} - z_1^{n-2} & z_3^{n-1} - z_1^{n-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & z_n - z_1 & z_n^2 - z_1^2 & \cdots & z_n^{n-2} - z_1^{n-2} & z_n^{n-1} -z_1^{n-1}  \end{vmatrix}
按照第一列展开:
 det(V_n) = \begin{vmatrix} z_2 - z_1 & z_2^2 - z_1^2 & \cdots & z_2^{n-2} -z_1^{n-2} & z_2^{n-1} - z_1^{n-1} \\ z_3 -z_1 & z_3^2 - z_1^2 & \cdots & z_3^{n-2} - z_1^{n-2} & z_3^{n-1} - z_1^{n-1} \\ \vdots & \vdots & \ddots & \vdots & \vdots\\ z_n - z_1 & z_n^2 - z_1^2 & \cdots & z_n^{n-2} - z_1^{n-2} & z_n^{n-1} -z_1^{n-1}  \end{vmatrix}
唔,看上去有点乱却又挺整齐的呢。
接下来我们尝试降阶,之前我们将V_4降为V_3的时候做了什么操作?
好像是把最后一列减去它前一列的z_1倍,对吗?
那么我们从第二列开始,对V_n的每一列也这样做试试看:
 det(V_n )= \begin{vmatrix} z_2 - z_1 & z_2^2 - z_1z_2 & \cdots & z_2^{n-2} - z_1z_2^{n-3} & z_2^{n-1} - z_1z_2^{n-2} \\ z_3 - z_1 & z_3^2 - z_1z_3 & \cdots & z_3^{n-2} - z_1z_3^{n-3} & z_3^{n-1} - z_1z_3^{n-2} \\ \vdots & \vdots &\ddots & \vdots & \vdots \\ z_n - z_1 & z_n^2 - z_1z_n & \cdots & z_n^{n-2} - z_1z_n^{n-3} & z_n^{n-1} - z_1z_n^{n-2} \\ \end{vmatrix}

每一行都能提出来一个公因式,于是det(V_n)变成了一个连乘和一个行列式的积。
这个连乘就是:\prod\limits_{2 \le k \le n}{(z_k - z_1)}
而行列式是
 \begin{vmatrix} 1 & z_1 & z_1^2 & \cdots & z_1^{n-2} \\ 1 & z_2 & z_2^2 & \cdots & z_2^{n-2} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & z_{n-1} & z_{n-1}^2 & \cdots & z_{n-1}^{n-2}  \end{vmatrix}
这正是V_{n-1}的行列式,根据我们最开始的假设,它应该等于:\prod\limits_{1 \le j<i \le (n-1)}{(z_i - z_j)},我们可以直接把这个式子拿来用了!
也就是说,有:
 det(V_n) = \prod\limits_{1 \le j<i \le (n-1)}{(z_i - z_j)} \prod\limits_{2 \le k \le n}{(z_k - z_1)}
最后一步,不要被i,j,k这些不同的字母所迷惑了,这两个连乘后的结果再乘在一起,其意义正是:\prod\limits_{1 \le j<i \le n}{(z_i - z_j)} 哦!

那么对于V2来说,aws成立,假设对于Vn-1成立,则对于Vn也成立——我们顺利地通过归纳法证明了Vandermonde行列式的“通项公式”。

最后,Vandermonde矩阵可逆的条件也很容易看出来,那就是zi≠zj(i≠j,且i , j < n)。

好啦,关于Vandermonde矩阵的行列式就写到这里,这个矩阵并不复杂,计算行列式也不难——我主要是试试看在博客上写Latex行不行……结论是十分反人类,没有自动补全也没联想,手打真的好难受(

发表评论