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

  数学 线性代数 离散数学    浏览次数:14373        分享
1

我有一个关于拉普拉斯矩阵的疑惑。我们知道我们可以用拉普拉斯矩阵来表示一个图,那么为什么拉普拉斯矩阵的最小特征值一定是0呢?怎么证明呢?

 

剪叔   2019-05-08 23:17



   2个回答 
11

@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$是半正定的。

SofaSofa数据科学社区DS面试题库 DS面经

LiShanfei   2019-05-09 23:21

谢谢提醒还需要证明$L$半正定。 - Zealing   2019-05-10 00:58
4

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

如果图中有k个子图(connected component),就有k个0特征值。因为至少有一个子图,所有至少有一个0特征值。

详细数学证明可以看这里

SofaSofa数据科学社区DS面试题库 DS面经

Zealing   2019-05-09 00:14



  相关讨论

关于边的个数的图论问题

离散数学中偏序是什么意思?

python里如何判断一个集合是另一个集合的子集?

python求笛卡尔积

python中求两个集合的交集?

无环图和树有什么区别?

python中计算二项式系数?

轮流射击先中枪的概率题

半正定或者正定矩阵一定要是对称的吗?

对称的实数矩阵的所有特征值都是实数吗

  随便看看

抛的硬币直到连续出现两次正面为止,平均要扔多少次

怎么直观理解ROC AUC的概率统计意义?

如何获取pyspark DataFrame的行数和列数?

pandas.DataFrame的index重新排列(从0开始)

keras里sparse_categorical_crossentropy和categorical_crossentropy什么不同?