---
title: 线性代数 第 10 章 · 应用 习题答案
aliases:
  - 线性代数应用 习题答案
tags:
  - 类型/习题答案
  - 线性代数/应用
chapter: "10"
created: 2026-10-17
updated: 2026-10-17
---

# 线性代数 第 10 章 · 应用（40 题）

> [!abstract] 本章速览
> 5 篇 · 40 题：图与网络（10-1，9 题）、Markov 矩阵与稳态（10-2，9 题）、线性规划（10-3，6 题）、傅里叶级数与函数空间（10-4，7 题）、图形学与密码学（10-5，9 题）。

## 10-1 图与网络（9 题）

| 题号 | 结论 |
|---|---|
| 10.1.1 | $\operatorname{rank}A=3$；$\dim\mathbf N(A)=1$、$\dim\mathbf N(A^{\mathsf T})=0$；独立回路 $1$ |
| 10.1.2 | $\lambda=0,2,4,2$；生成树 $4$（目测 $4$） |
| 10.1.3 | 电势 $(3,2,1,0)$；电流 $(1,1,1)$；$\sum y^2=\mathbf f^{\mathsf T}\mathbf x=3$ |
| 10.1.4 | $\operatorname{rank}L=n-c$ |
| 10.1.5 | KVL 的两种表述 |
| 10.1.6–10.1.9 | 见解析 |

### 10.1.1　（$P_4$ 的关联矩阵）

**解**

**第 1 步：$A$（$3\times4$，行=边）。**

$$
A=\begin{bmatrix}-1&1&0&0\\0&-1&1&0\\0&0&-1&1\end{bmatrix}
$$

**第 2 步：读数。** 三个主元 ⇒ $\operatorname{rank}A=3=n-1$；$\dim\mathbf N(A)=4-3=1$，基 $\{(1,1,1,1)^{\mathsf T}\}$（常电势）；$\dim\mathbf N(A^{\mathsf T})=3-3=0$（基为空——树无回路）。

**第 3 步：四个基本子空间。**

- $\mathbf C(A^{\mathsf T})$（行空间，$\mathbb R^4$，维 $3$）：$\operatorname{span}\{(-1,1,0,0),(0,-1,1,0),(0,0,-1,1)\}$；
- $\mathbf N(A)$：$\operatorname{span}\{(1,1,1,1)\}$；
- $\mathbf C(A)=\mathbb R^3$（维 $3$）；
- $\mathbf N(A^{\mathsf T})=\{\mathbf 0\}$。

**第 4 步：欧拉公式。** 独立回路数

$$
m-n+c=3-4+1=0\ ?
$$

注意这里的欧拉公式针对**几何图**：$V-E+F=2$。对树而言独立回路数 $m-n+1=0$ ✓（$P_4$ 无回路），与 $\dim\mathbf N(A^{\mathsf T})=0$ 一致。

**答案**　如上。

### 10.1.2　（$C_4$ 的拉普拉斯矩阵与生成树）

**解**

**第 1 步：$L=A^{\mathsf T}A$。**

$$
L=\begin{bmatrix}2&-1&0&-1\\-1&2&-1&0\\0&-1&2&-1\\-1&0&-1&2\end{bmatrix}
$$

**第 2 步：特征值。** 对 $n$ 圈，$\lambda_k=2-2\cos\frac{2\pi k}{n}$：

$$
\lambda=0,\ 2,\ 4,\ 2
$$

**第 3 步：生成树个数。**

$$
\tau=\frac1n\prod_{k\ge2}\lambda_k=\frac14\left(2\cdot4\cdot2\right)=4
$$

**第 4 步：目测。** $C_4$ 去掉任意一条边即得生成树 ⇒ $4$ 棵 ✓ 一致。

**答案**　如上。

### 10.1.3　（电阻网络）

**解**

**第 1 步：$L$ 与接地。** $L$ 同 10.1.2 的形式（$P_4$）：

$$
L=\begin{bmatrix}1&-1&0&0\\-1&2&-1&0\\0&-1&2&-1\\0&0&-1&1\end{bmatrix}
$$

注入 $\mathbf f=(1,0,0,-1)^{\mathsf T}$；接地节点 $4$（$x_4=0$）。

**第 2 步：解方程（节点 1–3）。**

$$
x_1-x_2=1,\quad -x_1+2x_2-x_3=0,\quad -x_2+2x_3=0
$$

由第三式 $x_2=2x_3$；代入第二式 $x_1=3x_3$；代入第一式 $x_3=1$。故

$$
\mathbf x=(3,2,1,0)^{\mathsf T}
$$

**第 3 步：电流。** $y_j=x_p-x_q$：

$$
\mathbf y=(1,1,1)^{\mathsf T}
$$

**第 4 步：功率守恒。**

$$
\sum_j y_j^2=3,\qquad \mathbf f^{\mathsf T}\mathbf x=1\cdot3+(-1)\cdot0=3
$$

✓

**第 5 步：为什么线性下降。** 每个内部节点满足 $\sum$ 邻边电流 $=0$，即

$$
-x_{i-1}+2x_i-x_{i+1}=0
$$

这正是 $u''=0$ 的中心差分 ⇒ 解为线性函数。

**答案**　$\mathbf x=(3,2,1,0)^{\mathsf T}$、$\mathbf y=(1,1,1)^{\mathsf T}$。

### 10.1.4　（$\operatorname{rank}L=n-c$）

**解**

**第 1 步：二次型。** 由 $L=A^{\mathsf T}A$：

$$
\mathbf x^{\mathsf T}L\mathbf x=\lVert A\mathbf x\rVert^2=\sum_{\text{边 }pq}\left(x_q-x_p\right)^2
$$

