解释：可以看到，上面的图是无向图，所以其对应的邻接矩阵是对称矩阵，表示如果顶点1和顶点3有边，那么3到顶点1也有边，但是注意对于有向图就未必，因为可能顶点1指向顶点3，顶点3却没有指向顶点1，这个时候顶点3到顶点1是没有边的。

解释：度矩阵应该很好理解，即一共有多少条边与该顶点有关，然后把这个数写在方阵的对角线上。

可以看到，拉普拉斯矩阵还是对称矩阵。

上面是连通图的例子，我们举一个非连通图的例子。请注意：下面这个图有两个连通分量(或者叫做连通子图），这个概念后面会用到。 邻接矩阵为： 度矩阵为： 由此可得拉普拉斯矩阵为： 注：我画方框是因为每一个方框都是 一个连通图，都为方阵， 方阵之外的其他地方的值必全为0.

上面提到了拉普拉斯矩阵，下面说一说他的性质。 5个性质：

性质1. 性质2. 上面两个性质是一起的。

性质1大家看看拉普拉斯矩阵的定义， D − W D-W D−W，而度矩阵 D D D的对角线的值就是邻接矩阵 W W W的行和。由于 D D D除了对角线之外其余为0，一减 W W W，除对角线之外全是负的，也就是说：如果去除对角线的值，拉普拉斯矩阵的行和就是 W W W的行和的相反数，然后加上等于 W W W行和的对角线，所以行和全部是0了。

######

性质2，熟悉线性代数的人都知道，对一个方阵求行和，其实相当于乘以一个 n n n维的，每一个维度都为1的向量，一般我们用 e ⃗ \vec e e 表示。

所以 L ∗ e ⃗ = 0 ⃗ L*\vec e=\vec 0 L∗e =0 （等于0是因为性质1），其中 0 ⃗ \vec 0 0 向量也是 n n n维向量，每一个维度都为0，对应于性质1：L的每个行和为0，共有 n n n行。

我们将上述等式改写成 L ∗ e ⃗ = 0 ∗ e ⃗ L*\vec e=0*\vec e L∗e =0∗e ，这是特征值和特征向量的定义，这个等式告诉我们：L有一个特征值为0，且这个特征值对应的特征向量中有一个是 e ⃗ \vec e e 。

性质3. 性质4. 性质3，4是一起的，我们需要先证明性质4 第一行变换到第二行其实就是将第一行复制了一遍。 其他的应该好理解了，比如第2行到第3行，我们利用了度 d d d和邻接矩阵 w i j w_{ij} wij​的关系。

既然已经证明了L是半正定的矩阵，那么当然就可以推出性质3，有n个非负的特征值。

性质5.

我们把这个证明从易到难来进行。先来个线性代数的预备知识，方阵可逆的情况下，特征值 λ 1 \lambda_1 λ1​的重数等于 λ 1 \lambda_1 λ1​对应的特征向量中线性无关的最大个数；方阵不可逆的情况下，特征值 λ 1 \lambda_1 λ1​的重数大于等于 λ 1 \lambda_1 λ1​对应的特征向量中线性无关的最大个数。

情况1

这个我们要证明的是，0特征值对应的特征向量每个分量相同，也即该特征向量是 k e ⃗ k\vec e ke 。 我们前面有： 也即证明了每一个分量需要相等，证明完毕。

不过，上述可能会有一点难懂， w i j w_{ij} wij​非负，为什么可以证明后面的为0呢？难道没有可能后面的某一项不为0，恰好此时 w i j w_{ij} wij​为0，从而继续保持整体为0？

那我们就假设有一项 f i − f j ! = 0 f_i-f_j!=0 fi​−fj​!=0，那么会发生什么情况呢？ f f f的其他分量会因为这个不相等从而至少分成两个阵营，比如 f m f_m fm​只有两种情况：

我们讨论第一种情况就够了，即假设分成了两个阵营，假设四个顶点的无向图， f 1 , f 2 f_1,f_2 f1​,f2​一组， f 3 , f 4 f_3,f_4 f3​,f4​一组，由于两个阵营不相等，那么强迫 w i j = 0 w_{ij}=0 wij​=0，从而会发生节点1，2不会有边连接到节点3,4。这就不是只有一个连通图了啊，而是至少两个。

情况2 这个证明是容易的。 即： 注意到，上面的每一个L都对应一个连通图，是方阵，它的上下左右都是0，至于是几阶，那么看情况了。如果觉得抽象地可以参照引言处非连通图的例子。

然后精彩之处来了，我们可以构造 你会发现重大秘密

情况2得证，性质5证毕。

关于性质5的例子： 组合成一个L 将这两个基向量组合起来。 （从机器学习谱聚类的角度）把上面这个看做一个矩阵， x 1 = ( 1 , 0 ) x_1=(1,0) x1​=(1,0)，这是我们赋予 x 1 x_1 x1​的新特征。 即从数学上可知，两个连通图中的顶点各为一类。这也很符合我们的直觉。

下面接着介绍两种非常常见的：归一化拉普拉斯矩阵。 一个非常疑惑的问题是：为什么需要归一化，这样有什么好处呢？大家可以好好思考。

对于对称型，有性质： 这个很显然，将对称型完整带入上面，然后先对 f f f进行操作，就是上面的结果，相当于那个归一化 D − 1 / 2 D^{-1/2} D−1/2变成了归一到 f f f上去了。 这里我想不用多说吧，只需要利用特征值概念就可以发现这是充要条件。 这个证明比上面这个还简单。 这个也很容易证明，直接用归一化的L与特征向量相乘会发现是0向量。

以上两个都可以类似L那样，写出半正定定义 > = 0 >=0 >=0的式子。 这个也是类似的，简短的说就是左右乘以一个对角矩阵不会影响这个性质，也就是说有下面：