为什么这一讲重要

前几讲的矩阵多是课堂上临时构造的，这一讲换成一个有真实结构的矩阵：图的关联矩阵。真实问题里的矩阵都带着结构，而结构决定了哪些问题可以不算就能回答。

图由节点与边组成。它可以表示电网、水管网、桥梁结构，也可以表示友谊关系与网页链接。Strang 说它是应用数学中最重要的离散模型。

本讲用一个小图：4 个节点，5 条边，每条边人为指定一个方向：

• $e_1: 1\to2$
• $e_2: 2\to3$
• $e_3: 1\to3$
• $e_4: 1\to4$
• $e_5: 3\to4$

时间轴

关联矩阵

对每条边写一行，对每个节点写一列。边从某节点出发记 $-1$，进入某节点记 $+1$：

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

这是一个 $5\times4$ 的稀疏矩阵：每行只有两个非零元，总非零元数为 $2m$（$m$ 为边数）。大图会得到很大的矩阵，但结构极其规整。

零空间：常电位

把 $A$ 乘上一个向量 $\mathbf{x}=(x_1,x_2,x_3,x_4)^\top$，得到

$$A\mathbf{x}= \begin{bmatrix} x_2-x_1\\ x_3-x_2\\ x_3-x_1\\ x_4-x_1\\ x_4-x_3 \end{bmatrix}.$$

若把 $x_i$ 看作节点电位，那么 $A\mathbf{x}$ 正好是每条边上的电位差。

令 $A\mathbf{x}=\mathbf{0}$，就是要求所有电位差为零。显然 $\mathbf{x}=(1,1,1,1)$ 满足，任何常数向量都满足。因此

$$N(A)=\operatorname{span}\{(1,1,1,1)\},\qquad \dim N(A)=1.$$

物理含义：电位只能确定到一个常数。真正驱动电流的是电位差，把所有电位同时抬高或降低，什么都不会改变。要给电位一个基准，就把某个节点接地，令它的电位为 0——那一列随之消失，剩下三列线性无关。

秩与列空间

$A$ 是 $5\times4$，零空间维数为 1，所以

$$r=n-1=4-1=3.$$

任意三个电位都是独立变量，第四个由「差值为零」的条件确定。列空间是 $\mathbb{R}^5$ 中的一个三维子空间，具体含义是「所有满足基尔霍夫电压定律的电位差组合」。

左零空间：回路

$A^\top\mathbf{y}=\mathbf{0}$ 是应用数学中最基本的方程之一。先看它逐行写出是什么：

$$\begin{aligned} -y_1-y_3-y_4&=0 &&\text{（节点 1）}\\ y_1-y_2&=0 &&\text{（节点 2）}\\ y_2+y_3-y_5&=0 &&\text{（节点 3）}\\ y_4+y_5&=0 &&\text{（节点 4）} \end{aligned}$$

每一行说的是：流入某节点的电流等于流出该节点的电流。这就是基尔霍夫电流定律（KCL）——一个平衡方程，电荷不会在节点堆积。

维数为

$$\dim N(A^\top)=m-r=5-3=2.$$

两组基对应两个独立回路：

• 回路 $e_1,e_2,e_3$：$\mathbf{y}=(1,1,-1,0,0)$；
• 回路 $e_3,e_4,e_5$：$\mathbf{y}=(0,0,1,-1,1)$。

绕整个外圈 $(1,1,0,-1,1)$ 也是解，但它是前两个之和，不是新的基向量。回路的数量与位置，正是左零空间的维数与基。

欧拉公式

由 $\dim N(A^\top)=m-r$ 与 $r=n-1$（连通图），得

$$\#\text{回路}=m-(n-1)=m-n+1.$$

移项：

$$\#\text{节点}-\#\text{边}+\#\text{回路}=1.$$

这就是欧拉公式。节点是零维对象，边是一维对象，回路是二维对象，这个计数对任何连通平面图都成立。线性代数在这里给出的是一个拓扑事实的证明。

三个方程：应用数学的骨架

把电学量按顺序串起来：

1. 电位差：$\mathbf{e}=A\mathbf{x}$，其中 $\mathbf{x}$ 是节点电位。
2. 欧姆定律：$\mathbf{y}=C\mathbf{e}$，$C$ 是对角矩阵，对角元是各边的电导（电阻的倒数）。
3. 基尔霍夫电流定律：$A^\top\mathbf{y}=\mathbf{f}$，$\mathbf{f}$ 是外部注入节点的电流源。

合起来：

$$A^\top C A\,\mathbf{x}=\mathbf{f}.$$

