Lecture 11: Matrix Spaces; Rank 1; Small World Graphs

目录 · ← l10 · l12 →

Lecture 11: Matrix Spaces; Rank 1; Small World Graphs

概述

上一讲的四个子空间全部住在 $\mathbb{R}^n$ 或 $\mathbb{R}^m$ 里——它们是向量的集合。本讲要做一个关键的跳跃：把矩阵本身看作向量。所有 $3\times3$ 矩阵构成一个 9 维向量空间 $M$，而对称矩阵、上三角矩阵、对角矩阵都是它漂亮的子空间。有了这个视角，”矩阵的空间”和”向量的空间”就是同一套理论，于是上一讲的维数公式（尤其是 $\dim(S+U)=\dim S+\dim U-\dim(S\cap U)$）可以直接搬过来用。

本讲的第二条线是秩 1 矩阵 $A=\mathbf{u}\mathbf{v}^{\mathsf T}$：它是最简单的矩阵，也是理解一切矩阵的”原子”。任何秩 $r$ 矩阵都能写成 $r$ 个秩 1 矩阵之和，这正是 $A=CR$ 分解的含义，也直接预告了讲次 29 的 SVD。

第三条线是小世界图：如何把一个网络写成一个矩阵。邻接矩阵 $A$ 和关联矩阵 $B$ 让图的连通性、环、路径计数全部变成线性代数问题——”六度分隔”于是成了一个关于 $A^k$ 的陈述。这是四个子空间最具体、最有趣的应用现场。

核心概念的几何直觉

概念一：矩阵空间 $M$（the vector space of matrices）

• 定义与目的：固定尺寸 $m\times n$，把所有这样的实矩阵收进一个集合 $M$，定义加法（逐元素相加）与数乘（逐元素缩放）。$M$ 满足向量空间的全部八条公理，所以它是一个向量空间。目的：让”矩阵”这个对象也能享受子空间、基、维数、线性无关这一整套语言。

• 几何直觉（它在空间中是什么样子？）：$M$ 就是 $\mathbb{R}^{mn}$ 穿了件”方阵外衣”。$3\times3$ 矩阵有 9 个位置，每个位置可以自由填一个实数，而填数这个动作是逐位置独立的——所以 $M$ 的”自由度”就是 $mn=9$。事实上映射 \(\begin{bmatrix}a_{11}&\cdots&a_{1n}\\ \vdots&&\vdots\\ a_{m1}&\cdots&a_{mn}\end{bmatrix}\longmapsto (a_{11},a_{12},\dots,a_{mn})\in\mathbb{R}^{mn}\) 是一个可逆的线性变换（叫”拉直”或 vectorization），它把矩阵空间同构成 $\mathbb{R}^{mn}$。所以维数不用猜：$\dim M=mn$。

• 具体示例：一个 3×3 矩阵的标准基（Strang 常写在黑板上）就是 9 个”单点矩阵”： \(\begin{bmatrix}1&0&0\\0&0&0\\0&0&0\end{bmatrix},\ \begin{bmatrix}0&1&0\\0&0&0\\0&0&0\end{bmatrix},\ \dots,\ \begin{bmatrix}0&0&0\\0&0&0\\0&0&1\end{bmatrix}.\) 任意 3×3 矩阵都是这 9 个的线性组合，且组合系数唯一（系数就是它的 9 个元素）。因此这 9 个矩阵线性无关，$\dim M(3\times3)=9$。

概念二：矩阵空间的子空间 —— 对称、上三角、对角

• 定义与目的：在 $M$ 里挑出满足额外条件的矩阵，看它们是否仍然是子空间（对数乘与加法封闭）。三个经典选手：
  • 对称矩阵 $S=\{A: A^{\mathsf T}=A\}$；
  • 上三角矩阵 $U=\{A: a_{ij}=0 \text{ 当 } i>j\}$；
  • 对角矩阵 $D=\{A: a_{ij}=0 \text{ 当 } i\neq j\}$。
• 几何直觉（它在空间中是什么样子？）：这三个集合都是线性约束切出来的”平板”，因而都是子空间。注意”约束”的含义：
  • $S$ 的约束是 $a_{ij}=a_{ji}$：等式型约束（不是设为零！），它把上三角的 3 个位置”绑定”到下三角的 3 个位置。自由度 = 对角 3 + 上三角 3 = 6。
  • $U$ 的约束是下三角 3 个位置必须为 0。自由度 = 9 − 3 = 6。
  • $D$ 的约束是非对角 6 个位置必须为 0。自由度 = 3。 三者关系：$D=S\cap U$（既对称又上三角 ⇒ 非对角元素既相等又为零 ⇒ 只能是对角）。这是理解本讲维数公式的钥匙。
• 具体示例：3×3 对称矩阵的 6 个基”积木”： \(\begin{bmatrix}1&0&0\\0&0&0\\0&0&0\end{bmatrix},\begin{bmatrix}0&0&0\\0&1&0\\0&0&0\end{bmatrix},\begin{bmatrix}0&0&0\\0&0&0\\0&0&1\end{bmatrix},\begin{bmatrix}0&1&0\\1&0&0\\0&0&0\end{bmatrix},\begin{bmatrix}0&0&1\\0&0&0\\1&0&0\end{bmatrix},\begin{bmatrix}0&0&0\\0&0&1\\0&1&0\end{bmatrix}.\) 3 个对角”单点” + 3 个”对称配对”（每对同时点燃两个位置）。每个 3×3 对称矩阵都是这 6 个的唯一组合，所以 $\dim S=6$。

维数公式（子空间版的容斥原理）：

其中 $S+U=\{s+u: s\in S,\;u\in U\}$（所有”对称阵 + 上三角阵”的集合，它也是子空间）。代入数字：

