线性代数学习笔记8-1：复数矩阵与Hermite矩阵、酉矩阵、傅里叶矩阵和快速傅里叶变换FFT

即使是实矩阵，也可能有复特征值，因此矩阵运算中无法避免的会碰到复数

这里我们先特别关注复数矩阵的情况，并明确如何处理复矩阵，而在后续学习中一般只研究实矩阵，可以将其推广到复数情况

复向量的内积和共轭转置

对于复向量$\mathbf{x}=\left[\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_{\mathrm{n}}\end{array}\right]\in {\mathbf{C}}^n$，其中每个分量都是复数

在实数情况下，我们学习过，${\mathbf{x}}^T\mathbf{x}$表示$\mathbf{x}$与自己的内积/点积，结果是一个正实数（向量$\mathbf{x}$长度的平方）

• 复向量的模长的平方：在$\mathbf{x}$为复数情的况下不能再使用${\mathbf{x}}^T\mathbf{x}$，复向量模长的平方应推广为${\overline{\mathbf{x}}}^T\mathbf{x}$，对于复向量，这是一个常见、很重要的运算
  具体带入可知，${\overline{\mathbf{x}}}^T\mathbf{x}$的结果必然为非负实数（仅当$\mathbf{x}=0$时${\overline{\mathbf{x}}}^T\mathbf{x}=0$），这符合“模长平方”的数学意义：$${\overline{\mathbf{x}}}^T\mathbf{x}=\left[\begin{array}{llll}{\bar{x}}_1& {\bar{x}}_2& {\bar{x}}_3& {\bar{x}}_4\end{array}\right]\left[\begin{array}{l}{x}_1\\ x_2\\ x_3\\ x_4\end{array}\right]={\left|x_1\right|}^2+{\left|x_2\right|}^2+{\left|x_3\right|}^2+{\left|x_4\right|}^2$$其中，对于复数$x_i$，${\bar{x}}_i{x}_i={\left|x_i\right|}^2$（由于$(a+ib)(a-ib)=a^2+b^2$），可见，结果的每一项都是非负实数

例如，我们认为复向量$\left[\begin{array}{c}1\\ i\end{array}\right]$模长的平方为2，因为$\left[\begin{array}{ll}1& -i\end{array}\right]\left[\begin{array}{c}1\\ i\end{array}\right]=2$

• 一般的，复向量的内积运算为${\mathbf{y}}^H\mathbf{x}$：$${\mathbf{y}}^H\mathbf{x}={\overline{\mathbf{y}}}^T\mathbf{x}={\bar{y}}_1{x}_1+{\bar{y}}_2{x}_2+\cdots +{\bar{y}}_n{x}_n$$
  若${\mathbf{y}}^H\mathbf{x}=0$，说明两个复向量互相垂直/正交

可见，实数情况下的转置${\mathbf{x}}^T$，在复数情况下推广为共轭转置${\overline{\mathbf{x}}}^T={\mathbf{x}}^H$，也称为Hermite转置

复数矩阵 Complex matrices 与Hermite转置

由上，矩阵的转置运算${\mathbf{A}}^T$，在复空间中推广为Hermite转置${\mathbf{A}}^H$

• Hermite矩阵：${\mathbf{A}}^H={\bar{\mathbf{A}}}^T$

一般而言，从n维实空间${\mathbf{R}}^n$，推广到n维复空间${\mathbf{C}}^n$，将各个转置运算换为Hermite转置即可，如：

Hermitian矩阵

• 对称矩阵，实数下为$\mathbf{A}={\mathbf{A}}^T$，复数下为$\mathbf{A}={\mathbf{A}}^H$，称为Hermitian矩阵

酉矩阵

