Reference request: Strong Connectivity and the Incidence Matrix

Question

Question: What would be a good reference for characterizations of strong connectivity of a digraph in terms of its incidence matrix?

Details: Consider a digraph $(V, E)$ with vertex set

$$V = \{v_1, \ldots, v_m\}$$

and edge set

$$E = \{e_1, \ldots, e_n\} = \{(v_{11},v_{12}), \ldots, (v_{n1},v_{n2})\} \subseteq V \times V\,.$$

The incidence matrix $M$ of $(V, E)$ is the $|V| \times |E|$ matrix defined by,

$$M_{ij} = -1, \quad \text{if} \ v_{1j} = v_i\,,$$ $$M_{ij} = 1, \quad \text{if} \ v_{2j} = v_i\,,$$ $$M_{ij} = 0, \quad \text{otherwise}\,.$$

Thus, an entry $M_{ij}$ is $-1$ if edge $j$ leaves vertex $i$, $1$ if edge $j$ reaches vertex $i$, and $0$ otherwise.

The digraph $(V, E)$ is said to be strongly connected if, for any two vertices $v, v' \in V$, there exists a directed path connecting $v$ and $v'$; in other words, there exist vertices $v^{(1)}, \ldots, v^{(k)} \in V$ such that

$$(v, v_1), (v_1, v_2), \ldots, (v_{k-1}, v_k), (v_k, v') \in E\,.$$

Context: I am familiar with characterizations of strong connectivity in terms of the adjacency matrix, but not the incidence matrix. A Google search has not yielded anything helpful in that direction.

Thanks in advance!

Answer 1

It needs to be the case that for every $(0,1)$-vector $x$ (other than the zero vector and the all-ones vector) the vector $M^Tx$ has at least one entry positive and one entry negative.

Otherwise, if this fails for some vector $x$, then you have that $X=\{i\in V : x_i\neq 0\}$ is a set of vertices such that all arcs incident to one vertex in $X$ and one not in $X$ go "in the same direction" -- i.e., either all such arcs leave $X$ or they all enter $X$, and of course the existence of such a (nonempty, proper) set of vertices is what it means for strong connectivity to fail. (Well, unless such an $x$ actually makes $M^Tx$ zero, in which case the graph isn't even weakly connected.)