2
$\begingroup$

The wikipedia's page for Birkhoff polytope states that the polytope has $n^2$ facets, determined by the inequalities $x_{ij} \geq 0$, for $1 \leq i,j \leq n$. I've tried different things but can't see how this claim makes sense. How should I look at this?

Also is this only true for $n > 2$? According to the Birkhoff - von Neumann theorem, $B(2)$ would have dimension $(n-1)^2 = 1$, $n! = 2$ vertices, but also $n^2 = 4$ facets, which are also vertices?

$\endgroup$
0
$\begingroup$

The penultimate sentence of the Wikipedia article is referring to half-spaces of the $(n-1)^2$ dimensional space containing $B_n$. $B_n$ is the intersection of these half-spaces. The formula for the facets themselves is $a_{i,j} = 0$ for each of the $n^2$ entries.

And, yes, the number of facets of $B_n$ is $n^2$ only for $n \gt 2$. The Wikipedia article is not stated correctly. As you have deduced, $B_2$ is a line segment.

$\endgroup$
  • $\begingroup$ I have made my first Wikipedia edit to the Birkhoff polytope page, clarifying the number of facets in the case n = 2. $\endgroup$ – Dan Moore Apr 1 at 13:38

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.