---
title: 线性代数 第 9 章 · 复向量与复矩阵 习题答案
aliases:
  - 复向量与复矩阵 习题答案
tags:
  - 类型/习题答案
  - 线性代数/复矩阵
chapter: "9"
created: 2026-10-17
updated: 2026-10-17
---

# 线性代数 第 9 章 · 复向量与复矩阵（15 题）

> [!abstract] 本章速览
> 3 篇 · 15 题：复数与复向量（9-1，5 题）、Hermitian 与酉矩阵（9-2，5 题）、快速傅里叶变换（9-3，5 题）。

## 9-1 复数与复向量（5 题）

| 题号 | 结论 |
|---|---|
| 练习 1 | $3+2\mathrm i$；$1-4\mathrm i$；$5+5\mathrm i$；$-\frac1{10}-\frac7{10}\mathrm i$ |
| 练习 2 | $2,\frac{2\pi}3$；$2,-\frac\pi2$；$3,\pi$；$z^6=64$ |
| 练习 3 | 厄米；$\sqrt3,\sqrt3$；$\mathbf v^{\mathsf H}\mathbf w=-2\mathrm i$；$\lambda=4,1$ |
| 练习 4 | 见解析 |
| 练习 5 | 见解析 |

### 练习 1　（四则运算）

**解**

**第 1 步：加减。**

$$
z+w=(2+1)+(-1+3)\mathrm i=3+2\mathrm i,\qquad z-w=(2-1)+(-1-3)\mathrm i=1-4\mathrm i
$$

**第 2 步：乘法。** 用 $\mathrm i^2=-1$：

$$
zw=(2-\mathrm i)(1+3\mathrm i)=2+6\mathrm i-\mathrm i-3\mathrm i^2=2+5\mathrm i+3=5+5\mathrm i
$$

**第 3 步：除法。** 分子分母同乘 $\bar w=1-3\mathrm i$：

$$
\frac{z}{w}=\frac{(2-\mathrm i)(1-3\mathrm i)}{1^2+3^2}=\frac{2-6\mathrm i-\mathrm i+3\mathrm i^2}{10}=\frac{-1-7\mathrm i}{10}=-\frac1{10}-\frac7{10}\mathrm i
$$

**答案**　如上。

**易错点**　① $\mathrm i^2$ 忘记写成 $-1$；② 除法只乘分子不乘分母；③ 分母用了 $1-3\mathrm i$ 的模平方 $10$ 却写成 $1+9=10$ 之外的值。

### 练习 2　（模、辐角与棣莫弗）

**解**

**第 1 步：(a) $z=-1+\sqrt3\mathrm i$。** 在第二象限：

$$
\lvert z\rvert=\sqrt{1+3}=2,\qquad \theta=\pi-\frac{\pi}{3}=\frac{2\pi}{3}
$$

**第 2 步：棣莫弗。**

$$
z^6=2^6\mathrm e^{\mathrm i\cdot6\cdot\frac{2\pi}{3}}=64\mathrm e^{4\pi\mathrm i}=64
$$

是实数 ✓

**第 3 步：(b) $z=-2\mathrm i$。** $\lvert z\rvert=2$，$\theta=-\frac\pi2$。

**第 4 步：(c) $z=-3$。** $\lvert z\rvert=3$，$\theta=\pi$（负实轴，主辐角取 $\pi$）。

**答案**　如上。

**易错点**　① (a) 的辐角按第四象限算成 $-\frac\pi3$；② 主辐角范围 $(-\pi,\pi]$ 与 $[0,2\pi)$ 混淆；③ 棣莫弗的角度忘记乘 $6$。

### 练习 3　（复矩阵的基本量）

**解**

**第 1 步：(a) 共轭转置。**

$$
A^{\mathsf H}=\begin{bmatrix}2&\overline{1-\mathrm i}\\[1mm]\overline{1+\mathrm i}&3\end{bmatrix}=\begin{bmatrix}2&1+\mathrm i\\1-\mathrm i&3\end{bmatrix}=A
$$

故 $A$ 是**厄米矩阵**。

**第 2 步：(b) 长度（用 $\mathbf x^{\mathsf H}\mathbf x=\sum\lvert x_i\rvert^2$）。**

$$
\lVert\mathbf v\rVert=\sqrt{\lvert1+\mathrm i\rvert^2+1}=\sqrt{2+1}=\sqrt3,\qquad \lVert\mathbf w\rVert=\sqrt{1+\lvert-1-\mathrm i\rvert^2}=\sqrt3
$$

**第 3 步：(c) 复内积。**

$$
\mathbf v^{\mathsf H}\mathbf w=\overline{(1+\mathrm i)}\cdot1+\overline{1}\cdot(-1-\mathrm i)=(1-\mathrm i)+(-1-\mathrm i)=-2\mathrm i\ne0
$$

⇒ 不正交。

**第 4 步：(d) 特征值。** $\operatorname{tr}=5$、$\det=6-(1+\mathrm i)(1-\mathrm i)=6-2=4$：

$$
\lambda^2-5\lambda+4=0\ \Longrightarrow\ \lambda=4,1
$$

都是实数 ✓（厄米矩阵的特征值必为实数）。

**答案**　如上。

**易错点**　① 转置不取共轭（得不出厄米性）；② 长度用 $\mathbf v^{\mathsf T}\mathbf v$（会得到复数）；③ 内积顺序（$\mathbf v^{\mathsf H}\mathbf w$ 与 $\mathbf w^{\mathsf H}\mathbf v$ 互为共轭）。

### 练习 4　（伴随恒等式与正交补）

**解**

**第 1 步：恒等式。** 由 $(AB)^{\mathsf H}=B^{\mathsf H}A^{\mathsf H}$：

$$
(A\mathbf x)^{\mathsf H}\mathbf y=\mathbf x^{\mathsf H}A^{\mathsf H}\mathbf y
$$

两边都是数（$1\times1$），可直接比较 ✓

**第 2 步：$\mathbf C(A)^{\perp}=\mathbf N(A^{\mathsf H})$。**

$\mathbf y\perp\mathbf C(A)$ ⟺ 对一切 $\mathbf x$ 有 $(A\mathbf x)^{\mathsf H}\mathbf y=0$；由第 1 步 ⟺ 对一切 $\mathbf x$ 有 $\mathbf x^{\mathsf H}\left(A^{\mathsf H}\mathbf y\right)=0$。

**第 3 步：取 $\mathbf x=A^{\mathsf H}\mathbf y$。** 若上式对一切 $\mathbf x$ 成立，则取 $\mathbf x=A^{\mathsf H}\mathbf y$ 得 $\lVert A^{\mathsf H}\mathbf y\rVert^2=0$，故 $A^{\mathsf H}\mathbf y=\mathbf 0$；反之显然。故两集合相等。$\blacksquare$

### 练习 5　（三个「为什么」）

**解**

**第 1 步：(a) 全复特征值的实矩阵。** 取

$$
A=\begin{bmatrix}0&-1&0&0\\1&0&0&0\\0&0&0&-2\\0&0&2&0\end{bmatrix}=\operatorname{diag}\left(R_{\pi/2},\ 2R_{\pi/2}\right)
$$

特征值为 $\pm\mathrm i$ 与 $\pm2\mathrm i$。为什么必然是 $4$ 个复的：实矩阵的非实特征值必成**共轭对**出现，$4$ 个非实特征值恰好组成两对；若出现一个实特征值，它的共轭是它自己，会占掉奇数个位置，与「两对」的结构冲突。

**第 2 步：(b) $\mathbb C$ 不能全序。** 假设存在这样的序。

- 若 $\mathrm i\ge0$：由 $0\le a,0\le b\Rightarrow0\le ab$ 得 $\mathrm i^2=-1\ge0$，即 $1\le0$；又 $0\le1$（$1=1^2$）⇒ 矛盾。
- 若 $\mathrm i<0$：则 $-\mathrm i>0$，同法得 $(-\mathrm i)^2=-1>0$，同样 $1<0$，再由 $0\le(-1)(-1)=1$ 得矛盾。

