Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
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

1 Answer 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.

share|improve this answer
    
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. –  A.Schulz Oct 5 '12 at 19:57
    
@ 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
    
@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? –  Alex R. Oct 6 '12 at 5:32
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.