The polytope of even doubly stochastic matrices (Q1175954)

An even doubly stochastic matrix is even if it is the convex combination of even permutation matrices. This paper studies the combinatorial structure of the polytope of these matrices of a fixed order \(n\). For \(n\geq 4\) the dimension is \((n-1)^ 2\). Five families of valid independent inequalities (necessary conditions) and one sufficient condition are derived. A characterization of the pairs of even permutations defining an edge of the polytope is obtained, from which it follows that for \(n\geq 4\) any two vertices may be joined by an edge path of length 2. A counterexample shows that a well-known algorithm for expressing a doubly stochastic matrix as a convex combination of permutation matrices fails for the even case. Finally it is conjectured that the number of faces is exponential and that a certain lower bound holds for the permanent of any even doubly stochastic matrix.