线性代数 第 10 章 · 应用(40 题)
本章速览
5 篇 · 40 题:图与网络(10-1,9 题)、Markov 矩阵与稳态(10-2,9 题)、线性规划(10-3,6 题)、傅里叶级数与函数空间(10-4,7 题)、图形学与密码学(10-5,9 题)。
10-1 图与网络(9 题)
| 题号 | 结论 |
|---|---|
| 10.1.1 | ;、;独立回路 |
| 10.1.2 | ;生成树 (目测 ) |
| 10.1.3 | 电势 ;电流 ; |
| 10.1.4 | |
| 10.1.5 | KVL 的两种表述 |
| 10.1.6–10.1.9 | 见解析 |
10.1.1 ( 的关联矩阵)
解
第 1 步:(,行=边)。
第 2 步:读数。 三个主元 ⇒ ;,基 (常电势);(基为空——树无回路)。
第 3 步:四个基本子空间。
- (行空间,,维 ):;
- :;
- (维 );
- 。
第 4 步:欧拉公式。 独立回路数
注意这里的欧拉公式针对几何图:。对树而言独立回路数 ✓( 无回路),与 一致。
答案 如上。
10.1.2 ( 的拉普拉斯矩阵与生成树)
解
第 1 步:。
第 2 步:特征值。 对 圈,:
第 3 步:生成树个数。
第 4 步:目测。 去掉任意一条边即得生成树 ⇒ 棵 ✓ 一致。
答案 如上。
10.1.3 (电阻网络)
解
第 1 步: 与接地。 同 10.1.2 的形式():
注入 ;接地节点 ()。
第 2 步:解方程(节点 1–3)。
由第三式 ;代入第二式 ;代入第一式 。故
第 3 步:电流。 :
第 4 步:功率守恒。
✓
第 5 步:为什么线性下降。 每个内部节点满足 邻边电流 ,即
这正是 的中心差分 ⇒ 解为线性函数。
答案 、。
10.1.4 ()
解
第 1 步:二次型。 由 :
第 2 步:零空间。 每条边上 在每个连通分量内为常数。
第 3 步:维数。 设连通分量数为 ,则 由各分量的示性向量张成 ⇒ 。
第 4 步:结论。 由秩—零化度:
10.1.5 (KVL 的两种表述)
解
第 1 步: 的含义。 存在节点电势 使 ,即每条边上有 (电势差)。
第 2 步:等价性。 沿任一回路 求和,电势差望远镜相消:
反之,若所有回路求和为零,则「沿路径积分与路径无关」⇒ 可定义单值电势 ⇒ 。
第 3 步:三角形反例。 取三角形 ,若 ,则沿回路求和 ⇒ 。物理含义:这种电压分布无法由任何电势实现,即违反 KVL——不存在这样的稳态电阻网络。
答案 得证。
10.1.6 (反向一条边)
解
第 1 步: 的变化。 第 行()变成 ,即该行取反(非零元位置由 变为 )。
第 2 步:节点方程。 中等式左边 的系数全变号 ⇒ 相当于把未知量换成 。
第 3 步:自由度与解集。 不变、 不变 ⇒ 自由度 不变;通解的形状不变,只需把 换成 (即环流方向反号)。基础解系(回路向量)的结构不变。
答案 该行取反;方程中 变号;自由度与基础解系结构不变。
10.1.7 (灌溉网)
解
第 1 步:(1) 总和。 ✓(可解的必要条件)。
第 2 步:(2) 自由度。 连通图:。
第 3 步:(3) 孤立节点。 封闭后节点 孤立且 。此时 的秩
(剩下 个节点仍连通),而增广矩阵多一列(含 所在方程常数)
⇒ 无解。
第 4 步:(4) 改数据。 新 ⇒ 仍无解(总量不为零是硬性障碍)。
答案 如上。
10.1.8 (Kruskal 与最小生成树)
解
第 1 步:(1) 排序。 权重 对应边 –,从小到大:。
第 2 步:逐步加边。 依次加入 (不成圈,收)、(收)、(收)——已得 条边,算法停止。
第 3 步:(2) 列无关。 生成树无回路 ⇒ 对应 3 列的关联矩阵子块满秩(),故线性无关。
第 4 步:(3) 与独立回路数。 补边数
生成树的边数 、补边数 ,二者之和为 ✓
答案 MST 为 (总权 ),其余见解析。
10.1.9 (两个可行方案之差)
解
第 1 步:差满足齐次方程。 若 ,则
第 2 步:零空间即回路空间。 由「沿独立回路绕行」的向量张成(维数 )。
第 3 步:物理结论。 两个可行流量方案的差别只能是环流(绕圈流动、净效果为零)——不改变任何节点的净注入。
10-2 Markov 矩阵与稳态(9 题)
| 题号 | 结论 |
|---|---|
| 10.2.1 | 是随机矩阵; 稳态不唯一 |
| 10.2.2 | ;稳态 |
| 10.2.3 | ;不收敛;时间平均收敛 |
| 10.2.4 | 三条证明 |
| 10.2.5 | 正稳态 强连通 |
| 10.2.6–10.2.9 | 见解析 |
10.2.1 (四个矩阵)
解
第 1 步:判随机性(列和为 )。 ✓; ✓; 列和 、 ✓; ✓。四个都是随机矩阵。
第 2 步:稳态。
- :,幂迭代收敛();
- :解 得 ,收敛();
- :任意 都是稳态,稳态不唯一, 不收敛到唯一点。
答案 如上。
10.2.2 (二状态链的闭式)
解
第 1 步:特征值。 、:
第 2 步:稳态。 由 得 ,配合 :
第 3 步:闭式。 由 ,:
第 4 步:极限。 ⇒ 。
答案 如上。
10.2.3 (三周期链)
解
第 1 步:特征值。 是三轮换置换矩阵,:
第 2 步:为什么不收敛。 初值沿特征向量方向的分量按 旋转而不衰减,故 以周期 振荡。
第 3 步:稳态。 由对称性 。
第 4 步:时间平均。
(因 是秩 矩阵,列全等于 。)
答案 如上。
10.2.4 (对称随机矩阵)
解
第 1 步:(1) 双随机。 列和为 ,由 得行和 。
第 2 步:(2) 实特征值与 。 对称 ⇒ 可正交对角化 ⇒ 特征值全实。又对任意特征对,…更直接:由 (列和)得 。
第 3 步:(3) 唯一稳态。 ⇒ 不可约且非周期 ⇒ 单重 ⇒ 稳态唯一;由双随机性 ✓。
10.2.5 (正稳态与强连通)
解
第 1 步()。 设 。由 与 、,得所有满足 的 都有 。反复传播,与 互通的节点全为 ——若强连通则 ,矛盾。
第 2 步()。 强连通 ⇒ 不可约 ⇒ 由 Perron–Frobenius, 的(右)特征向量可取全正。
答案 得证。
10.2.6 ( 的 PageRank)
解
第 1 步:。 。
第 2 步:稳态。 用
第 3 步:零入链页面。 其分数来自均匀项,为
(原来 时为 。) 越小,均匀项越大,排名越「平均」。
答案 如上。
10.2.7 ( 与 的特征值关系)
解
第 1 步:特征方程。 设 、:
第 2 步:左乘 。 因 随机 ⇒ :
左边 ,故
(这一步用到 。)
第 3 步:回代。 均匀项消失,,即
故 是 的特征值。
10.2.8 (复特征值链)
解
第 1 步:(1) 随机性。 三列和都是 :、、 ✓
第 2 步:(2) 特征值。 特征多项式 :
复根的模 。
第 3 步:(3) 收敛性。 有自环(,概率 )⇒ 非周期 ⇒ 幂迭代收敛(不是周期病态,也不可约?——检查:;;,三状态互通 ⇒ 不可约 ✓)。
第 4 步:(4) 加阻尼。 的特征值为
后两者的模 ⇒ 必然收敛。
答案 如上。
10.2.9 ()
解
第 1 步:(1) 随机性。 列和 ✓
第 2 步:(2) 稳态不变。 若 ,则 ,故 ✓
第 3 步:(3) 更多初值收敛。 取周期链 、:
的幂对一般初值振荡不收敛;而 全正 ⇒ 任意初值都收敛到 。即「更多初值收敛」(这是 MCMC 中「取平均」思想的雏形)。
10-3 线性规划(6 题)
| 题号 | 结论 |
|---|---|
| 基础 1 | 标准形见解析 |
| 基础 2 | 顶点 ;;(不唯一) |
| 进阶 3 | 对偶与互补松弛 |
| 进阶 4 | 原问题 、对偶 |
| 思考 5、6 | 见解析 |
基础 1 (化标准形)
解
第 1 步:目标。 改写成
第 2 步:约束方向。 两边乘 :
第 3 步:自由变量。 ()。
第 4 步:标准形。
答案 如上。
基础 2 (顶点枚举)
解
第 1 步:顶点。 两两约束取等的交点中满足全部约束者:
( 是 与 的交点。)
第 2 步:。
第 3 步:。
在 与 都取到 ⇒ 整条边都是最优解(不唯一),因为 与约束 平行。
答案 如上。
进阶 3 (对偶与互补松弛)
解
第 1 步:对偶形式。 原问题 、、 的对偶是
第 2 步:可行性验证。 代入 检查 与 (按第 3.2 节的具体数据代入即可)。
第 3 步:为什么 。 互补松弛要求
若原问题最优解使第 条约束严格不紧(),则必有 ——这条约束「没有起到限制作用」,其影子价格为 。
答案 如上。
进阶 4 (原问题与对偶)
解
第 1 步:原问题。
第 2 步:可行顶点。 、、、(后者是 与 的交点)。
第 3 步:目标值。
第 4 步:对偶。
第 5 步:对偶最优。 原问题第 、 条约束紧、第 条松 ⇒ ,解
对偶值 ⇒ 强对偶 ✓
第 6 步:互补松弛。 ⇒ 对偶第二约束紧: ✓; ⇒ 原第二约束可松: ✓
答案 、,最优值 。
思考 5 (等值线平行于约束边)
解
第 1 步:梯度方向。 目标 的等值线法向为 。
第 2 步:取等面。 若 (),则沿第 条约束面 移动时目标值不变(因为移动方向与 垂直)。
第 3 步:结论。 该面上任一顶点都是最优解 ⇒ 最优解集包含整条边。几何上:等值线与某条边平行时,目标沿该边恒定,故最优不唯一。
思考 6 ( 的形状)
解
第 1 步:对偶表示。 由强对偶(对 max 问题):
第 2 步:凹性。 是若干线性函数 的逐点最小 ⇒ 凹函数 ✓
第 3 步:分段线性。 对偶可行域的顶点有限, 在每个「最优顶点不变」的区域上是线性的;顶点切换处出现折点。
第 4 步:折点与基。 原问题最优基为 时 ; 变化使基更换 ⇒ 跳变 ⇒ 的斜率跳变(折点)。
10-4 傅里叶级数与函数空间(7 题)
| 题号 | 结论 |
|---|---|
| 基础 1 | 三组正交关系 |
| 基础 2 | (a)(c) ;(b) ;(d) 无必然为零的系数 |
| 进阶 3 | 三角波级数; |
| 进阶 4 | Leibniz 级数; |
| 进阶 5 | 偶延拓更快 |
| 思考 6、7 | 见解析 |
基础 1 (三角函数的正交性)
解
第 1 步:余弦。 时用积化和差:
时 ✓
第 2 步:正弦。 同理 。
第 3 步:交叉项。
(整周期上正弦积分为零。)
基础 2 (哪些系数必为零)
解
第 1 步:(a) 。 偶函数 ⇒ 。
第 2 步:(b) 。 奇函数 ⇒ (含 )。
第 3 步:(c) 。 偶函数 ⇒ 。
第 4 步:(d) 。 既非奇也非偶 ⇒ 一般 都非零( 型,均非零)。
答案 (a)(c) ;(b) ;(d) 无必然为零者。
进阶 3 (三角波)
解
第 1 步:偶函数。 是偶函数 ⇒ 。
第 2 步:。
第 3 步:。
第 4 步:级数。
第 5 步:代入 。 左边 :
✓
答案 如上。
进阶 4 (Leibniz 与 Basel 级数)
解
第 1 步:锯齿波。 的傅里叶级数为
第 2 步:代入 。
(因 只在 时非零且符号交替。)故
第 3 步:帕塞瓦尔。 ,而 :
✓
答案 如上。
进阶 5 (偶延拓 vs 奇延拓)
解
第 1 步:奇延拓。 本身就是奇函数,级数为
在 处收敛到 ✓
第 2 步:偶延拓。 得 型(三角波)的余弦级数:
在 处也为 ✓
第 3 步:收敛速度。 偶延拓()连续、分段光滑,系数 ;奇延拓在 处有跳跃( 与 ),系数只有 。故偶延拓级数收敛更快。
答案 如上。
思考 6 (系数的衰减)
解
第 1 步:分部积分。
第 2 步:边界项消失。 以 为周期 ⇒ ,而 ⇒ 边界项为 。
第 3 步:界。 记 ,由柯西–施瓦茨:
同理 。
第 4 步:光滑性的作用。 每多一次分部积分(要求 多一阶可导)就多一个 因子 ⇒ 越光滑衰减越快( 函数系数 ,解析函数指数衰减)。
思考 7 (特征函数与对角化)
解
第 1 步:特征函数。
即 是 的特征函数,特征值 。
第 2 步:热方程被对角化。 把 代入 :
由正交性(各频率独立)得无穷多个解耦的一阶方程
每个都解为指数衰减。
第 3 步:与 的共同点。 两者都是特征分解:把耦合系统变换到特征基上变成对角(解耦)系统。有限维用 (特征向量矩阵),无限维用傅里叶基(特征函数系);热方程的 对应矩阵情形的 。
10-5 图形学与密码学(9 题)
| 题号 | 结论 |
|---|---|
| 基础 1 | ; |
| 基础 2 | ; |
| 基础 3 | 、 见解析;HI→WJ |
| 进阶 4 | 逆转置法向 |
| 进阶 5 | 旋转时 |
| 进阶 6 | |
| 思考 7–9 | 见解析 |
基础 1 (旋转 + 平移)
解
第 1 步:顺序。 列向量左乘 ⇒ 右边先作用。「先旋转、后平移」写作
第 2 步:矩阵。
第 3 步:作用。
答案 ,。
基础 2 (旋转矩阵正交)
解
第 1 步:。
✓
第 2 步:逆。 正交 ⇒ ;而 正是把 换成 的矩阵 ⇒ 。几何上「转回去 = 反转同样的角」。
基础 3 (希尔密码)
解
第 1 步:行列式。 , ⇒ 模 可逆。
第 2 步:逆。 ():
第 3 步:加密 HI。 、:
第 4 步:解密。
✓
答案 如上。
进阶 4 (法向量的逆转置)
解
第 1 步:(a) 变换法向。 对角 ⇒ :
内积 ✓
第 2 步:(b) 直接用 变换法向。
✗ 不再垂直。
第 3 步:(c) 几何解释。 方向拉伸 倍后,原本垂直于平面的方向被「拉斜」——平面倾斜了,法向必须相应调整才保持垂直。逆转置 使内积保持不变:
答案 如上。
进阶 5 (旋转时无需逆转置)
解
第 1 步:正交性。 旋转 ⇒ 、。
第 2 步:逆转置。
第 3 步:结论。 故 ——旋转下法向可以直接用 变换。几何上:刚体旋转不改变夹角,法向随曲面一起转即可。
进阶 6 (扩展欧几里得)
解
第 1 步:辗转相除。
第 2 步:回代。
第 3 步:取模。
核对:pow(17,-1,3120) 给出 ✓
答案 。
思考 7 ( 上可逆的判据)
解
第 1 步:逆的公式。 ,在 中需 有逆元。
第 2 步:逆元存在条件。 。而 ,故
第 3 步:逐个判断。 四个矩阵的行列式分别为 、、、——都是奇数且不被 整除 ⇒ 都可逆。
思考 8 (投影不可逆 = 无法恢复三维)
解
第 1 步:投影矩阵。 透视/正交投影 满足 、 ⇒ ⇒ 不可逆。
第 2 步:四大子空间的语言。
- 屏幕坐标空间 (可见的像);
- 丢失的信息 (沿视线方向的分量);
- 由于 ,不同的三维点可以映到同一屏幕点(差一个 中的向量)。
第 3 步:结论。 「投影不可逆」与「无法由屏幕坐标唯一恢复三维坐标」是同一件事:解 有无穷多解(特解 + )。
思考 9 (无噪声 LWE 可解)
解
第 1 步:问题退化。 噪声 时,——这是一个线性方程组。
第 2 步:求解步骤。
- 在 中选出 列,使其构成的子矩阵 在 上可逆();
- 取对应的 ,计算 (高斯消元,);
- 用其余方程验证。
第 3 步:复杂度与启示。 多项式时间可解。带噪声时 变成「含错的线性方程组」,一般情形下是 NP 困难(LWE 的安全性来源)。这也说明希尔密码(正是 的线性体制)在已知明文攻击下不安全:用 组明文—密文对即可解出密钥矩阵。