特殊矩陣 (8)：Vandermonde 矩陣

本文的閱讀等級：初級

法國數學家范德蒙 (Alexandre-Théophile Vandermonde) 是行列式的奠基者之一，他在十八世紀提出行列式專有符號，將行列式應用於解線性方程組，並且對行列式理論進行了開創性的研究。兩百多年後，他的名字因為一個特殊矩陣而經常被提及。Vandermonde 矩陣具有以下形式：

$A_n=\begin{bmatrix} 1&x_1&x_1^2&\cdots&x_1^{n-1}\\ 1&x_2&x_2^2&\cdots&x_2^{n-1}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&x_n&x_n^2&\cdots&x_n^{n-1} \end{bmatrix}$ ，

其中 $A_n=[a_{ij}]$ 是一個 $n\times n$ 階矩陣，各元為 $a_{ij}=x_i^{j-1}$ 。同樣地， $A_n^T$ 也稱為 Vandermonde 矩陣。

下面我們推導 Vandermonde 矩陣的行列式。先看 2 階行列式

$\det A_2=\begin{vmatrix} 1&x_1\\ 1&x_2 \end{vmatrix}=x_2-x_1$ 。

考慮 3 階行列式，以基本列運算化簡再用餘因子 (cofactor) 展開計算，可得

$\begin{aligned} \det A_3&=\begin{vmatrix} 1&x_1&x_1^2\\ 1&x_2&x_2^2\\ 1&x_3&x_3^2 \end{vmatrix}\\ &=\begin{vmatrix} 1&x_1&x_1^2\\ 0&x_2-x_1&x_2^2-x_1^2\\ 0&x_3-x_1&x_3^2-x_1^2 \end{vmatrix}\\ &=\begin{vmatrix} x_2-x_1&x_2^2-x_1^2\\ x_3-x_1&x_3^2-x_1^2 \end{vmatrix}\\ &=(x_2-x_1)(x_3-x_2)(x_3-x_1).\end{aligned}$

這時我們可以放膽猜測 $n\times n$ 階 Vandermonde 矩陣的行列式公式如下：

$\det A_n=\displaystyle\prod_{1\le j<i\le n}(x_i-x_j)$ 。

證明使用數學歸納法。假設 $k$ 階 Vandermonde 行列式為

$\det A_k=\displaystyle\prod_{1\le j<i\le k}(x_i-x_j)$ ，

我們要證明 $k+1$ 階 Vandermonde 行列式也有相同的形式。將 $A_{k+1}$ 的最末列 $1, x_{k+1}, x_{k+1}^2,\ldots,x_{k+1}^k$ 替換為 $1, x, x^2,\ldots, x^{k}$ ，並設此矩陣的行列式為

$f(x)=\begin{vmatrix} 1&x_1&x_1^2&\cdots&x_1^{k}\\ 1&x_2&x_2^2&\cdots&x_2^{k}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&x_k&x_k^2&\cdots&x_k^{k}\\ 1&x&x^2&\cdots&x^{k} \end{vmatrix}$ 。

你用最末列的餘因子展開式可知 $f(x)$ 為 $k$ 次多項式。若一個矩陣有相同的兩列，則該矩陣的行列式等於零，因此 $f(x_1)=f(x_2)=\cdots=f(x_k)=0$ 。換句話說， $x_1, x_2,\ldots,x_k$ 為多項式 $f(x)$ 的 $k$ 個根， $f(x)$ 可表示為

$f(x)=\alpha(x-x_1)(x-x_2)\cdots(x-x_k)$ ，

上式中 $\alpha$ 為非零常數。剩下的問題是決定 $\alpha$ 。

再由 $f(x)$ 的餘因子展開式可得到 $x^{k}$ 的係數，即

$\alpha=\begin{vmatrix} 1&x_1&x_1^2&\cdots&x_1^{k-1}\\ 1&x_2&x_2^2&\cdots&x_2^{k-1}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&x_k&x_k^2&\cdots&x_k^{k-1} \end{vmatrix}$ 。

