Combinatorics of signed oriented graphs/skew-symmetric matrices - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T01:02:11Z http://mathoverflow.net/feeds/question/28358 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/28358/combinatorics-of-signed-oriented-graphs-skew-symmetric-matrices Combinatorics of signed oriented graphs/skew-symmetric matrices Wadim Zudilin 2010-06-16T08:08:09Z 2010-06-16T08:08:09Z <p>Consider a "complete" <a href="http://en.wikipedia.org/wiki/Signed_graph" rel="nofollow">signed graph</a> on $n$ vertices indexed by $1,2,\dots,n$, that is, a graph in which any two distinct vertices $i$ and $j$ are connected by an oriented edge. For each pair of vertices $i$ and $j$, write $v_{ij}=1$ or $-1$ depending on whether the connecting edge goes from $i$ to $j$ or from $j$ to $i$, respectively, and $v_{ii}=0$. The corresponding <a href="http://en.wikipedia.org/wiki/Adjacency_matrix" rel="nofollow">adjacency matrix</a> $V=(v_{ij})_{1\le i,j\le n}$ is a <a href="http://en.wikipedia.org/wiki/Skew-symmetric_matrix" rel="nofollow">skew-symmetric matrix</a> with entries $\pm1$ only outside the main diagonal. In particular, its determinant is 0 for $n$ odd and nonnegative for $n$ even; by a simple parity argument it can be shown that $\det(V)$ is odd (hence positive) in the latter case. On the other hand, $\det(V)$ seems to assume all possible odd positive values restricted only by <a href="http://en.wikipedia.org/wiki/Hadamard%27s_inequality" rel="nofollow">Hadamard's_inequality</a>.</p> <p>My general question is whether the condition $\det(V)=1$ imposes some known combinatorial structure in the set of complete signed oriented graphs (or maybe in a reasonable subset of this set). Some kind of related questions is whether the matrix $V$ in general imposes some interesting combinatorial structure of the underlying graph (I even do not the answer in the case when $v_{ij}$ depends only on the distance $i-j$, that is, $v_{ij}=\epsilon_{i-j}$).</p>