拉普拉斯矩阵

定义

有向加权图（Weighted Digraph）的拉普拉斯矩阵的通用定义是：

$L = D_{out} - A$

$A$ (Adjacency matrix，邻接矩阵)：代表图的“骨架”和“权重”。节点 $i$ 指向节点 $j$ 有边，且权重是 $a_{ij}$，那么矩阵的第 $i$ 行第 $j$ 列就是 $a_{ij}$。
$D_{out}$ (Out-degree matrix，出度矩阵)：代表每个节点“向外输出”的总能量或总权重。它是一个对角矩阵（只有主对角线上有数字），对角线上的值是该节点所有出边权重之和。
$L$ (拉普拉斯矩阵)：两者相减。

对于加权有向图：

非对角线元素 ($i \neq j$): $\ell_{ij} = -a_{ij}$。即节点 $i$ 指向节点 $j$ 的边权重的相反数。如果节点间没有该方向的连边，则为 0。
对角线元素 ($i = j$): $\ell_{ii} = \sum_{h=1, h \neq i}^n a_{ih}$。这是节点 $i$ 的出度（注意求和条件 $h \neq i$ 明确排除了自环）。它等于该节点所有指向其他节点的边权重之和。

对于无权无向图特例：

对角线: 变为节点 $i$ 的度数 $d(i)$（即连接的边数）。
非对角线: 相连的两个节点之间为 $-1$，不相连则为 $0$。

因为对角线元素是该行所有非对角线元素的绝对值之和（且非对角线元素带负号），所以拉普拉斯矩阵有一个极其重要的性质：它的每一行元素加起来必然等于 0！ 也就是 $L \mathbf{1} = \mathbf{0}$。这是后续做系统稳定性分析的重要前提。

举个例子：

对于这个图，其邻接矩阵A为：

$A = \begin{bmatrix} 0 & 3.7 & 2.6 & 0 & 0 \\ 8.9 & 0 & 0 & 1.2 & 0 \\ 0 & 0 & 0 & 1.9 & 2.3 \\ 0 & 0 & 0 & 0 & 0 \\ 4.4 & 0 & 0 & 2.7 & 4.4 \end{bmatrix}$

出度矩阵为：

$D_{out} = \begin{bmatrix} 6.3 & 0 & 0 & 0 & 0 \\ 0 & 10.1 & 0 & 0 & 0 \\ 0 & 0 & 4.2 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 11.5 \end{bmatrix}$

其拉普拉斯矩阵为：

$L = D_{out} - A= \begin{bmatrix} 6.3 & -3.7 & -2.6 & 0 & 0 \\ -8.9 & 10.1 & 0 & -1.2 & 0 \\ 0 & 0 & 4.2 & -1.9 & -2.3 \\ 0 & 0 & 0 & 0 & 0 \\ -4.4 & 0 & 0 & -2.7 & 7.1 \end{bmatrix}$

另一个例子：考虑一个一个具有 $n$ 个节点的完全无向图 ( undirected graph) 。完全图意味着任意两个节点之间都有边直接相连。

邻接矩阵 $A_{K_n}$: 除了对角线自身到自身为0，其余所有元素全为1。这可以用数学表达为 $\mathbf{1}_n\mathbf{1}_n^\top - I_n$ （全1矩阵减去单位矩阵）。

度矩阵 $D$: 因为每个节点都连接另外 $n-1$ 个节点，所以每个节点的度都是 $n-1$。度矩阵为 $(n-1)I_n$。

$L_{K_n} = D - A = (n-1)I_n - (\mathbf{1}_n\mathbf{1}_n^\top - I_n) = nI_n - \mathbf{1}_n\mathbf{1}_n^\top=n\Pi_n$

其中 $\Pi_n$ 是投影矩阵

$\Pi_n x = \left( I_n - \frac{1}{n}\mathbf{1}_n\mathbf{1}_n^\top \right) x = x - \frac{1}{n}\mathbf{1}_n (\mathbf{1}_n^\top x)$

