离散傅里叶变换矩阵

离散傅里叶变换矩阵是将离散傅里叶变换以矩阵乘法来表达的一种表示式。

定义

N点的离散傅里叶变换可以用一个 $n\times m$ 的矩阵乘法来表示，即 $X=Wx$ ，其中 $x$ 是原始的输入信号， $X$ 是经过离散傅里叶变换得到的输出信号。一个 $n\times n$ 的变换矩阵 $W$ 可以定义成 $W=(\omega ^{ij})_{i,j=0,\ldots ,N-1}/{\sqrt {N}}$ ，或等效如下：

W={\frac {1}{\sqrt {N}}}{\begin{bmatrix}1&1&1&1&\cdots &1\\1&\omega &\omega ^{2}&\omega ^{3}&\cdots &\omega ^{N-1}\\1&\omega ^{2}&\omega ^{4}&\omega ^{6}&\cdots &\omega ^{2(N-1)}\\1&\omega ^{3}&\omega ^{6}&\omega ^{9}&\cdots &\omega ^{3(N-1)}\\\vdots &\vdots &\vdots &\vdots &&\vdots \\1&\omega ^{N-1}&\omega ^{2(N-1)}&\omega ^{3(N-1)}&\cdots &\omega ^{(N-1)(N-1)}\\\end{bmatrix}},

其中 $\omega$ 是 $1$ 的 $n$ 次方根的主值（primitive nth root of unity）,大小为 $e^{\frac {-2\pi i}{N}}$ 。需要注意的是在总和前面的正规化因数 ${\frac {1}{\sqrt {N}}}$ ，还有 $\omega$ 中指数的正负号是依据惯例，并且会因为处理的方法有所不同。以下所有的讨论考虑到大多数的细节变动且不论是否为一般惯例均适用之。唯一重要的是，正变换和逆变换有相反的指数正负号标志，而其正规化因数乘积为 ${\frac {1}{N}}$ 。然而，这里为了使得最后的离散傅里叶变换矩阵结果正规化所选择的因数，在许多情况下都是通用的。

快速傅里叶变换算法利用矩阵的对称性与W的周期性，以减少乘法所需要的时间（把计算复杂度从 $O(N^{2})$ 降为 $O(N\log N)$ ）。类似的方法也可适用于其他矩阵乘法如阿达马矩阵和沃尔什矩阵。

特殊情况

3点的离散傅里叶变换具有特殊的意义。例如：Charles LeGeyt Fortescue（英语：Charles LeGeyt Fortescue）于1918年所发表的对称分量变换（Symmetrical Components Transform, SCT），它定义了三相平衡（three phase balance），即3点离散傅里叶变换可分解成一个直流成分，以及两个交流成分（一个是顺时针相位，另一个为逆时针相位）。

例子

两点离散傅里叶变换矩阵

两点的离散傅里叶变换是一个很简单的例子，其第一列代表是直流成分（总和）和第二列是交流成分（差异）。

{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}/{\sqrt {2}}

第一列处理总和的部分，第二列处理相差的部分。因数 $1/{\sqrt {2}}$ 致使整个矩阵规一化（见下文）。

四点离散傅里叶变换矩阵

四点的离散傅里叶变换矩阵如下：

{\frac {1}{2}}{\begin{bmatrix}1&1&1&1\\1&-i&(-i)^{2}&(-i)^{3}\\1&(-i)^{2}&(-i)^{4}&(-i)^{6}\\1&(-i)^{3}&(-i)^{6}&(-i)^{9}\end{bmatrix}}.

八点离散傅里叶变换矩阵

八点的离散傅里叶变换矩阵如下：

W={\frac {1}{\sqrt {8}}}{\begin{bmatrix}\omega ^{0}&\omega ^{0}&\omega ^{0}&\ldots &\omega ^{0}\\\omega ^{0}&\omega ^{1}&\omega ^{2}&\ldots &\omega ^{7}\\\omega ^{0}&\omega ^{2}&\omega ^{4}&\ldots &\omega ^{14}\\\omega ^{0}&\omega ^{3}&\omega ^{6}&\ldots &\omega ^{21}\\\omega ^{0}&\omega ^{4}&\omega ^{8}&\ldots &\omega ^{28}\\\omega ^{0}&\omega ^{5}&\omega ^{10}&\ldots &\omega ^{35}\\\vdots &&\vdots &\ddots &\vdots \\\omega ^{0}&\omega ^{7}&\omega ^{14}&\ldots &\omega ^{49}\\\end{bmatrix}}

其中

\omega =e^{-{\frac {2\pi i}{8}}}={\frac {1}{\sqrt {2}}}-{\frac {i}{\sqrt {2}}}

以下用图片来解说离散傅里叶变换的矩阵乘法概念：

图中实部（余弦波）是由实线代表，虚部（正弦波）由虚线代表。最上面一行全为1，（透过乘上 $1/{\sqrt {8}}$ 来规一化），因此这个部分代表输入信号的直流分量。下一行是8个负一次循环的复指数取样（samples of negative one cycle of complex exponential），即分频（fractional frequency）为−1/8倍频率的信号。因此，这一行代表在分频+1/8的信号强度。再下一行是8个负二次循环的复指数取样，所以它代表-1/4倍的分频。因此，这一行代表在分频+1/4的信号强度。以下总结了八点离散傅里叶变换代表的意义，依行排序，以分频表示：

0代表直流信号成分
-1/8代表分频为+1/8 的信号强度
-1/4代表分频为+1/4 的信号强度
-3/8代表分频为+3/8 的信号强度
-1/2代表分频为+1/2 的信号强度
-5/8代表分频为+5/8 的信号强度
-3/4代表分频为+3/4 的信号强度
-7/8代表分频为+7/8 的信号强度

等效上最后一行，可以当作是分频为+1/8即代表分频-1/8的信号强度。如此一来，则可以说这个矩阵的上面列是信号的正频率部分的强度而下面列是信号负频率部分的强度。

规一化变换（unitary transform）

离散傅里叶变换（或可能是透过适当的尺度选择）是一个规一化的变换，即符合能量保留（preserves energy）。可以达到规一化的合适尺度是 $1/{\sqrt {N}}$ ，这使得能量物理意义上跟在傅里叶定义上是一样的，即满足傅里叶变换（帕塞瓦尔定理）。（其他未规一化的尺度，也普遍被使用以方便计算；例如，折积（折积定理）需较简单的形式与尺度选择，详述于离散傅里叶变换条目中）。