This question is migrated from MSE where it turned out to be much harder than I thought. I still cannot figure this out. Does anyone have any ideas?

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:

More generally suppose the polytope $P \subset \mathbb R^d$ has affine hull $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.

Equivalently the width is the minimiser of $$F(v) = \max\{v \cdot (p_1 - p_2) :p_1,p_2 \in P \text{ are vertices}\}.$$ Note $F$ is the maximum of a bunch of linear functions so is convex, and we are looking to minimise a convex function. The problem is the domain is a sphere rather than a convex region.

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 \}.$$

and

$$A= \left \{x \in \mathbb R^d: \sum_j x^i_j =0, \sum_i x^i_j =0\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_1 = \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)\\[30pt] v_2 = \left( {\begin{array}{cccc} 1/2 & -1/2 & 0& 0\\ -1/2 & 1/2 & 0 & 0\\ 0 & 0 & 0 & 0\\ 0 & 0& 0 & 0 \end{array} } \right)$$

In these cases we can choose the correct permutations (vertices) to force the interval to have length 2.

Other choices like $$ v_3 = \left( {\begin{array}{cccc} 1/4 & -1/4 & 0& 0\\ -1/4 & 1/4 & 0 & 0\\ 0 & 0 & \sqrt{3/16} & -\sqrt{3/16}\\ 0 & 0& -\sqrt{3/16} & \sqrt{3/16}\\ \end{array} } \right) $$

You can use to get interval greater than 1. My intuition for why $v_1,v_2$ are optimal is along the lines of "If you try to shift mass to ruin some choice of vertices, others choices will become better."

Here are some things I am able to prove:

The vectors $v_1$ and $v_2$ are local minima of the function $F(v) = \max\{v \cdot( \sigma - \rho): \sigma - \rho \text{ vertices of } \mathcal B\}$. However we do not have a local minimum over the ball, or any guarantee this is a global minimum.

At $v_1$ and $v_2$ then $F$ has a subgradient normal outwards to the sphere. This means moving along the sphere will have a small influence on $F$ compared to moving towards the centre.

If we add a perturbation $\epsilon^i_j$ to $v= v_1,v_2$ such that $\|v + \epsilon\| = 1$ and $v + \epsilon \in A$ then we have $$\sum_{i+j \ \text{even}} \epsilon^i_j \le 0 \qquad \qquad \sum_{i+j \ \text{odd}} \epsilon^i_j \ge 0$$ This is because otherwise you push $v$ out of the unit ball. From this I can show there is either a

*positive*diagonal $\sigma$ with $\epsilon^1_{\sigma(1)} + \ldots+ \epsilon^1_{\sigma(n)} \ge 0$ or a*negative*diagonal $\rho$ with $\epsilon^1_{\rho(1)} + \ldots+ \epsilon^1_{\rho(n)} \le 0$. Here positive diagonal means all $v^i_{\sigma(i)} >0$. If I could prove both exist at once I'd be done.Partial converse to 1: If at some some $w$ in the sphere the subgradient to $F$ contains $w$ itself then for each positive entry $w^i_j$ there is a diagonal $\sigma$ with $w^1_{\sigma(1)} + \ldots+ w^1_{\sigma(n)} = \max\{w \cdot \rho : \rho \text{ a vertex of } \mathcal B\}$ and likewise for each negaive entry $w^i_j$ there is a diagonal $\sigma$ with $w^1_{\sigma(1)} + \ldots+ w^1_{\sigma(n)} = \min\{w \cdot \rho : \rho \text{ a vertex of } \mathcal B\}$.

If I could probe deeper into 4. and somehow categorise all vectors similar to $v_1,v_2$ then I could check them case by case and determine the minimiser. But so far I am stuck and imagine the correct proof is a big more elementary than what I'm trying. Any ideas?