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?
[Math] why are the eigenvalues of the normalized Laplacian matrix of graph $G$ non-negative
graph theorymatrices
Related Solutions
This is a quick exercise in matrix algebra:
$$ D^{-1/2} (D- A) D^{-1/2} = I - D^{-1/2} A D^{-1/2} $$
Then notice $\lambda$ is an eigenvalue of $M$ if and only if $1-\lambda$ is an eigenvalue of $I-M$. In fact the eigenvectors corresponding to $\lambda$ for $M$ are the same as the eigenvectors corresponding to $1-\lambda$ for $I-M$, and vice versa.
I can make two sort of hand-wavy observations. From basic linear algebra properties we know that given a matrix $ \mathbf{L} $ \begin{equation} \sum_{i}d_{i}= \sum_{i}\lambda_{i} \end{equation}
where $ \lambda $ are the eigenvalues, and $ d $ are the the diagonal elements of your matrix $ \mathbf{L} $.
The elements on the diagonal of the Laplacian correspond to the degrees of the vertices. Assuming no isolated vertices and that the graph is simple (i.e weights are either $0$ or $1$), $ d_{i} \geq 1 $.
If most of your eigenvalues are equal to $1$, then their sum is also likely a small number. That means that the sum of degrees is also a small number, which means that your graph is probably sparsely connected.
The next observation has to do with star graphs. In general, complete bipartite graphs with $n$ and $m$ vertices on each group respectively, have Laplacian eigenvalues:
- $n$ with multiplicity $m-1$
- $m$ with multiplicity $n-1$
- $0$ with multiplicity $1$
- $m+n$ with multiplicity 1
Consider the star graph below which is a complete bipartite graph with $n=1$ and $m=8$
Its eigenvalues are $1$ with multiplicity $7$, $0$ with multiplicity $1$ and $9$ with multiplicity $1$.
So, if your graph contains starlike subgraphs, then your Laplacian is going to have a bunch of $1$-eigenvalues. I include two examples below (the random isolated component belongs to the graph on the right).
. 
Both of these graphs have eigenvalue $1$ with multiplicity $9$.
Best Answer
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.]