一个重要的公式
下面 循环矩阵 的行列式
\[\det\left[
\begin{matrix}
a_0&a_1&\cdots&a_{n-1}\a_{n-1}&a_1&\cdots&a_{n-2}\\vdots&\vdots&\ddots&\vdots\a_1&a_2&\cdots&a_0
\end{matrix}
\right]=\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=[n\mid d]
\]
引理证明只需分类讨论 \(w^i\) 是否为 \(1\) 即可，如果为 \(1\) 不能使用等比数列求和。
为了让 \(a_i\) 在合适的时候出现，不难写出来这样的形式
\[\sum_{d=0}^{n-1}a_d\sum_{i=0}^{n-1}\frac{w^{i(d-t)}}n=a_t
\]
记该循环矩阵为 \(P\)，则 \(p_{x,y}=a_{(y-x)\bmod n}\)，代入得：
\[p_{x,y}=\sum_{d=0}^{n-1}a_d\sum_{i=0}^{n-1}\frac{w^{i(d+x-y)}}n
\]
再想一想这个式子，发现里面含有 \(i\) ？只有在矩阵乘法的时候会遇到。我们尝试将其写成两个矩阵相乘的形式
\[\begin{aligned}
p_{x,y}&=\sum_{i=0}^{n-1}w^{ix}w^{-iy}\frac1n\sum_{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[
\begin{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}
\right]
\times
\left[
\begin{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}
\right]
\]
注意到
\[\det(AB)=\det A\det B
\]
和
\[\det A=\det A^T
\]
并且在 FFT 中，有
\[\left[
\begin{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}
\right]
\times
\left[
\begin{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}
\right]
=nI
\]
故行列式为
\[n^n\prod_{i=0}^{n-1}f(w^i)
\]
乘上 \(n^n\) 即证等式。
网上大佬给的证明
懒，直接挂图了 QwQ。
循环矩阵的行列式
原文：https://www.cnblogs.com/ac-evil/p/14734728.html