这个 $A^\top C A$ 就是本章后面反复出现的矩阵的原型。它对称、稀疏，并且把图的连通结构编码进代数方程。数值线性代数里大量系统都长这个样子。

关于 $A^\top A$

$A^\top A$ 总是对称的，因为

$$(A^\top A)^\top=A^\top (A^\top)^\top=A^\top A.$$

对关联矩阵而言，$A^\top A$ 是一个图拉普拉斯矩阵：对角元是节点度数，非对角元在相邻节点处为 $-1$。它将在后面的网络与聚类问题中再次出现。

本讲结论

• 关联矩阵每一行对应一条边，每一列对应一个节点。
• 零空间是常电位向量，维数 1；接地一个节点即可消除这个自由度。
• 左零空间是回路空间，维数 $m-r$。
• 对连通图，$r=n-1$，于是节点数减边数加回路数等于 1，即欧拉公式。
• 电位差、欧姆定律、电流守恒三步给出 $A^\top C A\mathbf{x}=\mathbf{f}$。

理解检验

1. 为什么关联矩阵每行只有两个非零元？这对稀疏性意味着什么？

参考答案：关联矩阵的一行对应一条边，而一条边只有起点和终点两个节点：起点记 $-1$、终点记 $+1$，其余节点的列全为 $0$。所以每行恰有两个非零元。

整个矩阵是 $m\times n$ 的，非零元总数为 $2m$，密度为 $2m/(mn)=2/n$。节点数越大，密度越低：一张百万节点的图，每行仍只有两个非零元。这正是稀疏矩阵的典型结构——存储只需 $O(m)$ 而非 $O(mn)$，消元与迭代求解也可以只沿边进行。

2. 为什么零空间里的向量必须是常数向量？

参考答案：$A\mathbf{x}=\mathbf{0}$ 逐行写出，就是每条边两端电位相等：对边 $i\to j$ 有 $x_j-x_i=0$，即 $x_i=x_j$。

图是连通的，任意两个节点之间都有一条路径，沿着路径逐边传递相等关系，就得到所有 $x_i$ 相等。所以 $\mathbf{x}=c(1,1,1,1)$，零空间恰为一维，由全 1 向量张成。若图不连通，则每个连通分支贡献一个常数，零空间维数等于连通分支数。

3. 回路与外圈回路的关系，为什么外圈不是新的基向量？

参考答案：外圈 $(1,1,0,-1,1)$ 对应的边是 $e_1,e_2,e_4,e_5$，它确实是左零空间里的向量，但

$$(1,1,0,-1,1)=(1,1,-1,0,0)+(0,0,1,-1,1),$$

即它是两个基本回路向量之和，落在它们张成的空间里。

左零空间维数为 $m-r=5-3=2$，任意一组基只能有 2 个向量；加入第三个必然相关。所以外圈回路存在，但不提供新的方向，不能作为第三个基向量。这也说明「回路数」与「独立回路数」不是一回事：图的回路可以很多，独立回路数固定为 $m-n+1$。

4. 对一张有 6 个节点、8 条边的连通图，秩与独立回路数各是多少？

参考答案：连通图满足 $r=n-1$，所以

$$r=6-1=5 .$$

独立回路数（左零空间维数）为

$$m-r=8-5=3 .$$

也可以直接用欧拉公式核对：$n-m+\#\text{回路}=6-8+3=1$。注意这里假设图连通且没有孤立节点；若有不连通的部分，秩要相应减少。

5. 写出 $A^\top A$ 的对角元与非对角元的含义。

参考答案：$A^\top A$ 是 $n\times n$ 的（$n$ 为节点数），其 $(i,j)$ 元等于 $A$ 的第 $i$ 列与第 $j$ 列的内积。

• 对角元 $(i,i)$：第 $i$ 列与自身的内积。该列在每个与节点 $i$ 相连的边上恰有一个 $\pm1$，平方为 $1$，所以对角元等于节点 $i$ 的度数（关联的边数）。
• 非对角元 $(i,j)$，$i\ne j$：两列同时非零，当且仅当存在连接 $i$、$j$ 的边；此时该边上两列的分量一为 $-1$、一为 $+1$，乘积为 $-1$。所以非对角元在相邻节点处为 $-1$，否则为 $0$。

因此

$$A^\top A=D-\text{（邻接矩阵）},$$

其中 $D$ 是度数对角矩阵。这正是图拉普拉斯矩阵，它对称、半正定、行和为 $0$，零空间由各连通分支的常向量张成。

与前后课程的关系