故不存在与加乘相容的全序。（$\mathbb C$ 只能定义「模」这种非序的大小。）

**第 3 步：(c) $\mathbf v^{\mathsf H}\mathbf v=0\Rightarrow\mathbf v=\mathbf 0$。**

$$
\mathbf v^{\mathsf H}\mathbf v=\sum_i\lvert v_i\rvert^2=0\ \Longrightarrow\ \lvert v_i\rvert=0\ \forall i\ \Longrightarrow\ \mathbf v=\mathbf 0
$$

实域同理（$\sum v_i^2=0\Rightarrow v_i=0$）。但若**不取共轭**，$\mathbf v^{\mathsf T}\mathbf v=\sum v_i^2$ 可为 $0$ 而 $\mathbf v\ne\mathbf 0$：取 $\mathbf v=(1,\mathrm i)$，则 $1+\mathrm i^2=0$——这正是复内积必须带共轭的理由。$\blacksquare$

## 9-2 Hermitian 矩阵与酉矩阵（5 题）

| 题号 | 结论 |
|---|---|
| 练习 1 | $A_1$ 厄米且酉（$\lambda=\pm1$）；$A_2,A_3$ 都不是 |
| 练习 2 | $\lambda=5,1$；$Q\Lambda Q^{\mathsf H}$ 见解析 |
| 练习 3 | **原题系数 $1/\sqrt5$ 有误**，应为 $1/2$；$\det=-1$；$\lambda=\frac{\sqrt3+\mathrm i}{2}$ 等 |
| 练习 4 | 四条证明 |
| 练习 5 | 见解析 |

### 练习 1　（三者的定性）

**解**

**第 1 步：(a) $A_1=\begin{bmatrix}0&-\mathrm i\\ \mathrm i&0\end{bmatrix}$。**

$$
A_1^{\mathsf H}=\begin{bmatrix}0&\overline{\mathrm i}\\ \overline{-\mathrm i}&0\end{bmatrix}=\begin{bmatrix}0&-\mathrm i\\ \mathrm i&0\end{bmatrix}=A_1
$$

⇒ 厄米 ✓。又 $A_1^{\mathsf H}A_1=A_1^2$：

$$
A_1^2=\begin{bmatrix}(-\mathrm i)(\mathrm i)&0\\0&(\mathrm i)(-\mathrm i)\end{bmatrix}=\begin{bmatrix}1&0\\0&1\end{bmatrix}
$$

⇒ 也是酉矩阵 ✓。特征值：$\operatorname{tr}=0$、$\det=-(-\mathrm i)(\mathrm i)=-1$，故 $\lambda^2-1=0$，$\lambda=\pm1$（实数 ✓）。

**第 2 步：(b) $A_2=\frac{1}{\sqrt2}\begin{bmatrix}1&\mathrm i\\ \mathrm i&1\end{bmatrix}$。** 它对称但

$$
A_2^{\mathsf H}=\frac{1}{\sqrt2}\begin{bmatrix}1&-\mathrm i\\ -\mathrm i&1\end{bmatrix}\ne A_2
$$

⇒ 非厄米。且 $A_2^{\mathsf H}A_2=\begin{bmatrix}1&0\\-\mathrm i&1\end{bmatrix}\ne I$ ⇒ 非酉。

**第 3 步：(c) $A_3=\begin{bmatrix}1&2\mathrm i\\ 2\mathrm i&1\end{bmatrix}$。** $A_3^{\mathsf H}=\begin{bmatrix}1&-2\mathrm i\\ -2\mathrm i&1\end{bmatrix}\ne A_3$ ⇒ 非厄米；$A_3^{\mathsf H}A_3=\begin{bmatrix}5&0\\0&5\end{bmatrix}\ne I$ ⇒ 非酉。

**答案**　$A_1$ 厄米且酉（$\lambda=\pm1$）；$A_2$、$A_3$ 都不是。

