用线性代数的眼光来看离散傅立叶变换

如果 $x$ 和 $c$ 都是长度为 $n$ 的向量，那么它们循环卷积的结果 $y$ 就有

y_k = (x \otimes c)_k = \sum_{i=0}^{n-1} x_i c_{k-i}

其中 $c_{k-i}$ 代表循环移位。

将 $c$ 的循环移位写成矩阵的形式

C= \begin{bmatrix} c_0 & c_{n-1} & \dots & c_{2} & c_{1} \\ c_{1} & c_0 & c_{n-1} & & c_{2} \\ \vdots & c_{1}& c_0 & \ddots & \vdots \\ c_{n-2} & & \ddots & \ddots & c_{n-1} \\ c_{n-1} & c_{n-2} & \dots & c_{1} & c_0 \\ \end{bmatrix}

于是就有

y = Cx

举个例子：

\begin{bmatrix} 16 \\ 14 \\ 16 \\ 14 \\ \end{bmatrix} =\begin{bmatrix} 1 & 4 & 3 & 2 \\ 2 & 1 & 4 & 3 \\ 3 & 2 & 1 & 4 \\ 4 & 3 & 2 & 1 \\ \end{bmatrix} \begin{bmatrix} 1 \\ 2 \\ 1 \\ 2 \\ \end{bmatrix}

其中 $C$ 可以用另一种方式表示：

C=f(P)=c_0I+c_1P+c_2P^2+\ldots+c_{n-1}P^{n-1}

$P$ 矩阵是一个置换矩阵，也被称作循环矩阵。

P= \begin{bmatrix} 0&0&\ldots&0&1\\ 1&0&\ldots&0&0\\ 0&\ddots&\ddots&\vdots&\vdots\\ \vdots&\ddots&\ddots&0&0\\ 0&\ldots&0&1&0 \end{bmatrix}

它可以表示为

\begin{pmatrix} 0 & I_{n-k} \\ I_k & 0 \end{pmatrix}

可以得到 $\vert P - \lambda I_n\vert = \lambda^n - 1$ ，也可以通过 $P^n = I$ 来得到 $\lambda^n = 1$ 。根据 $e^{-j2\pi k} = 1$ ，解出来得到 $\lambda_k = e^{\frac{-j2\pi k}{n}} = \omega^k$ ，计算可以得到 $P\alpha_k = \omega^k(\alpha_{k(n-1)}, \alpha_{k(0)}, \cdots, \alpha_{k(n-3)}, \alpha_{k(n-2)})^T$ 。

这里不明白 $\omega = e^{-j2\pi/n}$ ，还是 $\omega = e^{j2\pi/n}$ ，感觉是一样的。

从而有 $\alpha_{k(i)} = \omega^k\alpha_{k(i-1)}$ 前一项乘以 $\omega^{k}$ 等于后一项，最后一项乘以 $\omega^{k}$ 得到第一项。如果 $\alpha_{k} = (1, \omega^{k}, \omega^{2k}, \cdots, \omega^{(n-1)k})^T$ 就正好满足，其中有 $\omega^{kn}=\omega^{k0}=1$ 。