Question

命题“当一个图包含有向生成树时，其拉普拉斯矩阵秩为n-1且其特征值均具有非负实部”是否为真，求证明

Answer 1

该命题为真命题。
首先我们要知道：图的拉普拉斯矩阵L是半正定的：设图的顶点的邻接权重矩阵W，顶点的度矩阵为D。拉普拉斯矩阵为L=D-W。容易证明任意N阶矩阵X的转置XT、L、X满足如下关系：XT*L*X>=0。
接着，因为Laplacian矩阵为半正定矩阵，依据半正定矩阵的性质。则其中一个特征值为0，那么其他特征值均为正。

Answer 2

拉普拉斯矩阵零空间的维数为其最大连通子图的个数，含spanning tree的话最大连通子图就是原图本身，秩为n-1。由于拉普拉斯矩阵为主对角占优矩阵，利用盖尔圆盘定理可以得到所有特征值非负。

Answer 3

是真命题，具体可以参考任伟老师Distibuted Consensus in Multi-vehicle Cooperative Control 一书里第二章，里面有详细的证明