### 练习 2　（厄米矩阵的谱分解）

**解**

**第 1 步：(a) 厄米性。**

$$
A^{\mathsf H}=\begin{bmatrix}3&\overline{-2\mathrm i}\\[1mm]\overline{2\mathrm i}&3\end{bmatrix}=\begin{bmatrix}3&2\mathrm i\\-2\mathrm i&3\end{bmatrix}=A
$$

✓

**第 2 步：(b) 特征值。** $\operatorname{tr}=6$、$\det=9-(2\mathrm i)(-2\mathrm i)=9-4=5$：

$$
\lambda^2-6\lambda+5=0\ \Longrightarrow\ \lambda=5,1
$$

**第 3 步：特征向量。** $\lambda=5$：$A-5I=\begin{bmatrix}-2&2\mathrm i\\-2\mathrm i&-2\end{bmatrix}$ ⇒ $-2x_1+2\mathrm i x_2=0$ ⇒ $x_1=\mathrm i x_2$，取 $\mathbf v_1=(\mathrm i,1)^{\mathsf T}$。

$\lambda=1$：$A-I=\begin{bmatrix}2&2\mathrm i\\-2\mathrm i&2\end{bmatrix}$ ⇒ $x_1=-\mathrm i x_2$，取 $\mathbf v_2=(-\mathrm i,1)^{\mathsf T}$。

**第 4 步：(c) 正交性。**

$$
\mathbf v_1^{\mathsf H}\mathbf v_2=\overline{\mathrm i}\cdot(-\mathrm i)+1\cdot1=(-\mathrm i)(-\mathrm i)+1=\mathrm i^2+1=0
$$

✓

**第 5 步：(d) 谱分解。** 归一化（$\lVert\mathbf v_i\rVert=\sqrt2$）：

$$
Q=\frac{1}{\sqrt2}\begin{bmatrix}\mathrm i&-\mathrm i\\1&1\end{bmatrix},\qquad \Lambda=\begin{bmatrix}5&0\\0&1\end{bmatrix},\qquad A=Q\Lambda Q^{\mathsf H}
$$

**答案**　如上。

### 练习 3　（酉矩阵：原题系数有误）

**解**

**第 1 步：检验列长。**

$$
\left\lvert1+\mathrm i\right\rvert^2=2,\qquad \left\lvert1-\mathrm i\right\rvert^2=2
$$

两列的范数都是 $\sqrt{2+2}=2$，故

$$
U=\frac{1}{\sqrt5}\begin{bmatrix}1+\mathrm i&1+\mathrm i\\1-\mathrm i&-1+\mathrm i\end{bmatrix}
$$

并不酉：$U^{\mathsf H}U=\frac45I$。

> [!warning] 原题系数应为 $\frac12$
> 要使矩阵酉，前置系数应取 $\frac12$（使列长为 $1$）。下面用修正后的
> $$U=\frac12\begin{bmatrix}1+\mathrm i&1+\mathrm i\\1-\mathrm i&-1+\mathrm i\end{bmatrix}$$
> 继续作答。

**第 2 步：(a) 三性验证（修正版）。**

$$
U^{\mathsf H}=\frac12\begin{bmatrix}1-\mathrm i&1+\mathrm i\\1-\mathrm i&-1-\mathrm i\end{bmatrix},\qquad U^{\mathsf H}U=\frac14\begin{bmatrix}4&0\\0&4\end{bmatrix}=I
$$

✓

**第 3 步：(b) 行列式。**

$$
\det U=\frac14\left[(1+\mathrm i)(-1+\mathrm i)-(1+\mathrm i)(1-\mathrm i)\right]=\frac14\left[-2-2\right]=-1
$$

$\lvert\det U\rvert=1$ ✓

**第 4 步：(c) 特征值。** $\operatorname{tr}U=\frac12\left[(1+\mathrm i)+(-1+\mathrm i)\right]=\mathrm i$，$\det U=-1$：

