Conditions for a matrix to be a Graph Laplacian [closed]

Question

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.

Answer 1

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.