Let M be a symmetric non-negative definite $n\times n$ matrix. Let $K\_n$ denote the complete graph on $n$ vertices. Under what conditions is it possible to assign edge weights to $K\_n$ in such a way that $M$ is the corresponding graph Laplacian? Obviously the nullspace of M must contain the constant vector $(1,1,...)$, but are there any other obstructions?


I would be interested in answers for either the normalized or unnormalized Laplacian. 



Conditions for a matrix to be a Graph Laplacian
If $M$ is the Laplacian of an undirected graph, then $M$ has to satisfy $a\_{ii} = -\sum\_{j: i \not = j} a\_{ij}$ where $a\_{ij} = a\_{ji}$ is the $ij$-the entry of $M$, and $a\_{ij}=a\_{ji}$ (symmetric)


These conditions are sufficient though: Give edge $\{i,j\}$ in $K\_n$ the weight $a\_{ij}$ and then $M$ will be the Laplacian.


