Skip to main content
MathOverflow

Return to Question

Capitalise title, while this is on the front page; `=\in` -> `\in`
Source Link
LSpice
LSpice
  • 12.9k
  • 4
  • 45
  • 69

positive Positive-semidefiniteness of laplacianLaplacian of signed graph

Consider a signed complete graph $G(E,V)$ with adjacency $A_{ij}=\in\{-1,+1\}$$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.

positive-semidefiniteness of laplacian of signed graph

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.

Positive-semidefiniteness of Laplacian of signed graph

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.

Source Link
tony
tony
  • 405
  • 2
  • 8

positive-semidefiniteness of laplacian of signed graph

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.