这里 $\mathbf{1}_n^\top x = x_1 + x_2 + \dots + x_n$，也就是所有状态的总和。那么 $\frac{1}{n}(\mathbf{1}_n^\top x)$ 就是这些状态的平均值（记为 $\bar{x}$）。所以：

$\Pi_n x = x - \bar{x}\mathbf{1}_n = \begin{bmatrix} x_1 - \bar{x} \\ x_2 - \bar{x} \\ \vdots \\ x_n - \bar{x} \end{bmatrix}$

拉普拉斯矩阵的关键性质

(i) 符号特征 (Sign pattern): $L$ 矩阵的对角线元素永远是非负的（$\ge 0$），非对角线元素永远是非正的（$\le 0$）。在动力学方程 $\dot{x} = -Lx$ 中，这恰好反映了“正向的自我反馈”与“负向的邻居误差耦合”。
(ii) 与自环无关: 拉普拉斯矩阵完全不包含图中自环（Self-loops）的信息。这是因为即使节点存在自环，它在 $D_{out}$ 中增加的值，刚好会被 $-A$ 在对角线上减去，两者抵消（或者从定义上看，计算对角线出度时直接排除了自身）。
(iii) 矩阵对称与无向图: $L$ 是对称矩阵 当且仅当 原图是无向图（即邻接矩阵对称）。在无向图中，信息的交互是双向对等的，此时入度等于出度（$D_{in} = D_{out} = D$）。
(iv) 对角线元素为0的物理意义: 在有向图中，某个节点的对角线元素 $\ell_{ii} = 0$ 当且仅当 该节点出度为0。这意味着该节点在网络中是一个纯粹的“接收者”或“汇聚点”（Sink），它只听取邻居的状态，但不向外广播自己的状态。
(v) 不可约性与强连通: 拉普拉斯矩阵是不可约的 (irreducible) 当且仅当 对应的有向图是强连通的 (strongly connected)

常用等价(Useful equalities)（讲课跳过）

局部误差与加权平均

当我们把拉普拉斯矩阵 $L$ 乘以一个系统的状态向量 $x$ 时，其第$i$个元素的值是：

$(Lx)_i = \sum_{j \in \mathcal{N}_{out}(i)} a_{ij}(x_i - x_j)$

物理意义： 向量 $Lx$ 的第 $i$ 个元素，等于节点 $i$ 的自身状态 $x_i$ 与其所有邻居状态 $x_j$ 之间差值的加权和。

推导如下：

$(Lx)_i = \sum_{j=1}^{n} \ell_{ij} x_j = \ell_{ii} x_i + \sum_{\substack{j=1 \\ j \ne i}}^{n} \ell_{ij} x_j$ $= \left( \sum_{\substack{j=1 \\ j \ne i}}^{n} a_{ij} \right) x_i + \sum_{\substack{j=1 \\ j \ne i}}^{n} (-a_{ij}) x_j= \sum_{\substack{j=1 \\ j \ne i}}^{n} a_{ij} (x_i - x_j) = \sum_{j \in \mathcal{N}_{out}(i)} a_{ij} (x_i - x_j)$

举个例子，假设我们有 3 个节点，状态向量 $x = [x_1, x_2, x_3]^\top$ 代表它们的温度，初始值为 $x = [10, 5, 8]^\top$。

节点 1 指向节点 2，权重 $a_{12} = 2$；节点 1 指向节点 3，权重 $a_{13} = 3$，节点 2 和 3 没有出边。其A和D为：

$A = \begin{bmatrix} 0 & 2 & 3 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}, \quad D_{out} = \begin{bmatrix} (2+3) & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix} = \begin{bmatrix} 5 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}$

拉普拉斯矩阵为：

$L = \begin{bmatrix} 5 & -2 & -3 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}$

