范德蒙德矩阵（Vandermonde matrix）是一种将多项式从其系数表示法转换为在一组点上的值表示法的矩阵。

对于多项式 $f(x) = a_0 +a_1x + a_2x^2+\dots+a_{k-1}x^{k-1}$，其系数表示法为：

范德蒙德矩阵通过单次运算即可计算该多项式在 $k$ 个不同点上的求值。

将多项式求值表示为矩阵乘积

为了简单起见，我们假设 $k=4$，那么我们有一个次数为 $k-1 =3$ 的多项式。

在单点上求值

多项式 $f(x)$ 在点 $x_0$ 处的求值为：

这可以写成矩阵乘积：将包含 $x_0$ 连续幂的 $1\times 4$ 矩阵乘以多项式系数向量，如下所示：

在两个点上求值

为了在 $x_0$ 和 $x_1$ 两个点上求值，我们可以将它们表示为两个独立的矩阵乘积。不过，我们可以将这些行向量堆叠成一个 $2 \times 4$ 矩阵：

其中每一行分别包含 $x_0$ 和 $x_1$ 的连续幂。

因此，在两个点上对多项式求值等价于将一个 $2 \times k = 2 \times 4$ 矩阵乘以系数向量。

在 $4$ 个点上求值

如果我们将点扩展到 $4$ 个点，在假设 $k=4$ 的情况下，所得到的方程组等价于将一个 $k\times k = 4\times 4$ 矩阵乘以系数向量：

这个矩阵被称为 $4\times 4$ 的范德蒙德矩阵，记作 $\mathbf{V}$。

上面的等式可以简写为以下形式：

其中 $\mathbf{a}$ 是多项式的系数向量，$\mathbf{p}$ 是其点值向量。

在 4 次单位根上将多项式求值表示为矩阵乘积

现在，考虑在 4 次单位根 $\{\omega^0, \omega^1, \omega^{2}, \omega^{3}\}$ 上对多项式 $f(x)$ 求值，而不是在任意的 $4$ 个点上。我们得到的范德蒙德矩阵 $\mathbf{V}$ 如下：

我们可以利用 $\omega^{\frac{k}{2}} = \omega^2 = -1$ 和 $\omega^k=1$ 的性质，化简大于等于 $\omega^{\frac{k}{2}}$ 的每一项，如下所示：

• $\omega^2 \equiv -1$ 意味着 $(\omega^2)^2 \equiv (-1)^2 = 1$ 且 $(\omega^2)^3 \equiv (-1)^3 = -1$。
• $\omega^3 = \omega^2\cdot\omega\equiv -1\cdot\omega = -\omega$ 意味着：
  • $(\omega^3)^2 \equiv (-\omega)^2 = \omega^2\equiv -1$ 且
  • $(\omega^3)^3 \equiv (-\omega)^3 = -\omega^3 =-(-\omega) =\omega$。

我们现在将这些化简结果代入矩阵中：

因此，该矩阵化简为以下模式：

举个具体的例子，$\omega=13$ 是有限域 $\mathbb{F}_{17}$（其算术运算为模 17）中的本原 4 次单位根，此时范德蒙德矩阵为：

结论

在一个 $k-1$ 次多项式的 $k$ 个点上求值，等价于将一个 $k \times k$ 范德蒙德矩阵 $\mathbf{V}$ 乘以系数向量 $\mathbf{a}$，该过程可以用公式 $\mathbf{V}\cdot\mathbf{a} = \mathbf{p}$ 进行形式化表示。