证明拉普拉斯矩阵是半正定矩阵

因为\(L=D-W\),那么\(x^TLx\)有: \[ x^TLx = x^T(D-W)x = x^TDx - x^TWx \] \(W\)为一个对称矩阵,将\(W\)的各行元素累加得到了\(D\),由于\(D\)是对角矩阵\(x^TDx=\sum_{i=1}^nd_ix_i^2\)\[ \begin{aligned} x^TLx &= \sum_{i=1}^nd_ix_i^2 - \sum_{i=1}^n\sum_{j=1}^nw_{ij}x_ix_j\\\ &=\frac{1}{2}(\sum_{i=1}^nd_ix_i^2 - 2\sum_{i=1}^n\sum_{j=1}^nw_{ij}x_ix_j + \sum_{j=1}^nd_jx_j^2)\\\ &=\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n(w_{ij}x_i^2-2w_{ij}x_ix_j+w_{ji}x_i^2)\\\ &=\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^nw_{ij}(x_i-x_j)^2\geq0 \end{aligned} \]

综上拉普拉斯矩阵\(L=D-W\)是一个半正定的矩阵。