也就是说，任何 3×3 矩阵都能写成一个对称矩阵与一个上三角矩阵之和。下面用代码块图示这个”分割”：

   3x3 矩阵 M  (dim 9)
   +-------------------+-------------------+
   |  对称  S (dim 6)  |  <= 二者有重叠 =>  |
   |                   |     不是直和!      |
   |        +===============+               |
   |        | 对角 D (dim 3)| <= S ∩ U = D   |
   |        +===============+               |
   |                   |  上三角 U (dim 6) |
   +-------------------+-------------------+

   dim(S) + dim(U) = 6 + 6 = 12
   重叠部分 S ∩ U = D, dim = 3
   dim(S + U) = 12 - 3 = 9 = dim M   =>  S + U = M

   对比: 反对称 K (dim 3) 与 S 的交是 {0}, 6 + 3 = 9
         所以 M = S ⊕ K (直和), 交错和 = 没有重叠和

注意区分两种”和”：$S+U$ 是有重叠的和（重叠 3 维），必须减去重叠；而 $S\oplus K$（对称 + 反对称）是直和，交集只有零矩阵，维数直接相加 $6+3=9$。这个对比能让你明白维数公式里那个”$-\dim(S\cap U)$”什么时候等于 0。

概念三：秩 1 矩阵 $A=\mathbf{u}\mathbf{v}^{\mathsf T}$（rank one matrices）

• 定义与目的：秩 1 矩阵就是能写成一个列向量乘一个行向量的矩阵：$A=\mathbf{u}\mathbf{v}^{\mathsf T}$，其中 $\mathbf{u}\in\mathbb{R}^m,\ \mathbf{v}\in\mathbb{R}^n$。它是矩阵世界的”原子”——最简单、信息量最小（但非零）的矩阵。

• 几何直觉（它在空间中是什么样子？）：看它的行列结构： \(A=\mathbf{u}\mathbf{v}^{\mathsf T}=\begin{bmatrix}u_1\\u_2\\\vdots\\u_m\end{bmatrix}\begin{bmatrix}v_1&v_2&\cdots&v_n\end{bmatrix}=\begin{bmatrix}u_1v_1&u_1v_2&\cdots&u_1v_n\\ u_2v_1&u_2v_2&\cdots&u_2v_n\\ \vdots&&&\vdots\\ u_mv_1&u_mv_2&\cdots&u_mv_n\end{bmatrix}.\) 每一列都是 $\mathbf{u}$ 的倍数（第 $j$ 列 $=v_j\mathbf{u}$），每一行都是 $\mathbf{v}^{\mathsf T}$ 的倍数（第 $i$ 行 $=u_i\mathbf{v}^{\mathsf T}$）。所以：
  • C(A) 是一条直线（$\operatorname{span}\{\mathbf{u}\}$），维数 1；
  • C(Aᵀ) 是一条直线（$\operatorname{span}\{\mathbf{v}\}$），维数 1；
  • $A$ 把整个 $\mathbb{R}^n$ 压到 $\mathbf{u}$ 这条直线上，同时把”与 $\mathbf{v}$ 垂直的整个超平面”压成零。

  这正是”秩 1”的几何肖像：一个方向的输出，一个方向的盲区。

• 具体示例：$\mathbf{u}=(1,2,1)^{\mathsf T},\ \mathbf{v}=(1,-1,2)^{\mathsf T}$： \(A=\begin{bmatrix}1\\2\\1\end{bmatrix}\begin{bmatrix}1&-1&2\end{bmatrix}=\begin{bmatrix}1&-1&2\\2&-2&4\\1&-1&2\end{bmatrix}.\) 三列分别是 $(1,2,1)$ 的 $1,-1,2$ 倍；三行分别是 $(1,-1,2)$ 的 $1,2,1$ 倍。秩当然是 1。

• 重要提醒：秩 1 矩阵的集合不是子空间！ 两个秩 1 矩阵相加可能变成秩 2，例如 \(\begin{bmatrix}1&2&0\\2&4&0\\1&2&0\end{bmatrix}+\begin{bmatrix}0&0&1\\0&0&2\\0&0&3\end{bmatrix}=\begin{bmatrix}1&2&1\\2&4&2\\1&2&3\end{bmatrix}\) 左边两个都是秩 1，右边（消元可验）秩为 2。因此”秩 1”不是线性条件，秩 1 矩阵全体只是 $\mathbb{R}^{mn}$ 中的一个 5 维曲面（3×3 情形：$u$ 的 3 个参数 + $v$ 的 3 个参数，减去 $(c\mathbf{u})(\frac1c\mathbf{v})$ 的 1 个缩放冗余），不是子空间。

概念四：把图变成矩阵 —— 邻接矩阵与关联矩阵

• 定义与目的：一个图（graph）由节点集和边集组成。两种把它写成矩阵的标准做法：
  • 邻接矩阵（adjacency matrix） $A$：$n\times n$，$a_{ij}=1$（或权重 $w_{ij}$）若节点 $i,j$ 之间有边，否则 0。
  • 关联矩阵（incidence matrix） $B$：$n\times m$（节点 × 边），每一列对应一条边，在它的两个端点处放 $+1$ 和 $-1$，其余为 0。 目的：让图论问题变成线性代数问题——连通性、环、路径计数、电流电压，全部有子空间的解释。

• 几何直觉（它在空间中是什么样子？）：邻接矩阵把”谁挨着谁”编码进去，于是矩阵与向量的乘积有了图论意义：设 $\mathbf{x}$ 是节点上的数值（权重、温度、信号），则 \((A\mathbf{x})_i=\sum_{j\sim i}w_{ij}x_j=\text{（与节点 }i\text{ 相连的邻居数值之和，按边权加权）}.\) 也就是说，$A$ 是一个”扩散 / 求和算子“：它在图上把每个节点的值传播给邻居。图的度数（degree）就是 $A\mathbf{1}$ 的分量（取全 1 向量时，每个节点收到”有多少邻居”）。

• 具体示例：5 个节点的小图（详见下一小节的 ASCII 图），其邻接矩阵 $A$ 与 $A\mathbf{1}=(3,2,3,2,2)^{\mathsf T}$ 就是各节点的度数。

