Lecture 12: Graphs, Networks, Incidence Matrices

目录 · ← l11 · l13 →

Lecture 12: Graphs, Networks, Incidence Matrices

概述

本讲把图（graph）翻译成一个矩阵：关联矩阵（incidence matrix） $A$。这是全课程最漂亮的跨学科翻译：节点电势 $x$、边电势差 $y=Ax$，基尔霍夫电流定律变成 $A^{\mathsf T}y=\mathbf{0}$，而回路（loops）正好是 $N(A^{\mathsf T})$ 的基向量。讲次 10 的四个基本子空间在这里不再是抽象玩具，而是电路与网络流里可摸可算的东西；$A^{\mathsf T}A$ 则给出图拉普拉斯矩阵。

核心概念的几何直觉

图与关联矩阵

• 定义与目的：图由节点（nodes） $1,\dots,n$ 与边（edges） $e_1,\dots,e_m$ 组成，每条边连两个节点。矩阵 $A$ 行对应边、列对应节点，规模 $m\times n$；第 $i$ 行只在第 $i$ 条边的两端非零，一端 $-1$（起点）、一端 $+1$（终点）。方向是人为约定，取反只让整行变号，结论不变。
• 几何直觉（它在空间中是什么样子？）：$A$ 作用在节点向量 $x\in\mathbb R^n$ 上，输出边向量 $y=Ax\in\mathbb R^m$。$x$ 是各节点电势（potential），$y$ 是各边两端的电势差。所以 $A$ 是一台”做减法”的机器：把节点上的值转成边上的落差。
• 具体示例：一条边连节点 1、2，$y=x_2-x_1=[-1,\ 1]\begin{bmatrix}x_1\\x_2\end{bmatrix}$。整行 $[-1,1]$ 就是这条边的关联行——这是 1 维的”导数”。

四个子空间在图上的物理含义

• 定义与目的：$A$ 是 $m\times n$，故 $N(A)\subseteq\mathbb R^n$、$C(A^{\mathsf T})\subseteq\mathbb R^n$、$N(A^{\mathsf T})\subseteq\mathbb R^m$、$C(A)\subseteq\mathbb R^m$。本讲给它们起了名字。
• 几何直觉（它在空间中是什么样子？）：$N(A)=$ 全部节点同加常数的等电势向量；$C(A^{\mathsf T})=$ 节点空间里”能由电势产生的边落差”的方向；$N(A^{\mathsf T})=$ 满足 KCL 的环流（回路空间）；$C(A)=$ 所有可实现的边电势差。
• 具体示例：下例中 $\dim N(A)=1$（整体电势平移）、$\dim N(A^{\mathsf T})=2$（两个独立回路）。

基尔霍夫电流定律（KCL）

• 定义与目的：$A^{\mathsf T}y=\mathbf{0}$。$A^{\mathsf T}$ 是 $n\times m$，第 $j$ 行（对应节点 $j$）说：连到节点 $j$ 的所有边电流带符号相加为零，即流入 = 流出。
• 几何直觉（它在空间中是什么样子？）：电流像水，节点是接头，水不能在接头里堆积。$A^{\mathsf T}y=\mathbf{0}$ 就是”每个接头净流量为零”。
• 具体示例：一圈回路上的单位电流（沿环走 $+1$），在每个节点恰好一进一出，$A^{\mathsf T}y=\mathbf{0}$ 自动成立。

图拉普拉斯矩阵 $L=A^{\mathsf T}A$

• 定义与目的：$A^{\mathsf T}A$ 是 $n\times n$ 对称矩阵。$L_{jj}=$ 节点 $j$ 的度数（degree），$L_{ij}=-1$（节点 $i,j$ 之间有边），否则 $0$。
• 几何直觉（它在空间中是什么样子？）：$L$ 是图上的二阶差分算子（离散拉普拉斯），度量”这个节点的值与邻居差多少”。$x^{\mathsf T}Lx=\sum_{\text{边}}(x_j-x_i)^2$ 是整张图的能量。
• 具体示例：下例 $L$ 的对角元为 $(3,2,3,2)$，正是四节点的度数。

计算步骤与手算演示

