为什么图的拉普拉斯矩阵的最小特征值一定是0？

@Zealing 提到了拉普拉斯矩阵$L_G$一定存在0特征值，因为$(1,1,\cdots,1)^T$就是0特征值对应的特征向量。

要证明最小特征值是0，我们还需要证明$L_G$是半正定的。

首先我们回顾一下拉普拉斯矩阵的定义。假设$\{e_i\}$是标准基，也就是$e_i$是第$i$个元素为1其他元素为0的向量。那么图$G$的拉普拉斯矩阵

$$L_G=\sum_{(i,j)\in E_G}w_{i,j}(e_i-e_j)(e_i-e_j)^T$$

$E_G$是图$G$中所有的边，$w_{i,j}$是边$(i,j)$的权重。

对于任意非零列向量$x$，

\begin{eqnarray*}x^TL_Gx&=&x^T\left(\sum_{(i,j)\in E_G}w_{i,j}(e_i-e_j)(e_i-e_j)^T\right)x\\&=&\sum_{(i,j)\in E_G}w_{i,j}x^T(e_i-e_j)(e_i-e_j)^Tx\\&=&\sum_{(i,j)\in E_G}w_{i,j}(x^T(e_i-e_j))^2\end{eqnarray*}

图里的边的权重是非负的，所以上面二次型就是非负的，所以$L_G$是半正定的。

因为拉普拉斯矩阵$L$每一行的和为0，全1向量$v_0=[1,1,...,1]^T$满足$Lv_0=0=0v_0$，所以最小特征值为0。

如果图中有k个子图（connected component），就有k个0特征值。因为至少有一个子图，所有至少有一个0特征值。

详细数学证明可以看这里。