FFT，FWT问题里面遇到的矩阵

在FFT问题里面，我们遇到的问题是多项式单点求值和其逆运算。我们找到多个自变量，代入多项式中，然后将对应的结果值相乘，然后通过逆运算反推结果多项式的结构，其中，通过多项式上的点推出多项式的系数，我们使用拉格朗日插值，但是这个公式和线性代数之间有什么联系吗：

$f_i(x)=y_i \prod_{i \not =j} \frac{x-x_i}{x_j-x_i},f(x)=\sum f_i(x)$

其本质就是：给你一个范德蒙德矩阵：

$A=\begin{bmatrix} 1& 1 & 1& \cdots & 1\\ x_0& x_1& x_2& \cdots & x_n\\ x_0^2& x_1^2 & x_ 2^2& \cdots & x_n^2\\ \vdots& \vdots& \vdots& \ddots& \vdots\\ x_0^n & x_1^n& x_2^n & \cdots & x_n^n \end{bmatrix}$

然后给你结果的矩阵：

$y=\begin{bmatrix}y_0 \\ y_1 \\ \vdots \\y_n \end{bmatrix}$

问系数矩阵 $a$，使得 $aA=y$。于是我们的任务就是求 $A^{-1}$。从拉格朗日插值的角度考虑，$(A^{-1})_{ij}=[x^{j-1}] \prod_{k \not=i} \frac{x-x_k}{x_i-x_k}$。当然我们也可以用伴随矩阵算出 $A^{-1}$，但是比较复杂。

当 $A=V(\omega_n^0,\omega_n^{1},\omega_n^{2},\cdots,\omega_n^{n-1})$，这种情况比较简单就可以求出逆矩阵，下面我们验证 $A^{-1}=\frac{1}{n} V(\omega_n^0,\omega_n^{-1},\omega_n^{-2},\cdots,\omega_n^{-n+1})$。这个等价于验证：$(AV(\omega_n^0,\omega_n^{-1},\omega_n^{-2},\cdots,\omega_n^{-n+1}))_{ij}=n\delta_{i,j}$：

$(A^2)_{ij}=\sum_{k=0}^{n-1} (\omega_n^i)^k (\omega_n^{-k})^j=(\sum_{k=0}^{n-1} \omega_{n}^{k(i-j)})$

众所周知，$i-j=0$ 时上式的值为 $n$，否则值为 $0$。

FWT 问题操作的下标都可以表示为若干个向量按顺序组成的向量序列，我们可以证明，FWT 问题操作的各个向量都是独立的，于是问题转化为对每个位置上的向量该如何操作。在这种问题中，我们最常遇到的就是范德蒙德矩阵。范德蒙德矩阵自然也有其意义，表示将 $x_1,x_2,\cdots,x_n$ 代入多项式中，计算出多项式的值，所以求得范德蒙德矩阵的逆矩阵自然对应求解对应多项式的过程。

$\begin{bmatrix} 1& 1 & 1& \cdots & 1\\ 1& \omega_p^1& \omega_p^2& \cdots & \omega_p^{p - 1}\\ 1& \omega_p^2 & \omega_p^4& \cdots & w_p^{2(p - 1)}\\ \vdots& \vdots& \vdots& \ddots& \vdots\\ 1& \omega_p^{p - 1}& \omega_p^{2(p - 1)} & \cdots & \omega_p^{(p - 1)(p - 1)} \end{bmatrix}$