示例：4 节点 5 边连通图（正方形 + 一条对角线）

        (1)────────e1────────(2)
         │  ╲                │
         │    ╲              │
        e4      e5           e2
         │        ╲          │
         │          ╲        │
        (4)────────e3────────(3)

   节点 1,2,3,4  (n = 4)
   e1 = 1—2 (上边)   e2 = 2—3 (右边)   e3 = 3—4 (下边)
   e4 = 4—1 (左边)   e5 = 1—3 (对角线)
   共 m = 5 条边，连通，无自环，无重边

演示 1：写出 $A$ 并求秩

步骤 1：规定方向。 统一取”小编号 → 大编号”为正向：$e_1:1\to2$，$e_2:2\to3$，$e_3:3\to4$，$e_4:1\to4$，$e_5:1\to3$。起点列填 $-1$，终点列填 $+1$。

步骤 2：逐行写出（行 = 边，列 = 节点 1,2,3,4）：

步骤 3：先找一个”必零”的组合。 把四列相加：每行恰有一个 $-1$ 和一个 $+1$，相加得零向量，所以

步骤 4：行化简求秩。

       A                            RREF(A)
 -1  1  0  0                    1  0  0 -1
  0 -1  1  0                    0  1  0 -1
  0  0 -1  1    ── 行化简 ──►    0  0  1 -1
 -1  0  0  1                    0  0  0  0
 -1  0  1  0                    0  0  0  0

 主元在第 1,2,3 列   ⇒   rank(A) = 3

【计算机制解说】：为什么连通图恰好差一个秩？下界由步骤 3 给出（列相关 ⇒ $\operatorname{rank}\le n-1$）。上界由”路径相加”给出：从节点 1 沿边走到节点 $j$，把路径上各边的行相加，中间节点的 $\pm1$ 两两抵消，只剩起点 $-1$ 与终点 $+1$，于是行空间含 $e_j-e_1$（$j=2,3,4$）以及 $e_1$ 的某个方向，维数达 $n-1$。图连通 $\iff$ 任何节点都能被”走到” $\iff \operatorname{rank}(A)=n-1$。有 $k$ 个连通块时 $\operatorname{rank}=n-k$。

演示 2：$N(A)$（等电势）与 $N(A^{\mathsf T})$（回路）

步骤 1：求 $N(A)$。 从 RREF 读出 $x_1-x_4=0$，$x_2-x_4=0$，$x_3-x_4=0$，即四者相等：

直接验证 $A(1,1,1,1)^{\mathsf T}=\mathbf{0}$：五条边两端都相等，落差为零 ✓。物理含义：全部节点电势同时抬高 1 伏，边上的落差一个数都不变，$y=Ax$ 不变。所以 $N(A)$ 就是”电势整体平移”这一个自由度——这解释了为什么只有电势差可观测。

步骤 2：写出 $A^{\mathsf T}$，它就是 KCL。 $A^{\mathsf T}$ 是 $4\times5$：

第 1 行给出节点 1 的方程 $-y_1-y_4-y_5=0$，即”连到节点 1 的三条边电流之和为零”。逐行都是”流入 = 流出”。

步骤 3：求 $N(A^{\mathsf T})$。 由秩-零化度定理 $\dim N(A^{\mathsf T})=m-r=5-3=2$。解 $A^{\mathsf T}y=\mathbf{0}$，一组漂亮的基是

逐个节点验算 $A^{\mathsf T}y^{(1)}$：

\(\text{节点 1}:\ -1-(-1)-0=0\ \checkmark\quad \text{节点 2}:\ 1-1=0\ \checkmark\) \(\text{节点 3}:\ 1-1+0=0\ \checkmark\quad \text{节点 4}:\ 1+(-1)=0\ \checkmark\)

逐个节点验算 $A^{\mathsf T}y^{(2)}$：

\(\text{节点 1}:\ -1-0-(-1)=0\ \checkmark\quad \text{节点 2}:\ 1-1=0\ \checkmark\) \(\text{节点 3}:\ 1-0+(-1)=0\ \checkmark\quad \text{节点 4}:\ 0+0=0\ \checkmark\)

两者都通过，且线性无关（$y^{(1)}-y^{(2)}=(0,0,1,-1,1)^{\mathsf T}\neq\mathbf{0}$），维数正好 2，故构成 $N(A^{\mathsf T})$ 的一组基。

