线性代数学习笔记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$），这符合“模长平方”的数学意义： x ‾ T x = [ x ˉ 1 x ˉ 2 x ˉ 3 x ˉ 4 ] [ x 1 x 2 x 3 x 4 ] = ∣ x 1 ∣ 2 + ∣ x 2 ∣ 2 + ∣ x 3 ∣ 2 + ∣ x 4 ∣ 2 \overline{\mathbf{x}}^{T} \mathbf{x}=\left[
  x¯1x¯2x¯3x¯4" role="presentation" style="text-align: center; position: relative;">x¯1x¯2x¯3x¯4$$\begin{array}{llll}{\overline{x}}_1& {\overline{x}}_2& {\overline{x}}_3& {\overline{x}}_4\end{array}$$
  \right]\left[
  x1x2x3x4" role="presentation" style="text-align: center; position: relative;">x1x2x3x4$$\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} xTx=[xˉ1​​xˉ2​​xˉ3​​xˉ4​​]⎣ ⎡​x1​x2​x3​x4​​⎦ ⎤​=∣x1​∣2+∣x2​∣2+∣x3​∣2+∣x4​∣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转置

复数矩阵 与 共轭转置（Hermite转置）

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

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

共轭转置（Hermite转置）的运算性质：

1. $({\mathbf{A}}^H{)}^H=\mathbf{A}$
2. $(\mathbf{A}+\mathbf{B}{)}^H={\mathbf{A}}^H+{\mathbf{B}}^H$
3. $(\mathbf{AB}{)}^H={\mathbf{B}}^H{\mathbf{A}}^H$
4. $({\mathbf{A}}^{-1}{)}^H=({\mathbf{A}}^H{)}^{-1}$
5. $(k\mathbf{A}{)}^H=\bar{k}{\mathbf{A}}^H$

一般而言，从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）
  酉矩阵的列向量都是复向量，且构成复空间中的标准正交向量组，满足 q ‾ j T q k = { 0 j ≠ k 1 j = k \overline{\mathbf{q}}_{j}^{T} \mathbf{q}_{k}=\left\{
  0j≠k1j=k" role="presentation" style="text-align: center; position: relative;">01j≠kj=k$$\begin{array}{ll}0& j\ne k\\ 1& j=k\end{array}$$
  \right. q​jT​qk​={01​j=kj=k​

傅里叶矩阵

使用傅里叶矩阵，可以实现离散傅里叶变换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}$有一定关系
• 具体而言， [ F 64 ] = [ I D I − D ] [ F 32 0 0 F 32 ] [ P ] \left[\boldsymbol{F}_{64}\right]=\left[
  IDI−D" role="presentation">IID−D$$\begin{array}{rr}\mathit{I}& \mathit{D}\\ \mathit{I}& -\mathit{D}\end{array}$$
  \right]\left[
  F3200F32" role="presentation" style="text-align: center; position: relative;">F3200F32$$\begin{array}{rr}{\mathit{F}}_{32}& 0\\ 0& {\mathit{F}}_{32}\end{array}$$
  \right][\boldsymbol{P}] [F64​]=[II​D−D​][F32​0​0F32​​][P]
• 其中，置换矩阵 P = [ 1 0 0 0 ⋯ ⋯ 0 0 0 0 1 0 0 0 ⋮ 0 0 0 0 ⋯ ⋯ 1 0 0 1 0 0 ⋯ ⋯ 0 0 0 0 0 1 ⋯ ⋯ 0 0 ⋮ 0 0 0 0 ⋯ ⋯ 0 1 ] \boldsymbol{P}=\left[
  1000⋯⋯00001000⋮0000⋯⋯100100⋯⋯000001⋯⋯00⋮0000⋯⋯01" role="presentation" style="text-align: center; position: relative;">10000000010001000000⋮001⋮0⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯001000000001$$\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] P=⎣ ⎡​100000​000100​010000​00⋮001⋮0​⋯⋯⋯⋯⋯​⋯⋯⋯⋯⋯​001000​000001​⎦ ⎤​，功能是将奇数次项（1,3,5）提到前面，将偶数次项（2,4,6）放到后面
  对角阵 D = [ 1 ω ω 2 ⋱ ω 31 ] \boldsymbol{D}=\left[
  1ωω2⋱ω31" role="presentation" style="text-align: center; position: relative;">1ωω2⋱ω31$$\begin{array}{ccccc}1& & & & \\ & \omega & & & & \\ & & {\omega }^2& & \\ & & & \ddots & \\ & & & & {\omega }^{31}\end{array}$$
  \right] D=⎣ ⎡​1​ω​ω2​⋱​ω31​⎦ ⎤​
• 计算量对比：
  原来对长度为$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$