• “六度分隔”与 $A^k$：$(A^k){ij}$ = 从节点 $i$ 到节点 $j$ 恰好走 $k$ 步的路径条数。** 直观理由：$A^2=A\cdot A$，$(A^2){ij}=\sum_t a_{it}a_{tj}$ 就是在数”通过某个中间节点 $t$ 的两步走法”；归纳到 $k$ 步就是标准的”动态规划”。所以”六度分隔”（six degrees of separation）就是一个关于最小 $k$ 的陈述：大多数真实网络里，任两点之间都存在一条长度不超过 6 的路径，即 $A^k$ 在 $k$ 很小时就已经”处处非零”。本讲的 5 节点例子只有 **直径 2（6 条边、5 个节点），是个微型的”小世界”。

计算步骤与手算演示

示例一：$A=CR$ 分解（手算 + 逐格验证）

取 \(A_8=\begin{bmatrix}1&2&1&3\\2&4&3&7\\0&0&1&1\end{bmatrix}\qquad(m=3,\;n=4).\)

步骤 1：消元求 RREF。 $r_2\leftarrow r_2-2r_1$：

主元在第 1、3 列，$r=2$。

步骤 2：写出 $C$（主元列，取自原矩阵）。

步骤 3：写出 $R$（RREF 的非零行）。

步骤 4：验证 $CR=A_8$，逐格算。

$CR$ 的第 1 行（$C$ 的第 1 行 $(1,1)$ 乘 $R$）：

• $(1,1)\cdot(1,0)=1$ ✓（对应 $a_{11}=1$）
• $(1,1)\cdot(2,0)=2$ ✓
• $(1,1)\cdot(0,1)=1$ ✓
• $(1,1)\cdot(2,1)=3$ ✓

第 2 行（$C$ 第 2 行 $(2,3)$）：

• $(2,3)\cdot(1,0)=2$ ✓
• $(2,3)\cdot(2,0)=4$ ✓
• $(2,3)\cdot(0,1)=3$ ✓
• $(2,3)\cdot(2,1)=7$ ✓

第 3 行（$C$ 第 3 行 $(0,1)$）：

• $(0,1)\cdot(1,0)=0$ ✓
• $(0,1)\cdot(2,0)=0$ ✓
• $(0,1)\cdot(0,1)=1$ ✓
• $(0,1)\cdot(2,1)=1$ ✓

所以

步骤 5：拆成两个秩 1 矩阵（$A=\sum \mathbf{c}_i\mathbf{r}_i^{\mathsf T}$）。

• 第一项：第 1 主元列 × 第 1 个非零行 \(\mathbf{c}_1\mathbf{r}_1^{\mathsf T}=\begin{bmatrix}1\\2\\0\end{bmatrix}\begin{bmatrix}1&2&0&2\end{bmatrix}=\begin{bmatrix}1&2&0&2\\2&4&0&4\\0&0&0&0\end{bmatrix}\)
• 第二项：第 2 主元列 × 第 2 个非零行 \(\mathbf{c}_2\mathbf{r}_2^{\mathsf T}=\begin{bmatrix}1\\3\\1\end{bmatrix}\begin{bmatrix}0&0&1&1\end{bmatrix}=\begin{bmatrix}0&0&1&1\\0&0&3&3\\0&0&1&1\end{bmatrix}\)

逐格相加：

（顺带核对：$r=2$，恰好两项，不多不少。）

步骤 6：顺手取四个子空间。 $m=3,n=4,r=2$，故

• C(A₈) = span$\{(1,2,0)^{\mathsf T},(1,3,1)^{\mathsf T}\}$，$\dim 2$；
• C(A₈ᵀ) = span$\{(1,2,0,2),(0,0,1,1)\}$，$\dim 2$；
• N(A₈)：RREF 给出 $x_1+2x_2+2x_4=0$、$x_3+x_4=0$。自由变量 $x_2,x_4$：
  • $x_2=1,x_4=0\Rightarrow x_1=-2,x_3=0$：$(-2,1,0,0)^{\mathsf T}$
  • $x_2=0,x_4=1\Rightarrow x_1=-2,x_3=-1$：$(-2,0,-1,1)^{\mathsf T}$

  $\dim 2=n-r$ ✓

• N(A₈ᵀ)：解 $y_1+2y_2=0$、$y_1+3y_2+y_3=0$。取 $y_2=1\Rightarrow y_1=-2,y_3=-1$，基 $(2,-1,1)^{\mathsf T}$（乘 $-1$），$\dim 1=m-r$ ✓

正交验证：$(1,2,0,2)\cdot(-2,1,0,0)=-2+2+0+0=0$ ✓；$(1,2,0,2)\cdot(-2,0,-1,1)=-2+0+0+2=0$ ✓；$(0,0,1,1)\cdot(-2,1,0,0)=0$ ✓；$(0,0,1,1)\cdot(-2,0,-1,1)=0-1+1=0$ ✓；$(1,2,0)\cdot(2,-1,1)=2-2+0=0$ ✓；$(1,3,1)\cdot(2,-1,1)=2-3+1=0$ ✓

【计算机制解说】为什么 $R$ 恰好是”$A$ 的列的坐标说明书”？ 消元是对行做可逆操作，而可逆行操作不改变”列与列之间的线性关系”。于是 $\text{RREF}=EA$（$E$ 可逆）后，RREF 里每一列都是主元列（即标准基向量 $\mathbf{e}_1,\dots,\mathbf{e}_r$）的显式组合：RREF 第 $j$ 列的那 $r$ 个数字就是系数。因为这些系数在消元中被保持，原矩阵 $A$ 的第 $j$ 列也以同样的系数组合主元列： \(\text{col}_j(A)=\sum_{i=1}^{r}R_{ij}\,\mathbf{c}_i.\) 这正是 $A=CR$（比较两边第 $j$ 列：$C\cdot(R\text{第}j\text{列})$）。所以 $R$ 不是”另一个矩阵”，而是 $A$ 的列在 C(A) 里的坐标表；$C$ 则是 C(A) 的一组基。 二者合起来就是”$A$ 的秩 $r$ 骨架”。

顺带一提：这个论证也解释了为什么 $A=CR$ 是免费的——你已经为了求秩做了消元，$C$ 和 $R$ 就在手边，零额外成本。