符号要点：追踪回路时，与行进方向相反的边要取 $-1$。正方形环上 $e_4$ 的方向是 $1\to4$，而回路走的是 $4\to1$，所以 $y^{(1)}$ 第 4 个分量是 $-1$。这是本讲最容易算错的地方——务必用 $A^{\mathsf T}y=\mathbf{0}$ 逐节点回代验证。

步骤 4：欧拉公式。 把 $\dim N(A)=n-r$、$\dim N(A^{\mathsf T})=m-r$ 相减：

移项即得恒等式 $\dim N(A)-\dim N(A^{\mathsf T})+m=n$。代入本图：$1-2+5=4$ ✓（两边都是自动相等，不算独立信息）。

真正有内容的是把 $\dim N(A^{\mathsf T})$ 认作回路数 $\ell$。因为 $\dim N(A^{\mathsf T})=m-r$，而连通图 $r=n-1$，所以

本图：$4-5+2=1$ ✓。这就是欧拉公式的图论形式（凸多面体 $V-E+F=2$ 的近亲）。几何解读：$n$ 个节点的一棵生成树（spanning tree）恰有 $n-1$ 条边，每加回一条树外的边就闭合出一个新回路，故 $\ell=m-(n-1)$。

【计算机制解说】：为什么”$A^{\mathsf T}y=\mathbf{0}$ 的解 = 回路”？三层论证。 ① 回路满足 KCL：沿环走一圈每节点一进一出，净流量为零，故 $\{\text{回路}\}\subseteq N(A^{\mathsf T})$。 ② 反之亦然：若 $y\in N(A^{\mathsf T})$ 在某边非零，从该边出发，KCL 迫使两端点另有非零边接续；有限步内必回到已访问节点，形成回路。按比例扣掉该回路的电流（合法组合），$y$ 的非零边数严格减少。反复消减，$y$ 写成若干回路之和，故 $N(A^{\mathsf T})\subseteq\{\text{回路组合}\}$。 ③ 独立回路数 $=m-n+1$：先取生成树（$n-1$ 条边），每加一条树外边恰好闭合一个新回路，且这些回路线性无关（每条树外边只出现在它对应的那个回路里）。 三层合起来：$N(A^{\mathsf T})$ 就是回路空间，KCL 的解就是环流——水可以在管道里绕圈打转，但不在接头处堆积。

演示 3：$L=A^{\mathsf T}A$ 与图拉普拉斯

步骤 1：算出 $L$（$L_{ij}=\sum_{k=1}^{5}A_{ki}A_{kj}$，即 $A$ 的第 $i,j$ 列的内积）：

步骤 2：读数。 对角元 $(3,2,3,2)$ 正是四节点度数：节点 1 连 $e_1,e_4,e_5$（3 条）；节点 2 连 $e_1,e_2$（2 条）；节点 3 连 $e_2,e_3,e_5$（3 条）；节点 4 连 $e_3,e_4$（2 条）✓。非对角元：节点 1-2 有边 ⇒ $L_{12}=-1$ ✓；节点 1-3 有对角线 ⇒ $L_{13}=-1$ ✓；节点 2-4 不直接相连 ⇒ $L_{24}=0$ ✓。这印证

步骤 3：验证 $L\mathbf{1}=\mathbf{0}$ 与秩。 每行和为零（度数减去邻居个数）：

计算得 $\operatorname{rank}(L)=3$，故 $\dim N(L)=1$，$N(L)=\operatorname{span}\{\mathbf{1}\}$。

步骤 4：能量恒等式的数值验算（最漂亮的一步）。 取 $x=(3,1,4,2)^{\mathsf T}$：

另一条路，按边求相邻节点差的平方和（$x_1=3,x_2=1,x_3=4,x_4=2$）：

（顺便 $Ax=(-2,3,-2,-1,1)^{\mathsf T}$，$\vert Ax\vert ^2=4+9+4+1+1=19$ ✓。）

【计算机制解说】：一行代数就够：

