[第27集] 复数矩阵和快速傅里叶变换

根据网易公开课之MIT线性代数视频所做的笔记—[第27集] 复数矩阵和快速傅里叶变换。

—————————————————————————————

    视频地址：http://v.163.com/special/opencourse/daishu.html

—————————————————————————————

这节课的内容：

复数矩阵

复数矩阵最重要的一个变化—傅里叶矩阵

快速傅里叶变换（FFT）

1，求模长

对于给定向量z，求其模长。

Z不再属于R^n空间，属于n维复空间。每个元素都是复数，向量z在C^n而不是R^n，即n维复空间（complex space）。

实数矩阵求模长是矩阵的转置乘以矩阵(Z^TZ)，但是复空间不可行。

可以用Z的共轭的转置乘以Z得到模长。

取转置的时候同时取共轭，有个专有名字 Hermitian

Z^HZ

Z Hermitian Z就是模长的平方。

同样，内积的公式改变。两个向量的内积不再是y的转置乘以x(y^Tx)

对复向量来说，做转置的同时要取共轭(y^Hx)，结果也不再是实数，大部分情况下，内积的值是复数。但是，如果y和x相同的话，都是Z，则：

Z^HZ =|Z|²

向量与自身的内积就等于其模长的平方。（实数复数通用）

2，对称矩阵：

A^T = A 仅适用于实数矩阵

对复矩阵：A^H = A

复数情况下的对称矩阵。

3，垂直性：

q1, q2, q3, …… , qn是一列正交矩阵。 

注意计算的时候要共轭转置

正交矩阵的概念有个专有词：unitary,酉矩阵

unitary： n阶方阵，列向量正交，是单位向量

4，傅里叶矩阵

构造矩阵

(Fn)ij = W^(ij)，有个特殊的性质就是其n次方为1

取w的值为 w=e^(i2π/n) = cos(2π/n)+isin(2π/n)

w的值在复空间落在单位为1的圆上。

w的所在位置的角度是一整圈的1/n。假如令n=6

w^1为一圈的1/6, 即6阶傅里叶方阵。

这完全通过这个数和它的乘方构造出来的，同样，它的乘方也在单位圆上，因为是求复数的平方，它的模也跟着平方，仍然等于1，无论n次方始终在单位圆上。

w^1, w^2, w^3, w^4, w^5, w^6对应圆上的六个点。

且w^6=1，（n=6）可以这么说，它们是1的6个六次方根。

w^1（位于60°的点），称为原根w。

另一个例子：

n=4时， w=e^(i2π/4)=i

则w^1-4分别为：i, i^2=-1, i^3=-i, i^4=1

同样对w^n = 1

写成矩阵形式：

可以看出幂指数的规律为，指数等于行序数乘以列序数，序数都是从0开始。

这个矩阵是四点傅里叶变换实际作用于四维向量。

向量分别左乘矩阵F4或者F4^(-1)，一个是傅里叶变换，一个是傅里叶逆变换。

对各列求内积，可以发现相互之间内积为0，但是计算的时候内积公式应该是先共轭再转置相乘！可知矩阵是正交矩阵，但不是标准正交，因为列向量的长度为2。

因为W64是1的64次方根，W32是1的32次方根，则

(W64)² = W32

两者之间可以联系为：

最终分解成一阶的傅里叶矩阵，但是两边有修正矩阵。

对于n阶傅里叶变换，无需n²次乘法，只要1/2nlogn即可。