$$
\lambda^2-\mathrm i\lambda-1=0\ \Longrightarrow\ \lambda=\frac{\mathrm i\pm\sqrt{-1+4}}{2}=\frac{\pm\sqrt3+\mathrm i}{2}
$$

两个特征值的模都是 $\sqrt{\frac{3+1}{4}}=1$ ✓ 都在单位圆上。

**第 5 步：(d) $U^2$。**

$$
U^2=\frac14\begin{bmatrix}2+2\mathrm i&-2+2\mathrm i\\0&2-2\mathrm i\end{bmatrix}=\frac12\begin{bmatrix}1+\mathrm i&-1+\mathrm i\\0&1-\mathrm i\end{bmatrix}
$$

**答案**　修正后：酉、$\det=-1$、$\lambda=\frac{\pm\sqrt3+\mathrm i}{2}$、$U^2$ 如上。

### 练习 4　（四条证明）

**解**

**第 1 步：(a)** 厄米 $A=Q\Lambda Q^{\mathsf H}$（$\lambda_k$ 实）。定义

$$
\mathrm e^{\mathrm i tA}=Q\operatorname{diag}\left(\mathrm e^{\mathrm i t\lambda_k}\right)Q^{\mathsf H}
$$

则 $\left(\mathrm e^{\mathrm i tA}\right)^{\mathsf H}=Q\operatorname{diag}\left(\mathrm e^{-\mathrm i t\lambda_k}\right)Q^{\mathsf H}$，两者相乘得 $QIQ^{\mathsf H}=I$ ⇒ 酉。

**第 2 步：(b) 反厄米。** 设 $A\mathbf x=\lambda\mathbf x$。用 $A^{\mathsf H}=-A$：

$$
\lambda\lVert\mathbf x\rVert^2=\mathbf x^{\mathsf H}A\mathbf x,\qquad \overline{\lambda}\lVert\mathbf x\rVert^2=\left(\mathbf x^{\mathsf H}A\mathbf x\right)^{\mathsf H}=\mathbf x^{\mathsf H}A^{\mathsf H}\mathbf x=-\mathbf x^{\mathsf H}A\mathbf x=-\lambda\lVert\mathbf x\rVert^2
$$

故 $\overline\lambda=-\lambda$，即 $\lambda$ 为纯虚数（或 $0$）。

**第 3 步：(c) 酉可对角化 ⇒ 正规。** $A=Q\Lambda Q^{\mathsf H}$：

$$
A^{\mathsf H}A=Q\overline{\Lambda}\Lambda Q^{\mathsf H}=Q\left\lvert\Lambda\right\rvert^2Q^{\mathsf H}=AA^{\mathsf H}
$$

⇒ $A$ 正规 ✓

**第 4 步：(d) $F_4F_4^{\mathsf H}=4I$。** $F_4$ 的元素是 $\omega^{jk}$（$\omega=\mathrm i$）。第 $k$ 行与第 $l$ 行的内积

$$
\sum_{j=0}^{3}\omega^{j(k-l)}=\begin{cases}4,&k=l\\ \dfrac{1-\omega^{4(k-l)}}{1-\omega^{k-l}}=0,&k\ne l\end{cases}
$$

故 $F_4F_4^{\mathsf H}=4I$，即行两两正交、每行长度为 $2$。$\blacksquare$

### 练习 5　（三问）

**解**

**第 1 步：(a) 实矩阵的特例。** 厄米条件 $A^{\mathsf H}=A$ 在实矩阵上退化为 $A^{\mathsf T}=A$；酉条件 $U^{\mathsf H}U=I$ 在实矩阵上退化为 $U^{\mathsf T}U=I$。

反例：$U=\operatorname{diag}(\mathrm i,1)$ 酉但 $U^{\mathsf H}=\operatorname{diag}(-\mathrm i,1)\ne U$ ⇒ 非厄米；$H=\operatorname{diag}(1,2)$ 厄米但 $H^{\mathsf H}H=\operatorname{diag}(1,4)\ne I$ ⇒ 非酉。