这个恒等式把”$L$ 是二阶差分”与”$\vert Ax\vert ^2$ 是能量”焊在一起，同时给出两条结论：$L$ 永远半正定（它是平方和）；$x^{\mathsf T}Lx=0\iff Ax=\mathbf{0}\iff$ 每条边两端相等 $\iff x\in\operatorname{span}\{\mathbf{1}\}$。这独立地再次证明 $N(L)=N(A)$。连通图上 $\mathbf{1}$ 是 $L$ 的唯一零特征向量——这正是谱聚类（spectral clustering）的起点。若给每条边加权 $w_k$（电阻倒数），则 $L_w=A^{\mathsf T}WA$，$W=\operatorname{diag}(w_k)$，即加权拉普拉斯。

演示 4：$Ax=b$ 何时有解？网络流的相容条件

步骤 1：问题的位置。 $A$ 是 $5\times4$ 秩 3，方程 5 个、秩 3，必有 $m-r=2$ 个相容条件。由讲次 14 的 $C(A)=N(A^{\mathsf T})^{\perp}$，条件就是 $b\perp N(A^{\mathsf T})$，即$b$ 与两个回路基向量的内积为零。

步骤 2：把条件写成紧凑的标量形式。 用步骤 3 的基 $y^{(1)}=(1,1,1,-1,0)$、$y^{(2)}=(1,1,0,0,-1)$：

\(b\cdot y^{(1)}=b_1+b_2+b_3-b_4=0 \quad\Longrightarrow\quad \boxed{b_4=b_1+b_2+b_3}\) \(b\cdot y^{(2)}=b_1+b_2-b_5=0 \quad\Longrightarrow\quad \boxed{b_5=b_1+b_2}\)

这不是两个抽象条件，而是”绕回路一圈落差不累积”（基尔霍夫电压定律 KVL）。$b_4=b_1+b_2+b_3$ 是正方形环；$b_5=b_1+b_2$ 是三角形环。

步骤 3：动手验算四组 $b$。

(a) $b=(1,1,1,3,2)^{\mathsf T}$：这是 $x=(-3,-2,-1,0)$ 产生的落差（$A x=(1,1,1,3,2)$ ✓）。检查 $b_4=3=b_1+b_2+b_3=3$ ✓，$b_5=2=b_1+b_2=2$ ✓。有解（程序验算 consistent = true ✓）。

(b) $b=(2,-1,-1,0,0)^{\mathsf T}$：$b_4=0=b_1+b_2+b_3=0$ ✓，但 $b_5=0\neq b_1+b_2=1$ ✗。三角形环条件失败 ⇒ 无解（程序验算 consistent = false ✓）。直觉：绕三角形转一圈有净环流，任何电势场都做不到。

(c) $b=(1,0,0,0,0)^{\mathsf T}$：$b_4=0\neq b_1+b_2+b_3=1$ ✗ ⇒ 无解 ✓。只有一条边有落差，绕一圈回不到原值。

(d) $b=(1,-1,2,-2,0)^{\mathsf T}$：$b_4=-2\neq 1-1+2=2$ ✗ ⇒ 无解 ✓。

步骤 4：对偶视角——节点空间的相容条件。 考虑另一个方程 $A^{\mathsf T}y=f$（$f$ 是各节点注入的电流，求电流 $y$）。$A^{\mathsf T}$ 是 $4\times5$ 秩 3，同样差 2 个条件。这次给条件的是 $N(A)$：$f\perp N(A)=\operatorname{span}\{\mathbf{1}\}$，即

（”注入节点的总电流必须为零”——这正是 KCL 的能量表述。）验算：$f=(2,-1,-1,0)$，和 $=0$，有解 ✓；$f=(1,1,1,1)$，和 $=4\neq0$，无解 ✓。

步骤 5：注意这个对称性。 两边的条件长得不一样，容易记混：

  方程            所在空间      相容条件                  含义
  ------------------------------------------------------------------
  Ax = b        b ∈ R^m        b ⊥ N(A^T)  (2 个条件)   绕每个回路落差不累积
                               ⇔ b4=b1+b2+b3, b5=b1+b2

  A^T y = f     f ∈ R^n        f ⊥ N(A)    (1 个条件)   注入总量为零
                               ⇔ Σ f_j = 0
  ------------------------------------------------------------------
  注意 R^m 里的条件数 = dim N(A^T) = 2，R^n 里的条件数 = dim N(A) = 1

