为什么必须引入复数

实矩阵也可能有复特征值，例如旋转 $90^\circ$ 的矩阵特征值是 $\pm i$。因此必须弄清：当向量、矩阵与内积都变成复数时，哪些定义要改。

核心原则只有一条：转置时要同时取共轭。

时间轴

复向量的长度与内积

长度

对复向量 $z$，$z^Tz$ 不再适用。以 $z=(1,i)$ 为例：

$$z^Tz=1^2+i^2=1-1=0$$

但向量显然不是零向量。正确做法是

$$\|z\|^2=\bar z^Tz=\bar z_1z_1+\cdots+\bar z_nz_n =|z_1|^2+\cdots+|z_n|^2$$

对 $(1,i)$：

$$\|z\|^2=1\cdot1+(-i)\cdot i=1+1=2$$

所以长度是 $\sqrt2$。

Hermitian 转置

把「转置 + 共轭」合成一个符号：

$$z^H=\bar z^T$$

于是长度平方写成 $z^Hz$。两个复向量的内积是

$$\langle y,x\rangle=y^Hx$$

它通常是复数；当 $y=x$ 时得到非负实数，正是长度平方。

正交

两个复向量正交，指向量内积为零：

$$q_i^Hq_j=0\quad(i\ne j)$$

单位化后 $q_i^Hq_i=1$。

从对称到 Hermitian，从正交到酉

Hermitian 矩阵的对角元必须是实数：转置后位置不变，再取共轭仍要等于自身，只有实数满足。非对角元成共轭对：若 $a_{ij}=3+i$，则 $a_{ji}=3-i$。

傅里叶矩阵

定义

设

$$W=e^{2\pi i/n}$$

它是 $n$ 次单位根，位于单位圆上，角度为 $2\pi/n$。$n$ 阶傅里叶矩阵的第 $(i,j)$ 项（$i,j$ 从 0 到 $n-1$）是

$$(F_n)_{ij}=W^{ij}$$

也就是说，行号乘列号作为 $W$ 的指数。

四阶例子

$n=4$ 时

$$W=e^{2\pi i/4}=e^{i\pi/2}=i$$

于是

$$F_4= \begin{bmatrix} 1&1&1&1\\ 1&i&-1&-i\\ 1&-1&1&-1\\ 1&-i&-1&i \end{bmatrix}$$

指数表：

$$\begin{matrix} 0&0&0&0\\ 0&1&2&3\\ 0&2&4&6\\ 0&3&6&9 \end{matrix}$$

再用 $i^2=-1$、$i^3=-i$、$i^4=1$ 化简。

列为什么正交

取第 2 列与第 4 列（下标 1 与 3）：

$$\begin{bmatrix}1\\i\\-1\\-i\end{bmatrix} \quad\text{与}\quad \begin{bmatrix}1\\-i\\-1\\i\end{bmatrix}$$

如果直接点乘（不取共轭），得到

$$1\cdot1+i\cdot(-i)+(-1)(-1)+(-i)\cdot i =1+1+1+1=4$$

看起来不为零。但复内积必须先对第一个向量取共轭：

$$\bar q_2^Tq_4 = 1\cdot1+(-i)(-i)+(-1)(-1)+i\cdot i =1-1+1-1=0$$

所以它们确实正交。忘记共轭是这一节最常见的错误。

每列的长度平方为 $n$。把 $F_n$ 除以 $\sqrt n$，就得到酉矩阵：

$$\frac{1}{\sqrt n}F_n \text{ 是酉矩阵}$$

于是

$$F_n^{-1}=\frac1nF_n^H$$

快速傅里叶变换

问题

直接用 $F_n$ 乘一个向量需要 $n^2$ 次乘法，因为矩阵是满的。FFT 把它降到约 $\frac n2\log_2 n$。

分解思路

以 $n=64$ 为例。关键观察：

$$W_{64}^2=W_{32}$$

因为角度翻倍，$2\pi/64$ 的两倍就是 $2\pi/32$。于是 $F_{64}$ 可以写成

$$F_{64}= \begin{bmatrix}I&D\\I&-D\end{bmatrix} \begin{bmatrix}F_{32}&0\\0&F_{32}\end{bmatrix} P$$

三个因子分别是：

1. $P$：奇偶置换矩阵，把向量的偶数下标分量排在前面、奇数下标排在后面。它不需要乘法，只是重排。
2. 两个 $F_{32}$：分别作用在偶数分量与奇数分量上。
3. 修正矩阵：$I$ 与 $-D$ 几乎不花代价，真正的代价是乘以对角矩阵 $$D=\operatorname{diag}(1,W,W^2,\dots,W^{31})$$ 共 32 次乘法。

因此 $64^2$ 次乘法变成

$$2\cdot 32^2+32$$

递归

