第二十七讲：复数矩阵和快速傅里叶变换 ​

本讲主要介绍复数向量、复数矩阵的相关知识（包括如何做复数向量的点积运算、什么是复数对称矩阵等），以及傅里叶矩阵（最重要的复数矩阵）和快速傅里叶变换。

复数矩阵运算 ​

先介绍复数向量，我们不妨换一个字母符号来表示：$z=\left[\begin{array}{c}{z}_1\\ z_2\\ ⋮\\ z_n\end{array}\right]$，向量的每一个分量都是复数。此时$z$不再属于${\mathbb{R}}^n$实向量空间，它现在处于${\mathbb{C}}^n$复向量空间。

计算复向量的模 ​

对比实向量，我们计算模只需要计算$\left|v\right|=\sqrt{v^{T}v}$即可，而如果对复向量使用$z^{T}z$则有$z^{T}z=\left[\begin{array}{cccc}{z}_1& z_2& \cdots & z_n\end{array}\right]\left[\begin{array}{c}{z}_1\\ z_2\\ ⋮\\ z_n\end{array}\right]=z_1^2+z_2^2+\cdots +z_n^2$，这里$z_i$是复数，平方后虚部为负，求模时本应相加的运算变成了减法。（如向量$\left[\begin{array}{cc}1& i\end{array}\right]$，右乘其转置后结果为$0$，但此向量的长度显然不是零。）

根据上一讲我们知道，应使用$\left|z\right|=\sqrt{{\overline{z}}^{T}z}$，即$\left[\begin{array}{cccc}{\overline{z}}_1& {\overline{z}}_2& \cdots & {\overline{z}}_n\end{array}\right]\left[\begin{array}{c}{z}_1\\ z_2\\ ⋮\\ z_n\end{array}\right]$，即使用向量共轭的转置乘以原向量即可。（如向量$\left[\begin{array}{cc}1& i\end{array}\right]$，右乘其共轭转置后结果为$\left[\begin{array}{cc}1& -i\end{array}\right]\left[\begin{array}{c}1\\ i\end{array}\right]=2$。）

我们把共轭转置乘以原向量记为$z^{H}z$，$H$读作埃尔米特（人名为Hermite，形容词为Hermitian）

计算向量的内积 ​

有了复向量模的计算公式，同理可得，对于复向量，内积不再是实向量的$y^{T}x$形式，复向量内积应为$y^{H}x$。

对称性 ​

对于实矩阵，$A^T=A$即可表达矩阵的对称性。而对于复矩阵，我们同样需要求一次共轭${\overline{A}}^T=A$。举个例子$\left[\begin{array}{cc}2& 3+i\\ 3-i& 5\end{array}\right]$是一个复数情况下的对称矩阵。这叫做埃尔米特矩阵，有性质$A^H=A$。

正交性 ​

