# Graph Laplacian, requirements

What are the necessary and sufficient conditions for a PSD matrix $S$, to be a graph Laplacian? I know $S1=0$ is required. But clearly a real zero sum PSD matrix is not necessarily a graph Laplacian.

Second question arises after seeing the useful responses here: What are the conditions for a PSD matrix to be a weighted graph Laplacian?

-
What is a PSD matrix? – PAD Oct 5 '12 at 17:47
Sorry, I meant positive semi-definite matrix. – user25004 Oct 5 '12 at 20:13

@ Alex: How is it possible that Erdos Gallai condition for degrees does not hold, when the off-diagonal elements are directly giving the adjacency matrix for the graph? Constraining values in set $\{-1,0\}$ prevents multi-edges. Perhaps we only need a symmetric matrix then? – user25004 Oct 5 '12 at 22:59
To be clear, take something like \begin{bmatrix} 3&-1 \\\\ -1&1 \end{bmatrix} whose eigenvalues are all positive. – Alex R. Oct 6 '12 at 6:12
@Alex: For your example, the row-sums are not zero. What I want to claim is that any PSD matrix $S$, where $S_{ij}\in {-1, 0}$ and $S1= 0$ is a Laplacian matrix regardless of Erdos Gallai condition. However, I think some of my conditions are redundant – user25004 Oct 6 '12 at 21:20