一个重要的公式

下面 循环矩阵 的行列式

[detleft[
egin{matrix}
a_0&a_1&cdots&a_{n-1}\
a_{n-1}&a_0&cdots&a_{n-2}\
vdots&vdots&ddots&vdots\
a_1&a_2&cdots&a_0
end{matrix}
ight]=prod_{i=0}^nf(w^i)
]

其中 (f(x)=sum_{i=0}^{n-1}a_ix^i)。

自己的菜鸡证明

发现下标极其富有规律，想到了什么？

引理 1：

[sum_{i=0}^{n-1}frac{w^{id}}n=[nmid d]
]

引理证明只需分类讨论 (w^i) 是否为 (1) 即可，如果为 (1) 不能使用等比数列求和。

为了让 (a_i) 在合适的时候出现，不难写出来这样的形式

[sum_{d=0}^{n-1}a_dsum_{i=0}^{n-1}frac{w^{i(d-t)}}n=a_t
]

记该循环矩阵为 (P)，则 (p_{x,y}=a_{(y-x)mod n})，代入得：

[p_{x,y}=sum_{d=0}^{n-1}a_dsum_{i=0}^{n-1}frac{w^{i(d+x-y)}}n
]

再想一想这个式子，发现里面含有 (i) ？只有在矩阵乘法的时候会遇到。我们尝试将其写成两个矩阵相乘的形式

[egin{aligned}
p_{x,y}&=sum_{i=0}^{n-1}w^{ix}w^{-iy}frac1nsum_{d=0}^{n-1}a_dw^{id}\
&=sum_{i=0}^{n-1}w^{ix}w^{-iy}n^{-n}f(w^i)
end{aligned}
]

暂时略去 (n^{-n})，我们不仅可以写成两个矩阵的相乘，还得到了 (f(w^i))

[left[
egin{matrix}
1&1&1&cdots&1\
1&w^1&w^2&cdots&w^{n-1}\
1&w^2&w^4&cdots&w^{2(n-1)}\
vdots&vdots&vdots&ddots&vdots\
1&w^{n-1}&w^{2(n-1)}&cdots&w^{(n-1)(n-1)}
end{matrix}
ight]
imes
left[
egin{matrix}
f(1)&w^{-1}f(1)&w^{-2}f(1)&cdots&w^{-(n-1)}f(1)\
f(w^1)&w^{-1}f(w^1)&w^{-2}f(w^1)&cdots&w^{-(n-1)}f(w^1)\
f(w^2)&w^{-1}f(w^2)&w^{-2}f(w^2)&cdots&w^{-(n-1)}f(w^2)\
vdots&vdots&vdots&ddots&vdots\
f(w^{n-1})&w^{-1}f(w^{n-1})&w^{-2}f(w^{n-1})&cdots&w^{-(n-1)}f(w^{n-1})
end{matrix}
ight]
]

注意到

[det(AB)=det Adet B
]

和

[det A=det A^T
]

并且在 FFT 中，有

[left[
egin{matrix}
1&1&1&cdots&1\
1&w^1&w^2&cdots&w^{n-1}\
1&w^2&w^4&cdots&w^{2(n-1)}\
vdots&vdots&vdots&ddots&vdots\
1&w^{n-1}&w^{2(n-1)}&cdots&w^{(n-1)(n-1)}
end{matrix}
ight]
imes
left[
egin{matrix}
1&1&1&cdots&1\
1&w^{-1}&w^{-2}&cdots&w^{-(n-1)}\
1&w^{-2}&w^{-4}&cdots&w^{-2(n-1)}\
vdots&vdots&vdots&ddots&vdots\
1&w^{-(n-1)}&w^{-2(n-1)}&cdots&w^{-(n-1)(n-1)}
end{matrix}
ight]
=nI
]

故行列式为

[n^nprod_{i=0}^{n-1}f(w^i)
]

乘上 (n^n) 即证等式。

网上大佬给的证明

懒，直接挂图了 QwQ。