2
$\begingroup$

Consider a signed complete graph $G(E,V)$ with adjacency $A_{ij}\in\{-1,+1\}$. Define the Laplacian matrix as $L:=D-A$ where $D$ is the degree matrix, $D_{ii}=\sum_{j\neq 1}A_{ij}$.

my question.

If $\sum_S\sum_{S^c} A_{ij}\geq 0$ holds for any non-empty subsets $S,S^c$, $S\cup S^c=V$ , is it true that $L$ is psd matrix?

If not, what does it actually imply?

motivation.

I came across this problem in my research, where I need to understand whether the statement that $L\succeq 0$ implies positive crossing edges are more than negative ones, for every node separation is loosy or not.

Improve this question
$\endgroup$
1
  • $\begingroup$ What does "loosy" mean? Also, your sets $S$ and $S^c$ should not just union to $V$, but, as the notation suggests, be disjoint, right? (I suppose that it doesn't matter since any overlap adds only non-negative terms.) $\endgroup$
    – LSpice
    Commented Jul 5 at 10:24

1 Answer 1

Reset to default
1
$\begingroup$

If I understand correctly, this condition does not imply that $L$ is psd. Take $G$ to be the signed graph which is a triangle with two positive edges and one negative edge. The Laplacian matrix for this is $$\begin{pmatrix}2 & 1 & 1 \\ 1 & 0 & -1 \\ 1 & -1 & 0\end{pmatrix}$$ which satisfies your condition, but is not psd since the principal submatrix consisting of the last two rows and columns is not psd.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .