附录 A 学习笔记：概率、线性代数与图论背景材料
配套译文：附录 A 精校翻译（译文不在公开版）。本页只放学习层内容：路线、解释、补证、隐藏任务闭合与校勘说明；其中标明“学习笔记补充（非原书 Proof）”的内容不是原书正文。
1. 一句话定位
附录 A 是全书后续网络统计论证所依赖的“工具箱”：A.1 给出从期望、方差到集中不等式的概率底座，A.2 把图的连通性编码为邻接矩阵和 Laplacian 的谱结构，A.3 提供对称矩阵、范数和 Courant–Fisher 变分表述，A.4 将梯度、散度和 Laplacian 延拓到图上。
2. 本附录导读
阅读顺序不是四个互不相干的知识清单，而是一条由“随机量的控制”走向“图算子的控制”的链：
- 概率层（A.1）：先用指标变量把事件概率写成期望，再用一阶矩控制“是否发生”，用二阶矩控制“偏离均值”，最后用 Hoeffding 控制有界独立和的尾部。
- 图结构层（A.2）：节点—边—路径—连通分量的组合结构被邻接矩阵 $A$ 与度矩阵 $D$ 编码；$L=D-A$ 的二次型把“相邻节点取值差异”变成能量。
- 谱层（A.3）：半正定性保证能量非负，谱定理与 Courant–Fisher 把二次型最小化变成特征值问题；这正是谱聚类、半监督学习与网络嵌入的共同入口。
- 图微积分层（A.4）：图梯度把节点差异放到边上，散度是其伴随，二者复合得到图 Laplacian；读者需要特别留意本书的有向/无向边计数约定，因为它影响因子 $2$。
3. 本页使用方式
第一遍只看每个对象的条件、结论和“后续用途”；第二遍按本页的 proof-* 卡片补齐原书把计算压缩成一句话的地方；第三遍把 A.2 的二次型、A.3 的变分式与 A.4 的伴随关系放在一起复述。翻译页中只出现原书内容与显式校勘，所有解释和补证都留在这里。
4. 学习路线与依赖图
指标变量与期望
↓
Markov → 一阶矩方法 → Union bound
↓
Chebyshev → 二阶矩方法 → 弱大数律
↓
Hoeffding（有界独立和）
图的路径/连通分量 → A、D
↓
L=D−A 的二次型与 Ker L
↓
零特征值重数 = 连通分量数
↓
对称矩阵谱定理 → PSD/范数 → Courant–Fisher
↓
图梯度 → 伴随散度 → Δ_γ 与标准/随机游走 Laplacian
5. 60 个编号对象：计数器不能合并
本附录不是一条统一的 “A.x” 计数器。对齐时必须按类型分别计数：
| 类型 | 编号范围 | 数量 | 备注 |
|---|---|---|---|
| Definition | A.1–A.17 | 17 | 独立计数器 |
| Proposition | A.1–A.15 | 15 | 独立计数器 |
| Example | A.1–A.7 | 7 | 独立计数器 |
| Remark | A.1–A.6 | 6 | 独立计数器 |
| Corollary | A.1, A.2, A.5 | 3 | 与其他类型不共用 |
| Application | A.3, A.4 | 2 | 与其他类型不共用 |
| Lemma | A.6, A.7, A.10, A.11, A.14, A.15 | 6 | 与 Proposition 不共用 |
| Theorem | A.8, A.13 | 2 | 与 Lemma 等共享另一条序列 |
| Counterexample | A.9, A.12 | 2 | 与 Theorem/Lemma/Corollary/Application 共享另一条序列 |
| 合计 | 60 | 不能按出现顺序重编号 |
例如，Proposition A.11、Theorem A.13、Lemma A.14 同时存在，分别属于三个类型计数器；“A.13”本身不能唯一指代对象。
6. 核心对象与符号卡片
6.1 概率
- 指标变量：$1_A(X)$ 把事件转成 $0/1$ 随机变量，$\mathbb{E}1_A(X)=\mathbb{P}(X\in A)$ 是一阶矩方法的桥。
- Markov：只需 $X\ge0$，用均值控制单侧尾部；整数值时阈值 $1$ 直接给出“非零概率”上界。
- Chebyshev：对中心化平方变量应用 Markov，得到二侧偏差的方差界。
- 二阶矩方法：用 $\mathbb{P}(X=0)$ 的上界表达“随机量不消失”；Remark A.3 用 Cauchy–Schwarz 把分母从 $(\mathbb{E}X)^2$ 改进到 $\mathbb{E}(X^2)$。
- Hoeffding：需要独立性与确定的区间 $[a_i,b_i]$；其标准下尾应使用 $S_n\le\mathbb{E}S_n-t$，译文按原书排印保留了第二条的
$\ge$并标出校勘。
6.2 图与 Laplacian
对无向加权图，$A_{ij}=w_{ij}$、$D_{ii}=d_i=\sum_jw_{ij}$，标准 Laplacian 是 $L=D-A$。核心恒等式为
$$ x^\top Lx=\frac12\sum_{i,j}a_{ij}(x_i-x_j)^2. $$
它同时解释三件事：$L$ 半正定；$Lx=0$ 意味着每条边两端取值相同；零空间由各连通分量的指标向量张成。归一化 Laplacian $\mathcal L=D^{-1/2}LD^{-1/2}$ 只是在变量中插入 $D^{-1/2}$ 的缩放，并把谱上界压到 $2$。
6.3 线性代数
- 对称实矩阵可以正交对角化，故二次型可在特征坐标中逐坐标分析。
- PSD/PD 是二次型条件；$M^\top M$ 总是 PSD，只有 $M$ 可逆时才 PD。
- $p$-范数、诱导算子范数与 Frobenius 范数用途不同：前者作用于向量，诱导范数测量 $A$ 对向量的最坏放大，Frobenius 范数是所有元素平方和的平方根。
- Courant–Fisher 的关键是 Rayleigh 商 $x^\top Mx/(x^\top x)$ 对缩放不变；第 2 个特征值必须额外施加 $x\perp v_1$。
7. 原书跳步、隐藏任务与校勘总览
下列事项在学习层处理；它们不改变译文中原书的陈述。
| 位置 | 处理 |
|---|---|
| Application A.3 | 补出 $X=\sum_i1_{A_i}$ 的两行证明。 |
| Application A.4 | 说明原书证明显示式缺少中心化项且方差记号不一致，给出按正确目标的 Chebyshev 推导。 |
| Proposition A.11 | 原书仅写“类似 Proposition A.10”，补出二次型、半正定性、谱上界与零特征向量证明。 |
| Proposition A.13 | 原书 Proof 只有“straightforward + Minkowski”，补齐范数四公理。 |
| Example A.7 | 补四条诱导范数公式；第 4 条按标准公式校正平方根并保留原书版本。 |
| Counterexample A.9 | 补特征多项式的直接计算。 |
| Remark A.3 | 补从 Cauchy–Schwarz 到 $\operatorname{Var}(X)/\mathbb{E}(X^2)$ 的代数一步。 |
| Example A.2、Lemma A.7 | 补方差计算与 $LX=0$ 的逆向直接计算，并区分依概率/几乎处处的语义。 |
| Proposition A.14、Lemma A.11 | 虽无完整原书 Proof，给出短证，便于后续调用。 |
| Example A.5、A.4.2 末段 | 仅作校勘解释，不把修正后的命题伪装成原文。 |
8. 原书证明与学习笔记证明的边界
译文中保留的原书 Proof 共 15 处：Proposition A.6、Corollary A.2、Proposition A.7、Application A.4、Corollary A.5、Proposition A.9、Lemma A.6、Proposition A.10、Lemma A.7、Proposition A.12、Proposition A.13、Theorem A.13、Proposition A.15、Lemma A.14、Lemma A.15。下面同名 proof-* 卡片是对这些 Proof 的学习层展开，或明确注明是学习补证；不是把补证回填进翻译层。
9. 原书 Proof 的完整展开
完整证明（原书 Proof 的展开）Proposition A.6（Markov 不等式）
状态：完整证明已按当前笔记标准给出闭合推导。
**证明目标**：证明 $\mathbb P(X\ge a)\le\mathbb EX/a$，其中 $X\ge0$ 且 $a>0$。
在事件 $\{X\ge a\}$ 上有 $X\ge a$，在其补集上 $X1_{X\ge a}=0$，所以逐点有
$$X\ge X1_{X\ge a}\ge a1_{X\ge a}.$$
两边取期望，得到
$$\mathbb EX\ge\mathbb E(X1_{X\ge a})\ge a\mathbb E1_{X\ge a}=a\mathbb P(X\ge a).$$
除以 $a$ 即得结论。**闭合检查**：只使用了非负性与 $a>0$；不需要独立性或方差存在。
完整证明（原书 Proof 的展开）Corollary A.2（一阶矩方法）
状态：完整证明已按当前笔记标准给出闭合推导。
**证明目标**：对正整数值 $X$，证明 $\mathbb P(X\ne0)\le\mathbb EX$。
整数值性给出事件恒等式
$$\{X\ne0\}=\{X>0\}=\{X\ge1\}.$$
对阈值 $a=1$ 应用 Proposition A.6：
$$\mathbb P(X\ne0)=\mathbb P(X\ge1)\le\frac{\mathbb EX}{1}=\mathbb EX.$$
**闭合检查**：正值保证 Markov 的非负条件；整数值保证把“非零”变成阈值至少为 $1$ 的事件。
学习笔记补充（非原书 Proof）Application A.3（Union bound）
状态：证明骨架保留主要推导链，后续可补常数、边界或技术细节。
令 $X=\sum_{i=1}^{m}1_{A_i}$。这是一个正整数值随机变量，且
$$\{X>0\}=\bigcup_{i=1}^{m}A_i,qquad \mathbb EX=\sum_{i=1}^{m}\mathbb E1_{A_i}=\sum_{i=1}^{m}\mathbb P(A_i).$$
由 Corollary A.2，
$$\mathbb P\left(\bigcup_{i=1}^{m}A_i\right)=\mathbb P(X>0)\le\mathbb EX=\sum_{i=1}^{m}\mathbb P(A_i).$$
这里不需要事件相互独立；这正是并集界在网络随机事件估计中便于使用的原因。
完整证明（原书 Proof 的展开）Proposition A.7（Chebyshev 不等式）
状态：完整证明已按当前笔记标准给出闭合推导。
令 $Y=(X-\mathbb EX)^2\ge0$。事件 $\{|X-\mathbb EX|\ge a\}$ 等价于 $\{Y\ge a^2\}$，因此由 Markov 不等式
$$\mathbb P(|X-\mathbb EX|\ge a)=\mathbb P(Y\ge a^2)\le\frac{\mathbb EY}{a^2}=\frac{\operatorname{Var}X}{a^2}.$$
**闭合检查**：$a>0$ 使 $a^2$ 可作 Markov 阈值；无需对 $X$ 作有界性假设，只需方差有限才使右端有限。
学习笔记补充（按原书目标闭合；非原书文字改写）Application A.4（弱大数律）
状态：证明骨架保留主要推导链，后续可补常数、边界或技术细节。
令 $U_n=(X_1+\cdots+X_n)/n$。若 $X_i$ 独立同分布，均值为 $\mu$、方差为 $\sigma^2$，则
$$\mathbb E U_n=\mu,qquad \operatorname{Var}(U_n)=\frac{1}{n^2}\sum_{i=1}^{n}\operatorname{Var}(X_i)=\frac{\sigma^2}{n}.$$
对 $U_n$ 使用中心化的 Chebyshev 不等式，得到
$$\mathbb P(|U_n-\mu|\ge\varepsilon)\le\frac{\operatorname{Var}(U_n)}{\varepsilon^2}=\frac{\sigma^2}{n\varepsilon^2}\longrightarrow0.$$
原书显示式写成 $\mathbb P(|U_n|\ge\varepsilon)$，且把 $U_n$ 的方差叙述为 $\sigma^2$；这两处与上面的闭合推导不一致，译文已用校勘提示保留原样，学习笔记只说明能使陈述成立的标准解释。原书随后提到“有限方差不是必要条件”和强大数律；这两句是未展开的外部理论指针，不在本附录内证明。
完整证明（原书 Proof 的展开）Corollary A.5（二阶矩方法）
状态：完整证明已按当前笔记标准给出闭合推导。
若 $X=0$，则 $|X-\mathbb EX|=\mathbb EX$；更一般地，$|X-\mathbb EX|\ge\mathbb EX$ 蕴含 $X\le0$ 或 $X\ge2\mathbb EX$，所以
$$\{X=0\}\subseteq\{|X-\mathbb EX|\ge\mathbb EX\}.$$
由 Chebyshev，
$$\mathbb P(X=0)\le\frac{\operatorname{Var}X}{(\mathbb EX)^2}.$$
再用 $\operatorname{Var}X=\mathbb E(X^2)-(\mathbb EX)^2$，得到
$$\frac{\operatorname{Var}X}{(\mathbb EX)^2}=\frac{\mathbb E(X^2)}{(\mathbb EX)^2}-1.$$
学习笔记补充（隐藏一步；非原书 Proof）Remark A.3 的加强不等式
状态：证明骨架保留主要推导链，后续可补常数、边界或技术细节。
因为 $X=X1_{X>0}$（$X$ 为正随机变量），Cauchy–Schwarz 给出
$$\mathbb EX=\mathbb E(X1_{X>0})\le\sqrt{\mathbb E(X^2)}\sqrt{\mathbb P(X>0)}.$$
两边平方并除以 $\mathbb E(X^2)$，有
$$\mathbb P(X>0)\ge\frac{(\mathbb EX)^2}{\mathbb E(X^2)}.$$
取补集并使用 $\mathbb E(X^2)-(\mathbb EX)^2=\operatorname{Var}(X)$，便得
$$\mathbb P(X=0)\le1-\frac{(\mathbb EX)^2}{\mathbb E(X^2)}=\frac{\operatorname{Var}(X)}{\mathbb E(X^2)}.$$
学习笔记补充（隐藏计算；非原书 Proof）Example A.2 的方差
状态：完整证明已按当前笔记标准给出闭合推导。
由分布定义，$\mathbb EX_n=n^2(1/n)=n$，且 $\mathbb E(X_n^2)=n^4(1/n)=n^3$。因此
$$\operatorname{Var}(X_n)=\mathbb E(X_n^2)-(\mathbb EX_n)^2=n^3-n^2=n^2(n-1).$$
并且 $\mathbb P(X_n>0)=1/n\to0$，所以这里至少能无条件读成 $X_n\to0$ 依概率；若要说几乎处处收敛，还需要关于不同 $n$ 之间联合分布的额外信息，原书没有给出。
完整证明（原书 Proof 的展开）Proposition A.9（连通关系）
状态：完整证明已按当前笔记标准给出闭合推导。
自反性：每个节点 $u$ 都有长度为 $0$ 的路径回到自身，故 $u\leftrightarrow u$。
传递性：若 $u\leftrightarrow v$，存在从 $u$ 到 $v$ 的路径；若 $v\leftrightarrow z$，存在从 $v$ 到 $z$ 的路径。把两条路径在 $v$ 处拼接，得到从 $u$ 到 $z$ 的路径，故 $u\leftrightarrow z$。
对称性：无向图中从 $u$ 到 $v$ 的路径逐边反向后就是从 $v$ 到 $u$ 的路径，故 $u\leftrightarrow v$ 蕴含 $v\leftrightarrow u$。三条性质成立，所以 $\leftrightarrow$ 是等价关系。
完整证明（原书 Proof 的展开）Lemma A.6（L 与 $\mathcal L$ 的元素）
状态：完整证明已按当前笔记标准给出闭合推导。
无自环时，$A_{ii}=0$；对无向无权图，若 $i\sim j$ 则 $A_{ij}=1$，否则 $A_{ij}=0$，而 $D_{ii}=d_i$。因此 $L=D-A$ 给出
$$L_{ii}=d_i,\quad L_{ij}=-1\ (i\sim j),\quad L_{ij}=0\ \text{（其他）}.$$
又因为 $\mathcal L=D^{-1/2}LD^{-1/2}$，对角元为 $d_i^{-1/2}d_i d_i^{-1/2}=1$；相邻的非对角元为 $d_i^{-1/2}(-1)d_j^{-1/2}=-1/\sqrt{d_id_j}$，其余为 $0$。这正是引理中的两个分段式。
完整证明（原书 Proof 的展开）Proposition A.10（标准 Laplacian）
状态：完整证明已按当前笔记标准给出闭合推导。
**二次型恒等式。**由于 $d_i=\sum_j a_{ij}$ 且 $A$ 对称，
$$
\begin{aligned}
\frac12\sum_{i,j}a_{ij}(x_i-x_j)^2
&=\frac12\sum_{i,j}a_{ij}x_i^2-\sum_{i,j}a_{ij}x_ix_j+\frac12\sum_{i,j}a_{ij}x_j^2\\
&=\sum_i d_i x_i^2-\sum_{i,j}a_{ij}x_ix_j\\
&=x^\top Dx-x^\top Ax=x^\top Lx.
\end{aligned}
$$
对矩阵 $X=[X_{\cdot1},\ldots,X_{\cdot K}]$，迹的线性性给出
$$\operatorname{Tr}(X^\top LX)=\sum_{k=1}^{K}X_{\cdot k}^\top LX_{\cdot k},$$
对每一列使用刚证明的恒等式即得命题中的矩阵式。
**对称与半正定。**$D$、$A$ 对称，所以 $L$ 对称；二次型恒等式右边是非负项之和，故 $x^\top Lx\ge0$，$L$ 半正定。
**谱与零向量。**实对称矩阵的特征值为实数，半正定性使它们都非负。最后，$A1_n=d$（其中 $d=(d_1,\ldots,d_n)^\top$），所以
$$L1_n=(D-A)1_n=d-d=0_n.$$
**闭合检查**：二次型恒等式同时给出能量解释与零空间入口；它是 Lemma A.7、Proposition A.12 以及后续谱方法的共同依赖。
学习笔记补充（非原书 Proof）Proposition A.11（归一化 Laplacian）
状态：完整证明已按当前笔记标准给出闭合推导。
**证明目标**：证明 $\mathcal L=D^{-1/2}LD^{-1/2}$ 的二次型恒等式、半正定性、谱区间 $[0,2]$ 与零特征向量。以下假设没有孤立节点，或采用 Remark A.6 的逆矩阵约定。
令 $y=D^{-1/2}x$。由 Proposition A.10 的二次型恒等式，
$$x^\top\mathcal Lx=(D^{-1/2}x)^\top L(D^{-1/2}x)=y^\top Ly=\frac12\sum_{i,j}a_{ij}(y_i-y_j)^2,$$
即
$$x^\top\mathcal Lx=\frac12\sum_{i,j}a_{ij}\left(\frac{x_i}{\sqrt{d_i}}-\frac{x_j}{\sqrt{d_j}}\right)^2.$$
对矩阵 $X$ 按列相加即可得到迹公式。因此 $\mathcal L$ 对称且半正定。
为证明上界，对任意实数 $u,v$ 使用 $(u-v)^2\le2(u^2+v^2)$：
$$
\begin{aligned}
x^\top\mathcal Lx
&\le\frac12\sum_{i,j}a_{ij}\,2(y_i^2+y_j^2)\\
&=2\sum_i d_i y_i^2=2\sum_i x_i^2=2\|x\|_2^2.
\end{aligned}
$$
Rayleigh 商因此落在 $[0,2]$，所有特征值都在该区间。最后，$L1_n=0$，所以
$$\mathcal L(D^{1/2}1_n)=D^{-1/2}LD^{-1/2}D^{1/2}1_n=D^{-1/2}L1_n=0,$$
即 $D^{1/2}1_n$ 是零特征向量。**闭合检查**：谱上界只使用非负权重与对称性；若存在孤立节点，需按 Remark A.6 的约定逐坐标解释。
完整证明（原书 Proof 的展开）Lemma A.7（$LX=0$）
状态：完整证明已按当前笔记标准给出闭合推导。
设 $V_1,\ldots,V_K$ 是连通分量。若 $LX=0$，则
$$0=X^\top LX=\frac12\sum_{i,j}a_{ij}(x_i-x_j)^2.$$
每一项均非负，因此每条有正权边 $(i,j)$ 都满足 $x_i=x_j$。同一连通分量中的任意两个节点可由路径连接，沿路径逐边使用相等性，得到该分量上 $X$ 为常值。
反过来，若 $X$ 在每个 $V_k$ 上为常值，则每条边的两端属于同一连通分量，所以 $x_i-x_j=0$。于是对每个 $i$，
$$
(LX)_i=\sum_j a_{ij}(x_i-x_j)=0,
$$
从而 $LX=0$。这补全了原书 “Reciprocally, direct computation” 留下的一步。
完整证明（原书 Proof 的展开）Proposition A.12（零特征值与连通分量）
状态：完整证明已按当前笔记标准给出闭合推导。
按连通分量排序节点，$L$ 呈块对角形式 $\operatorname{diag}(L_1,\ldots,L_k)$。每个连通块 $L_r$ 由 Lemma A.7 知道其零空间恰由常向量张成：若 $L_rz=0$，则 $z$ 在该连通分量上为常值；反之常向量确实被 $L_r$ 消去。因此每个块的零特征值重数为 $1$，整体零空间维数为 $k$。
对每个分量 $V_r$，指标向量 $1_{V_r}$ 在该分量上为 $1$、其他分量上为 $0$，故 $L1_{V_r}=0$。这些向量支撑集互不相交，线性无关；又整体零空间维数为 $k$，因此它们构成 $\operatorname{Ker}L$ 的一组基。于是零特征值重数正好等于连通分量数。
学习笔记补充（隐藏计算；非原书 Proof）Counterexample A.9 的特征多项式
状态：证明骨架保留主要推导链，后续可补常数、边界或技术细节。
对 $M=\begin{pmatrix}1&i\\i&-1\end{pmatrix}$，
$$
\det(M-\lambda I)=\det\begin{pmatrix}1-\lambda&i\\i&-1-\lambda\end{pmatrix}
=(1-\lambda)(-1-\lambda)-i^2=\lambda^2.
$$
唯一特征值是 $0$，且代数重数为 $2$。但 $\ker M$ 只有一维（例如方程 $x+iy=0$ 只给出一个独立约束），几何重数为 $1$，所以 $M$ 不可对角化。这里“对称”是转置对称，不是 Hermitian 共轭转置对称。
学习笔记校勘补充（非原书 Proof）Example A.5：$M^\top M$ 应为 PSD
状态：完整证明已按当前笔记标准给出闭合推导。
对任意 $x\in\mathbb R^n$，
$$x^\top M^\top Mx=(Mx)^\top(Mx)=\|Mx\|_2^2\ge0,$$
所以 $M^\top M$ 对称且半正定。若 $M$ 可逆，则 $Mx=0$ 只可能在 $x=0$ 发生，于是对每个非零 $x$ 有 $\|Mx\|_2^2>0$，矩阵才是正定。故原书 “for all $M$ ... definite positive” 少了 $M$ 可逆的条件；译文保留原书措辞，学习笔记明确给出最小修正。
学习笔记补充（原书仅一句；非原书展开）Proposition A.13（$p$-范数）
状态：完整证明已按当前笔记标准给出闭合推导。
设 $p\ge1$，$\|x\|_p=(\sum_i|x_i|^p)^{1/p}$。
1. **正性**：每个 $|x_i|^p\ge0$，所以 $\|x\|_p\ge0$。
2. **定性**：$\|x\|_p=0$ 当且仅当每个 $|x_i|^p=0$，也就是每个 $x_i=0$，故 $x=0$。
3. **齐次性**：对 $t\in\mathbb R$，
$$\|tx\|_p=\left(\sum_i|t x_i|^p\right)^{1/p}=|t|\left(\sum_i|x_i|^p\right)^{1/p}=|t|\|x\|_p.$$
4. **三角不等式**：Minkowski 不等式给出
$$\left(\sum_i|x_i+y_i|^p\right)^{1/p}\le\left(\sum_i|x_i|^p\right)^{1/p}+\left(\sum_i|y_i|^p\right)^{1/p}.$$
因此 $\|\cdot\|_p$ 是范数。原书 Proof 只写“前三条 straightforward，三角不等式由 Minkowski”，本卡补足了前三条的逐点验证；Minkowski 本身作为标准不等式使用。
学习笔记补充（非原书 Proof）Lemma A.11（单位球取最大值）
状态：完整证明已按当前笔记标准给出闭合推导。
先看 $\|x\|=1$ 的情形。若 $x\ne0$，令 $y=x/\|x\|$，则 $\|y\|=1$ 且由齐次性 $\|Ax\|=\|x\|\|Ay\|$。因此
$$\sup_{x\ne0}\frac{\|Ax\|}{\|x\|}=\sup_{\|y\|=1}\|Ay\|.$$
若 $\|x\|\le1$，写成 $x=r y$（$0\le r\le1$，$\|y\|=1$）即可得 $\|Ax\|=r\|Ay\|\le\sup_{\|y\|=1}\|Ay\|$；单位球包含单位球面，所以两个 supremum 相等。最后，有限维空间中单位球是紧集，$x\mapsto\|Ax\|$ 连续，因此 supremum 在 $\|x\|\le1$ 上取得，成为最大值。
学习笔记补充（非原书 Proof）Example A.7（四条诱导范数公式）
状态：完整证明已按当前笔记标准给出闭合推导。
以下均从 $\|||A|||=\sup_{\|x\|=1}\|Ax\|$ 出发。
1. **$1$-范数。**有
$$\|Ax\|_1=\sum_i\left|\sum_jA_{ij}x_j\right|\le\sum_{i,j}|A_{ij}||x_j|=\sum_j\left(\sum_i|A_{ij}|\right)|x_j|.$$
当 $\|x\|_1=1$ 时，右端不超过最大列和；取 $x$ 为对应最大列的坐标向量并选择符号，即可达到该列和。因此
$$\|||A|||_1=\max_j\sum_i|A_{ij}|.$$
2. **$\infty$-范数。**有
$$\|Ax\|_\infty=\max_i\left|\sum_jA_{ij}x_j\right|\le\max_i\sum_j|A_{ij}|\,\|x\|_\infty.$$
取对应最大行的符号向量可达到上界，故
$$\|||A|||_\infty=\max_i\sum_j|A_{ij}|.$$
3. **$2$-范数。**对 $\|x\|_2=1$，
$$\|Ax\|_2^2=x^\top A^\top Ax.$$
$A^\top A$ 对称半正定，Rayleigh 商最大值是其最大特征值，所以
$$\|||A|||_2^2=\lambda_{\max}(A^\top A),\qquad\|||A|||_2=\sqrt{\lambda_{\max}(A^\top A)}.$$
4. **逆矩阵。**若 $A$ 可逆，则 $A^{-1}$ 的奇异值是 $A$ 的奇异值的倒数，故
$$\|||A^{-1}|||_2=\frac{1}{\sigma_{\min}(A)}=\frac{1}{\sqrt{\lambda_{\min}(A^\top A)}}.$$
原书写成 $1/\lambda_{\min}(A^\top A)$，缺少平方根；该卡给出的是与第 3 条和标准 Euclidean 算子范数一致的校正公式，**不是对译文原文的静默修改**。
学习笔记补充（非原书 Proof）Proposition A.14（次乘性）
状态：完整证明已按当前笔记标准给出闭合推导。
对任意 $x\ne0$，由诱导范数定义及齐次性，
$$\|ABx\|\le\|||A|||\,\|Bx\|\le\|||A|||\,\|||B|||\,\|x\|.$$
除以 $\|x\|$ 后取所有 $x\ne0$ 的 supremum，得到 $\|||AB|||\le\|||A|||\,\|||B|||$。注意这里关键是同一个向量范数先控制 $A$，再控制 $B$；任意元素范数不具有这条链，Counterexample A.12 正说明了这一点。
完整证明（原书双 Proof 的展开）Theorem A.13（Courant–Fisher）
状态：完整证明已按当前笔记标准给出闭合推导。
**证明目标**：证明 (A.1)、(A.2)、(A.3) 的 Rayleigh 商表述，并识别取极值的特征向量。
### 证明一：正交对角化
由谱定理，存在正交矩阵 $P$ 与对角矩阵 $D=\operatorname{diag}(\lambda_1,\ldots,\lambda_n)$，使 $M=P^\top DP$。令 $y=Px$，则 $\|y\|_2=\|x\|_2$，且
$$x^\top Mx=y^\top Dy=\sum_{i=1}^{n}\lambda_i y_i^2.$$
当 $\|x\|_2=1$ 时，$\sum_i y_i^2=1$，所以该值是特征值的加权平均，落在 $[\lambda_1,\lambda_n]$。令 $y=e_1$ 达到 $\lambda_1$，令 $y=e_n$ 达到 $\lambda_n$。因为 $v_i=P^\top e_i$，对应的 $x$ 正是 $v_1,v_n$。
若再施加 $x\perp v_1$，则
$$0=x^\top v_1=(Px)^\top(Pv_1)=y^\top e_1=y_1.$$
约束变为 $\sum_{i=2}^{n}y_i^2=1$，所以最小加权平均为 $\lambda_2$，由 $y=e_2$（即 $x=v_2$）取得。这证明了三条单位球形式；对非零 $x$，将 $x$ 归一化即可得到分式形式，因为
$$\frac{(cx)^\top M(cx)}{(cx)^\top(cx)}=\frac{x^\top Mx}{x^\top x}\quad(c\ne0).$$
### 证明二：Lagrange 乘子
在 $\|x\|_2=1$ 的约束下，令
$$\mathcal L(x,\lambda)=x^\top Mx-\lambda(x^\top x-1).$$
对 $\lambda$ 求导给出 $x^\top x=1$，对 $x$ 求导给出
$$\nabla_x\mathcal L=2Mx-2\lambda x=0,$$
即 $Mx=\lambda x$。因此任何受约束临界点都是特征向量，目标值为相应特征值；全局最小值和最大值分别是最小、最大特征值。加入 $x\perp v_1$ 后，允许的特征方向排除 $v_1$，最小可取方向变为 $v_2$。这与第一种证明的全局极值和取值向量一致。
**校勘/边界**：若特征值有重数，arg min 不止一个向量，而是对应特征子空间中的单位向量（或 Rayleigh 商不变的子空间）；原书“由 $v_i$ 取得”是一个选取，不应理解为唯一性。
学习笔记补充（非原书展开）Proposition A.15（迹最小化）
状态：完整证明已按当前笔记标准给出闭合推导。
令 $M=V\Lambda_MV^\top$，其中 $V=[v_1,\ldots,v_n]$ 正交，$\Lambda_M=\operatorname{diag}(\lambda_1,\ldots,\lambda_n)$。对约束 $H^\top H=I_K$，令 $Y=V^\top H$，则 $Y^\top Y=I_K$，且
$$\operatorname{Tr}(H^\top MH)=\operatorname{Tr}(Y^\top\Lambda_MY)=\sum_{i=1}^{n}\lambda_i\|Y_{i\cdot}\|_2^2.$$
这里 $0\le\|Y_{i\cdot}\|_2^2\le1$ 且 $\sum_i\|Y_{i\cdot}\|_2^2=\operatorname{Tr}(Y^\top Y)=K$。把总权重 $K$ 放在最小的 $K$ 个特征值上，所得下界为 $\sum_{i=1}^{K}\lambda_i$，由 $Y=[e_1,\ldots,e_K]$（即 $H=[v_1,\ldots,v_K]$）达到。因此该 $H$ 是一个最小化解。
原书 Lagrange 计算 $\partial_H\mathcal L=2MH-2H\Lambda=0$ 只说明列向量是特征向量，还需要上面的谱权重比较才能说明选的是最小的 $K$ 个方向。若存在特征值重数，任何相应最小特征子空间中的正交基都可给出等价解。
完整证明（原书 Proof 的展开）Lemma A.14（散度公式）
状态：完整证明已按当前笔记标准给出闭合推导。
由图梯度定义，
$$
\begin{aligned}
\langle\operatorname{grad}f,G\rangle_{\mathcal F(E)}
&=\sum_{i,j}\gamma(w_{ij})(f(j)-f(i))G(i,j)\\
&=\sum_{i,j}\gamma(w_{ij})f(j)G(i,j)-\sum_{i,j}\gamma(w_{ij})f(i)G(i,j).
\end{aligned}
$$
在第一项中交换哑指标 $i,j$，得到
$$\sum_{i,j}\gamma(w_{ji})f(i)G(j,i).$$
于是
$$
\langle\operatorname{grad}f,G\rangle
=\sum_i f(i)\sum_j\left[\gamma(w_{ji})G(j,i)-\gamma(w_{ij})G(i,j)\right].
$$
根据伴随定义，方括号中的和就是 $(\operatorname{div}G)(i)$，从而
$$
(\operatorname{div}G)(i)=\sum_j\gamma(w_{ji})G(j,i)-\gamma(w_{ij})G(i,j).
$$
若图无向，$w_{ij}=w_{ji}$，提出同一个 $\gamma(w_{ij})$ 即得翻译页中的简化式。这里把 OCR 中重复且下标混乱的中间行按 PDF 文本层的指标交换恢复；恢复的是原书推导，不是学习层的新结论。
完整证明（原书 Proof 的展开）Lemma A.15（$\Delta_\gamma$ 的显式式）
状态：完整证明已按当前笔记标准给出闭合推导。
记 $\gamma_{ij}=\gamma(w_{ij})$。由 Lemma A.14 和梯度定义，
$$
\begin{aligned}
(\Delta_\gamma f)(i)
&=(\operatorname{div}\operatorname{grad}f)(i)\\
&=\sum_j\left[\gamma_{ji}(\operatorname{grad}f)(j,i)-\gamma_{ij}(\operatorname{grad}f)(i,j)\right]\\
&=\sum_j\left[\gamma_{ji}^2(f(i)-f(j))-\gamma_{ij}^2(f(j)-f(i))\right]\\
&=\sum_j(\gamma_{ij}^2+\gamma_{ji}^2)(f(i)-f(j)).
\end{aligned}
$$
这就是引理的公式。若图无向，两个权重相等，于是得到
$$\Delta_\gamma f(i)=2\sum_j\gamma(w_{ij})^2(f(i)-f(j)).$$
**因子与函数依赖提示。**原书随后直接写 $L=\Delta_\gamma$（取 $\gamma(x)=\sqrt{x}$）以及 $L_{\rm rw}=\Delta_\gamma$（取 $\gamma(w_{ij})=\sqrt{w_{ij}/d_i}$）。若每条无向边按两个方向计入上述求和，前者会出现因子 $2$；后者的“$\gamma$”还依赖 $i$。因此这里应把原书识别式看作依赖其边集/归一化约定的排印陈述；译文保留原式，不能静默去掉这个疑点。
10. 隐藏验证任务清单
| 任务 | 闭合位置 | 结论/保留问题 |
|---|---|---|
| Application A.3 的并集界 | 补证 | 已闭合；只用一阶矩，不需独立性。 |
| 有限方差不是弱大数律必要条件 | Application A.4 笔记 | 原书外部断言，未在附录内证明。 |
| Proposition A.11 省略证明 | 补证 | 已闭合；上界用 $(u-v)^2\le2(u^2+v^2)$。 |
| Proposition A.13 的范数公理 | 补证 | 已闭合；Minkowski 作为标准工具调用。 |
| Example A.7 四条诱导公式 | 补证 | 前三条按原式闭合；第 4 条原书缺平方根，补证给出标准式。 |
| Counterexample A.9 特征多项式 | 补证 | 已闭合；复对称不等于 Hermitian。 |
| Remark A.3 的 “and thus” | 补证 | 已闭合。 |
| Example A.5 的 $M^\top M$ | 校勘补证 | 原书“正定”不严谨；最小修正是 PSD，$M$ 可逆时 PD。 |
| Example A.2 方差与收敛模式 | 补证 | 方差已算；$X_n\to0$ 的模式需联合分布才可升级到几乎处处。 |
| Lemma A.7 逆向 | 补证 | 已闭合。 |
| Prop A.14 次乘性 | 补证 | 已闭合；学习补证，原书无 Proof。 |
11. 公式卡片
本附录只有 3 个编号公式，全部属于 Theorem A.13：
| 公式 | 内容 | 使用提醒 |
|---|---|---|
| (A.1) | $\lambda_1=\min_{\|x\|=1}x^\top Mx=\min_{x\ne0}x^\top Mx/(x^\top x)$ | 无额外正交约束。 |
| (A.2) | $\lambda_2=\min_{\|x\|=1,\,x\perp v_1}x^\top Mx=\min_{x\ne0,\,x\perp v_1}x^\top Mx/(x^\top x)$ | PDF 文本层确认了 OCR 遗失的 $x\perp v_1$。 |
| (A.3) | $\lambda_n=\max_{\|x\|=1}x^\top Mx=\max_{x\ne0}x^\top Mx/(x^\top x)$ | 最大特征值。 |
12. 易混点与复习检查表
- [ ] 能说明为什么 $\mathbb E1_A(X)=\mathbb P(X\in A)$，并用它推导 Union bound。
- [ ] 能区分一阶矩方法（控制 $\mathbb P(X>0)$）与二阶矩方法（控制 $\mathbb P(X=0)$）。
- [ ] 能指出 Hoeffding 第二条下尾按标准形式应为“$\le$”，并知道译文保留了原书“$\ge$”。
- [ ] 能从 $L=D-A$ 推出 $x^\top Lx=\frac12\sum_{i,j}a_{ij}(x_i-x_j)^2$。
- [ ] 能说明 $\operatorname{Ker}L$ 为什么由连通分量指标向量张成。
- [ ] 能区分 $M^\top M$ 的 PSD 与 PD 条件。
- [ ] 能解释 (A.2) 的 $x\perp v_1$ 为什么把最小方向从 $v_1$ 推到 $v_2$。
- [ ] 能从诱导范数定义证明次乘性，并说出非诱导元素范数的反例。
- [ ] 能从“梯度—伴随—散度”链写出 $\Delta_\gamma=\operatorname{div}\operatorname{grad}$。
- [ ] 能指出 A.4 末段的因子 $2$ 与 $\gamma(w_{ij})$ 的节点依赖是需要回到底稿确认的校勘问题。
13. 外引断言与后续衔接
本附录正文明确指向的外部材料/标准结果有：
- Vershynin（2018）第 2 章：集中不等式更多细节；
- Serre（2010）：矩阵范数一节的来源标注；
- Hein et al.（2007）：图上微积分一节的更多细节；
- Minkowski、Cauchy–Schwarz、Markov、Chebyshev、Hoeffding 及强/弱大数律：作为标准定理或外部背景被调用。
这些指针来自原书 PDF；本工作单元没有独立取得并核验相应外部版本，因此它们在对齐记录中标为“外引指针，未闭合”，不把外部结论伪装成本附录内的证明。A.2 的标准 Laplacian 将在第 2–6 章反复出现；A.3 的谱工具直接连接第 3–5 章的特征值、谱聚类与半监督学习；A.4 的图微积分为后续图正则化和变分表达提供记号基础。