# why are the eigenvalues of the normalized Laplacian matrix of graph $G$ non-negative?

Let $G$ be a simple and connected graph with $n$ vertices. $d_i$ is the degree of the vertex $i$. Let $L$ be the Laplacian matrix of $G$. $D$ is a $n\times n$ diagonal matrix with the elements of diagonal are $d_i$ $i=1,...,n$. The normalized Laplacian matrix of $G$ defined to be $L_{norm} =D^{-\frac12}L D^{-\frac12}$. So why are the eigenvalues of the normalized Laplacian matrix $L_{norm}$ of graph $G$ non-negative?

I'll assume the minimum valency of $G$ is positve, and use $N$ for the normalized Laplacian. Suppose $x$ is a vector in $\mathbb{R}^n$ and set $y=D^{-1/2}x$. Then $x^TNx = y^TLy.$ Since $L$ is positive semidefinite, $y^TLy\ge0$ and it follows that $x^TNx\ge0$ for any vector $x$. Hence $N$ is positive semidefinite, and so its eigenvalues are non-negative. [The one-sentence summary of all this is that conjugate matrices have the same inertia.]
• For the interested reader, you can go here to see why $L$ is positive semidefinite. – D Poole Mar 17 '16 at 12:42