**第 2 步：(b) 多项式保持正规性。** 若 $A=Q\Lambda Q^{\mathsf H}$，则 $p(A)=Qp(\Lambda)Q^{\mathsf H}$（对角元为 $p(\lambda_i)$）。于是

$$
p(A)^{\mathsf H}p(A)=Q\overline{p(\Lambda)}p(\Lambda)Q^{\mathsf H}=Q\left\lvert p(\Lambda)\right\rvert^2Q^{\mathsf H}=p(A)p(A)^{\mathsf H}
$$

⇒ 正规 ✓

**第 3 步：(c) 四个虚特征值的实矩阵。**

$$
A=\operatorname{diag}\left(\begin{bmatrix}0&-1\\1&0\end{bmatrix},\ \begin{bmatrix}0&-2\\2&0\end{bmatrix}\right)
$$

特征值为 $\pm\mathrm i,\ \pm2\mathrm i$（无实特征值）。

**第 4 步：能是对称的吗？** **不能**：实对称矩阵的特征值全为实数（谱定理），而本题要求四个纯虚特征值。故 $A$ 必须非对称——事实上它是「反对称」的（$A^{\mathsf T}=-A$），而反对称阵的特征值恰为纯虚数（见练习 4(b)）。$\blacksquare$

## 9-3 快速傅里叶变换 FFT（5 题）

| 题号 | 结论 |
|---|---|
| 练习 1 | $\omega^k$ 列表见解析；两个和都是 $0$ |
| 练习 2 | $F_4\mathbf x=(0,0,4,0)^{\mathsf T}$；频率 $2$ |
| 练习 3 | $P_8,D_4$ 见解析；每层 $2n$ 个非零元 |
| 练习 4 | 循环卷积定理 |
| 练习 5 | 见解析 |

### 练习 1　（六次单位根）

**解**

**第 1 步：(a) 列表。** 记 $c=\frac12$、$s=\frac{\sqrt3}{2}$：

$$
\omega^0=1,\ \omega^1=c+s\mathrm i,\ \omega^2=-\tfrac12+s\mathrm i,\ \omega^3=-1,\ \omega^4=-\tfrac12-s\mathrm i,\ \omega^5=c-s\mathrm i,\ \omega^6=1
$$

**第 2 步：(b) 共轭配对。**

$$
\omega^{6-1}=\omega^5=c-s\mathrm i=\overline{\omega}\ ✓,\qquad \omega^{6-2}=\omega^4=-\tfrac12-s\mathrm i=\overline{\omega^2}\ ✓
$$

**第 3 步：(c) 两个和。**

$$
\sum_{j=0}^{5}\omega^{2j}=\frac{1-\omega^{12}}{1-\omega^{2}}=0\quad\left(\omega^{12}=1,\ \omega^2\ne1\right)
$$

$$
\sum_{j=0}^{5}\omega^{3j}=\sum_{j=0}^{5}(-1)^{j}=1-1+1-1+1-1=0
$$

与引理 3.2（$\sum_j\omega^{mj}=0$ 当 $n\nmid m$）一致 ✓

**答案**　如上。

### 练习 2　（四点 DFT）

**解**

**第 1 步：(a) 直接算。** $F_4=\left(\omega^{jk}\right)$，$\omega=\mathrm i$：

$$
F_4\mathbf x=\begin{bmatrix}1&1&1&1\\1&\mathrm i&-1&-\mathrm i\\1&-1&1&-1\\1&-\mathrm i&-1&\mathrm i\end{bmatrix}\begin{bmatrix}1\\-1\\1\\-1\end{bmatrix}=\begin{bmatrix}0\\0\\4\\0\end{bmatrix}
$$

（逐行：第 $1$ 行 $1-1+1-1=0$；第 $2$ 行 $1-\mathrm i-1+\mathrm i=0$；第 $3$ 行 $1+1+1+1=4$；第 $4$ 行 $1+\mathrm i-1-\mathrm i=0$。）

**第 2 步：(b) FFT 路径。** 奇偶置换得 $(x_0,x_2,x_1,x_3)=(1,1,-1,-1)$；两次 $F_2$（即和与差）得 $(2,0)$、$(-2,0)$；蝶形合并：