【计算机制解说】：为什么”回路上的行组合给出障碍”？把 $A$ 的行按正方形环 $1\to2\to3\to4\to1$ 带方向相加（$e_4$ 逆行取负号）：

回路上的行线性组合恰好为零向量，所以任何 $b=Ax$ 都必须满足同一组合给出 $0$，这就是 $b\cdot y^{(1)}=0$。同理三角形环给出 $b\cdot y^{(2)}=0$。而节点空间那一边，$\mathbf{1}^{\mathsf T}(A^{\mathsf T}y)=(\mathbf{1}^{\mathsf T}A^{\mathsf T})y=(A\mathbf{1})^{\mathsf T}y=\mathbf{0}^{\mathsf T}y=0$，左边恒为 $0$，右边必须是 $\mathbf{1}^{\mathsf T}f=\sum f_j$——所以 $\sum f_j=0$ 是必要条件；维数计数说明它也是充分的。

演示 5：电阻网络——”接地”如何把半正定变成正定（讲次 16 的预告）

步骤 1：物理设定。 把演示 1 的图当作单位电阻网络（每条边电导为 1）。在节点 1 注入 1 安培电流、从节点 4 抽出 1 安培，即 $f=(1,0,0,-1)^{\mathsf T}$。由演示 4 步骤 4，$\sum f_j=0$ 保证有解。但 $L$ 是奇异的（$N(L)=\operatorname{span}\{\mathbf{1}\}$），解不唯一。

步骤 2：接地固定电势。 令 $x_4=0$（把节点 4 接地）。删去 $L$ 的第 4 行第 4 列，得到 $3\times3$ 的接地拉普拉斯：

步骤 3：算行列式，判断可逆。 按第一行展开：

\(\det L_{\text{ground}}=3\begin{vmatrix}2&-1\\-1&3\end{vmatrix}-(-1)\begin{vmatrix}-1&-1\\-1&3\end{vmatrix}+(-1)\begin{vmatrix}-1&2\\-1&-1\end{vmatrix}\) \(=3(6-1)+1(-3-1)-1(1+2)=15-4-3=8\neq0\ \checkmark\)

接地删去一个自由度后，矩阵变成可逆的！

步骤 4：解出各节点电势。 解 $L_{\text{ground}}x_{\text{red}}=f_{\text{red}}$：

回代验算（逐个方程）：

\(3\cdot\tfrac58-1\cdot\tfrac12-1\cdot\tfrac38=\tfrac{15-4-3}{8}=\tfrac88=1\ \checkmark\quad(\text{节点 1})\) \(-1\cdot\tfrac58+2\cdot\tfrac12-1\cdot\tfrac38=\tfrac{-5+8-3}{8}=0\ \checkmark\quad(\text{节点 2})\) \(-1\cdot\tfrac58-1\cdot\tfrac12+3\cdot\tfrac38=\tfrac{-5-4+9}{8}=0\ \checkmark\quad(\text{节点 3})\) \(-1\cdot\tfrac58+0-1\cdot\tfrac38+2\cdot0=\tfrac{-5-3}{8}=-1\ \checkmark\quad(\text{节点 4，即被删去的行})\)

步骤 5：求各边电流。 $y=Ax$（单位电导，欧姆定律 $y=\Delta x$）：

步骤 6：三重验算 KCL 与功率。

节点 1：$-y_1-y_4-y_5=\tfrac18+\tfrac58+\tfrac14=\tfrac{1+5+2}{8}=1$，等于注入电流 $f_1=1$ ✓ 节点 2：$y_1-y_2=-\tfrac18+\tfrac18=0=f_2$ ✓ 节点 3：$y_2-y_3+y_5=-\tfrac18+\tfrac38-\tfrac14=\tfrac{-1+3-2}{8}=0=f_3$ ✓ 节点 4：$y_3+y_4=-\tfrac38-\tfrac58=-1=f_4$ ✓

即 $A^{\mathsf T}y=f$ ✓。再看耗散功率：

而 $x^{\mathsf T}f=\tfrac58\cdot1+\tfrac12\cdot0+\tfrac38\cdot0+0\cdot(-1)=\tfrac58$ ✓。

