A family of skew-symmetric matrices corresponding to cycles in graphs

Question

When investigating loops in Markov chains I ran into the following observation.

A cycle in a graph $G$ with $n$ vertices may be represented by a matrix $\Gamma \in \mathbb R^{n \times n}$ having the following properties:

(i) $\Gamma = -\Gamma^T$.

(ii) $\Gamma \mathbb 1 = 0$, i.e. $\sum_{j = 1}^n \Gamma(i,j) = 0$ for all $i =1, \dots, n$.

(iii) $\Gamma(i,j) = 0$ whenever there is no edge between vertices $i$ and $j$.

(iv) $\Gamma \neq 0$.

The simplest example of such a matrix is $\Gamma = \begin{pmatrix} 0 & 1 & -1 \\ -1 & 0 & 1 \\ 1 & -1 & 0 \end{pmatrix}$.

The representation mentioned above is made more precise by the following proposition.

Proposition Let $G$ be a graph over $n$ vertices and let $\Gamma$ satisfy the conditions (i)-(iv) above. Then there exists a cycle, i.e. a non-empty sub-graph $C = (V_C, E_C)$ with $V_C = \{ x_0, x_1, \dots, x_k\}$ and $E_C = \{x_0 x_1, x_1 x_2, \dots, x_k x_0 \}$, such that for every $x_i x_j \in E_C$, $\Gamma(x_i, x_j) > 0$. Conversely, if there exists a non-empty cycle $C = (V_C, E_C)$, then there exists a matrix $\Gamma$ satisfying (i)-(iv), and $\Gamma(i,j) > 0$ for $(i,j)\in E_C$.

Proof:

"$\Rightarrow$": Since $\Gamma \neq 0$ and $\Gamma$ is skew-symmetric, there exists a pair $(i_0,i_1)$, $i_1 \neq i_0$, such that $\Gamma(i_0, i_1) > 0$. Since $\Gamma$ is skew-symmetric, $\Gamma(i_1, i_0) < 0$, and because rows sum to zero, there must be a positive element on row $i_1$. Suppose this is at position $(i_1, i_2)$. Again $i_2 \neq i_1$. We may repeat this procedure until we encounter a node $i_k$ that we already obtained (which will surely happen within $n-1$ steps). If this vertex is $i_0$, we are done. If this vertex is $i_l = i_k$ for some $0 < l < k - 1$ (note $l=k$ is impossible by skew-symmetry), we obtain a cycle $\{x_{i_l}, x_{i_{l+1}}, \dots, x_k\}$ with the required properties by removing vertices $i_0, \dots, i_{l-1}$.

"$\Leftarrow$": Let the entries of $\Gamma(i,j) = 1$ and $\Gamma(j,i) = -1$ whenever there is a edge between $i$ and $j$ in the directed cycle $x_0, x_1, \dots, x_k$, and $\Gamma(i,j) = 0$ otherwise. For any $i$, $\sum_{j=1}^n \Gamma(i,j) = \sharp \{\mbox{directed edges out of $i$}\} - \sharp \{\mbox{directed edges into $i$}\} = 0$, so that (ii) is satisfied. The other conditions (i), (iii), (iv) are clearly satisfied. $\square$

This result seems quite basic to me, but I have trouble finding references in the literature. What would a matrix satisfying (i)-(iv) be called? I would like to understand the structure of the set of matrices satisfying (i)-(iv) for particular adjacency structures of graphs. Also results on the spectra of such matrices might prove helpful. Basically anything related to matrices satisfying (i)-(iv) would be of interest to me.

Note: in the (applied) literature on Markov chains I have found one other reference to these matrices. This is Sun, Gomez, Schmidhuber, Improving the asymptotic performance of Markov chains by inserting vortices, 2010. They prove a couple of interesting results related to such matrices but do not provide a reference to any literature on this topic. The notion of skew-adjacency matrices (see e.g. Cavers et al, Linear Algebra and its Applications, 2012) seems related but is different. (In particular, a matrix satisfying (i)-(iv) and containing only 0 and +/- 1 entries is a skew adjacency matrix for the cycle it represents, but in general not for the original graph containing such a cycle.)

It would help a lot if any of you could provide a reference for this kind of theory. Many thanks in advance.

Answer 1

This isn't a proper answer, but it's slightly too long for a comment...