$$
\left(2+(-2),\ 0+0,\ 2-(-2),\ 0-0\right)=(0,0,4,0)
$$

✓ 与 (a) 相同。

**第 3 步：(c) Parseval。** $\lVert F_4\mathbf x\rVert^2=16$，$4\lVert\mathbf x\rVert^2=4\cdot4=16$ ✓

**第 4 步：(d) 频率。** 序列 $1,-1,1,-1$ 的周期是 $2$，即每个采样点交替变号，对应**最高频率** $k=2=n/2$（Nyquist 频率）。因此能量全部集中在第 $2$ 个分量，谱很稀疏。

**答案**　$(0,0,4,0)^{\mathsf T}$；频率 $k=2$（Nyquist）。

### 练习 3　（$F_8$ 的分解）

**解**

**第 1 步：(a) 置换矩阵 $P_8$。** 它把偶下标排在前、奇下标排在后：

$$
P_8=\begin{bmatrix}1&0&0&0&0&0&0&0\\0&0&1&0&0&0&0&0\\0&0&0&0&1&0&0&0\\0&0&0&0&0&0&1&0\\0&1&0&0&0&0&0&0\\0&0&0&1&0&0&0&0\\0&0&0&0&0&1&0&0\\0&0&0&0&0&0&0&1\end{bmatrix}
$$

（每行每列恰一个 $1$，把 $(x_0,\dots,x_7)$ 变成 $(x_0,x_2,x_4,x_6,x_1,x_3,x_5,x_7)$。）

**第 2 步：(b) $D_4$。** $\omega=\mathrm e^{\pi\mathrm i/4}=c(1+\mathrm i)$，$c=\frac{\sqrt2}{2}$：

$$
D_4=\operatorname{diag}\left(1,\ \omega,\ \omega^2,\ \omega^3\right)=\operatorname{diag}\left(1,\ c(1+\mathrm i),\ \mathrm i,\ c(-1+\mathrm i)\right)
$$

**第 3 步：(c) 非零元个数。** $\begin{bmatrix}I_4&D_4\\I_4&-D_4\end{bmatrix}$ 中 $I_4$ 有 $4$ 个、$D_4$ 有 $4$ 个，四块共

$$
4+4+4+4=16=2n
$$

个非零元。乘以稀疏矩阵只需对每个非零元做一次「乘 + 加」，故 $O(n)$ 次运算（而稠密矩阵要 $O(n^2)$）。

**第 4 步：(d) 三层分解。** 再把 $F_4=\begin{bmatrix}I_2&D_2\\I_2&-D_2\end{bmatrix}P_4$ 代回，得

$$
F_8=\underbrace{\begin{bmatrix}I_4&D_4\\I_4&-D_4\end{bmatrix}}_{\text{第 }1\text{ 层}}\underbrace{\begin{bmatrix}B_4&0\\0&B_4\end{bmatrix}}_{\text{第 }2\text{ 层}}\underbrace{\begin{bmatrix}P_4&0\\0&P_4\end{bmatrix}P_8}_{\text{置换}}
$$

其中 $B_4=\begin{bmatrix}I_2&D_2\\I_2&-D_2\end{bmatrix}$。

逐层非零元数：第 $1$ 层 $16=2n$；第 $2$ 层两块各 $8$，合计 $16=2n$；最内层的 $F_2$ 层（四个 $F_2$）合计 $16=2n$。故 $F_8$ 乘一个向量只需

$$
\underbrace{2n}_{\text{每层}}\times\underbrace{\log_2 n}_{3\text{ 层}}=O(n\log n)
$$

次运算。$\blacksquare$

**答案**　如上。

### 练习 4　（循环卷积定理）

**解**

**第 1 步：(a) 循环矩阵。** 以 $n=4$ 为例，

$$
C(\mathbf h)=\begin{bmatrix}h_0&h_3&h_2&h_1\\h_1&h_0&h_3&h_2\\h_2&h_1&h_0&h_3\\h_3&h_2&h_1&h_0\end{bmatrix}
$$

