The Normalized Laplacian

We have previously meet the combinatorial graph Laplacian \(\mathbf{L} = \mathbf{D} - \mathbf{A}\), where \(\mathbf{D}\) is the diagonal matrix whose \(i\)th diagonal entry \(d_{ii} = k_i\), the degree of node \(i\).

In Laplacian spectral clustering, the algorithm which we will study today, we typically work with the normalized graph Laplacian \(\tilde{\mathbf{L}} = \mathbf{D}^{-\frac{1}{2}}\mathbf{L}\mathbf{D}^{-\frac{1}{2}}\). Fortunately, many properties of \(\mathbf{L}\) also carry over to \(\tilde{\mathbf{L}}\).

Part A

Prove that \(\tilde{\mathbf{L}}\) is positive semi-definite.

Part B

Prove that the vector \(\mathbf{v} = \mathbf{D}^{\frac{1}{2}}\mathbf{1}\) is an eigenvector of \(\tilde{\mathbf{L}}\) with eigenvalue \(0\).

Part C

As we saw with \(\mathbf{L}\), if \(G\) is disconnected then \(\mathbf{L}\) is block-diagonal, with one block for each connected component. Explain why the same must also be true of \(\tilde{\mathbf{L}}\).

Part D

Explain why \(\tilde{\mathbf{L}}\) always has the same number of zero eigenvalues as \(\mathbf{L}\).