证明任意循环矩阵可以被傅里叶变换矩阵对角化

设循环矩阵 $A$ 的大小为 $n \times n$，其中 $n$ 是正整数。则 $A$ 可以表示为：

$$
A = \begin{bmatrix}
a_1 & a_2 & \cdots & a_{n-1} & a_n \\
a_n & a_1 & \cdots & a_{n-2} & a_{n-1} \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
a_2 & a_3 & \cdots & a_n & a_{n-1} \\
a_{n-1} & a_n & \cdots & a_2 & a_1 \\
\end{bmatrix}
$$

将 $A$ 的第一列与最后一列交换，得到新的矩阵 $B$：

$$
B = \begin{bmatrix}
a_n & a_2 & \cdots & a_{n-1} & a_1 \\
a_1 & a_n & \cdots & a_{n-2} & a_{n-1} \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
a_{n-2} & a_{n-4} & \cdots & a_1 & a_{n-3} \\
a_{n-1} & a_{n-3} & \cdots & a_2 & a_n \\
\end{bmatrix}
$$

由于 $B$ 只是 $A$ 的列交换，因此它们有相同的特征值。设 $B$ 的特征向量为 $\mathbf{v} = [v_1, v_2, \cdots, v_n]^T$，则有：

$$
AB\mathbf{v} = BA\mathbf{v} = \lambda_B\mathbf{v}
$$

其中 $\lambda_B$ 是 $B$ 的特征值。将 $B$ 的表达式代入上式，得到：

$$
\begin{aligned}
AB\mathbf{v} &= \begin{bmatrix}
a_1 & a_2 & \cdots & a_{n-1} & a_n \\
a_n & a_1 & \cdots & a_{n-2} & a_{n-1} \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
a_2 & a_3 & \cdots & a_n & a_{n-1} \\
a_{n-1} & a_n & \cdots & a_2 & a_1 \\
\end{bmatrix} \begin{bmatrix}
a_n & a_2 & \cdots & a_{n-1} & a_1 \\
a_1 & a_n & \cdots & a_{n-2} & a_{n-1} \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
a_{n-2} & a_{n-4} & \cdots & a_1 & a_{n-3} \\
a_{n-1} & a_{n-3} & \cdots & a_2 & a_n \\
\end{bmatrix} \begin{bmatrix}
v_1 \\
v_2 \\
\vdots \\
v_{n-1} \\
v_n \\
\end{bmatrix} \\
&= \begin{bmatrix}
a_n & a_2 & \cdots & a_{n-1} & a_1 \\
a_1 & a_n & \cdots & a_{n-2} & a_{n-1} \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
a_{n-2} & a_{n-4} & \cdots & a_1 & a_{n-3} \\
a_{n-1} & a_{n-3} & \cdots & a_2 & a_n \\
\end{bmatrix} \begin{bmatrix}
a_1 & a_2 & \cdots & a_{n-1} & a_n \\
a_n & a_1 & \cdots & a_{n-2} & a_{n-1} \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
a_2 & a_3 & \cdots & a_n & a_{n-1} \\
a_{n-1} & a_n & \cdots & a_2 & a_1 \\
\end{bmatrix} \begin{bmatrix}
v_1 \\
v_2 \\
\vdots \\
v_{n-1} \\
v_n \\
\end{bmatrix} \\
&= \lambda_B\begin{bmatrix}
v_n \\
v_1 \\
\vdots \\
v_{n-2} \\
v_{n-1} \\
\end{bmatrix} \\
&= \lambda_A\mathbf{v}
\end{aligned}
$$

其中 $\lambda_A$ 是 $A$ 的特征值。因此，$\mathbf{v}$ 同时也是 $A$ 的特征向量。又因为 $B$ 是循环矩阵，其所有特征向量的线性组合可以表示为：

$$
\begin{bmatrix}
v_1 & v_n & v_{n-1} & \cdots & v_2 \\
v_2 & v_1 & v_n & \cdots & v_3 \\
v_3 & v_2 & v_1 & \cdots & v_4 \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
v_n & v_{n-1} & v_{n-2} & \cdots & v_1 \\
\end{bmatrix}
$$

即矩阵 $A$ 的特征向量构成的矩阵。由于 $A$ 的特征向量构成的矩阵是可逆的，因此矩阵 $A$ 可以被傅里叶变换矩阵对角化。