每一行是上一行右移一位（循环）。它是**正规**矩阵：$C(\mathbf h)^{\mathsf H}$ 也是循环矩阵，而两个循环矩阵必可交换（都是 $n$ 次循环移位算子的多项式），故 $C^{\mathsf H}C=CC^{\mathsf H}$。

**第 2 步：(b) 特征向量是傅里叶列。** 记 $\mathbf c_k=\left(\omega^{0k},\omega^{1k},\dots,\omega^{(n-1)k}\right)^{\mathsf T}$。直接计算 $C(\mathbf h)\mathbf c_k$ 的第 $j$ 个分量：

$$
\sum_{m=0}^{n-1}h_{j-m}\omega^{mk}=\omega^{jk}\sum_{m}h_{j-m}\omega^{(m-j)k}=\omega^{jk}\sum_{r}h_{r}\omega^{-rk}=\hat h_{-k}\omega^{jk}
$$

（用了 $\omega^{jk}\omega^{-jk}=1$ 与指标替换 $r=j-m$。）故 $\mathbf c_k$ 是特征向量，特征值为 $\hat h_{-k}$（取共轭下标即得 $\hat h_k$ 的版本）。

**第 3 步：(c) 谱分解。**

$$
C(\mathbf h)=\frac1nF_n^{\mathsf H}\operatorname{diag}\left(\hat{\mathbf h}\right)F_n
$$

于是对任意 $\mathbf x$：

$$
C(\mathbf h)\mathbf x=\frac1nF_n^{\mathsf H}\left(\hat{\mathbf h}\odot\left(F_n\mathbf x\right)\right)
$$

即「循环卷积 = 傅里叶变换 → 逐点相乘 → 逆变换」。

**第 4 步：(d) 复杂度。** 两次 FFT + 一次逐点乘 + 一次逆 FFT，各 $O(n\log n)$，合计

$$
O(n\log n)
$$

远快于直接卷积的 $O(n^2)$。$\blacksquare$

### 练习 5　（四问）

**解**

**第 1 步：(a) 为什么是 $O(n)$ 而非 $O(n^2)$。** $\begin{bmatrix}I&D\\I&-D\end{bmatrix}$ 每行只有**两个**非零元（对应「前一半 ± 后一半」的蝶形），共 $2n$ 个非零元：每对分量做 $1$ 次乘（乘 $D$ 的对角元）、$2$ 次加。故这一步 $O(n)$，而非稠密矩阵的 $O(n^2)$。

**第 2 步：(b) $n=3^k$ 的三分方案。** 按模 $3$ 分成三组，得

$$
T(n)=3T\left(\frac n3\right)+O(n)
$$

由主定理（$a=3$，$b=3$，$f(n)=O(n)$ ⇒ $\log_ba=1$ 恰为临界情形）：$T(n)=O(n\log n)$，底数为 $3$。与二进制版本只差常数因子（$\log_3 n=\log_2 n/\log_2 3$）。

**第 3 步：(c) 补零提高不了分辨率。** 补零只增加**频率采样点密度**（谱图上点更密，看起来更「平滑」），但真实分辨率由

$$
\Delta f\approx\frac1T
$$

决定，$T$ 是**观测时长**。补零不增加信息，故不能分辨更近的两个频率。

**第 4 步：(d) 正交基与可逆、保能量。** $F_n$ 的列正交且长为 $\sqrt n$，即 $F_n^{\mathsf H}F_n=nI$。于是

- **可逆**：$F_n^{-1}=\frac1nF_n^{\mathsf H}$ 显式存在；
- **保能量**（Parseval）：$\lVert F_n\mathbf x\rVert^2=\mathbf x^{\mathsf H}F_n^{\mathsf H}F_n\mathbf x=n\lVert\mathbf x\rVert^2$，即（归一化后）变换是酉变换、不改变能量。

两件事是同一事实（$F_n^{\mathsf H}F_n=nI$）的两个推论。$\blacksquare$
