Consider a simple, undirected graph $G$ on $n$ vertices. Let $L$ be the combinatorial laplacian matrix given by $L=D-A$ where $D$ is the diagonal matrix of degrees and $A$ is the adjacency matrix. Consider the normalized laplacian matrix $M = I – D^{-1/2}AD^{-1/2}$.
I want to prove that the eigenvalues of this matrix $M$, $\lambda_0,\leq \lambda_1 \leq \ldots \leq \lambda_{n-1}$, all lie in $[0,2]$. I know that the eigenvalues are all real as $M$ is symmetric, but I cannot get any further.
I also want to show that $\lambda_{n-1} =2$ if and only if $G$ is bipartite and that the multiplicity of the 0 eigenvalue is the number of connected components.
Any help would be appreciated, thanks.
Best Answer
You want to show that both $M$ and $2I-M$ are positive semidefinite.
Rather than working with $M = D^{-1/2}(D-A)D^{-1/2}$ and $2I-M = D^{-1/2}(D+A)D^{-1/2}$, it's enough to work with $D-A$ and $D+A$, and show that both of these are positive semidefinite. Multiplying by $D^{-1/2}$ on both sides doesn't change the positive semidefiniteness of a matrix.
There are a couple of approaches to this, but one is to write the quadratic forms $\mathbf x^{\mathsf T}(D-A)\mathbf x$ and $\mathbf x^{\mathsf T}(D+A)\mathbf x$ as sums of squares. (Hint: the natural way to do this is as a sum over all the edges in the graph.)
Finally, $\lambda_{n-1}=2$ exactly when $2I-M$ has a $0$ eigenvalue, which happens exactly when $D+A$ has a zero eigenvalue. Once you have written $\mathbf x^{\mathsf T}(D+A)\mathbf x$ as a sum of squares, you want to determine for which values of $x$ this sum of squares becomes $0$. This will happen only when $\mathbf x = \mathbf 0$ unless the graph is bipartite.