在第十七讲中，我们这样定义标准正交向量：$q_i^T{q}_j=\{\begin{array}{l}0i\ne j\\ 1i=j\end{array}$。现在，对于复向量我们需要求共轭：${\overline{q}}_i^T{q}_j=q_i^H{q}_j=\{\begin{array}{l}0i\ne j\\ 1i=j\end{array}$。

第十七讲中的标准正交矩阵：$Q=[q_1{q}_2\cdots q_n]$有$Q^{T}Q=I$。现在对于复矩阵则有$Q^{H}Q=I$。

就像人们给共轭转置起了个“埃尔米特”这个名字一样，正交性（orthogonal）在复数情况下也有了新名字，酉（unitary），酉矩阵（unitary matrix）与正交矩阵类似，满足$Q^{H}Q=I$的性质。而前面提到的傅里叶矩阵就是一个酉矩阵。

傅里叶矩阵 ​

$n$阶傅里叶矩阵$F_n=\left[\begin{array}{ccccc}1& 1& 1& \cdots & 1\\ 1& w& w^2& \cdots & w^{n-1}\\ 1& w^2& w^4& \cdots & w^{2(n-1)}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 1& w^{n-1}& w^{2(n-1)}& \cdots & w^{(n-1{)}^2}\end{array}\right]$，对于每一个元素有$(F_n{)}_{ij}=w^{ij}i,j=0,1,2,\cdots ,n-1$。矩阵中的$w$是一个非常特殊的值，满足$w^n=1$，其公式为$w=e^{i2\pi /n}$。易知$w$在复平面的单位圆上，$w=\cos \frac{2\pi }{n}+i\sin \frac{2\pi }{n}$。

在傅里叶矩阵中，当我们计算$w$的幂时，$w$在单位圆上的角度翻倍。比如在$6$阶情形下，$w=e^{2\pi /6}$，即位于单位圆上${60}^{\circ }$角处，其平方位于单位圆上${120}^{\circ }$角处，而$w^6$位于$1$处。从开方的角度看，它们是$1$的$6$个六次方根，而一次的$w$称为原根。

• 我们现在来看$4$阶傅里叶矩阵，先计算$w$有$w=i,w^2=-1,w^3=-i,w^4=1$，$F_4=\left[\begin{array}{cccc}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{array}\right]=\left[\begin{array}{cccc}1& 1& 1& 1\\ 1& i& -1& -i\\ 1& -1& 1& -1\\ 1& -i& -1& i\end{array}\right]$。

  矩阵的四个列向量正交，我们验证一下第二列和第四列，${\overline{c_2}}^T{c}_4=1-0+1-0=0$，正交。不过我们应该注意到，$F_4$的列向量并不是标准的，我们可以给矩阵乘上系数$\frac{1}{2}$（除以列向量的长度）得到标准正交矩阵$F_4=\frac{1}{2}\left[\begin{array}{cccc}1& 1& 1& 1\\ 1& i& -1& -i\\ 1& -1& 1& -1\\ 1& -i& -1& i\end{array}\right]$。此时有$F_4^H{F}_4=I$，于是该矩阵的逆矩阵也就是其共轭转置$F_4^H$。

快速傅里叶变换（Fast Fourier transform/FFT） ​

对于傅里叶矩阵，$F_6,F_3$、$F_8,F_4$、$F_{64},F_{32}$之间有着特殊的关系。

举例，有傅里叶矩阵$F_{6}4$，一般情况下，用一个列向量右乘$F_{64}$需要约${64}^2$次计算，显然这个计算量是比较大的。我们想要减少计算量，于是想要分解$F_{64}$，联系到$F_{32}$，有$[F_{64}]=\left[\begin{array}{cc}I& D\\ I& -D\end{array}\right]\left[\begin{array}{cc}{F}_{32}& 0\\ 0& F_{32}\end{array}\right]\left[\begin{array}{cccccccccc}1& & \cdots & & & 0& & \cdots & & \\ 0& & \cdots & & & 1& & \cdots & & \\ & 1& \cdots & & & & 0& \cdots & & \\ & 0& \cdots & & & & 1& \cdots & & \\ & & & \ddots & & & & & \ddots & & \\ & & & \ddots & & & & & \ddots & & \\ & & & \cdots & 1& & & & \cdots & 0\\ & & & \cdots & 0& & & & \cdots & 1\end{array}\right]$。

我们分开来看等式右侧的这三个矩阵：

• 第一个矩阵由单位矩阵$I$和对角矩阵$D=\left[\begin{array}{ccccc}1& & & & \\ & w& & & \\ & & w^2& & \\ & & & \ddots & \\ & & & & w^{31}\end{array}\right]$组成，我们称这个矩阵为修正矩阵，显然其计算量来自$D$矩阵，对角矩阵的计算量约为$32$即这个修正矩阵的计算量约为$32$，单位矩阵的计算量忽略不计。

• 第二个矩阵是两个$F_{32}$与零矩阵组成的，计算量约为$2\times {32}^2$。

• 第三个矩阵通常记为$P$矩阵，这是一个置换矩阵，其作用是讲前一个矩阵中的奇数列提到偶数列之前，将前一个矩阵从$[x_0{x}_1\cdots ]$变为$[x_0{x}_2\cdots x_1{x}_3\cdots ]$，这个置换矩阵的计算量也可以忽略不计。（这里教授似乎在黑板上写错了矩阵，可以参考FFT、How the FFT is computed做进一步讨论。）

所以我们把${64}^2$复杂度的计算化简为$2\times {32}^2+32$复杂度的计算，我们可以进一步化简$F_{32}$得到与$F_{16}$有关的式子$\left[\begin{array}{cc}{I}_{32}& D_{32}\\ I_{32}& -D_{32}\end{array}\right]\left[\begin{array}{cccc}{I}_{16}& D_{16}& & \\ I_{16}& -D_{16}& & \\ & & I_{16}& D_{16}\\ & & I_{16}& -D_{16}\end{array}\right]\left[\begin{array}{cccc}{F}_{16}& & & \\ & F_{16}& & \\ & & F_{16}& \\ & & & F_{16}\end{array}\right]\left[\begin{array}{cc}{P}_{16}& \\ & P_{16}\end{array}\right][P_{32}]$。而${32}^2$的计算量进一步分解为$2\times {16}^2+16$的计算量，如此递归下去我们最终得到含有一阶傅里叶矩阵的式子。

来看化简后计算量，$2(2(2(2(2(2{\left(1\right)}^2+1)+2)+4)+8)+16)+32$，约为$6\times 32={\log }_{2}64\times \frac{64}{2}$，算法复杂度为$\frac{n}{2}{\log }_{2}n$。

于是原来需要$n^2$的运算现在只需要$\frac{n}{2}{\log }_{2}n$就可以实现了。不妨看看$n=10$的情况，不使用FFT时需要$n^2=1024\times 1024$次运算，使用FFT时只需要$\frac{n}{2}{\log }_{2}n=5\times 1024$次运算，运算量大约是原来的$\frac{1}{200}$。

下一讲将继续介绍特征值、特征向量及正定矩阵。