• 正交矩阵，实数下为${\mathbf{Q}}^T\mathbf{Q}=\mathbf{I}$，复数下为${\mathbf{Q}}^H\mathbf{Q}=\mathbf{I}$，称为酉矩阵（unitary matrix）
  酉矩阵的列向量都是复向量，且构成复空间中的标准正交向量组，满足${\overline{\mathbf{q}}}_j^T{\mathbf{q}}_k=\{\begin{array}{ll}0& j\ne k\\ 1& j=k\end{array}$

傅里叶矩阵

使用傅里叶矩阵，可以实现离散傅里叶变换DFT

离散傅里叶变换DFT：$X[k]={\sum }_{n=0}^{N-1}x[n]{\mathrm{e}}^{-\mathrm{j}\frac{2\pi }{N}kn}$
离散傅里叶逆变换IDFT：$x[n]=\frac{1}{N}{\sum }_{k=0}^{N-1}x[n]{\mathrm{e}}^{\mathrm{j}\frac{2\pi }{N}kn}$

长度为$n$的离散向量${\mathbf{x}}_n$:

• 做离散傅里叶变换DFT：${\mathbf{F}}_n{\mathbf{x}}_n$；（结果是$n\times 1$的列向量，第$k$行来自于${\mathbf{F}}_n$的第$k$行与${\mathbf{x}}_n$相乘）
• 做离散傅里叶逆变换IDFT：${\mathbf{F}}_n^{-1}{\mathbf{x}}_n$

根据DFT和IDFT定义式，提取基本元素$\omega =e^{j2\pi /n}$，从而得到n阶傅里叶矩阵${\mathbf{F}}_n$：
$${\mathbf{F}}_n=\left[\begin{array}{rrrrr}1& 1& 1& \cdots & 1\\ 1& \omega & {\omega }^2& & {\omega }^{(n-1)}\\ 1& {\omega }^2& {\omega }^4& & {\omega }^{2(n-1)}\\ ⋮& & & \ddots & \\ 1& {\omega }^{n-1}& {\omega }^{2(n-1)}& & {\omega }^{(n-1{)}^2}\end{array}\right]$$其中，基本元素$\omega =e^{j2\pi /n}$的特点在于：

• $\omega =e^{j2\pi /n}$是复元素，但模长为1，因此其幂次方仅对应于单位圆上的旋转；
• 并且$\omega =e^{j2\pi /n}$的相角，就是将一整圈单位圆（$2\pi$）划分为$n$份得到的，从而${\omega }^n=1$

傅里叶矩阵的性质

注意，n阶傅里叶矩阵${\mathbf{F}}_n$满足：

• 矩阵元素通项公式：${\left({\mathbf{F}}_n\right)}_{ij}={\omega }^{(i-1)(j-1)}=(e^{j2\pi /n}{)}^{(i-1)(j-1)}$，即第$i$行第$j$列元素的指数，由$(i-1)(j-1)$相乘得到（$i,j\in [1,n]$）
• 有一定的对称性（满足${\mathbf{F}}_n={\mathbf{F}}_n^T$），但并不是Hermitian矩阵（复空间下不能算是对称矩阵，因为不满足$\mathbf{A}={\mathbf{A}}^H$）
• 傅里叶矩阵，各个列向量正交，但不是酉矩阵（列向量模长为$\sqrt{N}$）（复空间下不是“列向量标准正交”的正交矩阵）
  好处：列向量正交，可以将傅里叶矩阵分解为一系列稀疏矩阵（含有大量零元素），从而可以轻易做乘法、求逆
• 由上，各列向量正交但模长为$\sqrt{N}$，整个矩阵除以$\sqrt{N}$可以得到酉矩阵$\frac{1}{\sqrt{N}}{\mathbf{F}}_n$（正交矩阵在复空间下的推广，列向量为复向量且标准正交）
• 推论：$F_n^{-1}=\frac{1}{N}{F}_n^H$，或者说$\frac{1}{N}{\mathbf{F}}_n{}^H{\mathbf{F}}_n=\mathbf{I}$
  证明：根据上面，$\frac{1}{\sqrt{N}}{\mathbf{F}}_n$为酉矩阵，其逆矩阵为${\left(\frac{1}{\sqrt{N}}{F}_n\right)}^{-1}={\left(\frac{1}{\sqrt{N}}{F}_n\right)}^H=\frac{1}{\sqrt{N}}{F}_n^H$
  两步同乘以$\frac{1}{\sqrt{N}}$，即可得到$F_n^{-1}=\frac{1}{N}{F}_n^H$，证毕
  （ps. 这就是为什么DFT有系数$\frac{1}{N}$）

例如，对于$${\mathbf{F}}_4=\left[\begin{array}{cccc}1& 1& 1& 1\\ 1& e^{j\left(\frac{\pi }{2}\right)}& e^{j\left(\frac{\pi }{2}\right)2}& e^{j\left(\frac{\pi }{2}\right)3}\\ 1& e^{j\left(\frac{\pi }{2}\right)2}& e^{j\left(\frac{\pi }{2}\right)2\ast 2}& e^{j\left(\frac{\pi }{2}\right)2\ast 3}\\ 1& e^{j\left(\frac{\pi }{2}\right)3}& e^{j\left(\frac{\pi }{2}\right)3\ast 2}& e^{j\left(\frac{\pi }{2}\right)3\ast 3}\end{array}\right]=\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}{rrrr}1& 1& 1& 1\\ 1& i& -1& -i\\ 1& -1& 1& -1\\ 1& -i& -1& i\end{array}\right]$$各个列向量正交（内积${\overline{{\mathbf{x}}_i}}^T{\mathbf{x}}_j=0$），但列向量的模长平方${\overline{{\mathbf{x}}_i}}^T{\mathbf{x}}_i=4$
因此，可以修正得到一个酉矩阵：$$\frac{1}{2}{\mathbf{F}}_4=\frac{1}{2}\left[\begin{array}{rrrr}1& 1& 1& 1\\ 1& i& -1& -i\\ 1& -1& 1& -1\\ 1& -i& -1& i\end{array}\right]$$
酉矩阵$\frac{1}{2}{\mathbf{F}}_4$（复数下的正交矩阵）的逆矩阵：$\frac{1}{2}{\mathbf{F}}_4^H$（共轭转置即可）
满足$\frac{1}{4}{\mathbf{F}}_4{}^H{\mathbf{F}}_4=\mathbf{I}$