注意，上面以行列式表達的 $\alpha$ 即為 $\mathrm{det}A_k$ 。根據歸納法的假設，就有

$f(x)=\displaystyle\left[\prod_{1\le j<i\le k}(x_i-x_j)\right](x-x_1)(x-x_2)\cdots(x-x_k)$ 。

最後還有一個不能錯過的事實： $f(x_{k+1})=\mathrm{det}A_{k+1}$ 。將 $x=x_{k+1}$ 代入上式，

$\det A_{k+1}=\displaystyle\left[\prod_{1\le j<i\le k}(x_i-x_j)\right](x_{k+1}-x_1)(x_{k+1}-x_2)\cdots(x_{k+1}-x_k)$ 。

整理等號右端，得到

$\det A_{k+1}=\displaystyle\prod_{1\le j<i\le k+1}(x_i-x_j)$ ，

故證明所求。

Vandermonde 矩陣常見於數值分析的內插 (interpolation) 問題。給出 $n$ 個資料點 $(x_i,y_i)$ ， $i=1,2,\ldots,n$ ，求 $(n-1)$ 次多項式

$p(x)=a_{n-1}x^{n-1}+a_{n-2}x^{n-2}+\cdots+a_1x+a_0$

滿足

$\begin{aligned} p(x_1)&=a_0+a_1x_1+\cdots+a_{n-1}x_1^{n-1}=y_1\\ p(x_2)&=a_0+a_1x_2+\cdots+a_{n-1}x_2^{n-1}=y_2\\ &\vdots\\ p(x_n)&=a_0+a_1x_n+\cdots+a_{n-1}x_n^{n-1}=y_n.\end{aligned}$

將上面的線性方程組寫為矩陣形式 $A\mathbf{a}=\mathbf{y}$ ，其中 $A$ 為 $n\times n$ 階 Vandermonde 矩陣。內插問題就是要解出係數向量 $\mathbf{a}=\begin{bmatrix} a_0&a_1&\cdots&a_{n-1}\end{bmatrix}^T$ 。如果 $n$ 個參數 $x_1,x_2,\ldots,x_n$ 彼此相異，推知 $\mathrm{det}A_n\neq 0$ ， $A$ 是可逆的，方程式必定存在唯一解。

通常我們不直接解出 $a_i$ ，而是將多項式 $p(x)$ 表示為特殊 Lagrange 內插多項式，如下：

$L_i(x)=\displaystyle\frac{\prod_{j=1,j\neq i}^n(x-x_j)}{\prod_{j=1,j\neq i}^n(x_i-x_j)},~~i=1,2,\ldots,n$ 。

每個多項式 $L_i(x)$ 都是 $(n-1)$ 次，若 $j\neq i$ ， $L_i(x_j)=0$ ，但 $L_i(x_i)=1$ 。利用上述條件，可得 Lagrange 內插公式

$p(x)=y_1L_1(x)+y_2L_2(x)+\cdots+y_nL_n(x)$ 。

顯然， $(n-1)$ 次多項式 $p(x)$ 滿足前面給定的 $n$ 個內插條件， $p(x_i)=y_i$ ， $i=1,2,\ldots,n$ 。

繼續閱讀：

10 Responses to 特殊矩陣 (8)：Vandermonde 矩陣

VtripleV says:

11/24/2010 at 2:33 pm