现在，我们用矩阵 $L$ 乘以状态向量 $x$，来计算第一行（即节点 1 的结果）：

$(Lx)_1 = \begin{bmatrix} 5 & -2 & -3 \end{bmatrix} \begin{bmatrix} 10 \\ 5 \\ 8 \end{bmatrix}$ $(Lx)_1 = 5 \times 10 + (-2) \times 5 + (-3) \times 8 = 50 - 10 - 24 = \mathbf{16}$

也等于

$(Lx)_1 = a_{12}(x_1 - x_2) + a_{13}(x_1 - x_3)=16$

也就是说，$Lx$ 的第 $i$ 行，本质上就是节点 $i$ 当前的状态值，比它的邻居们高出了多少（以权重衡量）。

在一致性控制（Consensus Control）中，动力学方程通常写为 $\dot{x} = -Lx$。这就意味着节点 $i$ 状态的变化率只取决于它和邻居的“分歧”。如果它比邻居大（$x_i > x_j$），$(Lx)_i$ 为正，$\dot{x}_i$ 为负，它就会减小自己去迎合邻居。

若图 $\mathcal{G}$ 没有自环 (no self-loops)，并且节点 $i$ 的出度 $d_{out}(i) > 0$。对于节点 $i$ 的所有出边邻居 $j$，我们将每一条边的权重“归一化”，变成新的系数 $\alpha_{ij} = \frac{a_{ij}}{d_{out}(i)}$，这些系数是定义加权平均的凸组合系数 (convex combination coefficients)，且：

对于有权图：$(Lx)_i = d_{out}(i) \Big( x_i - \text{weighted-average}(\{x_j\}) \Big)$
对于无权图：$ (Lx)_i= \underbrace{d_{out}(i)}_{\text{for unit weights}} \Big( x_i - \textbf{average}(\{x_j, \text{for all out-neighbors } j\}) \Big) $

也就是说，在无权图中，$(Lx)_i$就是把“节点自身的当前状态”，减去“所有邻居状态的简单算术平均值”，最后再乘以“邻居的总个数”。

拉普拉斯势能函数

现在假设这个图是无向的，因为无向图的A对称（即 $a_{ij} = a_{ji}$），因此拉普拉斯矩阵也是对称的$L = L^\top$ 。

计算目标二次型 $x^\top Lx$：

$x^\top Lx = \sum_{i=1}^n x_i(Lx)_i = \sum_{i=1}^n x_i \left( \sum_{j=1, j \neq i}^n a_{ij}(x_i - x_j) \right)$ $= \sum_{i,j=1}^n a_{ij}x_i(x_i - x_j)$ $= \left(\frac{1}{2} + \frac{1}{2}\right) \sum_{i,j=1}^n a_{ij}x_i^2 - \sum_{i,j=1}^n a_{ij}x_ix_j$ $= \frac{1}{2} \sum_{i,j=1}^n a_{ij}x_i^2 + \frac{1}{2} \sum_{i,j=1}^n a_{ij}x_j^2 - \sum_{i,j=1}^n a_{ij}x_ix_j$

因为图是无向的 ($a_{ij} = a_{ji}$)，所以在双重求和中，对 $a_{ij}x_i^2$ 求和与对 $a_{ij}x_j^2$ 求和的结果是完全相等的。因此，将上一步拆出来的其中一半替换为了 $x_j^2$。

$x^\top Lx= \frac{1}{2} \sum_{i,j=1}^n a_{ij}(x_i - x_j)^2= \sum_{\{i,j\} \in E} \frac{1}{2} a_{ij}(x_i - x_j)^2$

函数 $x \mapsto x^\top Lx$ 有时被称为拉普拉斯势能函数。

拉普拉斯矩阵的性质

L 的行和为零

拉普拉斯矩阵的行和为零 (Zero row-sums)

$L\mathbf{1}_n = \mathbf{0}_n$