**第 2 步：零空间。** $\mathbf x^{\mathsf T}L\mathbf x=0\iff$ 每条边上 $x_p=x_q$ $\iff$ $\mathbf x$ 在**每个连通分量**内为常数。

**第 3 步：维数。** 设连通分量数为 $c$，则 $\mathbf N(L)$ 由各分量的示性向量张成 ⇒ $\dim\mathbf N(L)=c$。

**第 4 步：结论。** 由秩—零化度：

$$
\operatorname{rank}L=n-c
$$

$\blacksquare$

### 10.1.5　（KVL 的两种表述）

**解**

**第 1 步：$\mathbf e\in\mathbf C(A)$ 的含义。** 存在节点电势 $\mathbf x$ 使 $\mathbf e=A\mathbf x$，即每条边上有 $e_{pq}=x_q-x_p$（电势差）。

**第 2 步：等价性。** 沿任一回路 $p_1\to p_2\to\cdots\to p_k\to p_1$ 求和，电势差**望远镜相消**：

$$
\sum_{\text{回路}}e_{pq}=\sum\left(x_{q}-x_{p}\right)=0
$$

反之，若所有回路求和为零，则「沿路径积分与路径无关」⇒ 可定义单值电势 $\mathbf x$ ⇒ $\mathbf e=A\mathbf x\in\mathbf C(A)$。

**第 3 步：三角形反例。** 取三角形 $1\to2\to3\to1$，若 $\mathbf e=(1,0,0)^{\mathsf T}$，则沿回路求和 $=1\ne0$ ⇒ $\mathbf e\notin\mathbf C(A)$。物理含义：这种电压分布**无法由任何电势实现**，即违反 KVL——不存在这样的稳态电阻网络。

**答案**　得证。$\blacksquare$

### 10.1.6　（反向一条边）

**解**

**第 1 步：$A$ 的变化。** 第 $4$ 行（$B\to D$）变成 $D\to B$，即该行取反（非零元位置由 $-1,+1$ 变为 $+1,-1$）。

**第 2 步：节点方程。** $A^{\mathsf T}\mathbf x=\mathbf f$ 中等式左边 $x_4$ 的系数全变号 ⇒ 相当于把未知量换成 $-x_4$。

**第 3 步：自由度与解集。** $\operatorname{rank}$ 不变、$m,n$ 不变 ⇒ 自由度 $m-n+1$ 不变；通解的形状不变，只需把 $x_4$ 换成 $-x_4$（即环流方向反号）。基础解系（回路向量）的结构不变。

**答案**　该行取反；方程中 $x_4$ 变号；自由度与基础解系结构不变。

### 10.1.7　（灌溉网）

**解**

**第 1 步：(1) 总和。** $\sum f_j=30-10-15+5-10=0$ ✓（可解的必要条件）。

**第 2 步：(2) 自由度。** 连通图：$m-n+1=7-5+1=3$。

**第 3 步：(3) 孤立节点。** 封闭后节点 $C$ 孤立且 $f_C=-15\ne0$。此时 $A'$ 的秩