上一讲把矩阵与函数都看作向量空间；这一讲让向量空间落在真实的图上。下一讲复习前一半内容，随后进入正交性：行空间与零空间不仅是维数互补，还互相垂直。

Why this lecture matters

Earlier matrices were invented on the spot for illustration. This lecture uses a matrix with genuine structure: the incidence matrix of a graph. Real problems produce matrices with structure, and structure lets you answer questions without computing.

A graph is a set of nodes and edges. It can model an electrical grid, a water network, a bridge, a friendship relation, or the web. Strang calls it the most important discrete model in applied mathematics.

The example graph has 4 nodes and 5 edges, each given an arbitrary direction:

• $e_1: 1\to2$
• $e_2: 2\to3$
• $e_3: 1\to3$
• $e_4: 1\to4$
• $e_5: 3\to4$

Timeline

The incidence matrix

One row per edge, one column per node. An edge leaving a node contributes $-1$; entering contributes $+1$:

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

This is a sparse $5\times4$ matrix: every row has exactly two nonzero entries, so the total is $2m$ for $m$ edges. A large graph gives a large but extremely regular matrix.

Null space: constant potential

Multiply $A$ by $\mathbf{x}=(x_1,x_2,x_3,x_4)^\top$:

$$A\mathbf{x}= \begin{bmatrix} x_2-x_1\\ x_3-x_2\\ x_3-x_1\\ x_4-x_1\\ x_4-x_3 \end{bmatrix}.$$

If $x_i$ is the potential at node $i$, then $A\mathbf{x}$ is exactly the potential difference across each edge.

Setting $A\mathbf{x}=\mathbf{0}$ forces every difference to vanish. The constant vector $(1,1,1,1)$ works, and so does any constant vector. Hence

$$N(A)=\operatorname{span}\{(1,1,1,1)\},\qquad \dim N(A)=1.$$

The physical meaning: potentials are determined only up to a constant. Current is driven by differences. Raising every potential by the same amount changes nothing. To fix a reference, ground one node by setting its potential to zero; that column disappears and the remaining three are independent.

Rank and column space

$A$ is $5\times4$ with a one-dimensional null space, so

$$r=n-1=4-1=3.$$

Any three potentials are independent variables; the fourth is fixed by the zero-difference condition. The column space is a three-dimensional subspace of $\mathbb{R}^5$, consisting of all potential-difference patterns that satisfy Kirchhoff's voltage law.

Left null space: loops

$A^\top\mathbf{y}=\mathbf{0}$ is one of the fundamental equations of applied mathematics. Written row by row:

$$\begin{aligned} -y_1-y_3-y_4&=0 &&\text{(node 1)}\\ y_1-y_2&=0 &&\text{(node 2)}\\ y_2+y_3-y_5&=0 &&\text{(node 3)}\\ y_4+y_5&=0 &&\text{(node 4)} \end{aligned}$$

Each line says that current into a node equals current out. This is Kirchhoff's current law (KCL) — a balance equation. Charge does not accumulate at nodes.

The dimension is

$$\dim N(A^\top)=m-r=5-3=2.$$

Two independent loops give a basis:

• loop $e_1,e_2,e_3$: $\mathbf{y}=(1,1,-1,0,0)$;
• loop $e_3,e_4,e_5$: $\mathbf{y}=(0,0,1,-1,1)$.

Current around the outer loop, $(1,1,0,-1,1)$, is also a solution, but it is the sum of the first two and adds nothing to the basis. The number and placement of loops are exactly the dimension and basis of the left null space.

Euler's formula

From $\dim N(A^\top)=m-r$ and $r=n-1$ for a connected graph,

$$\#\text{loops}=m-(n-1)=m-n+1.$$

Rearranged:

$$\#\text{nodes}-\#\text{edges}+\#\text{loops}=1.$$

This is Euler's formula. Nodes are zero-dimensional, edges one-dimensional, loops two-dimensional, and the count holds for every connected planar graph. Linear algebra supplies a proof of a topological fact.

Three equations: the skeleton of applied math

Chain the electrical quantities:

1. Potential differences: $\mathbf{e}=A\mathbf{x}$, with $\mathbf{x}$ the node potentials.
2. Ohm's law: $\mathbf{y}=C\mathbf{e}$, where $C$ is diagonal with conductances (reciprocals of resistance).
3. Kirchhoff's current law: $A^\top\mathbf{y}=\mathbf{f}$, with $\mathbf{f}$ external current sources.

Combining them:

$$A^\top C A\,\mathbf{x}=\mathbf{f}.$$

