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

  数学 线性代数 离散数学    浏览次数:1345        分享
0

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

 

剪叔   2019-05-08 23:17



   2个回答 
8

@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求笛卡尔积   3回答

python中求两个集合的交集?   1回答

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

python中计算二项式系数?   2回答

轮流射击先中枪的概率题   2回答

矩阵的列空间什么意思?   1回答

矩阵A乘以B的秩等于B乘以A的秩吗   1回答

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

线性空间和向量空间是一回事吗?   2回答

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

两个方程组解之间的关系   1回答

为什么矩阵的二范数和向量的二范数的定义不同?   2回答



回答问题时需要注意什么?

我们谢绝在回答前讲“生动”的故事。

我们谢绝“这么简单,你自己想”、“书上有的,你认真看”这类的回答;如果你认为对方的提问方式或者内容不妥,你可以直接忽略该问题,不用进行任何作答,甚至可以对该问题投反对票。

我们谢绝答非所问。

我们谢绝自己不会、硬要回答。

我们感激每一个用户在编写答案时的努力与付出!