Eigenvalues of normalized Laplacian Matrix 归一化拉普拉斯矩阵的特征值范围

拉普拉斯矩阵可是使用节点度矩阵减去邻接矩阵（权重矩阵）得到：

而比较常用的归一化拉普拉斯矩阵有如下形式：

其中的每一个元素可以通过下式计算：

根据 GCN 开篇论文 Semi-Supervised Classification with Graph Convolutional Networks 中提到的，归一化拉普拉斯矩阵的特征值范围为，下面给出证明。

可以通过瑞利熵来计算特征值的上下界，瑞利熵的定义如下：

如果分别是矩阵的一对特征值和特征向量，则有，所以对矩阵的特征值有：

所以只需要求出的最小值和最大值，就能得到矩阵特征值的范围。

接下来就可以进行推导了，对于任意向量有：

令，有：

根据详解拉普拉斯矩阵中的运算来展开分子，然后展开分母，有：

由于，所以有

其中代表在的情况下，如果节点和之间有边，则进行求和。

现在估计 (4) 式的取值范围，即可得知拉标准化普拉斯矩阵特征值的取值范围。首先求最小值，只需要对于任意的就可以使 (4) 式等于 0，只需令即可。故标准化拉普拉斯矩阵的最小特征值为 0。

只能给出最大值范围，而不能求出确切的值。由于，则可以对 (4) 式进行放缩：

即，取等号的条件为对于任意相邻的节点有，进而得到。这样的条件恰好等价于图是一个二分图。无向图是一个二分图的充要条件为至少有两个节点，且中所有的环长度为偶数。

所以标准化拉普拉斯矩阵的最小特征值小于等于 2。