This is a graph problem, related to one I posted earlier as this is for a later part of the same question. I've tried a few things but haven't made much progress so far.
$\mathcal{E}$ is a set of edges such that $(x,y)$ is an edge between nodes $x$ and $y$.
$w_{(x,y)}$ is the weight of edge $(x,y)$.
$d_y=\sum_{x\ \text{such that}\ (x,y)\ \in\ \mathcal{E}}w_{(x,y)}$
$D=\text{diag}\{d_y\}$
Which means the diagonal matrix containing vector $\mathbf{d}$ on its leading diagonal which has elements which are the sums of rows of $w(x,y)$. But I am not really sure.
$W_{x,y}=\begin{cases}w_{(x,y)},& \text{for } (x,y)\ \in \ \mathcal{E}\\ 0, & \text{otherwise}\end{cases}$
$M=D-W$
Show that eigenvalues of $M$ are non-negative.
If anyone has any advice it would be much appreciated.
For every vector $f$ in $R^n$ we have:
$$f'Mf=f'Df-f'Wf=\sum_{i=1}^nd_if_i^2-\sum_{i,j=1}^nf_if_jw_{ij}$$ $$\frac{1}2(\sum_{i=1}^n d_if_i^2+\sum_{j=1}^nd_jf_j^2-2\sum_{i,j=1}^nf_if_jw_{ij})=\frac{1}2\sum_{i,j=1}^nw_{ij}(f_i-f_j)^2\geq0$$
This shows you that M is a positive semi-definite matrix, and hence the eigenvalues are non-negative.