I've read in several sources that the number of facets of the Birkhoff polytope $\mathcal{B}(n)$ is $n^2$.

Is this supposed to hold when $n=2$? Since $\mathcal{B}(2)$ has dimension $1$, the facets would be the two $0$-dimensional vertices, which are the two permutation matrices below: $$\begin{pmatrix} 1 & 0 \\ 0 &1 \end{pmatrix} \text{ and } \begin{pmatrix} 0 & 1 \\ 1 &0 \end{pmatrix}$$ However, the claim is that there should be $2^2 = 4$ facets. None of my sources have given any restriction on $n$. What am I missing?


No, it doesn't apply to $n=2$; your sources (like this one) apparently failed to treat this special case.

The generally $n^2$ facets correspond to the non-negativity constraints for the $n^2$ entries of the matrix. But for $n=2$, the $4$ non-negativity constraints form two pairs of identical constraints if you restrict them to the space defined by the row and column sum constraints: The row and column sum constraints span a $3$-dimensional space and thus leave only a $1$-dimensional space of doubly stochastic matrixes of the form

$$ \pmatrix{x&1-x\\1-x&x}\;, $$

in which the non-negativity constraints are pairwise identical on the diagonal and off the diagonal.

So you're right; there are only two facets in this case, defined by $x=0$ and $x=1$, which corresponds to the two matrices you gave.

  • $\begingroup$ This is from a different post but I received no answers from there, so I'd like to ask it here: could you explain the claim that the $n^2$ facets correspond to the non-negativity constraints for the $n^2$ entries? I tried different things but can't see how to deduce ones from the others. $\endgroup$ – ensbana Mar 21 '19 at 9:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.