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.