# Facets of the Birkhoff polytope

I recently became interested in the geometric structure of the Birkhoff polytope since it's connected to a problem that I'm working on. The Wikipedia article states that the Birkhoff polytope has $$n^2$$ facets, but doesn't explain the partitioning actually works. So I'm wondering how I can determine which vertices (which are permutation matrices) belong to the same facet.

The only clue that I've found comes from the paper "Faces of the Birkhoff Polytope", which says

The facets of the Birkhoff polytope are precisely defined by the inequalities $$x_{ij} \geq 0$$ for $$1 \leq i, j \leq n$$.

While this makes sense for continuous points, I'm not sure how to relate the inequality to find the vertices of the facets.

Since the facets lie in the hyperplanes $x_{ij}=0$, the facet corresponding to $x_{ij}$ contains all vertices that have $x_{ij}=0$, i.e. the permutation matrices that correspond to permutations that don't map $j$ to $i$. There are $(n-1)(n-1)!$ of these. (Pick one of the other $n-1$ elements to map $j$ to and then count the possible images of the remaining elements as usual.)
• I got stuck at the claim quoted in the question. How do the inequalities $x_{ij} \geq 0$ determine the facets of the Birkhoff polytopes? – ensbana Mar 9 at 10:44