$$
r\left(A'\right)=n-2=3
$$

（剩下 $4$ 个节点仍连通），而增广矩阵多一列（含 $f_C$ 所在方程常数）

$$
r\left(\overline{A'}\right)=4\ne3
$$

⇒ **无解**。

**第 4 步：(4) 改数据。** 新 $\sum f_j=45-10+0+5-10=30\ne0$ ⇒ 仍**无解**（总量不为零是硬性障碍）。

**答案**　如上。

### 10.1.8　（Kruskal 与最小生成树）

**解**

**第 1 步：(1) 排序。** 权重 $(4,5,1,3,2,6)$ 对应边 $1$–$6$，从小到大：$e_3(1),e_5(2),e_4(3),e_1(4),e_2(5),e_6(6)$。

**第 2 步：逐步加边。** 依次加入 $e_3$（不成圈，收）、$e_5$（收）、$e_4$（收）——已得 $n-1=3$ 条边，算法停止。

**第 3 步：(2) 列无关。** 生成树无回路 ⇒ 对应 3 列的关联矩阵子块满秩（$\det\ne0$），故线性无关。

**第 4 步：(3) 与独立回路数。** 补边数

$$
m-(n-1)=m-n+1=\text{独立回路数}
$$

生成树的边数 $n-1$、补边数 $m-n+1$，二者之和为 $m$ ✓

**答案**　MST 为 $\{e_3,e_5,e_4\}$（总权 $6$），其余见解析。

### 10.1.9　（两个可行方案之差）

**解**

**第 1 步：差满足齐次方程。** 若 $A^{\mathsf T}\mathbf x=A^{\mathsf T}\mathbf x'=\mathbf f$，则

$$
A^{\mathsf T}\left(\mathbf x-\mathbf x'\right)=\mathbf 0\ \Longrightarrow\ \mathbf x-\mathbf x'\in\mathbf N\left(A^{\mathsf T}\right)
$$

**第 2 步：零空间即回路空间。** $\mathbf N(A^{\mathsf T})$ 由「沿独立回路绕行」的向量张成（维数 $m-n+c$）。

**第 3 步：物理结论。** 两个可行流量方案的差别只能是**环流**（绕圈流动、净效果为零）——不改变任何节点的净注入。$\blacksquare$

## 10-2 Markov 矩阵与稳态（9 题）

| 题号 | 结论 |
|---|---|
| 10.2.1 | $A_1,A_3,A_4$ 是随机矩阵；$A_4=I$ 稳态不唯一 |
| 10.2.2 | $\lambda=1,0.5$；稳态 $\left(\frac25,\frac35\right)$ |
| 10.2.3 | $\lambda=1,\omega,\omega^2$；不收敛；时间平均收敛 |
| 10.2.4 | 三条证明 |
| 10.2.5 | 正稳态 $\iff$ 强连通 |
| 10.2.6–10.2.9 | 见解析 |

### 10.2.1　（四个矩阵）

**解**

**第 1 步：判随机性（列和为 $1$）。** $A_1=0.5J$ ✓；$A_2=A_1^{\mathsf T}=A_1$ ✓；$A_3$ 列和 $0.2+0.8=1$、$0.9+0.1=1$ ✓；$A_4=I$ ✓。四个都是随机矩阵。

**第 2 步：稳态。**

- $A_1$：$\mathbf u=\left(\frac12,\frac12\right)$，幂迭代收敛（$\lambda=1,0$）；
- $A_3$：解 $\mathbf u=A_3\mathbf u$ 得 $\mathbf u=\left(\frac9{17},\frac8{17}\right)$，收敛（$|\lambda_2|=0.7<1$）；
- $A_4=I$：任意 $\mathbf u$ 都是稳态，**稳态不唯一**，$\mathbf u_k=\mathbf u_0$ 不收敛到唯一点。

**答案**　如上。

### 10.2.2　（二状态链的闭式）

**解**

**第 1 步：特征值。** $\operatorname{tr}=1.5$、$\det=0.56-0.06=0.5$：

$$
\lambda^2-1.5\lambda+0.5=0\ \Longrightarrow\ \lambda=1,\ 0.5
$$

**第 2 步：稳态。** 由 $-0.3u_1+0.2u_2=0$ 得 $u_1=\frac23u_2$，配合 $u_1+u_2=1$：

$$
\mathbf u=\left(\frac25,\frac35\right)^{\mathsf T}
$$

**第 3 步：闭式。** 由 $\mathbf u_k=\mathbf u+0.5^k\left(\mathbf u_0-\mathbf u\right)$，$\mathbf u_0=(1,0)^{\mathsf T}$：

$$
\mathbf u_k=\begin{bmatrix}\frac25+\frac35\cdot0.5^k\\[1mm]\frac35-\frac35\cdot0.5^k\end{bmatrix}
$$

**第 4 步：极限。** $0.5^k\to0$ ⇒ $\mathbf u_k\to\left(\frac25,\frac35\right)$。

**答案**　如上。

### 10.2.3　（三周期链）

**解**

**第 1 步：特征值。** $A$ 是三轮换置换矩阵，$\lambda^3=1$：

$$
\lambda=1,\ \omega,\ \omega^2\quad\left(\omega=\mathrm e^{2\pi\mathrm i/3}\right)
$$

**第 2 步：为什么不收敛。** 初值沿特征向量方向的分量按 $\omega^k$ 旋转而不衰减，故 $\mathbf u_k$ 以周期 $3$ 振荡。

**第 3 步：稳态。** 由对称性 $\mathbf u=\left(\frac13,\frac13,\frac13\right)$。

**第 4 步：时间平均。**

$$
\frac1K\sum_{k=0}^{K-1}\mathbf u_k\longrightarrow\mathbf u
$$

（因 $(I+A+A^2)/3$ 是秩 $1$ 矩阵，列全等于 $\mathbf u$。）

**答案**　如上。

### 10.2.4　（对称随机矩阵）

**解**

**第 1 步：(1) 双随机。** 列和为 $1$，由 $a_{ij}=a_{ji}$ 得行和 $\sum_ja_{ij}=\sum_ja_{ji}=1$。

**第 2 步：(2) 实特征值与 $|\lambda|\le1$。** 对称 ⇒ 可正交对角化 ⇒ 特征值全实。又对任意特征对，$\lVert A\mathbf x\rVert_2\le\lVert A\rVert_1\lVert\mathbf x\rVert_\infty$…更直接：由 $\lVert A\rVert_1=1$（列和）得 $\rho(A)\le1$。

**第 3 步：(3) 唯一稳态。** $A>0$ ⇒ 不可约且非周期 ⇒ $\lambda=1$ 单重 ⇒ 稳态唯一；由双随机性 $\mathbf u=\frac1n\mathbf 1$ ✓。$\blacksquare$

### 10.2.5　（正稳态与强连通）

**解**

**第 1 步（$\Rightarrow$）。** 设 $u_j=0$。由 $u_j=\sum_i a_{ji}u_i$ 与 $a_{ji}\ge0$、$u_i\ge0$，得所有满足 $a_{ji}>0$ 的 $i$ 都有 $u_i=0$。反复传播，与 $j$ 互通的节点全为 $0$——若强连通则 $\mathbf u=\mathbf 0$，矛盾。

**第 2 步（$\Leftarrow$）。** 强连通 ⇒ $A$ 不可约 ⇒ 由 Perron–Frobenius，$\lambda=1$ 的（右）特征向量可取全正。

**答案**　得证。$\blacksquare$

### 10.2.6　（$d=0.5$ 的 PageRank）

**解**

**第 1 步：$M$。** $M=0.5P+0.1\,\mathbf 1\mathbf 1^{\mathsf T}$。

**第 2 步：稳态。** 用

$$
\mathbf u=\frac{1-d}{n}\left(I-dP\right)^{-1}\mathbf 1=\frac{0.5}{5}\left(I-0.5P\right)^{-1}\mathbf 1
$$

**第 3 步：零入链页面。** 其分数来自均匀项，为

$$
\frac{1-d}{n}=\frac{0.5}{5}=0.1
$$

（原来 $d=0.85$ 时为 $\frac{0.15}{5}=0.03$。）$d$ 越小，均匀项越大，排名越「平均」。

**答案**　如上。

### 10.2.7　（$M$ 与 $P$ 的特征值关系）

**解**

**第 1 步：特征方程。** 设 $M\mathbf v=\lambda\mathbf v$、$\lambda\ne1$：

$$
dP\mathbf v+\frac{1-d}{n}\mathbf 1\mathbf 1^{\mathsf T}\mathbf v=\lambda\mathbf v
$$

**第 2 步：左乘 $\mathbf 1^{\mathsf T}$。** 因 $P$ 随机 ⇒ $\mathbf 1^{\mathsf T}P=\mathbf 1^{\mathsf T}$：

$$
d\,\mathbf 1^{\mathsf T}\mathbf v+(1-d)\,\mathbf 1^{\mathsf T}\mathbf v=\lambda\,\mathbf 1^{\mathsf T}\mathbf v
$$

左边 $=\mathbf 1^{\mathsf T}\mathbf v$，故

$$
\left(1-\lambda\right)\mathbf 1^{\mathsf T}\mathbf v=0\ \Longrightarrow\ \mathbf 1^{\mathsf T}\mathbf v=0
$$

（这一步用到 $\lambda\ne1$。）

**第 3 步：回代。** 均匀项消失，$dP\mathbf v=\lambda\mathbf v$，即

$$
P\mathbf v=\frac{\lambda}{d}\mathbf v
$$

故 $\lambda/d$ 是 $P$ 的特征值。$\blacksquare$

### 10.2.8　（复特征值链）

**解**

**第 1 步：(1) 随机性。** 三列和都是 $1$：$0.5+0.5=1$、$0+0+1=1$、$1+0+0=1$ ✓

**第 2 步：(2) 特征值。** 特征多项式 $\lambda^3-0.5\lambda^2-0.5=(\lambda-1)\left(\lambda^2+0.5\lambda+0.5\right)$：

$$
\lambda=1,\qquad \lambda=\frac{-0.5\pm\mathrm i\sqrt{1.75}}{2}
$$

复根的模 $\sqrt{0.5}\approx0.707<1$。

**第 3 步：(3) 收敛性。** 有自环（$1\to1$，概率 $0.5$）⇒ 非周期 ⇒ 幂迭代**收敛**（不是周期病态，也不可约？——检查：$1\to1,2$；$2\to3$；$3\to1$，三状态互通 ⇒ 不可约 ✓）。

**第 4 步：(4) 加阻尼。** $M=0.85A+0.05\,\mathbf 1\mathbf 1^{\mathsf T}$ 的特征值为

$$
1,\quad0.85\lambda_2,\quad0.85\lambda_3
$$

后两者的模 $\approx0.85\times0.707\approx0.6<1$ ⇒ 必然收敛。

**答案**　如上。

### 10.2.9　（$B=\frac12(A+A^2)$）

**解**

**第 1 步：(1) 随机性。** 列和 $=\frac12(1+1)=1$ ✓

**第 2 步：(2) 稳态不变。** 若 $A\mathbf u=\mathbf u$，则 $A^2\mathbf u=\mathbf u$，故 $B\mathbf u=\mathbf u$ ✓

**第 3 步：(3) 更多初值收敛。** 取周期链 $A=\begin{bmatrix}0&1\\1&0\end{bmatrix}$、$A^2=I$：

$$
B=\frac12(A+I)=\begin{bmatrix}0.5&0.5\\0.5&0.5\end{bmatrix}
$$

$A$ 的幂对一般初值振荡不收敛；而 $B$ 全正 ⇒ 任意初值都收敛到 $\left(\frac12,\frac12\right)$。即「**更多初值**收敛」（这是 MCMC 中「取平均」思想的雏形）。$\blacksquare$

## 10-3 线性规划（6 题）

| 题号 | 结论 |
|---|---|
| 基础 1 | 标准形见解析 |
| 基础 2 | 顶点 $(0,0),(2.5,0),(0,4),(1,3)$；$\max(x+3y)=12$；$\max(2x+y)=5$（不唯一） |
| 进阶 3 | 对偶与互补松弛 |
| 进阶 4 | 原问题 $\max=10.5$、对偶 $\min=10.5$ |
| 思考 5、6 | 见解析 |

### 基础 1　（化标准形）

**解**

**第 1 步：目标。** $\min 2x_1-3x_2$ 改写成

$$
\max\ -2x_1+3x_2
$$

**第 2 步：约束方向。** $x_1+x_2\ge4$ 两边乘 $-1$：

$$
-x_1-x_2\le-4
$$

**第 3 步：自由变量。** $x_2=x_2^{+}-x_2^{-}$（$x_2^{\pm}\ge0$）。

**第 4 步：标准形。**

$$
\max\ -2x_1+3x_2^{+}-3x_2^{-}\quad\text{s.t.}\quad -x_1-x_2^{+}+x_2^{-}\le-4,\ \ x_1-x_2^{+}+x_2^{-}\le1,\ \ x_1,x_2^{\pm}\ge0
$$

**答案**　如上。

### 基础 2　（顶点枚举）

**解**

**第 1 步：顶点。** 两两约束取等的交点中满足全部约束者：

$$
(0,0),\quad(2.5,0),\quad(0,4),\quad(1,3)
$$

（$(1,3)$ 是 $x+y=4$ 与 $2x+y=5$ 的交点。）

**第 2 步：$\max(x+3y)$。**

$$
0,\ 2.5,\ 12,\ 10\ \Longrightarrow\ \max=12\ \text{at }(0,4)
$$

**第 3 步：$\max(2x+y)$。**

$$
0,\ 5,\ 4,\ 5\ \Longrightarrow\ \max=5
$$

在 $(2.5,0)$ 与 $(1,3)$ 都取到 ⇒ 整条边都是最优解（**不唯一**），因为 $2x+y=5$ 与约束 $2x+y\le5$ 平行。

**答案**　如上。

### 进阶 3　（对偶与互补松弛）

**解**

**第 1 步：对偶形式。** 原问题 $\max\mathbf c^{\mathsf T}\mathbf x$、$A\mathbf x\le\mathbf b$、$\mathbf x\ge\mathbf 0$ 的对偶是

$$
\min\mathbf b^{\mathsf T}\mathbf y\quad\text{s.t.}\quad A^{\mathsf T}\mathbf y\ge\mathbf c,\ \mathbf y\ge\mathbf 0
$$

**第 2 步：可行性验证。** 代入 $\mathbf y=(1,1,0)^{\mathsf T}$ 检查 $A^{\mathsf T}\mathbf y\ge\mathbf c$ 与 $\mathbf y\ge\mathbf 0$（按第 3.2 节的具体数据代入即可）。

**第 3 步：为什么 $y_3=0$。** 互补松弛要求

$$
y_i\left(\mathbf a_i^{\mathsf T}\mathbf x-b_i\right)=0
$$

若原问题最优解使第 $3$ 条约束**严格不紧**（$\mathbf a_3^{\mathsf T}\mathbf x<b_3$），则必有 $y_3=0$——这条约束「没有起到限制作用」，其影子价格为 $0$。

**答案**　如上。

### 进阶 4　（原问题与对偶）

**解**

**第 1 步：原问题。**

$$
\max\ 2x_1+3x_2\quad\text{s.t.}\quad x_1+x_2\le4,\ x_1+2x_2\le7,\ x_1+3x_2\le9,\ \mathbf x\ge\mathbf 0
$$

**第 2 步：可行顶点。** $(0,0)$、$(4,0)$、$(0,3)$、$(1.5,2.5)$（后者是 $x_1+x_2=4$ 与 $x_1+3x_2=9$ 的交点）。

**第 3 步：目标值。**

$$
0,\ 8,\ 9,\ 10.5\ \Longrightarrow\ \max=10.5\ \text{at }(1.5,2.5)
$$

**第 4 步：对偶。**

$$
\min\ 4y_1+7y_2+9y_3\quad\text{s.t.}\quad y_1+y_2+y_3\ge2,\ y_1+2y_2+3y_3\ge3,\ \mathbf y\ge\mathbf 0
$$

**第 5 步：对偶最优。** 原问题第 $1$、$3$ 条约束紧、第 $2$ 条松 ⇒ $y_2=0$，解

$$
y_1+y_3=2,\quad y_1+3y_3=3\ \Longrightarrow\ y_3=0.5,\ y_1=1.5
$$

对偶值 $=4(1.5)+9(0.5)=10.5$ ⇒ **强对偶** ✓

**第 6 步：互补松弛。** $x_2>0$ ⇒ 对偶第二约束紧：$1.5+2(0)+3(0.5)=3$ ✓；$y_2=0$ ⇒ 原第二约束可松：$1.5+5=6.5<7$ ✓

**答案**　$\mathbf x^*=(1.5,2.5)$、$\mathbf y^*=(1.5,0,0.5)$，最优值 $10.5$。

### 思考 5　（等值线平行于约束边）

**解**

**第 1 步：梯度方向。** 目标 $\mathbf c^{\mathsf T}\mathbf x$ 的等值线法向为 $\mathbf c$。

**第 2 步：取等面。** 若 $\mathbf c=\lambda\mathbf a_k$（$\lambda>0$），则沿第 $k$ 条约束面 $\mathbf a_k^{\mathsf T}\mathbf x=b_k$ 移动时目标值**不变**（因为移动方向与 $\mathbf c$ 垂直）。

**第 3 步：结论。** 该面上任一顶点都是最优解 ⇒ 最优解集包含整条边。几何上：等值线与某条边**平行**时，目标沿该边恒定，故最优不唯一。$\blacksquare$

### 思考 6　（$z^*(\mathbf b)$ 的形状）

**解**

**第 1 步：对偶表示。** 由强对偶（对 max 问题）：

$$
z^*(\mathbf b)=\min\left\{\mathbf b^{\mathsf T}\mathbf y:\ A^{\mathsf T}\mathbf y\ge\mathbf c,\ \mathbf y\ge\mathbf 0\right\}
$$

**第 2 步：凹性。** $z^*$ 是若干**线性函数** $\mathbf b\mapsto\mathbf b^{\mathsf T}\mathbf y$ 的逐点最小 ⇒ 凹函数 ✓

**第 3 步：分段线性。** 对偶可行域的顶点有限，$z^*$ 在每个「最优顶点不变」的区域上是线性的；顶点切换处出现**折点**。

**第 4 步：折点与基。** 原问题最优基为 $B$ 时 $\mathbf y=(B^{-1})^{\mathsf T}\mathbf c_B$；$\mathbf b$ 变化使基更换 ⇒ $\mathbf y$ 跳变 ⇒ $z^*$ 的斜率跳变（折点）。$\blacksquare$

## 10-4 傅里叶级数与函数空间（7 题）

| 题号 | 结论 |
|---|---|
| 基础 1 | 三组正交关系 |
| 基础 2 | (a)(c) $b_n=0$；(b) $a_n=0$；(d) 无必然为零的系数 |
| 进阶 3 | 三角波级数；$\sum\frac1{(2k+1)^2}=\frac{\pi^2}{8}$ |
| 进阶 4 | Leibniz 级数；$\sum\frac1{n^2}=\frac{\pi^2}{6}$ |
| 进阶 5 | 偶延拓更快 |
| 思考 6、7 | 见解析 |

### 基础 1　（三角函数的正交性）

**解**

**第 1 步：余弦。** $m\ne n$ 时用积化和差：

$$
\int_0^{2\pi}\cos mx\cos nx\,\mathrm{d}x=\frac12\int_0^{2\pi}\left[\cos(m-n)x+\cos(m+n)x\right]\mathrm{d}x=0
$$

$m=n$ 时 $\int\cos^2nx\,\mathrm{d}x=\pi$ ✓

**第 2 步：正弦。** 同理 $\int_0^{2\pi}\sin mx\sin nx\,\mathrm{d}x=\pi\delta_{mn}$。

**第 3 步：交叉项。**

$$
\int_0^{2\pi}\cos mx\sin nx\,\mathrm{d}x=\frac12\int_0^{2\pi}\left[\sin(n+m)x+\sin(n-m)x\right]\mathrm{d}x=0
$$

（整周期上正弦积分为零。）$\blacksquare$

### 基础 2　（哪些系数必为零）

**解**

**第 1 步：(a) $x^2$。** 偶函数 ⇒ $b_n=0$。

**第 2 步：(b) $x^3$。** 奇函数 ⇒ $a_n=0$（含 $a_0=0$）。

**第 3 步：(c) $\lvert x\rvert$。** 偶函数 ⇒ $b_n=0$。

**第 4 步：(d) $\mathrm e^x$。** 既非奇也非偶 ⇒ 一般 $a_n,b_n$ 都非零（$a_n=\frac{2\sinh\pi}{\pi(1+n^2)}$ 型，均非零）。

**答案**　(a)(c) $b_n=0$；(b) $a_n=0$；(d) 无必然为零者。

### 进阶 3　（三角波）

**解**

**第 1 步：偶函数。** $f(x)=\pi-\lvert x\rvert$ 是偶函数 ⇒ $b_n=0$。

**第 2 步：$a_0$。**

$$
a_0=\frac2\pi\int_0^\pi(\pi-x)\mathrm{d}x=\pi
$$

**第 3 步：$a_n$。**

$$
a_n=\frac2\pi\int_0^\pi(\pi-x)\cos nx\,\mathrm{d}x=\frac{2\left(1-(-1)^n\right)}{\pi n^2}=\begin{cases}\dfrac{4}{\pi n^2},&n\text{ 奇}\\0,&n\text{ 偶}\end{cases}
$$

**第 4 步：级数。**

$$
f(x)=\frac{\pi}{2}+\frac{4}{\pi}\sum_{k\ge0}\frac{\cos(2k+1)x}{(2k+1)^2}
$$

**第 5 步：代入 $x=0$。** 左边 $f(0)=\pi$：

$$
\pi=\frac{\pi}{2}+\frac4\pi\sum_{k\ge0}\frac{1}{(2k+1)^2}\ \Longrightarrow\ \sum_{k\ge0}\frac{1}{(2k+1)^2}=\frac{\pi^2}{8}
$$

✓

**答案**　如上。

### 进阶 4　（Leibniz 与 Basel 级数）

**解**

**第 1 步：锯齿波。** $f(x)=x$ 的傅里叶级数为

$$
x\sim2\sum_{n\ge1}\frac{(-1)^{n+1}\sin nx}{n}
$$

**第 2 步：代入 $x=\frac\pi2$。**

$$
\frac\pi2=2\sum_{n\ge1}\frac{(-1)^{n+1}\sin\frac{n\pi}{2}}{n}=2\sum_{k\ge0}\frac{(-1)^{k}}{2k+1}
$$

（因 $\sin\frac{n\pi}{2}$ 只在 $n=2k+1$ 时非零且符号交替。）故

$$
\sum_{k\ge0}\frac{(-1)^k}{2k+1}=\frac\pi4
$$

**第 3 步：帕塞瓦尔。** $\frac1\pi\int_{-\pi}^{\pi}x^2\mathrm{d}x=\frac{2\pi^2}{3}$，而 $\sum b_n^2=\sum\frac{4}{n^2}$：

$$
\frac{2\pi^2}{3}=4\sum_{n\ge1}\frac{1}{n^2}\ \Longrightarrow\ \sum_{n\ge1}\frac{1}{n^2}=\frac{\pi^2}{6}
$$

✓

**答案**　如上。

### 进阶 5　（偶延拓 vs 奇延拓）

**解**

**第 1 步：奇延拓。** $f(x)=x$ 本身就是奇函数，级数为

$$
x\sim2\sum_{n\ge1}\frac{(-1)^{n+1}\sin nx}{n}
$$

在 $x=0$ 处收敛到 $0$ ✓

**第 2 步：偶延拓。** 得 $\lvert x\rvert$ 型（三角波）的余弦级数：

$$
\lvert x\rvert\sim\frac\pi2-\frac4\pi\sum_{k\ge0}\frac{\cos(2k+1)x}{(2k+1)^2}
$$

在 $x=0$ 处也为 $0$ ✓

**第 3 步：收敛速度。** 偶延拓（$\lvert x\rvert$）连续、分段光滑，系数 $O(1/n^2)$；奇延拓在 $\pm\pi$ 处有**跳跃**（$-x$ 与 $x$），系数只有 $O(1/n)$。故**偶延拓级数收敛更快**。

**答案**　如上。

### 思考 6　（系数的衰减）

**解**

**第 1 步：分部积分。**

$$
a_n=\frac1\pi\int_{-\pi}^{\pi}f(x)\cos nx\,\mathrm{d}x=\frac{1}{\pi n}\int_{-\pi}^{\pi}f(x)\,\mathrm{d}\left(\sin nx\right)
$$

$$
=\frac{1}{\pi n}\left[f(x)\sin nx\right]_{-\pi}^{\pi}-\frac{1}{\pi n}\int_{-\pi}^{\pi}f'(x)\sin nx\,\mathrm{d}x
$$

**第 2 步：边界项消失。** $f$ 以 $2\pi$ 为周期 ⇒ $f(\pi)=f(-\pi)$，而 $\sin(\pm n\pi)=0$ ⇒ 边界项为 $0$。

**第 3 步：界。** 记 $M=\left(\int\lvert f'\rvert^2\right)^{1/2}$，由柯西–施瓦茨：

$$
\left\lvert a_n\right\rvert\le\frac{1}{\pi n}\left\lVert f'\right\rVert_2\sqrt{2\pi}=\frac{C}{n}
$$

同理 $\lvert b_n\rvert\le C/n$。

**第 4 步：光滑性的作用。** 每多一次分部积分（要求 $f$ 多一阶可导）就多一个 $1/n$ 因子 ⇒ **越光滑衰减越快**（$C^k$ 函数系数 $O(n^{-k})$，解析函数指数衰减）。$\blacksquare$

### 思考 7　（特征函数与对角化）

**解**

**第 1 步：特征函数。**

$$
\frac{\mathrm d^2}{\mathrm dx^2}\mathrm e^{\mathrm i nx}=(\mathrm in)^2\mathrm e^{\mathrm i nx}=-n^2\mathrm e^{\mathrm i nx}
$$

即 $\mathrm e^{\mathrm inx}$ 是 $\frac{\mathrm d^2}{\mathrm dx^2}$ 的特征函数，特征值 $-n^2$。

**第 2 步：热方程被对角化。** 把 $u(x,t)=\sum\hat u_n(t)\mathrm e^{\mathrm inx}$ 代入 $u_t=u_{xx}$：

$$
\sum\dot{\hat u}_n\mathrm e^{\mathrm inx}=\sum\left(-n^2\right)\hat u_n\mathrm e^{\mathrm inx}
$$

由正交性（各频率独立）得**无穷多个解耦的一阶方程**

$$
\dot{\hat u}_n=-n^2\hat u_n
$$

每个都解为指数衰减。

**第 3 步：与 $A=S\Lambda S^{-1}$ 的共同点。** 两者都是**特征分解**：把耦合系统变换到特征基上变成对角（解耦）系统。有限维用 $S$（特征向量矩阵），无限维用傅里叶基（特征函数系）；热方程的 $\exp(-n^2t)$ 对应矩阵情形的 $\mathrm e^{\lambda t}$。$\blacksquare$

## 10-5 图形学与密码学（9 题）

| 题号 | 结论 |
|---|---|
| 基础 1 | $M=TR$；$(2,3,0)\to(2,2,0)$ |
| 基础 2 | $R^{\mathsf T}R=I$；$R^{-1}=R(-\theta)$ |
| 基础 3 | $\det=7$、$K^{-1}$ 见解析；`HI`→`WJ` |
| 进阶 4 | 逆转置法向 |
| 进阶 5 | 旋转时 $(M^{-1})^{\mathsf T}=M$ |
| 进阶 6 | $17^{-1}\equiv2753$ |
| 思考 7–9 | 见解析 |

### 基础 1　（旋转 + 平移）

**解**

**第 1 步：顺序。** 列向量左乘 ⇒ **右边先作用**。「先旋转、后平移」写作

$$
M=TR
$$

**第 2 步：矩阵。**

$$
R=\begin{bmatrix}0&-1&0&0\\1&0&0&0\\0&0&1&0\\0&0&0&1\end{bmatrix},\qquad T=\begin{bmatrix}1&0&0&5\\0&1&0&0\\0&0&1&0\\0&0&0&1\end{bmatrix}
$$

$$
M=TR=\begin{bmatrix}0&-1&0&5\\1&0&0&0\\0&0&1&0\\0&0&0&1\end{bmatrix}
$$

**第 3 步：作用。**

$$
M\begin{bmatrix}2\\3\\0\\1\end{bmatrix}=\begin{bmatrix}-3+5\\2\\0\\1\end{bmatrix}=\begin{bmatrix}2\\2\\0\\1\end{bmatrix}
$$

**答案**　$(2,2,0)$，$M=TR$。

### 基础 2　（旋转矩阵正交）

**解**

**第 1 步：$R^{\mathsf T}R$。**

$$
R^{\mathsf T}R=\begin{bmatrix}\cos\theta&\sin\theta\\-\sin\theta&\cos\theta\end{bmatrix}\begin{bmatrix}\cos\theta&-\sin\theta\\\sin\theta&\cos\theta\end{bmatrix}=\begin{bmatrix}1&0\\0&1\end{bmatrix}
$$

✓

**第 2 步：逆。** 正交 ⇒ $R^{-1}=R^{\mathsf T}$；而 $R^{\mathsf T}$ 正是把 $\theta$ 换成 $-\theta$ 的矩阵 ⇒ $R^{-1}=R(-\theta)$。几何上「转回去 = 反转同样的角」。$\blacksquare$

### 基础 3　（希尔密码）

**解**

**第 1 步：行列式。** $\det K=2\cdot5-1\cdot3=7$，$\gcd(7,26)=1$ ⇒ 模 $26$ 可逆。

**第 2 步：逆。** $7^{-1}\equiv15\pmod{26}$（$7\cdot15=105=4\cdot26+1$）：

$$
K^{-1}=15\begin{bmatrix}5&-1\\-3&2\end{bmatrix}\equiv\begin{bmatrix}23&11\\7&4\end{bmatrix}\pmod{26}
$$

**第 3 步：加密 `HI`。** $H=7$、$I=8$：

$$
K\begin{bmatrix}7\\8\end{bmatrix}=\begin{bmatrix}22\\61\end{bmatrix}\equiv\begin{bmatrix}22\\9\end{bmatrix}=\texttt{WJ}
$$

**第 4 步：解密。**

$$
K^{-1}\begin{bmatrix}22\\9\end{bmatrix}=\begin{bmatrix}605\\190\end{bmatrix}\equiv\begin{bmatrix}7\\8\end{bmatrix}=\texttt{HI}
$$

✓

**答案**　如上。

### 进阶 4　（法向量的逆转置）

**解**

**第 1 步：(a) 变换法向。** $M$ 对角 ⇒ $(M^{-1})^{\mathsf T}=M^{-1}$：

$$
\left(M^{-1}\right)^{\mathsf T}\mathbf n=\left(0.5,\ 1,\ 0\right)^{\mathsf T},\qquad M\mathbf t=\left(2,-1,0\right)^{\mathsf T}
$$

内积 $=0.5\cdot2+1\cdot(-1)=0$ ✓

**第 2 步：(b) 直接用 $M$ 变换法向。**

$$
M\mathbf n=(2,1,0)^{\mathsf T},\qquad (M\mathbf n)\cdot(M\mathbf t)=4-1=3\ne0
$$

✗ 不再垂直。

**第 3 步：(c) 几何解释。** $x$ 方向拉伸 $2$ 倍后，原本垂直于平面的方向被「拉斜」——平面倾斜了，法向必须相应调整才保持垂直。逆转置 $(M^{-1})^{\mathsf T}$ 使内积保持不变：

$$
\left(M\mathbf t\right)^{\mathsf T}\left(M^{-1}\right)^{\mathsf T}\mathbf n=\mathbf t^{\mathsf T}M^{\mathsf T}\left(M^{\mathsf T}\right)^{-1}\mathbf n=\mathbf t^{\mathsf T}\mathbf n=0
$$

**答案**　如上。

### 进阶 5　（旋转时无需逆转置）

**解**

**第 1 步：正交性。** $M$ 旋转 ⇒ $M^{\mathsf T}M=I$、$M^{-1}=M^{\mathsf T}$。

**第 2 步：逆转置。**

$$
\left(M^{-1}\right)^{\mathsf T}=\left(M^{\mathsf T}\right)^{\mathsf T}=M
$$

**第 3 步：结论。** 故 $(M^{-1})^{\mathsf T}\mathbf v=M\mathbf v$——旋转下法向可以直接用 $M$ 变换。几何上：刚体旋转不改变夹角，法向随曲面一起转即可。$\blacksquare$

### 进阶 6　（扩展欧几里得）

**解**

**第 1 步：辗转相除。**

$$
3120=183\cdot17+9,\qquad 17=1\cdot9+8,\qquad 9=1\cdot8+1
$$

**第 2 步：回代。**

$$
1=9-8=9-(17-9)=2\cdot9-17=2(3120-183\cdot17)-17=2\cdot3120-367\cdot17
$$

**第 3 步：取模。**

$$
17^{-1}\equiv-367\equiv3120-367=2753\pmod{3120}
$$

核对：`pow(17,-1,3120)` 给出 $2753$ ✓

**答案**　$2753$。

### 思考 7　（$\mathbb Z_{26}$ 上可逆的判据）

**解**

**第 1 步：逆的公式。** $K^{-1}=\dfrac{1}{\det K}\begin{bmatrix}d&-b\\-c&a\end{bmatrix}$，在 $\mathbb Z_{26}$ 中需 $\det K$ 有逆元。

**第 2 步：逆元存在条件。** $\gcd(\det K,26)=1$。而 $26=2\cdot13$，故

$$
\gcd\left(\det K,26\right)=1\iff\det K\ \text{为奇数且}\ 13\nmid\det K
$$

**第 3 步：逐个判断。** 四个矩阵的行列式分别为 $1$、$3$、$-1$、$1$——都是奇数且不被 $13$ 整除 ⇒ **都可逆**。$\blacksquare$

### 思考 8　（投影不可逆 = 无法恢复三维）

**解**

**第 1 步：投影矩阵。** 透视/正交投影 $P$ 满足 $P^2=P$、$\operatorname{rank}P<3$ ⇒ $\det P=0$ ⇒ 不可逆。

**第 2 步：四大子空间的语言。**

- 屏幕坐标空间 $=\mathbf C(P)$（可见的像）；
- 丢失的信息 $=\mathbf N(P)$（沿视线方向的分量）；
- 由于 $\mathbf N(P)\ne\{\mathbf 0\}$，不同的三维点可以映到同一屏幕点（差一个 $\mathbf N(P)$ 中的向量）。

**第 3 步：结论。** 「投影不可逆」与「无法由屏幕坐标唯一恢复三维坐标」是同一件事：解 $P\mathbf x=\mathbf b$ 有无穷多解（特解 + $\mathbf N(P)$）。$\blacksquare$

### 思考 9　（无噪声 LWE 可解）

**解**

**第 1 步：问题退化。** 噪声 $\mathbf e=\mathbf 0$ 时，$\mathbf b=A\mathbf s\pmod q$——这是一个**线性方程组**。

**第 2 步：求解步骤。**

1. 在 $A$ 中选出 $n$ 列，使其构成的子矩阵 $A_n$ 在 $\mathbb Z_q$ 上可逆（$\det A_n\not\equiv0\pmod q$）；
2. 取对应的 $\mathbf b_n$，计算 $\mathbf s=A_n^{-1}\mathbf b_n\pmod q$（高斯消元，$O(n^3)$）；
3. 用其余方程验证。

**第 3 步：复杂度与启示。** 多项式时间可解。带噪声时 $\mathbf b=A\mathbf s+\mathbf e$ 变成「含错的线性方程组」，一般情形下是 NP 困难（LWE 的安全性来源）。这也说明**希尔密码**（正是 $\mathbf e=\mathbf 0$ 的线性体制）在已知明文攻击下不安全：用 $n$ 组明文—密文对即可解出密钥矩阵。$\blacksquare$