【计算机制解说】：这个例子把三条线索拧成一股。 第一，接地 = 消去零空间。 $L$ 半正定、奇异，零空间恰是”整体电势平移”$\operatorname{span}\{\mathbf{1}\}$。固定一个节点的电势就是从每个解里减去合适的常数，从而在这个 1 维平移自由度上取定唯一代表。删掉第 4 行第 4 列后，剩下的矩阵对任意非零 $z$ 都有 $z^{\mathsf T}L_{\text{ground}}z>0$，故严格正定（$\det=8>0$ 是它的一个表现，也是讲次 26 的判据：所有顺序主子式为正）。 第二，能量恒等式 $\vert y\vert ^2=x^{\mathsf T}Lx=x^{\mathsf T}f$ 就是焦耳定律。 输入的电功率 $x^{\mathsf T}f$ 恰好等于各电阻上耗散的 $\sum y_k^2$——这是 $L=A^{\mathsf T}A$ 的物理化身。 第三，$\det=8$ 的来源：矩阵-树定理（Matrix-Tree Theorem）。 $\det L_{\text{ground}}$ 恰好等于图的生成树数目。本图 $5$ 条边中任选 $3$ 条共 $\binom53=10$ 种选法，其中只有两种含环：

   含环的选择（2 种）:  {e1,e2,e5}    ← 三角形 1-2-3-1
                        {e3,e4,e5}    ← 三角形 1-3-4-1

   生成树（8 种，4 个节点全连通且无环）:
     e1,e2,e3     e1,e2,e4     e1,e3,e4     e1,e3,e5
     e1,e4,e5     e2,e3,e4     e2,e3,e5     e2,e4,e5

$10-2=8$ ✓，与 $\det L_{\text{ground}}=8$ 精确吻合。一个 $3\times3$ 行列式就数清了图的生成树——这是线性代数与组合数学最著名的联姻之一，也是 $L=A^{\mathsf T}A$ 结构信息量的最佳体现。

演示 6：把演示 4 的无解例子交给最小二乘

步骤 1：取一个无解之例。 用演示 4 步骤 3 的 (c)：$b=(1,0,0,0,0)^{\mathsf T}$。已验算它无解（$b\cdot y^{(1)}=1\neq0$）。退而求

步骤 2：写正规方程 $Lx=A^{\mathsf T}b$。 逐列计算 $A^{\mathsf T}b$（$A$ 的第 1 列是 $(-1,0,0,-1,-1)^{\mathsf T}$）：

这里有一步极易出错的计算：$b$ 只有第一个分量非零，容易只记住 $A_{11}=-1$ 而漏掉 $A_{12}=+1$。正确答案是 $(-1,1,0,0)^{\mathsf T}$，不是 $(-1,0,0,0)^{\mathsf T}$。

步骤 3：解方程（仍固定 $x_4=0$）。 接地后的 $3\times3$ 系统：

解得

回代验算（三个方程）：

\(3\!\left(-\tfrac18\right)-\tfrac12-\tfrac18=\tfrac{-3-4-1}{8}=-1\ \checkmark\) \(-\!\left(-\tfrac18\right)+2\!\left(\tfrac12\right)-\tfrac18=\tfrac{1+8-1}{8}=1\ \checkmark\) \(-\!\left(-\tfrac18\right)-\tfrac12+3\!\left(\tfrac18\right)=\tfrac{1-4+3}{8}=0\ \checkmark\)

步骤 4：算预测值与残差。

步骤 5：验证 $e\perp C(A)$（用 $A^{\mathsf T}e=\mathbf{0}$，逐节点）。

\(\text{节点 1}:\ -e_1-e_4-e_5=-\tfrac38+\tfrac18+\tfrac14=\tfrac{-3+1+2}{8}=0\ \checkmark\) \(\text{节点 2}:\ e_1-e_2=\tfrac38-\tfrac38=0\ \checkmark\) \(\text{节点 3}:\ e_2-e_3+e_5=\tfrac38-\tfrac18-\tfrac14=\tfrac{3-1-2}{8}=0\ \checkmark\) \(\text{节点 4}:\ e_3+e_4=-\tfrac18+\tfrac18=0\ \checkmark\)

$A^{\mathsf T}e=\mathbf{0}$ 全部通过 ⇒ $e\in N(A^{\mathsf T})=C(A)^{\perp}$ ⇒ 误差垂直于列空间。

