循环矩阵与傅里叶变换

无意之间看到的一个结论，还挺有意思，来搬运一下。

定理

设$A= \begin{pmatrix} 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{pmatrix}, f(x)=a_0+a_1x+\cdots+a_{n-1}x^{n-1}$A=⎝⎜⎜⎜⎛​a0​an−1​⋮a1​​a1​a0​⋮a2​​⋯⋯⋱⋯​an−1​an−2​⋮a0​​⎠⎟⎟⎟⎞​,f(x)=a0​+a1​x+⋯+an−1​xn−1
则$A$A的特征值组成的集合为$\{f(\omega_n^i)|0\le i \lt n\}${f(ωni​)∣0≤i<n}
其中$\omega_n$ωn​为$n$n次单位根，$A$A的特征向量的一组基为$\{(w_n^{0},w_n^i,w_n^{2i},\cdots,w_n^{(n-1)i})|0\le i \lt n\}${(wn0​,wni​,wn2i​,⋯,wn(n−1)i​)∣0≤i<n}
即$A$A可对角化为$W^{-1}DW$W−1DW，其中$W$W为傅里叶变换的矩阵，$D$D为傅里叶变换后的点值所组成的矩阵。

证明

直接搬运了。