PROBLEM

The Birkhoff polytope $B_n$ is the convex hull of all $n\times n$ permutation matrices. Prove that the permutahedron $\Pi(n)$ can be obtained as the image of $B_n$ under a linear map.

Note the size of this lift of $\Pi(n)$ versus the $O(n \log n)$ lift found by Goemans. Can you argue that $\Pi(n)$ cannot have lift of size smaller than $O(n \log n)$?

SOLUTION

Let $P_n$ be the set of $n\times n$ permutation matrices so $B_n$ is the convex hull of $P_n$. $\Pi(n)$ is the convex hull of the set of all permutations of the entries of the vector $v = (1,\ldots,n)^T$. Let $\pi$ be the linear map from $n \times n$ matrices to $\mathbb{R}^n$ given by $\pi(A) = Av$. Then $\pi$ projects $P_n$ to the vertices of $\Pi(n)$. Since $\pi$ is linear, $\pi(\text{conv}(P_n)) = \text{conv}(\pi(P_n))$.

The Birkhoff polytope is precisely the set of all doubly stochastic matrices. These can be defined by the following relations on the entries $a_{ij}$: for each $i$, $\sum_{j=1}^n a_{ij} = 1$; for each $j$, $\sum_{i=1}^n a_{ij} = 1$; for each $i,j$, $a_{ij} \geq 0$. This description involves $n^2$ inequalities, and all of the inequalities are necessary, so this lift has size $O(n^2)$ which is worse than Goemans' lift.

The permutathedron has $n!$ vertices. To check this, for each permutation $\sigma$, $\sigma v$ lies on the the sphere with radius $r^2 = \sum_{i = 1}^n i^2$ so it can't be a convex combination of other permutations of $v$. Since $\Pi(n)$ has $\geq n!$ faces, any lift has $\geq n!$ faces. The number of faces of a polytope is at most $2^k$ where $k$ is the number of inequalities defining the polytope. Therefore a lift of $\Pi(n)$ has size at least $\log (n!)$. Note that $\log (n!) = O(n \log n)$ (Stirling's approximation).