步骤 6：能量核对。 $x^{\mathsf T}(A^{\mathsf T}b)=\vert Ax\vert ^2+\vert e\vert ^2$？验证：

而 $\vert b\vert ^2=1$ ✓。正交分解把 $\vert b\vert ^2$ 精确拆成”模型解释的部分 $\vert Ax\vert ^2$”与”残差部分 $\vert e\vert ^2$”——这就是统计学里”总平方和 = 回归平方和 + 残差平方和”的几何本质。

矩阵分解的核心思想

本讲不引入新分解，但把已有分解全部点亮：

1. $L=A^{\mathsf T}A$。这与讲次 16 最小二乘的正规方程 $A^{\mathsf T}A\hat x=A^{\mathsf T}b$ 是同一个矩阵。在弹簧/电阻网络里它就是刚度矩阵。$L$ 对称、半正定、对角元为度数、$\operatorname{rank}(L)=\operatorname{rank}(A)=n-1$：它是讲次 26 正定矩阵家族最自然的活样本。
2. $A=CR$（讲次 11）。取 $R=\mathrm{RREF}(A)$ 的前 3 个非零行、$C$ 取 $A$ 的前 3 列（对应 $e_1,e_2,e_3$，构成 1-2-3-4 的链，无回路，是生成树）：

物理含义：每条边的落差都能用生成树上的落差组合出来；树外的边（$e_4,e_5$）是”多余”的，它们恰好形成回路。秩 = 生成树的边数，非常直观。

1. 秩-零化度定理的化身：$r=n-1$ 与 $\ell=m-r$ 合起来就是 $n-m+\ell=1$。四个子空间的维数表：

  子空间      维数        本图数值        物理含义
  ---------------------------------------------------------------------
  C(A)        r           3              可实现的边电势差 (KVL 相容)
  N(A^T)      m - r       2 = m-n+1      回路空间 (KCL 环流)
  C(A^T)      r           3              节点电势能张成的方向 = N(A)^perp
  N(A)        n - r       1 = n-m+1      整体电势平移 (等电势)
  ---------------------------------------------------------------------
  R^n = C(A^T) ⊕ N(A):   3 + 1 = 4 = n
  R^m = C(A)   ⊕ N(A^T): 3 + 2 = 5 = m

与其他讲次的关联

• 回顾讲次 10（四个基本子空间）：本讲是那张”大图”最具体的实现——$N(A)$ 是 1 维常数电势，$N(A^{\mathsf T})$ 是回路，尺寸全部可数可验。请把讲次 10 的 $r+(n-r)=n$、$r+(m-r)=m$ 对照本讲的 $(3+1=4,\ 3+2=5)$。
• 回顾讲次 11（$A=CR$）：关联矩阵的 $R$ 由生成树决定，秩 = 树的边数。
• 通向讲次 14（正交）：本讲的 $C(A)\perp N(A^{\mathsf T})$ 与 $C(A^{\mathsf T})\perp N(A)$ 正是那一讲的核心定理；这里先给了物理直觉，那里补严格证明。
• 通向讲次 16（最小二乘）：$L=A^{\mathsf T}A$ 出场。当 $Ax=b$ 无解（如上例 (b)(c)(d)）时退而求 $\min\vert Ax-b\vert ^2$，正规方程 $A^{\mathsf T}Ax=A^{\mathsf T}b$ 永远有解（因为 $A^{\mathsf T}b\in C(A^{\mathsf T})=C(A^{\mathsf T}A)$）。在电阻网络里这就是最小能量原理。
• 通向讲次 26（正定矩阵）：$x^{\mathsf T}Lx=\vert Ax\vert ^2\ge0$，取等仅当 $x=c\mathbf{1}$。固定某个节点的电势（消去那个自由度）即得严格正定矩阵。

关键要点