另外也可以验证${\mathbf{F}}_4$的逆矩阵：$F_4^{-1}=\frac{1}{4}{F}_4^H=\frac{1}{4}\left[\begin{array}{cccc}1& 1& 1& 1\\ 1& e^{-j\left(\frac{\pi }{2}\right)}& e^{-j\left(\frac{\pi }{2}\right)2}& e^{-j\left(\frac{\pi }{2}\right)3}\\ 1& e^{-j\left(\frac{\pi }{2}\right)2}& e^{-j\left(\frac{\pi }{2}\right)2\ast 2}& e^{-j\left(\frac{\pi }{2}\right)2\ast 3}\\ 1& e^{-j\left(\frac{\pi }{2}\right)3}& e^{-j\left(\frac{\pi }{2}\right)3\ast 2}& e^{-j\left(\frac{\pi }{2}\right)3\ast 3}\end{array}\right]$

快速傅里叶变换FFT

快速傅里叶变换FFT可以大大减少DFT的计算量，下面从矩阵角度看待这个问题

FFT中，将N=64的DFT拆为两个N=32的DFT
从矩阵角度：

• 傅里叶矩阵${\mathbf{F}}_{64}$和${\mathbf{F}}_{32}$的基本元素有如下关系：$w_{64}^2=w_{32}$，可见${\mathbf{F}}_{64}$和${\mathbf{F}}_{32}$有一定关系
• 具体而言，$\left[{\mathbf{F}}_{64}\right]=\left[\begin{array}{rr}\mathbf{I}& \mathbf{D}\\ \mathbf{I}& -\mathbf{D}\end{array}\right]\left[\begin{array}{rr}{\mathbf{F}}_{32}& 0\\ 0& {\mathbf{F}}_{32}\end{array}\right][\mathbf{P}]$
• 其中，置换矩阵$\mathbf{P}=\left[\begin{array}{cccccccc}1& 0& 0& 0& \cdots & \cdots & 0& 0\\ 0& 0& 1& 0& & & 0& 0\\ & & & ⋮& & & & \\ 0& 0& 0& 0& \cdots & \cdots & 1& 0\\ 0& 1& 0& 0& \cdots & \cdots & 0& 0\\ 0& 0& 0& 1& \cdots & \cdots & 0& 0\\ & & & ⋮& & & & \\ 0& 0& 0& 0& \cdots & \cdots & 0& 1\end{array}\right]$，功能是将奇数次项（1,3,5）提到前面，将偶数次项（2,4,6）放到后面
  对角阵$\mathbf{D}=\left[\begin{array}{cccccc}1& & & & & \\ & \omega & & & & \\ & & {\omega }^2& & & \\ & & & \ddots & & \\ & & & & {\omega }^{31}& \end{array}\right]$
• 计算量对比：
  原来对长度为$N$的向量$\mathbf{x}$直接做DFT，则${\mathbf{F}}_{64}\mathbf{x}$的计算量是$N\times N$
  改写为FFT后，计算量是两个${\mathbf{F}}_{32}\mathbf{x}$再加上一些修正项，修正项主要来自于与对角矩阵D的乘法，大约为32次；并且${\mathbf{F}}_{32}$可进一步拆为两个${\mathbf{F}}_{16}$、再拆为四个${\mathbf{F}}_8$…最终，所有计算来自于修正项，FFT计算量为$(N/2)lo{g}_{2}N$