对每个 $F_{32}$ 继续同样的分解，得到四个 $F_{16}$，再接上 32 大小的置换与修正。一直分解到 1 点变换。

$64\to32\to16\to8\to4\to2\to1$ 共 $\log_2 64=6$ 层。每一层的修正总共花 $n/2$ 次乘法，于是总代价

$$\frac n2\log_2 n$$

数量级

$n=1024=2^{10}$：

• 直接乘法：$n^2\approx 1{,}048{,}576$；
• FFT：$\frac n2\log_2 n=512\times10=5120$。

约 200 倍的加速。这正是 FFT 能改变整个行业的原因。

核心回顾

• 复向量长度用 $z^Hz$，内积用 $y^Hx$，必须取共轭。
• 对称推广为 Hermitian（$A=A^H$），正交推广为酉（$Q^HQ=I$）。
• 傅里叶矩阵 $(F_n)_{ij}=W^{ij}$，$W=e^{2\pi i/n}$。
• $F_n$ 的列正交，长度为 $\sqrt n$；$F_n^{-1}=\frac1nF_n^H$。
• FFT 利用 $W_{2n}^2=W_n$ 递归分解，代价从 $n^2$ 降到 $\frac n2\log_2 n$。

常见误区

1. 复内积忘记共轭，导致正交性判断错误。
2. 把 Hermitian 矩阵的对角元写成复数。对角元必须为实。
3. 把 $F_n^{-1}$ 写成 $F_n^T$。正确形式是 $\frac1nF_n^H$。
4. 认为 FFT 是近似算法。它是精确的矩阵分解，只是改变了乘法顺序。
5. 把 $W$ 写成 $\cos$ 与 $\sin$ 的直角坐标形式再求高次幂。用指数形式才看得清规律。

理解检验

1. 计算 $z=(1,i,1+i)$ 的长度平方。

参考答案：长度平方是 $\bar z^Tz=|z_1|^2+|z_2|^2+|z_3|^2$。逐项计算：$|1|^2=1$，$|i|^2=1$，$|1+i|^2=1^2+1^2=2$。所以 $\|z\|^2=1+1+2=4$，长度为 $2$。若误用 $z^Tz$，会得到 $1+i^2+(1+i)^2=1-1+2i=-2+2i$，既不是实数也不正确——复内积必须取共轭。

2. 写出 $F_4$，并验证第 2 列与第 3 列正交（记得取共轭）。

参考答案：$W=e^{2\pi i/4}=i$，

$$F_4=\begin{bmatrix}1&1&1&1\\1&i&-1&-i\\1&-1&1&-1\\1&-i&-1&i\end{bmatrix}.$$

第 2 列（下标 1）是 $q_2=(1,i,-1,-i)^T$，取共轭得 $\bar q_2=(1,-i,-1,i)^T$；第 3 列（下标 2）是 $q_3=(1,-1,1,-1)^T$。内积

$$\bar q_2^Tq_3=1\cdot1+(-i)(-1)+(-1)\cdot1+i\cdot(-1)=1+i-1-i=0 .$$

所以两列正交。若不取共轭直接点乘，得到 $1-i-1+i=0$ 只是巧合；换第 2、4 列就会失败，那正是正文展示的例子。

3. 为什么 Hermitian 矩阵的对角元必须是实数？

参考答案：Hermitian 要求 $A=A^H$，即 $a_{ij}=\overline{a_{ji}}$。取 $i=j$ 得 $a_{ii}=\overline{a_{ii}}$。一个复数等于其共轭，当且仅当它的虚部为零，所以对角元必须是实数。非对角元则成共轭对：$a_{ij}=\overline{a_{ji}}$，例如 $a_{ij}=3+i$ 时 $a_{ji}=3-i$。

4. $F_{64}$ 的分解中，哪个因子承担主要计算量？

参考答案：对角修正矩阵 $D=\operatorname{diag}(1,W,\dots,W^{31})$ 承担主要计算量，共 $32=n/2$ 次乘法。置换矩阵 $P$ 只重排下标，不需要乘法；$I$ 与 $-D$ 中的加减法代价很低；两个 $F_{32}$ 的代价递归计算。每一层修正花 $n/2$ 次乘法，共 $\log_2 n$ 层，所以总量是 $\frac n2\log_2 n$。

5. $n=1024$ 时，FFT 比直接乘法快多少倍？

参考答案：直接乘法需要 $n^2=1024^2=1{,}048{,}576$ 次；FFT 需要 $\frac n2\log_2 n=512\times10=5120$ 次。倍数约为 $1{,}048{,}576/5120=204.8$，即约 200 倍。注意 FFT 不是近似算法，它是精确的矩阵分解，只是把同一组乘法按递归顺序重排，减少了重复计算。

与前后课程的关系