示例二：矩阵空间 $S+U=M$ 的显式构造（用具体矩阵验证维数公式）

维数公式是抽象的，我们用真矩阵把它”摸”一遍。取

目标：把 $A_9$ 写成一个对称矩阵加一个上三角矩阵。

步骤 1：构造对称部分 $S$——把下三角的元素对称地”搬”到上三角。

$S$ 的对角取 0（后面交给 $U$），$S$ 的上三角直接抄 $A_9$ 的下三角：$s_{12}=4,\ s_{13}=7,\ s_{23}=8$。

步骤 2：令 $U=A_9-S$。

步骤 3：验证 $S+U=A_9$。

步骤 4：说明”为什么一定能做到”。 任取 $A$，按上面配方取 $S$（对角为零、上三角抄 $A$ 的下三角、再镜像），则 $U=A-S$ 的上三角之外必然为零（因为 $A$ 与 $S$ 在下三角完全相同）。所以 $\{S+U\}$ 覆盖了所有矩阵，即 $S+U=M$，$\dim(S+U)=9$。

步骤 5：核对维数公式。 $6+6-3=9$ ✓。

【计算机制解说】维数公式 $\dim(S+U)=\dim S+\dim U-\dim(S\cap U)$ 为什么成立？ 这是线性代数里的容斥原理，机制的直觉来自”数基向量”。

设 $S\cap U$ 的一组基为 $\mathbf{d}1,\dots,\mathbf{d}_k$（这里就是 3 个对角单点矩阵，$k=3$）。把它扩充成 $S$ 的基：$\mathbf{d}_1,\dots,\mathbf{d}_k,\mathbf{s}_1,\dots,\mathbf{s}{6-k}$；也扩充成 $U$ 的基：$\mathbf{d}1,\dots,\mathbf{d}_k,\mathbf{u}_1,\dots,\mathbf{u}{6-k}$。那么

张成 $S+U$（因为 $s+u$ 中”公共部分”已被 $\mathbf{d}$ 吸收），而且线性无关。线性无关的证明正是公式的核心：若 \(\sum a_i\mathbf{d}_i+\sum b_j\mathbf{s}_j+\sum c_\ell\mathbf{u}_\ell=\mathbf{0},\) 移项得 $\sum a_i\mathbf{d}i+\sum b_j\mathbf{s}_j=-\sum c\ell\mathbf{u}\ell$：左边属于 $S$，右边属于 $U$，所以这个公共向量属于 $S\cap U$，可以用 $\mathbf{d}$ 表示；但 $\mathbf{u}$ 与 $\mathbf{d}$ 一起是 $U$ 的基、线性无关，所以所有 $c\ell=0$；同理所有 $b_j=0$，于是所有 $a_i=0$。

于是总向量数 $=k+(6-k)+(6-k)=6+6-k=12-3=9$，恰好是公式。这个推导没有用到任何矩阵特殊性，它对任意两个子空间都成立——这就是为什么它是”容斥”。

顺便：当 $S\cap U=\{\mathbf{0}\}$（$k=0$）时公式退化为 $\dim(S+U)=\dim S+\dim U$，此时和是直和 $S\oplus U$，$S\oplus K=M$（$K$ 为反对称矩阵，$\dim K=3$，$6+3=9$）就是这样一例。

示例三：小世界图 —— 邻接矩阵、关联矩阵与四个子空间

看 5 个节点、6 条边的图：

                          (1)
                         / | \
                        /  |  \
                    e1 /  e6 \  e5
                      /    |    \
                    (2)   (3)   (5)
                      \    |    /
                    e2 \  e3|   / e4
                        \  |  /
                          (4)

   节点: 1,2,3,4,5          边: e1=1-2, e2=2-3, e3=3-4,
                                   e4=4-5, e5=5-1, e6=1-3

   结构: 一个 5 环 (1-2-3-4-5-1) 再加一条"捷径"弦 e6=1-3

节点 1 连到 2、3、5；节点 3 连到 2、4、1；注意边 e6 是那条”捷径”——它让原本环上距离 2 的节点 1 与 3 变成直接相连，这正是”小世界”的典型结构（局部稠密 + 少量长程捷径）。

步骤 1：写邻接矩阵 $A$（邻接矩阵是对称的，因为边没有方向）。

步骤 2：用 $A\mathbf{x}$ 求度数（$\mathbf{x}=\mathbf{1}$）。

• 节点 1：$0+1+1+0+1=3$（邻居 2,3,5）
• 节点 2：$1+0+1+0+0=2$（邻居 1,3）
• 节点 3：$1+1+0+1+0=3$（邻居 1,2,4）
• 节点 4：$0+0+1+0+1=2$（邻居 3,5）
• 节点 5：$1+0+0+1+0=2$（邻居 1,4）

所以 $A\mathbf{1}=(3,2,3,2,2)^{\mathsf T}$，度数之和 $3+2+3+2+2=12=2\times6=2E$ ✓（每条边被两个端点各数一次，这就是”握手引理”的矩阵版）。

步骤 3：用 $A^k$ 数路径。

• $(A^2)_{11}=3$：从节点 1 出发走 2 步回到自己的路径有 3 条（$1\to2\to1$、$1\to3\to1$、$1\to5\to1$）——正好等于节点 1 的度数。一般地，$\operatorname{diag}(A^2)=$ 度数向量 $(3,2,3,2,2)^{\mathsf T}$ ✓（注意看：$A^2$ 的对角线正是 $(3,2,3,2,2)$）。
• $(A^2)_{14}=2$：节点 1 到节点 4 走 2 步有 2 条路（$1\to3\to4$、$1\to5\to4$）。
• $(A^3)_{15}=5$：节点 1 到节点 5 走 3 步有 5 条路（$1\to2\to1\to5$、$1\to3\to1\to5$、$1\to3\to4\to5$、$1\to5\to1\to5$、$1\to5\to4\to5$）。

