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

假设 $A$ 是一个 $n\times n$ 的任意循环矩阵，即 $A$ 的每一行都是将前一行向右移动一位，使得最后一列元素移动到第一列。例如，一个 $4\times4$ 的循环矩阵可以写成：

$$
A=\begin{bmatrix} a_1 & a_2 & a_3 & a_4 \\ a_4 & a_1 & a_2 & a_3 \\ a_3 & a_4 & a_1 & a_2 \\ a_2 & a_3 & a_4 & a_1 \end{bmatrix}
$$

我们可以证明，任意循环矩阵 $A$ 可以被傅里叶变换矩阵对角化。傅里叶变换矩阵是一个 $n\times n$ 的矩阵，记作 $F_n$，其中第 $i$ 行第 $j$ 列的元素为：

$$
F_n(i,j) = \frac{1}{\sqrt{n}}e^{-2\pi i (i-1)(j-1)/n}
$$

现在我们来证明 $A$ 可以被 $F_n$ 对角化。首先，我们可以证明 $F_n$ 有一个很重要的性质：$F_n^*F_n=nI$，即 $F_n$ 的共轭转置和自身的乘积等于 $n$ 倍的单位矩阵。这个性质可以通过计算 $F_n^*F_n$ 得到：

$$
\begin{aligned}
(F_n^*F_n)_{i,j} &= \sum_{k=1}^n \overline{F_n(k,i)}F_n(k,j) \\
&= \frac{1}{n}\sum_{k=1}^ne^{2\pi i(k-1)(i-j)/n} \\
&= \begin{cases} 1 & i=j \\ 0 & i\neq j \end{cases}
\end{aligned}
$$

接下来，我们要证明的是：如果 $A$ 是一个任意循环矩阵，那么就存在一个矩阵 $U$，使得 $U$ 是幺正矩阵（即 $UU^*=U^*U=I$），并且 $U^{-1}AU$ 是对角矩阵。我们可以通过 $F_n$ 来构造这个矩阵 $U$：

$$
U = \frac{1}{\sqrt{n}}F_n
$$

首先，我们来证明 $U$ 是幺正矩阵。根据上面的性质，我们有：

$$
\begin{aligned}
UU^* &= \frac{1}{n}FF^*F_n \\
&= \frac{1}{n}F_n(nI) \\
&= I
\end{aligned}
$$

同样地，我们可以证明 $U^*U=I$。因此，$U$ 确实是一个幺正矩阵。

接下来，我们来计算 $U^{-1}AU$。首先，我们有：

$$
\begin{aligned}
U^{-1} &= \frac{1}{\sqrt{n}}F_n^{-1} \\
&= \frac{1}{\sqrt{n}}F_n^*
\end{aligned}
$$

因为 $A$ 是任意循环矩阵，所以可以将其写成一个矩阵 $B$ 的循环移位形式。例如，对于上面的 $4\times4$ 的循环矩阵 $A$，我们可以将其写成：

$$
A = \begin{bmatrix} a_1 & a_2 & a_3 & a_4 \\ a_4 & a_1 & a_2 & a_3 \\ a_3 & a_4 & a_1 & a_2 \\ a_2 & a_3 & a_4 & a_1 \end{bmatrix} = \begin{bmatrix} a_1 & a_2 & a_3 & a_4 \\ a_1 & a_2 & a_3 & a_4 \\ a_1 & a_2 & a_3 & a_4 \\ a_1 & a_2 & a_3 & a_4 \end{bmatrix} + \begin{bmatrix} 0 & 0 & 0 & 0 \\ a_4-a_1 & 0 & 0 & 0 \\ 0 & a_4-a_1 & 0 & 0 \\ 0 & 0 & a_4-a_1 & 0 \end{bmatrix}
$$

其中，第一个矩阵是 $B$，第二个矩阵是 $A-B$。注意到 $B$ 是一个常规矩阵，而 $A-B$ 的每一行都是将前一行向右移动一位。因此，我们可以将 $A-B$ 写成 $C$ 的循环移位形式，其中 $C$ 是一个 $n\times n$ 的矩阵，其第一行为 $a_4-a_1, 0, \cdots, 0$，其余行为 $0$。因此，我们有：

$$
C = \begin{bmatrix} a_4-a_1 & 0 & \cdots & 0 \\ 0 & a_4-a_1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & a_4-a_1 \end{bmatrix}
$$

于是，我们可以将 $A$ 写成 $B+C$ 的形式。接下来，我们来计算 $U^{-1}AU$：

$$
\begin{aligned}
U^{-1}AU &= \frac{1}{\sqrt{n}}F_n^*(B+C)F_n \\
&= \frac{1}{n}\sum_{i,j,k} \overline{F_n^*(i,k)}(B+C)_{k,j}F_n(j,i) \\
&= \frac{1}{n}\sum_{i,j,k} \overline{F_n(j,i)}(B+C)_{k,j}F_n(k,i)
\end{aligned}
$$

注意到 $B$ 是一个常规矩阵，因此 $BF_n=F_nB$。同时，$C$ 是一个循环矩阵，因此 $CF_n=F_nC$。因此，我们有：

$$
\begin{aligned}
U^{-1}AU &= \frac{1}{n}\sum_{i,j,k} \overline{F_n(j,i)}BF_n(k,i) + \frac{1}{n}\sum_{i,j,k} \overline{F_n(j,i)}CF_n(k,i) \\
&= B + \frac{1}{n}\sum_{i,j,k} \overline{F_n(j,i)}CF_n(k,i)
\end{aligned}
$$

因为 $C$ 是对角矩阵，所以 $CF_n$ 的每一列都是将前一列向右移动一位，使得最后一列元素移动到第一列。因此，$CF_n$ 可以写成：

$$
CF_n = \begin{bmatrix} c_1 & c_n & \cdots & c_2 \\ c_2 & c_1 & \cdots & c_3 \\ \vdots & \vdots & \ddots & \vdots \\ c_n & c_{n-1} & \cdots & c_1 \end{bmatrix}
$$

其中 $c_i$ 表示 $C$ 的第 $i$ 个对角元素。因此，我们有：

$$
\begin{aligned}
\frac{1}{n}\sum_{i,j,k} \overline{F_n(j,i)}CF_n(k,i) &= \frac{1}{n}\sum_{i,j,k} \overline{F_n(j,i)}c_kF_n(k,i) \\
&= \begin{bmatrix} \frac{1}{n}\sum_{k=1}^n c_k & 0 & \cdots & 0 \\ 0 & \frac{1}{n}\sum_{k=1}^n c_ke^{2\pi i(j-1)(k-1)/n} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \frac{1}{n}\sum_{k=1}^n c_ke^{2\pi i(j-1)(k-1)/n} \end{bmatrix}
\end{aligned}
$$

因此，我们有：

$$
U^{-1}AU = B + \begin{bmatrix} \frac{1}{n}\sum_{k=1}^n c_k & 0 & \cdots & 0 \\ 0 & \frac{1}{n}\sum_{k=1}^n c_ke^{2\pi i(j-1)(k-1)/n} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \frac{1}{n}\sum_{k=1}^n c_ke^{2\pi i(j-1)(k-1)/n} \end{bmatrix}
$$

因此，$U^{-1}AU$ 是一个对角矩阵。因此，我们证明了任意循环矩阵可以被傅里叶变换矩阵对角化。