这一讲完成了复数情形，并用傅里叶矩阵展示了矩阵分解的计算价值。下一讲回到实对称矩阵，系统讨论正定性：特征值、主元与顺序主子式三种判据如何等价。

Why complex numbers enter

A real matrix can have complex eigenvalues: the $90^\circ$ rotation has $\pm i$. So we must settle what changes when vectors, matrices, and inner products become complex.

There is one governing rule: conjugate whenever you transpose.

Timeline

Length and inner product of complex vectors

Length

For a complex vector $z$, $z^Tz$ is no longer usable. Take $z=(1,i)$:

$$z^Tz=1^2+i^2=1-1=0$$

Yet the vector is not zero. The correct definition is

$$\|z\|^2=\bar z^Tz=\bar z_1z_1+\cdots+\bar z_nz_n =|z_1|^2+\cdots+|z_n|^2$$

For $(1,i)$:

$$\|z\|^2=1\cdot1+(-i)\cdot i=1+1=2$$

so the length is $\sqrt2$.

The Hermitian transpose

Combine transpose and conjugation into one symbol:

$$z^H=\bar z^T$$

Then the length squared is $z^Hz$, and the inner product of two complex vectors is

$$\langle y,x\rangle=y^Hx$$

It is usually complex; when $y=x$ it is a nonnegative real number, namely the squared length.

Orthogonality

Two complex vectors are orthogonal when

$$q_i^Hq_j=0\quad(i\ne j)$$

and unit length means $q_i^Hq_i=1$.

Symmetric becomes Hermitian, orthogonal becomes unitary

The diagonal entries of a Hermitian matrix must be real: transposition leaves them in place, and conjugating must return the same value, which only real numbers satisfy. Off-diagonal entries come in conjugate pairs: if $a_{ij}=3+i$, then $a_{ji}=3-i$.

The Fourier matrix

Definition

Let

$$W=e^{2\pi i/n}$$

an $n$-th root of unity on the unit circle at angle $2\pi/n$. The $(i,j)$ entry of the $n\times n$ Fourier matrix, with $i,j$ from 0 to $n-1$, is

$$(F_n)_{ij}=W^{ij}$$

The exponent is the row index times the column index.

The $4 \times 4$ case

For $n=4$,

$$W=e^{2\pi i/4}=e^{i\pi/2}=i$$

so

$$F_4= \begin{bmatrix} 1&1&1&1\\ 1&i&-1&-i\\ 1&-1&1&-1\\ 1&-i&-1&i \end{bmatrix}$$

The exponent pattern:

$$\begin{matrix} 0&0&0&0\\ 0&1&2&3\\ 0&2&4&6\\ 0&3&6&9 \end{matrix}$$

and then $i^2=-1$, $i^3=-i$, $i^4=1$ simplify the entries.

Why the columns are orthogonal

Take columns 2 and 4 (indices 1 and 3):

$$\begin{bmatrix}1\\i\\-1\\-i\end{bmatrix} \quad\text{and}\quad \begin{bmatrix}1\\-i\\-1\\i\end{bmatrix}$$

A plain dot product without conjugation gives

$$1\cdot1+i\cdot(-i)+(-1)(-1)+(-i)\cdot i =1+1+1+1=4$$

which looks nonzero. But the complex inner product conjugates the first vector:

$$\bar q_2^Tq_4 = 1\cdot1+(-i)(-i)+(-1)(-1)+i\cdot i =1-1+1-1=0$$

So they are orthogonal after all. Forgetting the conjugate is the classic error here.

Each column has squared length $n$. Dividing $F_n$ by $\sqrt n$ produces a unitary matrix:

$$\frac{1}{\sqrt n}F_n \text{ is unitary}$$

and therefore

$$F_n^{-1}=\frac1nF_n^H$$

The fast Fourier transform

The problem

Multiplying by $F_n$ directly costs $n^2$ multiplications because the matrix is full. The FFT reduces this to about $\frac n2\log_2 n$.

The factorization

Take $n=64$. The key observation is

$$W_{64}^2=W_{32}$$

because doubling the angle $2\pi/64$ gives $2\pi/32$. Hence $F_{64}$ factors as

$$F_{64}= \begin{bmatrix}I&D\\I&-D\end{bmatrix} \begin{bmatrix}F_{32}&0\\0&F_{32}\end{bmatrix} P$$

The three factors are:

1. $P$, an even-odd permutation matrix: it puts even-indexed components first and odd-indexed ones second. No multiplications, only reordering.
2. Two copies of $F_{32}$, acting separately on the even and odd parts.
3. Fix-up matrices: $I$ and $-D$ are nearly free; the real cost is multiplying by the diagonal $$D=\operatorname{diag}(1,W,W^2,\dots,W^{31})$$ which is 32 multiplications.

So $64^2$ multiplications become

