关联矩阵编码图
每列一条边，每行一个节点，\(+1\) 离开、\(-1\) 进入。
18.06 · 第 12 课
线性代数不只是抽象的向量空间——它还是描述真实世界网络的语言。关联矩阵（incidence matrix）把图（graph）变成线性方程，基尔霍夫定律（Kirchhoff's laws）就是 \(A^T\mathbf{y}=\mathbf{f}\)。
一个有向图有 \(m\) 个节点和 \(n\) 条边。关联矩阵（incidence matrix）\(A\) 是 \(m\times n\) 矩阵，每列对应一条边，每行对应一个节点：
\[A_{ij} = \begin{cases} +1 & \text{边 } j \text{ 离开节点 } i,\\ -1 & \text{边 } j \text{ 进入节点 } i,\\ 0 & \text{边 } j \text{ 与节点 } i \text{ 无关}. \end{cases}\]例如 4 节点 5 条边的图：
\[A = \begin{bmatrix} -1 & -1 & 0 & 0 & 0 \\ 1 & 0 & -1 & -1 & 0 \\ 0 & 1 & 1 & 0 & -1 \\ 0 & 0 & 0 & 1 & 1 \end{bmatrix}.\]每列恰好一个 \(+1\) 和一个 \(-1\)，因此各行之和为零——行向量线性相关，秩最多为 \(m-1\)。
图与矩阵一一对应。关联矩阵把图的拓扑结构编码为线性代数对象。零空间对应常数电势，行空间对应节点电势差，列空间对应边上的电势差。
设 \(\mathbf{x}\in\mathbb{R}^m\) 是节点电势向量，则 \(A^T\mathbf{x}\in\mathbb{R}^n\) 是每条边两端的电势差。方程 \(A\mathbf{w}=\mathbf{0}\) 意味着每条边上的"环流差"为零。
对于连通图，\(A\) 的零空间由全 1 向量张成：
\[N(A) = \operatorname{span}\{\mathbf{1}\} = \operatorname{span}\left\{\begin{bmatrix}1\\1\\\vdots\\1\end{bmatrix}\right\},\quad \dim N(A)=1.\]因此 \(\operatorname{rank}(A)=m-1\)。列空间 \(C(A)\) 维数为 \(m-1\)，左零空间 \(N(A^T)\) 维数为 1，由全 1 向量张成——这正是"所有行加起来为零"的代数表达。
设 \(\mathbf{y}\in\mathbb{R}^n\) 是每条边上的电流，\(\mathbf{f}\in\mathbb{R}^m\) 是每个节点的外部电流源。基尔霍夫电流定律（Kirchhoff's Current Law, KCL）说：每个节点的净电流等于外部源：
\[A^T\mathbf{y} = \mathbf{f}.\]可解性条件：\(\mathbf{f}\) 必须在 \(C(A^T)\) 中。由于 \(N(A^T)=\operatorname{span}\{\mathbf{1}\}\)，需要 \(\mathbf{1}^T\mathbf{f}=0\)，即总电流源为零（电荷守恒）。
物理约束。KCL 可解当且仅当 \(\sum f_i = 0\)。如果题目给的电流源不满足这个条件，说明题目本身违反电荷守恒。
欧姆定律（Ohm's law）：边上的电流与电势差成正比。设 \(C=\operatorname{diag}(c_1,\dots,c_n)\) 是电导（conductance）矩阵，则
\[\mathbf{y} = C\,A^T\mathbf{x}.\]代入 KCL 得到电网络方程：
\[A^T C A\,\mathbf{x} = \mathbf{f}.\]这里 \(K = A^T C A\) 称为基尔霍夫矩阵（Kirchhoff matrix）或电导矩阵。它是对称半正定的，零空间由 \(\mathbf{1}\) 张成——电势可以整体平移而不影响电流。
三个物理定律 = 三个线性方程。欧姆定律给出 \(\mathbf{y}=CA^T\mathbf{x}\)，KCL 给出 \(A^T\mathbf{y}=\mathbf{f}\)，合起来就是 \(A^TCA\mathbf{x}=\mathbf{f}\)。线性代数把电路分析变成矩阵运算。
图的回路（loop）对应 \(A^T\) 的零空间中的向量。每个回路给出一个环流（circulation），这些环流构成 \(N(A^T)\) 的基。
环流 \(\mathbf{w}\in N(A^T)\) 满足 \(A^T\mathbf{w}=\mathbf{0}\)，即每个节点上流入等于流出——这正是 KCL 在无外部源时的表达。独立回路个数等于 \(n-(m-1)=n-m+1\)。
问题 1：在关联矩阵 \(A\) 中，第 \(j\) 列代表什么？
问题 2：方程 \(A^T\mathbf{y}=\mathbf{f}\) 可解的条件是什么？
问题 3：电网络方程 \(A^T C A\,\mathbf{x} = \mathbf{f}\) 中，\(K = A^T C A\) 叫做什么？
问题 4：连通图的关联矩阵 \(A\) 的零空间维数是多少？
每列一条边，每行一个节点，\(+1\) 离开、\(-1\) 进入。
欧姆定律 \(\mathbf{y}=CA^T\mathbf{x}\)、KCL \(A^T\mathbf{y}=\mathbf{f}\)、电网络方程 \(A^TCA\mathbf{x}=\mathbf{f}\)。
电荷守恒对应 \(\sum f_i=0\)，电势平移对应 \(N(A)=\operatorname{span}\{\mathbf{1}\}\)。
\(N(A^T)\) 中的向量对应图中的独立回路，是环流的基。
lecture_slides/lecture_12.pdflecture_summaries/lecture_1_12_summary.pdf