1. 构造：行 = 边，列 = 节点，每行恰有一个 $+1$、一个 $-1$。（Strang §8.2 用 $m\times n$；本笔记全程如此，勿中途切换。）
2. 连通 $\iff \operatorname{rank}(A)=n-1$；$k$ 个连通块 $\iff \operatorname{rank}(A)=n-k$。
3. 四个子空间的名字：$N(A)$ = 等电势；$N(A^{\mathsf T})$ = 回路空间（KCL）；$C(A^{\mathsf T})$ = 节点势方向；$C(A)$ = 相容的边落差。
4. 欧拉公式：连通图 $n-m+\ell=1$，其中 $\ell=m-n+1=\dim N(A^{\mathsf T})=m-r$。
5. $L=A^{\mathsf T}A$：$L_{jj}=$ 度数，$L_{ij}=-1$（有边）；$L\mathbf{1}=\mathbf{0}$；$x^{\mathsf T}Lx=\vert Ax\vert ^2=\sum(\Delta x)^2\ge0$。
6. 相容判据（务必分清两边）：$Ax=b$ 有解 $\iff b\perp N(A^{\mathsf T})$（$\mathbb R^m$ 里 $m-r$ 个条件）；$A^{\mathsf T}y=f$ 有解 $\iff f\perp N(A)\iff\sum f_j=0$（$\mathbb R^n$ 里 $n-r$ 个条件）。

常见误区与注意事项

1. 把行/列角色搞反。 若取 $A$ 为 $n\times m$（列 = 边），则 $N(A)$ 变成回路、$N(A^{\mathsf T})$ 变成等电势，索引全部错位。本笔记全程 $m\times n$（行 = 边）。
2. 以为”列和为 0”说明行相关。 恰恰相反：$\sum_i\text{col}_i=\mathbf{0}$ 说明列相关（$\dim N(A)\ge1$）。行之间的关系要用回路上的行组合去查。
3. 把 $N(A^{\mathsf T})$ 说成 $\mathbb R^n$ 里的子空间。 $A^{\mathsf T}$ 是 $n\times m$，故 $N(A^{\mathsf T})\subseteq\mathbb R^m$（边空间，长度 $=m=5$）。$\mathbb R^n$ 里的是 $N(A)$ 与 $C(A^{\mathsf T})$。行空间 $C(A^{\mathsf T})\subseteq\mathbb R^n$，不是 $\mathbb R^m$。
4. 混淆 $\dim N(A)=n-r$ 与 $\dim N(A^{\mathsf T})=m-r$。 本讲数字 $n-r=1$、$m-r=2$，写反会得出”1 个回路”的错误结论。
5. 把 $\sum b_k=0$ 当成 $Ax=b$ 的相容条件。 这是错的！反例：$b=(1,1,1,3,2)$ 满足 $\sum b_k=8\neq0$，但它有解。$\sum f_j=0$ 是另一个方程 $A^{\mathsf T}y=f$ 的条件（见关键要点 6 的对照表）。
6. 回路向量符号写错。 追踪回路时必须核对每条边方向是否与行进方向一致，反向的边取 $-1$。写完后一定用 $A^{\mathsf T}y=\mathbf{0}$ 逐节点回代验证。
7. 以为”图连通”只是画图的事。 它代数上就是 $\operatorname{rank}(A)=n-1$、$L$ 只有一个零特征值。若图分成两块（如 1-2 与 3-4），则 $\dim N(A)=2$，$L$ 有重零特征值，$\ell=m-n+2$。

思考题（带答案）

Q1.（纯计算） 取路径图 $P_4$：节点 $1,2,3,4$ 依次相连，只有 3 条边 $e_1=1\!-\!2$、$e_2=2\!-\!3$、$e_3=3\!-\!4$。写出 $A$（$3\times4$），求 $\operatorname{rank}(A)$、$N(A)$、$N(A^{\mathsf T})$、$L=A^{\mathsf T}A$，并用欧拉公式验证。

Q2.（概念理解） 有人说：”$N(A^{\mathsf T})$ 里的向量 $y$ 代表节点上的电势，因为 $A^{\mathsf T}$ 把边上的量变成节点上的量。” 这句话错在哪里？请用本讲的 4 节点图给出反例数据。

Q3.（概念 + 计算） 在 4 节点图中删掉一条边：先删树边 $e_2=2\!-\!3$，再改成删树外边 $e_5$（对角线）。分别说明 $\operatorname{rank}$、$\dim N(A)$、$\dim N(A^{\mathsf T})$ 与欧拉公式，并指出哪种删除”更危险”。