在关于逆数论变换的上一章中，我们断言本原 $k$ 次单位根 $\omega$ 的范德蒙德矩阵 $V(\omega)$ 的逆矩阵同样是一个范德蒙德矩阵，由 $\frac{1}{k}V(\omega^{-1})$ 给出。现在我们来证明这个事实。

对数学不太感兴趣的读者可以跳过本章，这不会有任何影响。只要接受我们提出的逆矩阵是有效的，就不需要为了理解 INTT 而阅读本章。

范德蒙德矩阵的定义是每一行都是一个等比数列的矩阵。

• 第一行是 $\omega^0$ 的等比数列，从 $(\omega^0)^0$ 到 $(\omega)^{k-1}$。
• 第二行是 $\omega^1$ 的等比数列，从 $(\omega^1)^{0}$ 到 $(\omega^1)^{k -1}$。
• 以此类推，直到最后一行，即 $\omega^{k-1}$ 的等比数列，从 $(\omega^{k-1})^0$ 到 $(\omega^{k-1})^{k-1}$。

因此，$V(\omega)$ 的第 $i$ 行、第 $j$ 列的每个元素由下式给出：

考虑一个次数至多为 $k-1$ 的多项式 $f(x)$，其表达式为：

设 $S$ 为由本原 $k$ 次单位根生成的 $k$ 次单位根集合：

$f(x)$ 在集合 $S$ 上的求值向量，

可以通过将系数向量 $\mathbf{a}$ 乘以 $V(\omega)$ 来获得：

其中 $a_0, a_1, ..., a_{k-1}$ 是多项式 $f(x)$ 的系数。

等式左边的每一行都是范德蒙德矩阵的第 $i$ 行与向量 $\mathbf{a}$ 的内积。例如，第 $i$ 个元素 $f(\omega^i)$ 为：

因此，这些求值可以写成：

其中 $i\in \{0,1,2,...,k-1\}$。

关于索引的注记：在上面的等式中，我们有两个索引。索引 $i$ 表示我们正在处理哪个求值，它可以取值 $0,1,2,\ldots, k-1$。这意味着上面的公式不仅代表一个等式，而是代表 $k$ 个等式，每个 $i$ 值对应一个。例如，上面的记法是以下形式的简写：

$\omega^{ij}$ 和 $a_j$ 中的索引 $j$ 是一个求和索引，因此被求和“消耗”掉了。因为它被求和消耗了，所以它不会出现在等式的左边。索引 $i$ 和 $j$ 的选择是任意的；我们本可以使用 $m,n,p,q$ 或任何其他字母。一般来说，对于向量索引，通常使用字母表中间的字母。

现在我们想找到反向的对应关系，以便从向量 $\mathbf{y}$ 中求得向量 $\mathbf{a}$。换句话说，我们想计算 $\mathbf{a} = V^{-1}(\omega) \cdot \mathbf{y}$，其中 $V^{-1}(\omega)$ 是 $V(\omega)$ 的逆矩阵。

我们的断言是，范德蒙德矩阵 $V(\omega)$ 的逆矩阵同样是一个范德蒙德矩阵，由 $\frac{1}{k}V(\omega^{-1})$ 给出。

为了更清楚起见，我们的断言是：

其中 $\omega$ 是一个本原 $k$ 次单位根。

如果该断言正确，向量 $\mathbf{a}$ 可以按如下方式计算：

分量 $a_i$ 是 $\frac{1}{k}V(\omega^{-1})$ 的第 $i$ 行与向量 $\mathbf{y}$ 之间的内积：

这个运算可以写成如下的求和：

其中 $i\in\{0,1,2,...,k-1\}$。

出于教学原因，我们将用两种不同的方法来证明我们的断言——范德蒙德矩阵 $V(\omega)$ 的逆矩阵是另一个范德蒙德矩阵，由 $\frac{1}{k}V(\omega^{-1})$ 给出。

首先，我们将证明 $V(\omega)$ 和 $\frac{1}{k}V(\omega^{-1})$ 的矩阵乘法结果为单位矩阵 $\mathbb{I}$，也就是说：

然后，我们将证明，如果我们首先将 $V(\omega)$ 乘以 $\mathbf{a}$ 得到 $\mathbf{y}$，然后再将 $\frac{1}{k}V(\omega^{-1})$ 乘以 $V(\omega)\mathbf{a}$，我们就能恢复出 $\mathbf{a}$。

这两个证明本质上是一样的，只是用了两种不同的表达方式。

$V(\omega) \cdot \frac{1}{k}V(\omega^{-1}) = \mathbb{I}$ 的证明

我们将证明 $V(\omega)$ 与 $\frac{1}{k} V(\omega^{-1})$ 的矩阵乘法结果为单位矩阵。

该证明依赖于单位根的正交性（orthogonality property），其表示为一个求和公式。因此，我们首先将矩阵乘法写成求和的形式，以便能够使用这一正交性。

索引记法下的乘法 $V(\omega) \cdot \frac{1}{k}V(\omega^{-1})$

回顾一下，$V(\omega)$ 中第 $i$ 行、第 $m$ 列的矩阵元素由下式给出：

注：这里的行号和列号是从 $0$ 开始计算的，而不是 $1$。

例如，$V(\omega)$ 中第 $1$ 行、第 $2$ 列的元素是 $(\omega^1)^2,$ 如下方用红色高亮标出的位置：