证明：

对于矩阵的任意第 $i$ 行，求和就是把对角线元素 $\ell_{ii}$ 和所有非对角线元素 $\ell_{ij}$ 加起来。

根据之前的定义，对角线元素等于出度：$\ell_{ii} = \sum_{j \neq i} a_{ij}$。

非对角线元素等于权重的相反数：$\ell_{ij} = -a_{ij}$。这两部分一加，正负抵消，结果必然是 0。

之前我们是先有图 $\mathcal{G}$，再根据图构造出矩阵 $L$。现在，抛开图像，纯粹从代数矩阵的角度来反向定义它：只要一个 $n \times n$ 的矩阵 $L$ 满足以下三个条件，它就被称为拉普拉斯矩阵

(i) 每一行的和为 0。
(ii) 非对角线元素是非正的 ( $\le 0$ )。
(iii) 对角线元素是非负的 ( $\ge 0$ )。

如果我们手里只有这样一个满足上述条件的代数矩阵 $L$，我们可以自然而然地“还原”出一张加权有向图 $\mathcal{G}$：只要发现某个位置 $\ell_{ij} < 0$，我们就认为节点 $i$ 到节点 $j$ 存在一条有向边，且权重就是 $-\ell_{ij}$。

当且仅当 G 是权重平衡时，L 的列和为零

当且仅当图 $\mathcal{G}$ 是权重平衡的，拉普拉斯矩阵 $L$ 有零列和。

因此下面两个表述等价：

(i) 图 $\mathcal{G}$ 是权重平衡的： 这意味着对于网络中的每一个节点，它的出度之和等于入度之和，即 $D_{out} = D_{in}$。
(ii) $\mathbf{1}_n^\top L = \mathbf{0}_n^\top$： 左乘一个全 1 的行向量，就相当于对矩阵 $L$ 进行按列求和。结果为全 0 的行向量，说明每一列的和都是 0。

证明：

计算第 $j$ 列的和，将第 $j$ 列的所有元素加起来：

$\sum_{i=1}^n \ell_{ij} = \ell_{jj} + \sum_{i=1, i \neq j}^n \ell_{ij}$

对角线元素 $\ell_{jj}$： 根据定义，它等于节点 $j$ 的出度（如果不算自环的话）。严谨一点写，如果考虑可能存在的自环 $a_{jj}$，那么 $\ell_{jj} = d_{out}(j) - a_{jj}$。
非对角线元素的列和 $\sum_{i \neq j} \ell_{ij}$： 矩阵的第 $j$ 列，代表的是所有从节点 $j$ 接收信息的节点 $i$。所以这些元素的和，其实是节点 $j$ 的入边权重之和的相反数。同样考虑到自环，这个和等于 $-(d_{in}(j) - a_{jj})$。

将上面两部分加起来：

$\sum_{i=1}^n \ell_{ij} = (d_{out}(j) - a_{jj}) + (-(d_{in}(j) - a_{jj}))= d_{out}(j) - d_{in}(j)$

也就是说，每一列的和 $(\mathbf{1}_n^\top L)_j$ 都等于节点 $j$ 的“出度减去入度”。因此，要想让所有的列和都为 0（即 $\mathbf{1}_n^\top L = \mathbf{0}_n^\top$），就必须让所有的 $d_{out}(j) - d_{in}(j) = 0$。这就等价于所有的节点都满足出度等于入度，也就是 $D_{out} = D_{in}$（图是权重平衡的）。

L 的谱

研究L的谱，就是研究拉普拉斯矩阵的特征值分布。

特征值的位置

除了特征值 0 之外，拉普拉斯矩阵 $L$ 的所有其他特征值，其实部都严格大于 0。

证明：盖尔果林圆盘定理 (Gersgorin Disks Theorem)—— 任何矩阵的特征值，都必定落在复平面上的一组“圆盘”之内。

圆盘的构造：