$$2\cdot 32^2+32$$

Recursion

Break each $F_{32}$ the same way, producing four $F_{16}$ plus a size-32 permutation and fix-up. Continue down to size 1.

There are $\log_2 64=6$ levels. Each level costs $n/2$ multiplications in its fix-up, so the total is

$$\frac n2\log_2 n$$

The scale

For $n=1024=2^{10}$:

• direct multiplication: $n^2\approx 1{,}048{,}576$;
• FFT: $\frac n2\log_2 n=512\times10=5120$.

About a 200-fold speedup. That is why the FFT changed entire industries.

Core review

• Complex length uses $z^Hz$; the inner product is $y^Hx$; conjugation is mandatory.
• Symmetry generalizes to Hermitian ($A=A^H$), orthogonality to unitary ($Q^HQ=I$).
• The Fourier matrix is $(F_n)_{ij}=W^{ij}$ with $W=e^{2\pi i/n}$.
• Its columns are orthogonal with squared length $n$, and $F_n^{-1}=\frac1nF_n^H$.
• The FFT uses $W_{2n}^2=W_n$ to recurse, cutting $n^2$ to $\frac n2\log_2 n$.

Common misconceptions

1. Dropping the conjugate in a complex inner product, which breaks orthogonality tests.
2. Giving a Hermitian matrix complex diagonal entries. The diagonal must be real.
3. Writing $F_n^{-1}=F_n^T$. The correct form is $\frac1nF_n^H$.
4. Calling the FFT an approximation. It is an exact factorization; only the order of multiplications changes.
5. Converting $W$ to sine and cosine before taking high powers. The exponential form is what reveals the pattern.

Check your understanding

1. Compute the squared length of $z=(1,i,1+i)$.

Reference answer: The squared length is $\bar z^Tz=|z_1|^2+|z_2|^2+|z_3|^2$. Term by term: $|1|^2=1$, $|i|^2=1$, and $|1+i|^2=1^2+1^2=2$. Hence $\|z\|^2=1+1+2=4$ and the length is $2$. Using $z^Tz$ instead gives $1+i^2+(1+i)^2=1-1+2i=-2+2i$, which is neither real nor correct — the complex inner product must conjugate.

2. Write $F_4$ and verify that columns 2 and 3 are orthogonal, remembering the conjugate.

Reference answer: With $W=e^{2\pi i/4}=i$,

$$F_4=\begin{bmatrix}1&1&1&1\\1&i&-1&-i\\1&-1&1&-1\\1&-i&-1&i\end{bmatrix}.$$

Column 2 (index 1) is $q_2=(1,i,-1,-i)^T$ with conjugate $\bar q_2=(1,-i,-1,i)^T$; column 3 (index 2) is $q_3=(1,-1,1,-1)^T$. Then

$$\bar q_2^Tq_3=1\cdot1+(-i)(-1)+(-1)\cdot1+i\cdot(-1)=1+i-1-i=0 .$$

So the columns are orthogonal. Without the conjugate one gets $1-i-1+i=0$ only by coincidence; columns 2 and 4 fail, which is exactly the example in the text.

3. Why must the diagonal of a Hermitian matrix be real?

Reference answer: Hermitian means $A=A^H$, i.e. $a_{ij}=\overline{a_{ji}}$. Setting $i=j$ gives $a_{ii}=\overline{a_{ii}}$. A complex number equals its conjugate exactly when its imaginary part is zero, so each diagonal entry is real. Off-diagonal entries come in conjugate pairs: $a_{ij}=\overline{a_{ji}}$, so $a_{ij}=3+i$ forces $a_{ji}=3-i$.

4. In the factorization of $F_{64}$, which factor carries most of the work?

Reference answer: The diagonal correction matrix $D=\operatorname{diag}(1,W,\dots,W^{31})$, which costs $32=n/2$ multiplications. The permutation $P$ only reorders entries and costs no multiplications, $I$ and $-D$ cost only cheap additions, and the two $F_{32}$ blocks are handled recursively. Each level spends $n/2$ multiplications and there are $\log_2 n$ levels, giving $\frac n2\log_2 n$ overall.

5. For $n=1024$, how many times faster is the FFT than direct multiplication?

Reference answer: Direct multiplication costs $n^2=1024^2=1{,}048{,}576$ multiplications; the FFT costs $\frac n2\log_2 n=512\times10=5120$. The ratio is $1{,}048{,}576/5120=204.8$, about 200 times faster. The FFT is not an approximation — it is an exact factorization that reorders the same multiplications so that repeated work is eliminated.

How this connects

This lecture completes the complex case and uses the Fourier matrix to show the computational value of matrix factorization. The next lecture returns to real symmetric matrices and develops positive definiteness, where eigenvalues, pivots, and leading minors give three equivalent tests.