The matrix $A^\top C A$ is the prototype that dominates the rest of the chapter. It is symmetric, sparse, and encodes the graph's connectivity in an algebraic system. Numerical linear algebra is full of systems with this shape.

About $A^\top A$

$A^\top A$ is always symmetric:

$$(A^\top A)^\top=A^\top (A^\top)^\top=A^\top A.$$

For an incidence matrix, $A^\top A$ is a graph Laplacian: diagonal entries are node degrees, and off-diagonal entries are $-1$ between adjacent nodes. It reappears in network and clustering problems.

Takeaways

• Each row of the incidence matrix is an edge; each column is a node.
• The null space is the constant-potential vector, dimension 1; grounding a node removes that freedom.
• The left null space is the loop space, dimension $m-r$.
• For a connected graph $r=n-1$, so nodes minus edges plus loops equals 1: Euler's formula.
• Potential differences, Ohm's law, and current conservation give $A^\top C A\mathbf{x}=\mathbf{f}$.

Check your understanding

1. Why does every row of the incidence matrix have only two nonzero entries, and what does that imply for sparsity?

Reference answer: A row corresponds to one edge, and an edge has exactly two endpoints: its tail gets $-1$, its head gets $+1$, and every other column is $0$. So each row has exactly two nonzero entries.

The matrix is $m\times n$ with $2m$ nonzero entries total, a density of $2m/(mn)=2/n$. The larger the graph, the sparser it is: even with a million nodes each row still has only two nonzeros. That is the canonical sparse structure — storage costs $O(m)$ rather than $O(mn)$, and elimination or iterative solves can run along the edges.

2. Why must every vector in the null space be constant?

Reference answer: Row by row, $A\mathbf{x}=\mathbf{0}$ says the potentials at the two ends of each edge agree: for the edge $i\to j$, $x_j-x_i=0$, i.e. $x_i=x_j$.

Since the graph is connected, any two nodes are joined by a path; propagating equality along the path gives $x_i=x_j$ for all $i,j$. Hence $\mathbf{x}=c(1,1,1,1)$ and the null space is one-dimensional, spanned by the all-ones vector. For a disconnected graph, each connected component contributes one constant, so the null-space dimension equals the number of components.

3. Why is the outer loop not an additional basis vector?

Reference answer: The outer loop $(1,1,0,-1,1)$ uses edges $e_1,e_2,e_4,e_5$ and does lie in the left null space, but

$$(1,1,0,-1,1)=(1,1,-1,0,0)+(0,0,1,-1,1),$$

so it is the sum of the two fundamental loop vectors and lies in their span.

The left null space has dimension $m-r=5-3=2$, so any basis has exactly two vectors; adding a third forces dependence. The outer loop exists but adds no new direction, so it cannot be a third basis vector. This also separates "number of loops" from "number of independent loops": a graph may have many loops, but the independent count is fixed at $m-n+1$.

4. For a connected graph with 6 nodes and 8 edges, what are the rank and the number of independent loops?

Reference answer: For a connected graph $r=n-1$, so

$$r=6-1=5 .$$

The number of independent loops, i.e. the left null-space dimension, is

$$m-r=8-5=3 .$$

Euler's formula confirms it: $n-m+\#\text{loops}=6-8+3=1$. This assumes the graph is connected with no isolated nodes; for a disconnected graph the rank drops accordingly.

5. What do the diagonal and off-diagonal entries of $A^\top A$ mean?

Reference answer: $A^\top A$ is $n\times n$ (with $n$ the number of nodes), and its $(i,j)$ entry is the inner product of columns $i$ and $j$ of $A$.

• Diagonal $(i,i)$: the inner product of column $i$ with itself. That column has a $\pm1$ in each row corresponding to an edge at node $i$, and $(\pm1)^2=1$, so the diagonal entry is the degree of node $i$.
• Off-diagonal $(i,j)$, $i\ne j$: the two columns are both nonzero exactly when some edge joins $i$ and $j$; on that edge one column has $-1$ and the other $+1$, whose product is $-1$. So the entry is $-1$ for adjacent nodes and $0$ otherwise.

Hence

$$A^\top A=D-(\text{adjacency matrix}),$$

where $D$ is the diagonal degree matrix. This is the graph Laplacian: symmetric, positive semidefinite, with row sums zero and a null space spanned by the constants on each connected component.

How this connects to the course

The previous lecture treated matrices and functions as vector spaces; this one grounds vector spaces in real graphs. The next lecture reviews the first half of the course, after which orthogonality shows that the row space and null space are not merely dimension-complementary but perpendicular.