图拉普拉斯矩阵

图拉普拉斯矩阵（graph Laplacian matrix）把相邻顶点之间的数值差汇总成一个线性算子。它的对角元为顶点度，非对角元为邻接权重的负值；由此得到的二次型恰好是所有边上差值平方的加权和。常数向量不会产生差值，连通分量因此直接出现在矩阵的零空间中。

三顶点路径上的差值

路径 $1-2-3$ 的两条边权均为一。按顶点顺序写邻接矩阵 A、度矩阵 D 和拉普拉斯矩阵 L： $$A=\left(\begin{array}{ccc}0& 1& 0\\ 1& 0& 1\\ 0& 1& 0\end{array}\right),D=\mathrm{diag}(1,2,1),L=D-A=\left(\begin{array}{ccc}1& -1& 0\\ -1& 2& -1\\ 0& -1& 1\end{array}\right).$$ 给三点赋值 $x=(2,0,1{)}^{𝖳}$，可算出 $Lx=(2,-3,1{)}^{𝖳}$，所以 $x^{𝖳}Lx=5$。沿边计算同样得到 $(2-0{)}^2+(0-1{)}^2=5$。矩阵表达与边差表达描述的是同一件事。

边只计算一次。顶点值可以为零或负数，能量仍非负。

定义与能量恒等式

设图有限、无向、无自环，边权 $w_{ij}=w_{ji}\ge 0$；没有的边权为零，零权边不计入连通性。令 $d_i=\sum _j{w}_{ij}$，$A=(w_{ij})$、$D=\mathrm{diag}(d_i)$，定义 $L=D-A$。于是 $$(Lx{)}_i=\sum _j{w}_{ij}(x_i-x_j).$$ 它衡量 i 的值相对于邻点的偏差。若边是导电支路，x 为电势且 w 为电导，这一分量就是流出 i 的净电流。

展开二次型，并把有序对 i、j 合并为无向边，得到完整恒等式 $$x^{𝖳}Lx=\sum _i{d}_i{x}_i^2-\sum _{i,j}{w}_{ij}{x}_i{x}_j=\sum _{\{i,j\}\in E}{w}_{ij}(x_i-x_j{)}^2.$$ 每个 $x_i^2$ 在与 i 相接的边中累计系数 $d_i$，每条边的交叉项为 $-2w_{ij}{x}_i{x}_j$，恰与矩阵展开一致。因此 L 实对称、半正定，全部特征值实且非负。这一结论使用了非负权重。

也可给边任意指定一个用于记账的方向，构造关联矩阵 B：每条边的一列在一个端点记一、另一端点记负一，其他位置为零。若 W 为边权对角矩阵，则 $$L=BW{B}^{𝖳}.$$ 逐边的一列贡献 $w_{ij}(e_i-e_j)(e_i-e_j{)}^{𝖳}$，与定义的四个矩阵元一致。把记账方向反过来只使该列变号，乘积不变；这没有把原来的无向图改成有向图。

零空间准确数出连通分量

由于每行元素和为零，$L\mathrm{𝟏}=0$。更强地，$Lx=0$ 当且仅当 x 在每个正权连通分量上为常数。必要性来自 $0=x^{𝖳}Lx$：右侧是非负项之和，故每条正权边两端值相同，沿路径传递即在分量内相同。充分性可直接代回 $(Lx{)}_i$，每项差值皆为零。

若有 c 个连通分量，各分量的指示向量相互独立，并且张成全部上述向量，所以 $\dim \ker L=c$、$\mathrm{rank}L=n-c$。孤立顶点单独算一个分量，其对应整行整列都是零。对无顶点图可以用空矩阵约定，但不再谈第一个或第二个特征值。

主例中三个彼此正交的向量 $$(1,1,1{)}^{𝖳},(1,0,-1{)}^{𝖳},(1,-2,1{)}^{𝖳}$$ 分别乘 L 后变为自身的零、一、三倍，所以全部特征值为 $0,1,3$。零特征值只有一个，与路径连通一致。

权重变式与不同矩阵的区别

把主例每条边权同时乘二，D、A、L 都乘二，特征向量不变，特征值变为 $0,2,6$。原赋值的能量从五变为十。若另加第四个孤立顶点，则矩阵增加一行一列零，零特征值再增加一个。度数和连通分量的作用可以分别观察。

L 本身通常不可逆：即使图连通，常数向量也在零空间。方程 $Lx=b$ 的右侧必须在每个连通分量上求和为零；满足这一条件时，解仍可在每个分量上加任意常数。这由对称矩阵的像空间等于核的正交补得到。固定某个电势或施加零均值条件，才能消除相应自由度。

若允许一条负权边，例如两点间权为负一，则 $L=\left(\begin{array}{cc}-1& 1\\ 1& -1\end{array}\right)$，向量 $(1,-1)$ 的能量为负四，半正定结论失效。有向图的出度减邻接矩阵一般不对称，也不能沿用这里的实对称谱证明。归一化拉普拉斯矩阵会另外按度调整尺度；代数连通度通常则指本篇未归一化矩阵的第二小特征值，二者数值不可混用。