同样，$\frac{1}{k} V(\omega^{-1})$ 中第 $m$ 行、第 $j$ 列的矩阵元素由下式给出：

例如，$\frac{1}{k} V(\omega^{-1})$ 中第 $2$ 行、第 $0$ 列的元素是 $(\omega^{-2})^0$，如下方高亮标出的位置：

因此，当这两个矩阵 $V(\omega)$ 和 $\frac{1}{k} V(\omega^{-1})$ 相乘时，所得矩阵中第 $i$ 行、第 $j$ 列的元素，是通过将 $V(\omega)$ 的第 $i$ 行（红色）与 $\frac{1}{k} V(\omega^{-1})$ 的第 $j$ 列（蓝色）相乘得到的：

我们将矩阵 $V(\omega) \cdot \frac{1}{k} V(\omega^{-1})$ 的每个元素记为 $M_{ij}$，那么它由下式给出：

现在我们需要证明元素 $M_{ij}$ 等于单位矩阵中的元素。为此，我们将使用单位根的正交性。

回顾：单位根的正交性

在关于单位根正交性的章节中，我们展示了：

简言之，上面的公式给出了两种情况下的求和结果：(1) 当 $i\equiv j$ 时，以及 (2) 当 $i \not\equiv j$ 时。我们将在下面使用这两种情况。

情况 1：当 $i\equiv j$ 时

我们想计算

在 $i\equiv j$ 时的值。单位根的正交性指出，当 $i\equiv j$ 时，

将此结果应用于 $M_{ij}$，我们有：

因此，对于对角线项（如 $M_{00}, M_{11}, M_{22},...,M_{(k-1)(k-1)}$），我们有：

情况 2：当 $i \not\equiv j$ 时

现在我们想计算

在 $i\not\equiv j$ 时的值。单位根的正交性指出，当 $i\not\equiv j$ 时，

将此结果应用于 $M_{ij}$，我们得到：

因此，对于任何非对角线项（如 $M_{10}, M_{01}, M_{12}, \dots$），我们有 $M_{ij} = 0$。

矩阵 $M$

综合考虑上面的情况 (1) 和 (2)，我们得到矩阵 $M = (M_{ij})$ 为：

这恰好是单位矩阵 $\mathbb{I}$。因此，矩阵 $V(\omega)$ 和 $\frac{1}{k} V(\omega^{-1})$ 互为逆矩阵，因为：

$\frac{1}{k}V(\omega^{-1})$ 与向量 $\mathbf{y}$ 的矩阵乘法将恢复出向量 $\mathbf{a}$

证明 $\frac{1}{k} V(\omega^{-1})$ 是 $V(\omega)$ 的逆矩阵的另一种方法，是证明它能够反转后者的操作。

也就是说，如果我们首先对 $\mathbf{a}$ 应用 $V(\omega)$ 得到 $\mathbf{y}$，

然后再对 $\mathbf{y}$ 应用 $\frac{1}{k}V(\omega^{-1})$，我们将恢复出 $\mathbf{a}$：

这正是我们将要证明的。

第一次变换：$\mathbf{y} = V(\omega) \cdot \mathbf{a}$

第一次变换通过以下矩阵运算，将系数向量 $\mathbf{a}$ 转换为求值向量 $\mathbf{y}$：

正如我们已经看到的，这个矩阵运算可以使用索引写为：

第二次变换：$\mathbf{\tilde{a}} = \frac{1}{k}V(\omega^{-1}) \mathbf{y}$

现在我们对向量 $\mathbf{y}$ 进行第二次变换，得到一个向量 $\mathbf{\tilde{a}}$：

如果我们能证明 $\mathbf{a} = \mathbf{\tilde{a}}$，那么第二次变换就是第一次变换的逆运算。

上面的矩阵运算可以写成索引形式：

现在代入 $f(\omega^i)$ 的表达式。回顾一下

其中 $i$ 只是一个可以替换为 $m$ 或任何其他字母的索引。因此，将 $\tilde{a}_j$ 结果中的 $f(\omega^m)$ 替换后，我们得到：

将其重写为双重求和的形式：

括号中的项恰好是正交关系式：

为了继续证明，我们可以像之前一样分别研究情况 (1) $i=j$ 和情况 (2) $i \neq j$，但这次我们将采用不同的方法。我们将引入一个叫做克罗内克 $\delta$ 函数（Kronecker delta）的符号。

克罗内克 $\delta$ 函数 $\delta_{ij}$ 是一个带有 2 个索引（在本例中为 $i$ 和 $j$）的符号，当 $i=j$ 时它的值为 $1$，否则为 $0$：

克罗内克 $\delta$ 函数可以被理解为单位矩阵中的元素。

使用克罗内克 $\delta$ 函数，我们可以将正交性写为：

在 $\tilde{a}_j$ 的表达式中使用克罗内克 $\delta$ 函数，我们有：

展开求和式，上面的表达式可以写成：

根据克罗内克 $\delta$ 函数的性质，求和中只有一个项是非零的。例如，对于 $j=2$，只有 $\delta_{22}$ 是非零的。因此，我们得到：

这对于任意 $j$ 都成立，因此我们得出：

对于任意 $j$ 均成立。

这表明变换 $\frac{1}{k} V(\omega^{-1})$ 是变换 $V(\omega)$ 的逆变换。

本文是我们 ZK Book 中关于数论变换系列文章的一部分