每条边的”最短”性质也能读出：$A$ 里 $a_{13}=1$（直接相连），所以 $\operatorname{dist}(1,3)=1$，而不是环上的 2。逐点算最短距离可得直径 = 2（任意两节点间最多 2 步）——5 个节点、6 条边就能做到这么”紧”，这就是小世界。

步骤 4：写关联矩阵 $B$（节点 × 边，每列一个 $+1$、一个 $-1$）。

步骤 5：读 $B$ 的四个子空间（这里是本讲的”高潮”）。

先算秩：前 5 行里，行 1+行 2+行 3+行 4+行 5 $=\mathbf{0}$（每列 $+1-1=0$），所以行线性相关，$r\le4$；实际 $r=4$。于是

• $\dim C(B)=4$（住在 $\mathbb{R}^5$），$\dim C(B^{\mathsf T})=4$（住在 $\mathbb{R}^6$）；
• $\dim N(B)=6-4=2$（住在 $\mathbb{R}^6$）——这就是”环”！维数 $=E-N+C=6-5+1=2$（本例连通，$C=1$，故也写作 $E-N+1$）。这两维对应两个独立的环，物理上叫回路数（number of independent loops），拓扑上叫第一贝蒂数。两组基：
  • 大环 $e_1+e_2+e_3+e_4+e_5=(1,1,1,1,1,0)$：沿 1-2-3-4-5-1 走一圈，每个节点进出各一次，所以 $B\cdot$该向量 $=\mathbf{0}$ ✓
  • 小环 $e_1+e_2-e_6=(1,1,0,0,0,-1)$：沿 1-2-3-1 走一圈（$e_6$ 反向），同样 $B\cdot$该向量 $=\mathbf{0}$ ✓
• $\dim N(B^{\mathsf T})=5-4=1$（住在 $\mathbb{R}^5$）——基为 $\mathbf{1}=(1,1,1,1,1)^{\mathsf T}$：所有节点电位相同 ⇒ 所有边上的电压差为零。这正是”图是连通的”（只有 1 个连通分量）在线性代数里的化身。

步骤 6：从关联矩阵得到拉普拉斯矩阵 $L=BB^{\mathsf T}$。

规律一目了然：对角元 = 该节点的度数，非对角元 $=-1$ 当两节点相邻。所以 $L=D-A$（$D$ 为度数对角阵）。逐格核对第一行：节点 1 的度数是 3（对角元 3），邻居是 2、3、5（这三个位置为 $-1$），非邻居 4 处为 0 ✓

• $L\mathbf{1}=\mathbf{0}$ ✓（每行之和为 0），即 $\mathbf{1}\in N(L)$，$\dim N(L)=1$ = 连通分量数。
• $\operatorname{tr}(L)=3+2+3+2+2=12=2E$ ✓
• $\operatorname{rank}(L)=4$，四个子空间的关系在这里第一次”显形”。

步骤 7：$B^{\mathsf T}\mathbf{x}$ 读”割”（cut），$B\mathbf{y}$ 读”差”。

取 $\mathbf{x}$ 为”节点 1、2 在左边，其余在右边”的指示向量 $\mathbf{x}=(1,1,0,0,0)^{\mathsf T}$，算 $B^{\mathsf T}\mathbf{x}$：

读法：$e_1=1\text{-}2$ 两端同侧 → 0；$e_2=2\text{-}3$ 跨过割 → $+1$；$e_3=3\text{-}4$ 同侧 → 0；$e_4=4\text{-}5$ 同侧 → 0；$e_5=5\text{-}1$ 跨过割 → $-1$；$e_6=1\text{-}3$ 跨过割 → $+1$。

$(B^{\mathsf T}\mathbf{x})_e\neq0$ 当且仅当边 $e$ 跨越这个”割”。 所以 $B^{\mathsf T}$ 把节点上的”分组”变成边上的”割标记”；$C(B^{\mathsf T})$ 就是割空间（cut space），维数 $r=4=n-1$，与环空间 $N(B)$（维数 2）正交互补，$4+2=6=E$ ✓。

【计算机制解说】为什么 $B$ 与 $B^{\mathsf T}$ 分别对应”节点求和”与”边的差”？ 把 $B$ 的乘法按”图上的动作”读出来，一切就通了。关键先看形状：$B$ 是 $5\times6$（节点 × 边），所以 $B$ 把”边上的数”送到”节点上的数”，$B^{\mathsf T}$ 反过来把”节点上的数”送到”边上的数”。

(1) $B^{\mathsf T}$：节点电位 → 边电压（求差）。 设 $\mathbf{x}\in\mathbb{R}^5$ 是节点上的数值（比如温度或电位）。$B^{\mathsf T}$ 是 $6\times5$，所以 $B^{\mathsf T}\mathbf{x}\in\mathbb{R}^6$ 是边上的数值，且对边 $e=(i,j)$ 有 \((B^{\mathsf T}\mathbf{x})_e=\pm(x_i-x_j)=\text{该边两端的数值之差}.\) 如果 $\mathbf{x}$ 是常数（所有节点同一电位），则每条边的差都是 0，所以 \(B^{\mathsf T}\mathbf{1}=\mathbf{0}\ \Longleftrightarrow\ \mathbf{1}\in N(B^{\mathsf T}).\) 这就是”给全图加同一个常数电位不改变任何电压差“——也正因如此，$\dim N(B^{\mathsf T})$ 数的是”常数电位的自由度”，等于连通分量个数 $C$。（对图丙的两个断开分量，可以各加各的常数，所以 $\dim N(B^{\mathsf T})=2$ ✓）

(2) $B$：边流量 → 节点净出流（求和）。 设 $\mathbf{y}\in\mathbb{R}^6$ 是边上的数值（比如电流）。$B$ 是 $5\times6$，所以 $B\mathbf{y}\in\mathbb{R}^5$ 是节点上的数值，且 \((B\mathbf{y})_i=\sum_{e\ \text{从}\ i\ \text{出发}}y_e-\sum_{e\ \text{进入}\ i}y_e=\text{节点 }i\text{ 的净流出量}.\) 基尔霍夫电流定律（Kirchhoff’s Current Law）说：每个节点净流入为零，即 \(B\mathbf{y}=\mathbf{0}\ \Longleftrightarrow\ \mathbf{y}\in N(B).\) 所以 $N(B)$ 就是”无源（divergence-free）的边流量配置“，即环空间。

