范德蒙德矩阵

在线性代数中, 范德蒙德矩阵(也译作范德蒙矩阵)得名于亚历山大‑泰奥菲勒·范德蒙德. 范德蒙德矩阵是一个各行(row)呈现出几何级数关系的矩阵: 它是一个$\left(m+1\right)\times \left(n+1\right)$矩阵

$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}}$

其中每一项是$V_{i,j}=x_{i}^{j}$, 也就是$x_{i}$的$j$次方, 其中下标$i$和$j$从0开始. 有些作者将范德蒙德矩阵定义为上述矩阵的转置.

当$n=m$时, 即范德蒙德矩阵为方阵时, 其行列式称作范德蒙德行列式或范德蒙德多项式. 范德蒙德行列式的值为:

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

范德蒙德行列式非零当且仅当所有$x_{i}$互异(即任意二者皆不相等), 此时范德蒙德矩阵可逆.

应用

多项式插值问题就是取找到一个多项式 $p\left(x\right)=a_{0}+a_{1}x+a_{2}x^{2}+\dots +a_{n}x^{n}$ 对给定的数据点 $\left(x_{0},y_{0}\right),\dots ,\left(x_{m},y_{m}\right)$ 满足 $p\left(x_{0}\right)=y_{0},\dots ,p\left(x_{m}\right)=y_{m}$. 这个问题可以在之后以范德蒙德矩阵为工具, 用线性代数的语言改述. 通过矩阵乘法$V\mathbf {a} =\mathbf {y}$, $V$ 可以计算 $p(x)$ 在点 $x=x_{0},\ x_{1},\dots ,\ x_{m}$处的值, 其中 $\mathbf {a} =\left(a_{0},\dots ,a_{n}\right)^{T}$ 是系数向量, 而 $\mathbf {y} =\left(y_{0},\dots ,y_{m}\right)^{T}=\left(p\left(x_{0}\right),\dots ,p\left(x_{m}\right)\right)^{T}$ 是值的向量 (都写作列向量的形式):

$${\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}}.$$若 $n=m$ 且 $x_{0},\dots ,x_{n}$ 互异, 则 $V$ 是行列式不为零的方块矩阵, 也就是可逆矩阵. 由此, 对给定的 $V$ 和 $\mathbf {y}$, 可以通过求解方程 $V\mathbf {a} =\mathbf {y}$ 来得到其系数$\mathbf {a}$ 以求出所需的 $p(x)$:

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

此时, 从系数到多项式的值是以$V$表示的线性双射(一一映射), 并且此插值问题有唯一解. 这个结果叫做唯一性定理, 是多项式环上的中国剩余定理的特例.

在统计学中, 方程 $V\mathbf {a} =\mathbf {y}$ 表示范德蒙德矩阵是多项式回归的设计矩阵.

在数值分析中, 可以朴素地使用高斯消元法作为一个算法来求解 $V\mathbf {a} =\mathbf {y}$, 其时间复杂度为 $O\left(n^{3}\right)$. 利用范德蒙德矩阵的结构, 可利用牛顿差商插值法(或拉格朗日插值法)以 $O\left(n^{2}\right)$ 的复杂度求解这个方程, 同时也给出了 $V^{-1}$ 的LU分解. 即使 $V$ 是病态的, 这个求解算法也可以得到极其精确的结果. (见多项式插值).

范德蒙德行列式可在对称群的表示论使用.

当$x_{i}$的值属于一个有限域时, 范德蒙德行列式也被称作Moore行列式, 并且具有对BCH码与里德-所罗门码理论来说重要的性质.

离散傅里叶变换由离散傅里叶变换矩阵定义, 此矩阵是一特定的范德蒙德矩阵, 其中 $x_{i}$ 处是 $n$ 次单位根($\mathrm {e} ^{\frac {2i\pi \mathrm {i} }{n}}\quad \left(i=0,\dots ,n-1\right)$). 快速傅里叶变换通过计算此矩阵与向量的乘积达到了 $O\left(n\log ^{2}\left(n\right)\right)$的时间复杂度. 详见多点多项式求值.

在物理学理论的量子霍尔效应中, 范德蒙德行列式指出, 填充因子为1的Laughlin波函数等于斯莱特行列式. 然而在分数量子霍尔效应中, 对于不同于1的填充因子, 这一说法不再成立.

在多面体几何中, 范德蒙德矩阵矩阵给出了循环多胞形任意 $k$ 维面的正规化量度. 具体来说, 若 $F=C_{d}\left(t_{i_{1}},\dots ,t_{i_{k+1}}\right)$ 是循环多胞形 $C_{d}(T)\subset \mathbb {R} ^{d}$ 的一个$k$维面, 而这个循环多胞形又与 $T=\{t_{1}<\cdots <t_{N}\}\subset \mathbb {R}$ 对应, 则有 $$\mathrm {nvol} (F)={\frac {1}{k!}}\prod _{1\leq m<n\leq k+1}{(t_{i_{n}}-t_{i_{m}})}.$$

参阅

• 拉格朗日多项式
• 朗斯基行列式