第二十七讲：复数矩阵和快速傅里叶变换
本讲主要介绍复数向量、复数矩阵的相关知识（包括如何做复数向量的点积运算、什么是复数对称矩阵等），以及傅里叶矩阵（最重要的复数矩阵）和快速傅里叶变换。
复数矩阵运算
先介绍复数向量，我们不妨换一个字母符号来表示：\(z=\begin{bmatrix}z_1\\z_2\\\vdots\\z_n\end{bmatrix}\)，向量的每一个分量都是复数。此时\(z\)不再属于\(\mathbb{R}^n\)实向量空间，它现在处于\(\mathbb{C}^n\)复向量空间。
计算复向量的模
对比实向量，我们计算模只需要计算\(\left|v\right|=\sqrt{v^Tv}\)即可，而如果对复向量使用\(z^Tz\)则有\(z^Tz=\begin{bmatrix}z_1&z_2&\cdots&z_n\end{bmatrix}\begin{bmatrix}z_1\\z_2\\\vdots\\z_n\end{bmatrix}=z_1^2+z_2^2+\cdots+z_n^2\)，这里\(z_i\)是复数，平方后虚部为负，求模时本应相加的运算变成了减法。（如向量\(\begin{bmatrix}1&i\end{bmatrix}\)，右乘其转置后结果为\(0\)，但此向量的长度显然不是零。）
根据上一讲我们知道，应使用\(\left|z\right|=\sqrt{\bar{z}^Tz}\)，即\(\begin{bmatrix}\bar z_1&\bar z_2&\cdots&\bar z_n\end{bmatrix}\begin{bmatrix}z_1\\z_2\\\vdots\\z_n\end{bmatrix}\)，即使用向量共轭的转置乘以原向量即可。（如向量\(\begin{bmatrix}1&i\end{bmatrix}\)，右乘其共轭转置后结果为\(\begin{bmatrix}1&-i\end{bmatrix}\begin{bmatrix}1\\i\end{bmatrix}=2\)。）
我们把共轭转置乘以原向量记为\(z^Hz\)，\(H\)读作埃尔米特（人名为Hermite，形容词为Hermitian）
计算向量的内积
有了复向量模的计算公式，同理可得，对于复向量，内积不再是实向量的\(y^Tx\)形式，复向量内积应为\(y^Hx\)。
对称性
对于实矩阵，\(A^T=A\)即可表达矩阵的对称性。而对于复矩阵，我们同样需要求一次共轭\(\bar{A}^T=A\)。举个例子\(\begin{bmatrix}2&3+i\\3-i&5\end{bmatrix}\)是一个复数情况下的对称矩阵。这叫做埃尔米特矩阵，有性质\(A^H=A\)。
正交性
在第十七讲中，我们这样定义标准正交向量：\(q_i^Tq_j=\begin{cases}0\quad i\neq j\\1\quad i=j\end{cases}\)。现在，对于复向量我们需要求共轭：\(\bar{q}_i^Tq_j=q_i^Hq_j=\begin{cases}0\quad i\neq j\\1\quad i=j\end{cases}\)。
第十七讲中的标准正交矩阵：\(Q=\Bigg[q_1\ q_2\ \cdots\ q_n\Bigg]\)有\(Q^TQ=I\)。现在对于复矩阵则有\(Q^HQ=I\)。
就像人们给共轭转置起了个“埃尔米特”这个名字一样，正交性（orthogonal）在复数情况下也有了新名字，酉（unitary），酉矩阵（unitary matrix）与正交矩阵类似，满足\(Q^HQ=I\)的性质。而前面提到的傅里叶矩阵就是一个酉矩阵。
傅里叶矩阵
\(n\)阶傅里叶矩阵\(F_n=\begin{bmatrix}1&1&1&\cdots&1\\1&w&w^2&\cdots&w^{n-1}\\1&w^2&w^4&\cdots&w^{2(n-1)}\\\vdots&\vdots&\vdots&\ddots&\vdots\\1&w^{n-1}&w^{2(n-1)}&\cdots&w^{(n-1)^2}\end{bmatrix}\)，对于每一个元素有\((F_n)_{ij}=w^{ij}\quad 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=\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}=\begin{bmatrix}1&1&1&1\\1&i&-1&-i\\1&-1&1&-1\\1&-i&-1&i\end{bmatrix}\)。
矩阵的四个列向量正交，我们验证一下第二列和第四列，\(\bar{c_2}^Tc_4=1-0+1-0=0\)，正交。不过我们应该注意到，\(F_4\)的列向量并不是标准的，我们可以给矩阵乘上系数\(\frac{1}{2}\)（除以列向量的长度）得到标准正交矩阵\(F_4=\frac{1}{2}\begin{bmatrix}1&1&1&1\\1&i&-1&-i\\1&-1&1&-1\\1&-i&-1&i\end{bmatrix}\)。此时有\(F_4^HF_4=I\)，于是该矩阵的逆矩阵也就是其共轭转置\(F_4^H\)。
快速傅里叶变换（Fast Fourier transform/FFT）
对于傅里叶矩阵，\(F_6,\ F_3\)、\(F_8,\ F_4\)、\(F_{64},\ F_{32}\)之间有着特殊的关系。
举例，有傅里叶矩阵\(F_64\)，一般情况下，用一个列向量右乘\(F_{64}\)需要约\(64^2\)次计算，显然这个计算量是比较大的。我们想要减少计算量，于是想要分解\(F_{64}\)，联系到\(F_{32}\)，有\(\Bigg[F_{64}\Bigg]=\begin{bmatrix}I&D\\I&-D\end{bmatrix}\begin{bmatrix}F_{32}&0\\0&F_{32}\end{bmatrix}\begin{bmatrix}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{bmatrix}\)。
我们分开来看等式右侧的这三个矩阵：
-
第一个矩阵由单位矩阵\(I\)和对角矩阵\(D=\begin{bmatrix}1&&&&\\&w&&&\\&&w^2&&\\&&&\ddots&\\&&&&w^{31}\end{bmatrix}\)组成，我们称这个矩阵为修正矩阵，显然其计算量来自\(D\)矩阵，对角矩阵的计算量约为\(32\)即这个修正矩阵的计算量约为\(32\)，单位矩阵的计算量忽略不计。
-
第二个矩阵是两个\(F_{32}\)与零矩阵组成的，计算量约为\(2\times 32^2\)。
-
第三个矩阵通常记为\(P\)矩阵，这是一个置换矩阵，其作用是讲前一个矩阵中的奇数列提到偶数列之前，将前一个矩阵从\(\Bigg[x_0\ x_1\ \cdots\Bigg]\)变为\(\Bigg[x_0\ x_2\ \cdots\ x_1\ x_3\ \cdots\Bigg]\)，这个置换矩阵的计算量也可以忽略不计。（这里教授似乎在黑板上写错了矩阵，可以参考FFT、How the FFT is computed做进一步讨论。）
所以我们把\(64^2\)复杂度的计算化简为\(2\times 32^2+32\)复杂度的计算，我们可以进一步化简\(F_{32}\)得到与\(F_{16}\)有关的式子\(\begin{bmatrix}I_{32}&D_{32}\\I_{32}&-D_{32}\end{bmatrix}\begin{bmatrix}I_{16}&D_{16}&&\\I_{16}&-D_{16}&&\\&&I_{16}&D_{16}\\&&I_{16}&-D_{16}\end{bmatrix}\begin{bmatrix}F_{16}&&&\\&F_{16}&&\\&&F_{16}&\\&&&F_{16}\end{bmatrix}\begin{bmatrix}P_{16}&\\&P_{16}\end{bmatrix}\Bigg[\ P_{32}\ \Bigg]\)。而\(32^2\)的计算量进一步分解为\(2\times 16^2+16\)的计算量，如此递归下去我们最终得到含有一阶傅里叶矩阵的式子。
来看化简后计算量，\(2\left(2\left(2\left(2\left(2\left(2\left(1\right)^2+1\right)+2\right)+4\right)+8\right)+16\right)+32\)，约为\(6\times 32=\log_264\times \frac{64}{2}\)，算法复杂度为\(\frac{n}{2}\log_2n\)。
于是原来需要\(n^2\)的运算现在只需要\(\frac{n}{2}\log_2n\)就可以实现了。不妨看看\(n=10\)的情况，不使用FFT时需要\(n^2=1024\times 1024\)次运算，使用FFT时只需要\(\frac{n}{2}\log_2n=5\times 1024\)次运算，运算量大约是原来的\(\frac{1}{200}\)。
下一讲将继续介绍特征值、特征向量及正定矩阵。