环 = 无源电流：沿一个环每边放电流 $+1$，每个节点恰好”一进一出”，净出流为零，所以 $B\cdot(\text{环向量})=\mathbf{0}$——这正是上面 $(1,1,1,1,1,0)$ 与 $(1,1,0,0,0,-1)$ 两组的来历。反过来说，树没有环，任何边的非平凡组合都会在某个叶子节点留下净流出，无法满足 $B\mathbf{y}=\mathbf{0}$，所以图甲 $\dim N(B)=0$。

两个子空间的分工一览（这是整段最值得记住的对照）：

   关联矩阵 B :  N 行 = 节点       E 列 = 边

   B   : R^E -> R^N      输入 = 边上的流量/差值量
                         输出 = 每个节点的"净流出"(求和)
                         B y = 0  <=>  基尔霍夫电流定律

   B^T : R^N -> R^E      输入 = 节点上的电位
                         输出 = 每条边两端的"差"
                         B^T x = 0 <=> x 是常数(每个分量上)

   -------------------- 四个子空间 --------------------
   N(B)     = 环空间 (loop space)      dim = E - N + C   住 R^E
   C(B^T)   = 割空间 (cut space)       dim = N - C       住 R^E
   N(B^T)   = 常数电位空间             dim = C           住 R^N
   C(B)     = 节点净流可达集           dim = N - C       住 R^N

   R^E = C(B^T) (+) N(B)       (割 与 环 正交互补, E = (N-C) + (E-N+C))
   R^N = C(B)  (+) N(B^T)      (N = (N-C) + C)

整个电路理论（节点电位、边电压、电流、基尔霍夫定律、欧姆定律）就建立在这两个子空间的分解上；讲次 12 会把它展开成完整理论。

同一套机制也解释了示例一中的 $A=CR$：$R$ 记录列的组合系数（”说明书”），$B$ 记录节点与边的连接关系（”拓扑说明书”）——两者都是”用一种更小的矩阵描述一个大矩阵的结构”。

示例四：三个小图对照 —— 树、环、断开的图（把维数公式用满）

同样 4 个节点，改变边就得到完全不同的子空间维数。这是”关联矩阵 = 图的拓扑探测器”最直接的证据。

图甲：一棵树（4 节点、3 边：1-2, 2-3, 3-4）。

消元后 $r=3$，于是：$\dim C(B)=3$、$\dim C(B^{\mathsf T})=3$、$\dim N(B)=3-3=\mathbf{0}$、$\dim N(B^{\mathsf T})=4-3=1$。

• $N(B)=\{\mathbf{0}\}$ 说明”树没有环“——任何边的非平凡组合都会在某个节点留下净流入，无法成为无源电流。$\dim N(B)=E-N+C=3-4+1=0$ ✓
• $N(B^{\mathsf T})=\operatorname{span}\{\mathbf{1}\}$，连通分量数 1 ✓
• $L=B B^{\mathsf T}=\begin{bmatrix}1&-1&0&0\\-1&2&-1&0\\0&-1&2&-1\\0&0&-1&1\end{bmatrix}$（三对角，正是”路径图”的典型形状）

图乙：一个 4 环（4 节点、4 边：1-2, 2-3, 3-4, 4-1）。

$r=3$，于是：$\dim N(B)=4-3=\mathbf{1}$，基恰好是 $\mathbf{1}=(1,1,1,1)^{\mathsf T}$——沿整个环走一圈的电流。$\dim N(B^{\mathsf T})=1$。

• 对比图甲：只多了一条边，零空间就从 0 维跳到 1 维。”多一个环 = 多一维零空间”这句话在这里被彻底暴露。$\dim N(B)=E-N+C=4-4+1=1$ ✓
• $L=B_{\text{乙}}B_{\text{乙}}^{\mathsf T}=\begin{bmatrix}2&-1&0&-1\\-1&2&-1&0\\0&-1&2&-1\\-1&0&-1&2\end{bmatrix}$（循环图的拉普拉斯，每行和为 0）

图丙：两个断开的边（4 节点、2 边：1-2 与 3-4）。

$r=2$，于是：$\dim N(B)=2-2=\mathbf{0}$（两条边各自独立，不构成环——而且它们根本不共端点）；$\dim N(B^{\mathsf T})=4-2=\mathbf{2}$，基为 $(1,1,0,0)$ 与 $(0,0,1,1)$。

• 这里出现了一个关于本讲的关键修正：$\dim N(B^{\mathsf T})=2$ 正好等于连通分量的个数。前面的”$\mathbf{1}\in N(B^{\mathsf T})$”只是连通图（$C=1$）的特例；一般情形下 $N(B^{\mathsf T})$ 的维数是”能在哪些节点上加同一个常数电位而不影响任何电压差“的自由度，也就是分量数。
• 相应地，独立环数的正确公式是 \(\dim N(B)=E-\operatorname{rank}(B)=E-(N-C)=E-N+C,\) 其中 $C$ 是连通分量个数。只有连通图（$C=1$）才能用常见的 $E-N+1$。 本例 $C=2$：$2-4+2=0$ ✓（若错用 $E-N+1$ 会得到 $-1$，一个负数维数显然荒谬——这正是检验公式是否用对的好办法）。
• $L=B_{\text{丙}}B_{\text{丙}}^{\mathsf T}=\begin{bmatrix}1&-1&0&0\\-1&1&0&0\\0&0&1&-1\\0&0&-1&1\end{bmatrix}$：分块对角，两块各自对应一个连通分量——$L$ 的块结构直接把图的连通结构”读”了出来。$\dim N(L)=2=C$ ✓