看到這個Vandermonde矩陣,瞬間回想到DFT開放課程中,印度老師的解說過程(http://www.youtube.com/watch?v=GDFTb-BwA0o ,第9分鐘之後)
對一個有限長度取樣信號sequence x(n) ,n=0…N-1, 對該訊號取fourier transform => X(e^jw)=x(0)+x(1)e^(-jw)+…+X(N-1)e^(-j(N-1)w)
上式的LHS基本上可以視為e^(-jw)的N-1次多項式，有N個係數，所以該N-1次多項式由N個係數唯一決定，或是從此N-1次多項式函數中N個相異的取樣值決定(在time-space(or domain)或是w-space(domain)取樣)。也就是可以對X(e^jw)函數於w-space進行N點取樣,就足夠描述X(e^jw), 於是 X(e^jw) sample X(e^jw) at N points==> X(e^jwk),k=0…N-1,簡單的取樣就是2pi等N分取樣，於是就誕生了DFT X(k)=DFT[x(n)], DFT矩陣跟反矩陣正好是Vandermonde 矩陣長像.

ccjou says:

11/24/2010 at 3:31 pm

你應該會有興趣閱讀
特殊矩陣(七)：循環矩陣
https://ccjou.wordpress.com/2009/10/23/%E7%89%B9%E6%AE%8A%E7%9F%A9%E9%99%A3%E4%B8%83%EF%BC%9A%E5%BE%AA%E7%92%B0%E7%9F%A9%E9%99%A3/

最近垃圾分檢系統常有誤判情況，我將請管理員研究改善方案。

vtriplev says:

11/24/2010 at 7:03 pm

P^0=P^N=I (對應於W^0=W^N=1)
複數跟矩陣性質真的好類似啊

ccjou says:

11/25/2010 at 7:44 am

是的，更多的類比情形請見”矩陣與複數的類比”
https://ccjou.wordpress.com/2010/03/04/%E7%9F%A9%E9%99%A3%E8%88%87%E8%A4%87%E6%95%B8%E7%9A%84%E9%A1%9E%E6%AF%94/

熊大帥 says:

02/02/2016 at 5:03 pm

好複雜，我只是預習高二下範圍，上網找資料，只是好複雜，還是死記等人教到再聽如何證的好了

陳易聖 says:

01/17/2017 at 5:38 pm

請問這是否也是最小平方法的求法呢？

- ccjou says:
  
  01/17/2017 at 6:55 pm
  
  你是說上文的內插問題嗎？給出n個資料點(限制條件)，n-1次多項式有n個係數(未知數)，因此有唯一解，不需要使用最小平方法求近似解。
  
fabo says:

11/16/2017 at 10:39 pm

我們要證明 k+1 階 Vandermonde 行列式也有相同的形式。
您好:
想請問這裡的f(x)的問題。
我覺得f(x)應該不只是x的函數吧，應該還有x1,x2,x3….等，所以f(x)=a(x-x1)….(x-xk)應該不只這樣吧，譬如說還有(x1-x2)等，也就是f(x)=a(x-x1)…(x-xk)(x1-x2)之類的。
想問問為甚麼可以只寫成f(x)為x的函數，因為這個行列式應該同時也是x1,x2,…,xk的函數吧?

pinjie wu says:

06/10/2018 at 9:17 pm

老師您好，感謝分享如此多的資訊！

想請教老師：
「我們要證明 k+1 階 Vandermonde 行列式也有相同的形式。將 A_{k+1} 的最末列替換為 1, x, x^2,\ldots, x^{k}，設此矩陣的行列式為 f(x)，亦即………由最末列的餘因子展開式可知 f 為變數 x 的 k 次多項式。若矩陣有相同的兩列，其行列式等於零，故 f(x_i)=0，i=1,2,\ldots,k，也就是說 x_i，i=1,2,\ldots,k，為多項式 f(x) 的 k 個根，」

用這個證法，則最後一列會變成「行列式等於零」，這樣整個Vandermonde 行列式就等於0了，為什麼還要繼續證明下去呢？謝謝！

偉晨 says:

12/10/2019 at 3:29 pm

回覆給上面的同學，老師的目的是證明當給你n個相異點時你所製造出來的Vandermonde是可逆矩陣，而我們只是利用歸納法並將最後項先假設是x以便你可以看出他帶某些值整個行列式是如何影響

	陳倍恩 on 線性代數的第一堂課──矩陣乘法的定義
	輕鬆談如何教學二項式定理？… on 牛頓的二項式定理 (上)
	madhouse on 高斯消去法
	WishMobile on 翻轉 LU 分解
	周子傑 on Karush-Kuhn-Tucker (KKT) 條件
	Cloud Huang on 線性泛函與伴隨