Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Consider a "complete" signed graph 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 adjacency matrix $V=(v_{ij})_{1\le i,j\le n}$ is a skew-symmetric matrix 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 Hadamard's_inequality.

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}$).

share|improve this question
    
This combinatorial structure (a complete graph with an orientation) is known as a tournament. Also, as a skew-symmetric matrix, $\det(V)$ is a square (the square of the Pfaffian of $V$). –  Robin Chapman Jun 16 '10 at 8:28
    
Robin, I provide the required links which explain that $\det(V)$ is the square of the Pfaffian. I can even compute the Pfaffian as a single determinant of a $(n/2)\times(n/2)$ matrix in the case $v_{ij}=\epsilon_{i-j}$. A tournament is another way to say a complete signed (oriented) graph, but I am looking for a structure of graphs satisfying $\det(V)=1$. –  Wadim Zudilin Jun 16 '10 at 9:09
1  
Wadim, Robin was commenting on your statement that "det(V) seems to assume all possible odd positive values restricted only by Hadamard's_inequality": there is an additional requirement that det(V) be a perfect square (or you should say Pfaffian). –  Victor Protsak Jun 16 '10 at 14:18
    
Victor and Robin, thanks for notifying this mistake. Yes, of course, I meant that only the squares have to be taken in the range. –  Wadim Zudilin Jun 16 '10 at 14:25
1  
Did you try to interpret the determinant as generating function for non-intersecting lattice paths via Stembridge's theorem (Advances in Mathematics 83, Nonintersecting Paths, Pfaffians, and Plane Partitions)? –  Martin Rubey Jun 16 '10 at 16:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.