2
$\begingroup$

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?

  • 2
    What is a PSD matrix?2012-10-05
  • 0
    Sorry, I meant positive semi-definite matrix.2012-10-05

1 Answers 1

1

Assuming you mean positive-semidefinite for PSD, a graph laplacian has degrees of the graph on the diagonal, so we must have the Erdos Gallai condition for the degrees (that's necessary and sufficient for existance of the graph with given degree sequence). Other than that, the other entries must be either -1 or 0 with row and column sumbs equal to 0.

  • 0
    Depending on your setting it might be okay to use other off-diagonal entries than -1. For example you could build a Laplace matrix for a weighted graph, or a graph with parallel edges.2012-10-05
  • 0
    @ 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?2012-10-05
  • 0
    @user25004: If I understand you correctly, you're saying, put in 0 and -1 entries making sure the matrix is positive definite, then make sure the diagonal is minus the sum along a row or column. Right, so you'd be specifying the graph. But you're asking for necessary and sufficient conditions right?2012-10-06
  • 0
    To be clear, take something like $$$$\begin{bmatrix} 3&-1 \\\\ -1&1 \end{bmatrix}$$ whose eigenvalues are all positive.2012-10-06
  • 0
    @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 redundant2012-10-06