# How wide is the Birkhoff Polytope?

Now also posted on Math Overflow.

Define the width of a polytope $$P \subset \mathbb R^d$$ as the minimum length of the interval $$\{v \cdot p:p \in P\}$$ for $$v$$ in the unit sphere. In other words the width is the smallest number $$W$$ such that you can sandwich $$P$$ between two hyperplanes distance $$W$$ apart. Here's a picture:

Suppose the polytope $$P \subset \mathbb R^d$$ is contained in the affine subspace $$A + x$$ for $$A \subset \mathbb R^d$$ a hyerplane. Define the relative width as the smallest length of $$\{v \cdot p:p \in P\}$$ as $$v$$ ranges over the unit sphere in $$A$$. In other words translate the affine subspace to contain the origin and then ignore the perpendicular directions.

The Birkhoff polytope $$\mathcal B$$ is defined as the convex hull of the $$n!$$ permutation matrices. That means the $$n \times n$$ matrices with all zeros except for exactly one $$1$$ in each row and column. Equivalently $$\mathcal B$$ is the set of nonnegative matrices with all row and column sums equal to $$1$$.

In this case the affine subspace is defined as

$$\left \{x \in \mathbb R^d: \sum_j x^i_j =1, \sum_i x^i_j =1\right \}.$$

This just says the row and column sums equal $$1$$. Within that subspace the polytope is defined as the intersection with the first quadrant.

I am having trouble computing or estimating the height of $$\mathcal B$$. I would imagine the $$v$$ that minimises the projection is something like

$$v = \left( {\begin{array}{cccc} 1/4 & -1/4 & 1/4& -1/4\\ -1/4 & 1/4 & -1/4 & 1/4\\ 1/4 & -1/4 & 1/4 & -1/4\\ - 1/4 & 1/4 & - 1/4 & 1/4\\ \end{array} } \right)$$

or in general make half the diagonals equal to $$1/n$$ and the other equal to $$-1/n$$. Then choosing the correct permutation matrices for the endpoints of the interval, we can force the interval to have length $$2$$.

The only reason I have to believe this is there are many choices of permutation matrices, and we want to minimise the interval length among all pairs. So $$v$$ should be symmetric in some sense.

Does anyone have ideas?

Define a function $$F: S_{n \times n} \to \mathbb R$$ by $$F(x) = \max\{|x \cdot(a-b)|: a,b \text{ vertices of } \mathcal B\}$$
To show $$v \in S_{n \times n}$$ is a minimiser it is enough to show the subgradient at $$v$$ contains a vector normal to the sphere. Namely $$v$$ itself. The subgradient of $$F= \max\{f_1,\ldots, f_N\}$$ at the point $$x$$ is the convex hull of
$$\{\nabla f_i (x): f_i(x)=F(x)\}$$
Since $$i$$ runs over pairs of vertices it is straightforward to see $$f_i(v)=F(v)$$ iff $$a$$ and $$b$$ are in some positive and negative diagonal of $$v$$. By symmetry add up all the $$\nabla f_i (x)$$ to get a positive multiple of $$v$$ and done!