A matrix that satisfies (i) and (ii) is biregular and skew-symmetric. In principle a biregular skew-symmetric matrix could have non-zero row and column sums, but this just amounts to adding a matrix with all entries the same so gives no more generality.

Similar types of matrix crop up in studies of mixing and quasirandomness in groups and graphs, in particular through the notion of a $G$-circulant. To learn more I'd recommend two sources:

Product Growth and Mixing in Finite Groups by Laszlo Babai, Nikolay Nikolov and Laszlo Pyber.

My other recommended source is a famous and beautiful paper of Gowers:

Quasirandom groups by W.T. Gowers

Gowers discusses the connection with graphs at great length (the BNP paper above doesn't focus on this as much). Both papers are cracking!

Answer 2

The object you're interested in is an element of the kernel of the combinatorial divergence operator whose definition you give in (ii). But there's quite a nice theory of these kind of things that may be in the spirit of what you (were, I see this is from 2014) after. In what follows, rather than have your matrix be all zeroes and $\pm1$, I'm going to generalize and allow it to have any real numbers.

Let $X$ be a finite set of vertices and consider the following three spaces for $k \in \{0,1,2\}$:

$$ \Omega^k(X) = \big\{\phi : X^{k+1} \to \mathbb{R} \; | \; \phi(x_{\sigma(0)}, \ldots, x_{\sigma(k)}) = \textrm{sign}(\sigma) \phi(x_0,\ldots, x_k)\big \}$$

where $\sigma$ is a permutation of $\{0, \ldots, k\}$. The space $\Omega^0$ is the space of real valued functions from your vertex set and so isomorphic to $\mathbb{R}^{|X|}$. The space $\Omega^1$ is the set of edge flows on the complete graph on $|X|$ vertices (where if we simply don't want an edge, we give it a zero flow weight). The permutation condition implies these are skew symmetric $|X| \times |X|$ matrices. The space $\Omega^2$ is the space of all triangular flows on the graph (an element of it is an alternating 3-tensor, or, a skew symmetric $|X| \times |X| \times |X|$ hypermatrix).

We may also define some natural linear maps between these spaces that are natural combinatorial analogues of the classic vector calculus operations. The gradient is a map:

$$ \textrm{grad}: \Omega^0 \to \Omega^1 $$

via $\textrm{grad}(a)_{ij} = a_j - a_i$. Similarly, the curl is a map:

$$ \textrm{curl}: \Omega^1 \to \Omega^2 $$ via $\textrm{curl}(A)_{ijk} = A_{ij} + A_{jk} + A_{ki}$.

Note that $\Omega^0$ inherits an inner product from $\mathbb{R} ^{|X|}$. Define a nice simple inner product structure on $\Omega^1$ via: $$ \langle A, B \rangle_1 = \sum_{\{i,j\} \in E} A_{ij} B_{ij} $$ where $E$ is just the edge set of your graph. Similarly for $\Omega^2$: $$ \langle\mathcal{A}, \mathcal{B}\rangle_2 = \sum_{\{ijk\} \in T} \mathcal{A}_{ijk} \mathcal{B}_{ijk}. $$ where $T$ is the set of triangles. Now using these we can construct the adjoints of $\textrm{grad}$ and $\textrm{curl}$:

$$ \textrm{grad}^* = -\textrm{div} = -\sum_{j \in X} A_{ij} $$ $$ \textrm{curl}^* = \sum_{k \in X} \mathcal{A}_{ijk}. $$ Then we have the two sequences: $$ \Omega^0(X) \xrightarrow{\text{grad}} \Omega^1(X) \xrightarrow{\text{curl}} \Omega^2(X) $$ and $$ \Omega^0(X) \xleftarrow{\text{ grad}^*} \Omega^1(X) \xleftarrow{\text{ curl}^*} \Omega^2(X). $$

Theorem (Combinatorial Hodge/Helmholtz Decomposition): $\Omega^1$ admits an orthogonal decomposition as: $$ \Omega^1 = \textrm{im}(\textrm{grad}) \oplus \underbrace{\textrm{ker}(\textrm{curl}) \cap \textrm{ker}(\textrm{div}) \oplus \textrm{im}(\textrm{curl}^*)}_{= \textrm{ker}(div)}. $$

Elements in the first component are precisely those flows that admit a potential function; flows in $\textrm{ker}(\textrm{div})$ are precisely those in your example: they are flows with everywhere zero divergence, and hence are sums of cycles and occupy a linear subspace orthogonal to those flows that admit a potential function.