范德蒙德矩陣

在線性代數中, 范德蒙德矩陣(也譯作范德蒙矩陣)得名於亞歷山大‑泰奧菲勒·范德蒙德（英語：Alexandre-Théophile_Vandermonde）. 范德蒙德矩陣是一個各列(row)呈現出幾何級數關係的矩陣: 它是一個${\displaystyle \left(m+1\right)\times \left(n+1\right)}$矩陣

${\displaystyle V=V(x_{0},x_{1},\cdots ,x_{m})={\begin{bmatrix}1&x_{0}&x_{0}^{2}&\dots &x_{0}^{n}\\1&x_{1}&x_{1}^{2}&\dots &x_{1}^{n}\\1&x_{2}&x_{2}^{2}&\dots &x_{2}^{n}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&x_{m}&x_{m}^{2}&\dots &x_{m}^{n}\end{bmatrix}}}$

其中每一項是${\displaystyle V_{i,j}=x_{i}^{j}}$, 也就是${\displaystyle x_{i}}$的${\displaystyle j}$次方, 其中下標${\displaystyle i}$和${\displaystyle j}$從0開始. ^[1]有些作者將范德蒙德矩陣定義為上述矩陣的轉置. ^[2][3]

當${\displaystyle n=m}$時, 即范德蒙德矩陣為方陣時, 其行列式稱作范德蒙德行列式或范德蒙德多項式（英語：Vandermonde_polynomial）. 范德蒙德行列式的值為:

${\displaystyle \det \left(V\right)=\prod _{0\leq i<j\leq m}\left(x_{j}-x_{i}\right).}$

范德蒙德行列式非零若且唯若所有${\displaystyle x_{i}}$互異(即任意二者皆不相等), 此時范德蒙德矩陣可逆.

應用

多項式插值問題就是取找到一個多項式 ${\displaystyle p\left(x\right)=a_{0}+a_{1}x+a_{2}x^{2}+\dots +a_{n}x^{n}}$ 對給定的數據點 ${\displaystyle \left(x_{0},y_{0}\right),\dots ,\left(x_{m},y_{m}\right)}$ 滿足 ${\displaystyle p\left(x_{0}\right)=y_{0},\dots ,p\left(x_{m}\right)=y_{m}}$. 這個問題可以在之後以范德蒙德矩陣為工具, 用線性代數的語言改述. 通過矩陣乘法${\displaystyle V\mathbf {a} =\mathbf {y} }$, ${\displaystyle V}$ 可以計算 ${\displaystyle p(x)}$ 在點 ${\displaystyle x=x_{0},\ x_{1},\dots ,\ x_{m}}$處的值, 其中 ${\displaystyle \mathbf {a} =\left(a_{0},\dots ,a_{n}\right)^{T}}$ 是係數向量, 而 ${\displaystyle \mathbf {y} =\left(y_{0},\dots ,y_{m}\right)^{T}=\left(p\left(x_{0}\right),\dots ,p\left(x_{m}\right)\right)^{T}}$ 是值的向量 (都寫作列向量的形式):

$${\displaystyle {\begin{bmatrix}1&x_{0}&x_{0}^{2}&\dots &x_{0}^{n}\\1&x_{1}&x_{1}^{2}&\dots &x_{1}^{n}\\1&x_{2}&x_{2}^{2}&\dots &x_{2}^{n}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&x_{m}&x_{m}^{2}&\dots &x_{m}^{n}\end{bmatrix}}\cdot {\begin{bmatrix}a_{0}\\a_{1}\\\vdots \\a_{n}\end{bmatrix}}={\begin{bmatrix}p\left(x_{0}\right)\\p\left(x_{1}\right)\\\vdots \\p\left(x_{m}\right)\end{bmatrix}}.}$$若 ${\displaystyle n=m}$ 且 ${\displaystyle x_{0},\dots ,x_{n}}$ 互異, 則 ${\displaystyle V}$ 是行列式不為零的方塊矩陣, 也就是可逆矩陣. 由此, 對給定的 ${\displaystyle V}$ 和 ${\displaystyle \mathbf {y} }$, 可以通過求解方程 ${\displaystyle V\mathbf {a} =\mathbf {y} }$ 來得到其係數${\displaystyle \mathbf {a} }$ 以求出所需的 ${\displaystyle p(x)}$:^[4]

${\displaystyle \mathbf {a} =V^{-1}\mathbf {y} }$.

此時, 從係數到多項式的值是以${\displaystyle V}$表示的線性雙射(一一映射), 並且此插值問題有唯一解. 這個結果叫做唯一性定理, 是多項式環上的中國剩餘定理（英語：Chinese remainder theorem#Over univariate polynomial rings and Euclidean domains）的特例.

在統計學中, 方程 ${\displaystyle V\mathbf {a} =\mathbf {y} }$ 表示範德蒙德矩陣是多項式回歸的設計矩陣.

在數值分析中, 可以樸素地使用高斯消元法作為一個算法來求解 ${\displaystyle V\mathbf {a} =\mathbf {y} }$, 其時間複雜度為 ${\displaystyle O\left(n^{3}\right)}$. 利用范德蒙德矩陣的結構, 可利用牛頓差商插值法^[5](或拉格朗日插值法^[6][7])以 ${\displaystyle O\left(n^{2}\right)}$ 的複雜度求解這個方程, 同時也給出了 ${\displaystyle V^{-1}}$ 的LU分解. 即使 ${\displaystyle V}$ 是病態的, 這個求解算法也可以得到極其精確的結果.^[2] (見多項式插值).

范德蒙德行列式可在對稱群的表示論（英語：Representation_theory_of_the_symmetric_group）使用.^[8]

當${\displaystyle x_{i}}$的值屬於一個有限域時, 范德蒙德行列式也被稱作Moore行列式（英語：Moore matrix）, 並且具有對BCH碼與里德-所羅門碼理論來說重要的性質.

離散傅里葉變換由離散傅里葉變換矩陣定義, 此矩陣是一特定的范德蒙德矩陣, 其中 ${\displaystyle x_{i}}$ 處是 ${\displaystyle n}$ 次單位根(${\displaystyle \mathrm {e} ^{\frac {2i\pi \mathrm {i} }{n}}\quad \left(i=0,\dots ,n-1\right)}$). 快速傅里葉變換通過計算此矩陣與向量的乘積達到了 ${\displaystyle O\left(n\log ^{2}\left(n\right)\right)}$的時間複雜度.^[9] 詳見多點多項式求值（英語：Polynomial_evaluation#Multipoint_evaluation）.

在物理學理論的量子霍爾效應中, 范德蒙德行列式指出, 填充因子為1的Laughlin波函數（英語：Laughlin wavefunction）等於斯萊特行列式. 然而在分數量子霍爾效應中, 對於不同於1的填充因子, 這一說法不再成立.

在多面體幾何中, 范德蒙德矩陣矩陣給出了循環多胞形（英語：cyclic polytope）任意 ${\displaystyle k}$ 維面的正規化量度. 具體來說, 若 ${\displaystyle F=C_{d}\left(t_{i_{1}},\dots ,t_{i_{k+1}}\right)}$ 是循環多胞形 ${\displaystyle C_{d}(T)\subset \mathbb {R} ^{d}}$ 的一個${\displaystyle k}$維面, 而這個循環多胞形又與 ${\displaystyle T=\{t_{1}<\cdots <t_{N}\}\subset \mathbb {R} }$ 對應, 則有 $${\displaystyle \mathrm {nvol} (F)={\frac {1}{k!}}\prod _{1\leq m<n\leq k+1}{(t_{i_{n}}-t_{i_{m}})}.}$$