对照表（同一张表把四个子空间与图性质绑在一起）：

   4 节点图          E   C   rank(B)=N-C   dim N(B)   dim N(B^T)   图的性质
                                                      = E-N+C    = C
   ------------------------------------------------------------------------
   甲: 树            3   1        3            0          1        无环, 连通
   乙: 4 环          4   1        3            1          1        恰有一个独立环, 连通
   丙: 两条断边      2   2        2            0          2        无环, 2 个连通分量
   ------------------------------------------------------------------------
   本讲示例三        6   1        4            2          1        2 个独立环, 连通
   (5 节点小世界)

   规律: rank(B) = N - C  (节点数 减去 连通分量数)
        "一个图最多只能有 N-1 个独立行"

【计算机制解说】为什么 $\operatorname{rank}(B)=N-C$？ $B$ 是 $N\times E$。对每一列（一条边），$+1$ 与 $-1$ 相加为 0，所以每列之和为 0——这给出一个行之间的线性关系：$\mathbf{1}^{\mathsf T}B=\mathbf{0}^{\mathsf T}$，即 $\mathbf{1}\in N(B^{\mathsf T})$，所以 $\operatorname{rank}(B)\le N-1$。

反过来证明”不可能更少”：沿着图的每条边”传播”电位。固定某个连通分量里的一个节点电位为 0，沿边逐跳地确定其余节点电位（因为每条边 $B^{\mathsf T}$ 的方程要求两端差为 0 才能让 $\mathbf{y}^{\mathsf T}B=\mathbf{0}$ 成立……更直接的做法是把分量缩成一棵树：树上 $N-1$ 条边对应的列线性无关，可以逐列消元得到 $N-1$ 个主元）。于是每个连通分量贡献 $\operatorname{rank}=N_c-1$，全部相加：

代到秩–零化度定理的两侧，就得到上面表格里的两行公式： \(\dim N(B)=E-(N-C)=E-N+C,\qquad \dim N(B^{\mathsf T})=N-(N-C)=C.\)

这条推导的价值：它把”图有几个环”“图是否连通”这两个纯粹组合的问题，变成了一个矩阵的秩问题——这正是 Strang 说”线性代数是应用数学的瑞士军刀”的具体含义。讲次 12 会把这条线拉得更远（基尔霍夫定律、最小生成树、网络流）。

矩阵分解的核心思想

本讲的核心分解仍是 $A=CR$，但它在本讲获得了新的解释与推广对象：

• 形式：$C$ = 主元列（$m\times r$），$R$ = RREF 非零行（$r\times n$）。
• 含义：$A$ 由 $r$ 个秩 1 积组成；每个积 $\mathbf{c}_i\mathbf{r}_i^{\mathsf T}$ 贡献”一个方向进、一个方向出”。$A=CR$ 是秩 $r$ 的最经济表达（$mr+rn$ 个数 vs $mn$）。
• 揭示的结构性质：C(A)=C(C)、C(Aᵀ)=C(R)；四个子空间完全由 $C,R$ 承载。$C$ 与 $R$ 是非正交骨架（列取自 $A$，行取自 RREF，一般不互相垂直）。
• 应用价值：压缩、低秩近似、SVD 的出发点。SVD 做的事就是”把 $A=CR$ 再正交化”：找正交的 $U$（替代 $C$）、正交的 $V^{\mathsf T}$（替代 $R$），并让系数 $\sigma_1\ge\sigma_2\ge\cdots\ge\sigma_r>0$ 按重要性排序： \(A=\sum_{i=1}^{r}\sigma_i\mathbf{u}_i\mathbf{v}_i^{\mathsf T}.\) 每一项 $\sigma_i\mathbf{u}_i\mathbf{v}_i^{\mathsf T}$ 仍是秩 1！这就是”任何矩阵 = 秩 1 矩阵之和”的最美版本，而 $\sigma_i$ 告诉你哪几项最重要（截断到前 $k$ 项就得到最佳低秩近似）。详见讲次 29。

本讲的另一条结构性线索是矩阵空间的维数公式（子空间容斥）：

它与 $A=CR$ 是同一哲学：“用更小的、结构化的部件拼出整个空间”。一个说”矩阵由 $r$ 个秩 1 块拼成”，一个说”矩阵空间由对称块与三角块拼成，重叠部分要扣掉”。

与其他讲次的关联

• 与 Lecture 10（四个基本子空间）：本讲把四子空间从 $\mathbb{R}^n/\mathbb{R}^m$ 推广到”矩阵空间”，并给出 $A=CR$ 作为四子空间的载具。示例三的关联矩阵 $B$ 是一个 5×6 的普通矩阵，四子空间理论完全适用。
• 与 Lecture 12（图与网络、关联矩阵）：本讲只是”初见”关联矩阵与拉普拉斯 $L=BB^{\mathsf T}$；Lecture 12 会把它发展成完整理论（环空间、割空间、基尔霍夫定律、欧姆定律）。
• 与 Lecture 5–6（$A=LU$）：消元同时产出 $LU$（行信息）与 $CR$（列信息）。$A=CR$ 与 $A=LU$ 是同一算法的两个面孔。
• 与 Lecture 21–25（特征值、马尔可夫、正定）：邻接矩阵 $A$ 的特征值（尤其是”-马尔可夫/随机游走矩阵”）是 PageRank 与谱图理论的核心；$L=BB^{\mathsf T}$ 自动是半正定的（因为对任意 $\mathbf{x}$，$\mathbf{x}^{\mathsf T}L\mathbf{x}=\vert B^{\mathsf T}\mathbf{x}\vert ^2\ge0$）——这直接把本讲接到讲次 27 的正定性。
• 与 Lecture 29（SVD）：$A=\sum\sigma_i\mathbf{u}_i\mathbf{v}_i^{\mathsf T}$ 是本讲”$r$ 个秩 1 之和”的正交化版本，四子空间的正交基也由 SVD 一次性给出。
• 与 Lecture 30–33（线性变换、伪逆）：矩阵空间视角让”线性变换的集合”也变成向量空间，为伪逆与最小范数解铺路。

关键要点

1. 矩阵是向量：所有 $m\times n$ 矩阵构成 $mn$ 维向量空间 $M$。$\dim M(3\times3)=9$，$\dim S(\text{对称})=6$，$\dim U(\text{上三角})=6$，$\dim D(\text{对角})=3$，且 $D=S\cap U$。维数 = 自由参数的个数 = 总位置数 − 独立约束数。

2. 子空间维数公式（容斥）： \(\dim(S+U)=\dim S+\dim U-\dim(S\cap U).\) 验证：$6+6-3=9=\dim M$，所以 $S+U=M$（任一矩阵 = 对称 + 上三角）。对比直和 $M=S\oplus K$（$6+3=9$，$S\cap K=\{\mathbf{0}\}$）。

3. 秩 1 矩阵：$A=\mathbf{u}\mathbf{v}^{\mathsf T}$，其列全是 $\mathbf{u}$ 的倍数、行全是 $\mathbf{v}^{\mathsf T}$ 的倍数，C(A) 与 C(Aᵀ) 各是一条直线。$A=\sum_{i=1}^{r}\mathbf{c}_i\mathbf{r}_i^{\mathsf T}$：秩 $r$ = $r$ 个秩 1 之和。注意秩 1 矩阵全体不是子空间（相加可能升秩）。

4. $A=CR$：$C$ 取原矩阵的主元列，$R$ 取 RREF 的非零行，则 $A=CR$ 严格成立，且 $R$ 就是”$A$ 的列在 C(A) 中的坐标表”。

5. 图的矩阵化：邻接矩阵 $A$，$(A\mathbf{x})i$ = 节点 $i$ 的邻居权重之和，$A\mathbf{1}$ = 度数向量，$(A^k){ij}$ = 长度 $k$ 的路径条数。关联矩阵 $B$（$N$ 节点 × $E$ 边，每列一个 $+1$ 一个 $-1$）：$B^{\mathsf T}\mathbf{x}$ 给出边上的差（故 $B^{\mathsf T}\mathbf{1}=\mathbf{0}$），$B\mathbf{y}$ 给出节点上的净流出（故 $B\mathbf{y}=\mathbf{0}$ 即基尔霍夫电流定律）。于是 $N(B)$ = 环空间，$\dim=E-N+C$；$C(B^{\mathsf T})$ = 割空间，$\dim=N-C$；$N(B^{\mathsf T})$ = 常数电位空间，$\dim=C$（连通分量数）；$BB^{\mathsf T}=L$ = 拉普拉斯矩阵（对角为度数，非对角相邻为 $-1$）。

常见误区与注意事项

1. 把”矩阵空间”与”行列式的值”混为一谈。$M$ 的维数是 $mn$ 而不是别的数：$3\times3$ 矩阵有 9 个自由数。虽然”可逆矩阵”这个集合很大，但可逆矩阵不构成子空间（$\det(A+B)$ 一般 $\neq\det A+\det B$，且零矩阵不可逆）。同理”秩恰好为 1 的矩阵”也不是子空间。

2. 以为 $S\cap U$ 是空集或维数 1。$S\cap U$ = 既对称又上三角 = 对角矩阵，维数 3（不是 0、也不是 1）。用”$S$ 有 3 个独立位置 + $U$ 有 3 个”去理解更可靠：对角阵同时满足两边的条件。

3. 在 $A=CR$ 里用 RREF 的列充当 $C$。$C$ 必须来自原矩阵 $A$。RREF 的列空间一般是不同的子空间（讲次 10 已强调）。$R$ 才来自 RREF。

4. 误以为 $A=\sum\sigma_i\mathbf{u}_i\mathbf{v}_i^{\mathsf T}$ 里每一项的 $\mathbf{u}_i,\mathbf{v}_i$ 必须来自 $A$ 本身。在 $A=CR$ 中 $\mathbf{c}_i$ 确实取自 $A$ 的列，但在 SVD 中 $\mathbf{u}_i,\mathbf{v}_i$ 是新的正交方向，一般都不是 $A$ 的原始列或行。这是 $CR$ 与 SVD 的关键差别：$CR$ 保”取材于 $A$”，SVD 保”互相正交”。

5. 把关联矩阵的 $+1/-1$ 方向当儿戏。每条边必须有且仅有一个 $+1$、一个 $-1$（方向可以任意定，但不能两个都是 $+1$）。只有这样”每列和为 0”才成立，从而 $\mathbf{1}\in N(B^{\mathsf T})$、$B\cdot(\text{环})=\mathbf{0}$ 才成立。若把方向搞错，环就不是零空间里的向量了。

6. **算 $(A^k){ij}$ 时忘了”恰好 $k$ 步”。$A^k$ 数的是恰好** $k$ 步的路径（也叫 walk，允许重复经过节点），不是”最多 $k$ 步”、更不是”最短路径”。要判断连通只需看 $\sum{k=1}^{n-1}A^k$ 里对应位置是否非零。

思考题（带答案）

Q1.（纯计算） 设 $M$ 为所有 $4\times4$ 实矩阵构成的空间。求下列子空间的维数： (a) 全部 4×4 矩阵 $M$；(b) 对称矩阵 $S$；(c) 上三角矩阵 $U$；(d) 对角矩阵 $D$；(e) $S\cap U$；(f) $S+U$，并判断 $S+U$ 是否等于 $M$。

Q2.（概念） 判断正误并说明理由。 (a) 若图 $G$ 有 $n=6$ 个节点、$m=8$ 条边且连通，则其关联矩阵 $B$ 的零空间维数为 3。 (b) 邻接矩阵的 $(A^3)_{ij}$ 给出节点 $i$ 到 $j$ 的最短路径长度。 (c) 一个 $5\times5$ 的三对角矩阵（只有主对角和上下次对角非零）构成的空间，维数为 15。

Q3.（综合） 取小世界图的入度/权重版：设 3 个节点的有向图，边 $1\to2$（权重 2）、$1\to3$（权重 3）、$2\to3$（权重 1）。写出它的邻接矩阵 $A$（$a_{ij}$ = 边 $i\to j$ 的权重），计算 $A\mathbf{1}$ 和 $A^{\mathsf T}\mathbf{1}$，并解释它们各自的含义。