Strictly central matrices from strongly connected graph orientations

34 Views Asked by At

Let $G$ be a graph on $n$ vertices and $D$ and orientation of $G$. Suppose that $D$ is strongly connected, meaning for all $v, w \in V(D)$ there is a directed path from $v$ to $w$. Furthermore, suppose that $G$ is not $K_n$. Let $A$ be the adjacency matrix of $D$, meaning $a_{ij} = 1$ when $(i, j) \in E(D)$ and $a_{ij} = 0$ elsewhere. Let $K = A - A^T$, which is clearly skew-symmetric.

A matrix $M$ whose elements are from the set $\{0,-1,1\}$ is called central if there is a (component-wise) non-negative vector $x$ such that $Mx = 0$. If there is a positive vector $x$ such that $Mx = 0$, then $M$ is called strictly central.

Problem: Show that $K$ is a strictly central matrix (or find a counterexample).

Remark: If $G=K_n$, then the rank of $K$ is either $n$ or $n-1$. However, since $G \neq K_n$, we have $\mathrm{rank}(K) \leq n-2$.