一个重要的公式

下面 循环矩阵 的行列式

[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}^nfw^i)
]

其中 fx)=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^{id-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^{id+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}fw^i)
end{aligned}
]

暂时略去 n^{-n})，我们不仅可以写成两个矩阵的相乘，还得到了 fw^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^{2n-1)}\
vdots&vdots&vdots&ddots&vdots\
1&w^{n-1}&w^{2n-1)}&cdots&w^{n-1)n-1)}
end{matrix}
ight]
imes
left[
egin{matrix}
f1)&w^{-1}f1)&w^{-2}f1)&cdots&w^{-n-1)}f1)\
fw^1)&w^{-1}fw^1)&w^{-2}fw^1)&cdots&w^{-n-1)}fw^1)\
fw^2)&w^{-1}fw^2)&w^{-2}fw^2)&cdots&w^{-n-1)}fw^2)\
vdots&vdots&vdots&ddots&vdots\
fw^{n-1})&w^{-1}fw^{n-1})&w^{-2}fw^{n-1})&cdots&w^{-n-1)}fw^{n-1})
end{matrix}
ight]
]

注意到

[detAB)=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^{2n-1)}\
vdots&vdots&vdots&ddots&vdots\
1&w^{n-1}&w^{2n-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^{-2n-1)}\
vdots&vdots&vdots&ddots&vdots\
1&w^{-n-1)}&w^{-2n-1)}&cdots&w^{-n-1)n-1)}
end{matrix}
ight]
=nI
]

故行列式为

[n^nprod_{i=0}^{n-1}fw^i)
]

乘上 n^n) 即证等式。

网上大佬给的证明

懒，直接挂图了 QwQ。