Let $G=(V,A)$ be an oriented graph, stronlgy connected with $n\in\mathbb{N}^*$ vertices. Let $M\in\mathcal{M}_n(\mathbb{R})=(m_{i,j})$ be an skew-symmetric matrix of size $n$ and rank $r$, such that for all $i,j\in V$: $i\longrightarrow j\Longleftrightarrow m_{i,j}>0$ (hence $M$ is a skew-symmetric incidence matrix of $G$). Is there any necessary and sufficient condition on $G$ and $r$ ensuring that there exists a positive vector in $\text{Ker}(M)$?

I've tried several matrices for $n\in\{3,4,5\}$ and it seems that, given $G$ and $r$, the fact that there exists a positive vector in $\text{Ker}(M)$ does not depend on the exact values of the coefficients $m_{i,j}$, but I do not know how to predict that such a vector exists. I have just noticed that given $G$, the answer of the question can vary with $r$.

  • $\begingroup$ Sounds like a manifestation of (a weighted) Kastelyn's Theorem. $Det(M)$ is the square of the Pfaffian. However in some cases the latter is a sum of terms corresponding to matchings, involving the weights $m_{ij}$ and all contributing with the same sign. See, e.g., arxiv.org/abs/1409.4631 $\endgroup$ Jun 22, 2020 at 13:49


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.