圆心： 矩阵的对角线元素 $\ell_{ii}$。对于拉普拉斯矩阵，$\ell_{ii}$ 就是节点 $i$ 的出度（一个非负实数），所以圆心都在实轴的右侧。
半径： 该行所有非对角线元素的绝对值之和 $\sum_{j \neq i} |\ell_{ij}|$。

因为拉普拉斯矩阵满足“行和为0”（且非对角线非正，对角线非负），所以：

$\sum_{j \neq i} |\ell_{ij}| = \sum_{j \neq i} |-a_{ij}| = \sum_{j \neq i} a_{ij} = \ell_{ii}$

这就意味着：每个盖尔果林圆盘的“半径”，恰好等于它的“圆心”到原点的距离！如下图所示

由于所有的特征值都必须被包在这几个圆盘里，所以它们要么就在原点上（特征值 0），要么就在原点的右侧（实部严格大于 0）。特征值绝对不可能跑到左半平面去。

特征值 0 的重数

我们已经知道 0 是一个特征值了。现在的关键问题是：特征值 0 出现了几次（代数重数）？它有多少个对应的独立特征向量（几何重数）？

设 L 为具有 n 个节点的加权有向图 G 的拉普拉斯矩阵。设 $n_s ≥ 1$ 表示 G 的凝聚有向图中的汇点数量。则：

特征值 0 是半单的 (semisimple)，且重数为 $n_s$。
下列陈述等价：
- (a) 图 $\mathcal{G}$ 包含一个全局可达节点 (globally reachable node)
- (b) 特征值 0 是单根：这是频谱层面的代数条件。
- (c) 矩阵的秩 $\text{rank}(L) = n - 1$。

对称拉普拉斯矩阵与代数连通性

假设邻接矩阵 $A$ 是对称的 ($A = A^\top$)（无向图）。在无向图中，如果节点 $i$ 能影响节点 $j$，那么节点 $j$ 也必定以同样的权重影响节点 $i$。

注：汇点 = 连通分量： 在无向图中，信息是双向流动的，不存在只能进不能出的“汇点”。此时，有向图中的“汇点数量”就退化为了无向图中的“连通分量 (connected components) 数量”。一个连通分量就是一个彼此相连的节点孤岛。

因为矩阵是对称的，线性代数告诉我们，对称矩阵的特征值必定都是实数。既然是实数，我们就可以把它们从小到大排个序。根据之前的引理，我们知道：

至少有一个特征值是 0。
所有的特征值都大于等于 0 (非负)。

所以，我们可以将拉普拉斯矩阵的特征值排列为：

$0 = \lambda_1 \le \lambda_2 \le \dots \le \lambda_n$

拉普拉斯矩阵的第二小特征值 $\lambda_2$ 被赋予了一个专有名词：代数连通度 (algebraic connectivity)。为了纪念提出这个概念的数学家 Miroslav Fiedler，$\lambda_2$ 也经常被称为 Fiedler 特征值，它对应的特征向量被称为 Fiedler 特征向量。

对于一个具有对称拉普拉斯矩阵的无权无向图 $\mathcal{G}$：

(i) 图 $\mathcal{G}$ 是连通的，当且仅当 $\lambda_2 > 0$。 解释：如果 $\lambda_2 = 0$，意味着系统至少有两个 0 特征值（即 $\lambda_1=0, \lambda_2=0$）。根据下一条推论，这意味着图断裂成了至少两块。只有当 $\lambda_2$ 严格大于 0 时，才能保证只有一个 0 特征值，从而保证整个图是铁板一块的连通状态。
(ii) 0 作为特征值的重数，等于图 $\mathcal{G}$ 中连通分量的个数。 解释：如果图被切成了 $k$ 个互不相连的子网络，那么拉普拉斯矩阵就会有 $k$ 个等于 0 的特征值。每个 0 特征值代表着一个子网络内部可以达成自己的一致状态。