How wide is the Birkhoff Polytope?

Question

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:

1. 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.

2. 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.

3. 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.

4. 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?

Answer 1

For $n$ even, the width is exactly $\frac{2}{\sqrt{n-1}}$. For $n$ odd, I can prove this as a lower bound and $\frac{2n}{(n-1) \sqrt{n+1}} = \frac{2}{\sqrt{n-1} \sqrt{1-1/n^2}}$ as an upper bound.

---

Upper bound To start, let $n$ be even. Let $$\vec{j} = (1,1,\ldots, 1)^T$$ $$\vec{u} = \frac{1}{\sqrt{n}} (1,1,\ldots,1,-1,-1,\ldots,-1)^T$$ $$\vec{v} = \frac{1}{\sqrt{n(n-1)}} (n-1, -1,-1,\ldots,-1)^T$$ where $\vec{u}$ has equally many $1$'s and $-1$'s. We note that $|\vec{u}| = |\vec{v}|=1$ and $\vec{j} \cdot \vec{u} = \vec{j} \cdot \vec{v} = 0$.

Let $X$ be the $n \times n$ matrix $\vec{v} \vec{u}^T$. We have $X \vec{j} = \vec{v} (\vec{u}^T \vec{j}) = 0$ and $\vec{j}^T X = (\vec{j}^T \vec{v}) \vec{u} = 0$, so the rows and columns of $X$ sum to $0$. We also have $\mathrm{Tr}(X^T X) = \mathrm{Tr}(\vec{u} \vec{v}^T \vec{v} \vec{u}^T) = \mathrm{Tr}( \vec{v}^T \vec{v} \vec{u}^T \vec{u} ) = \mathrm{Tr}(1 \cdot 1) = 1$. So $X$ has length $1$.

Now, consider the linear functional $\mathrm{Tr}(X\ \underline{\quad } )$ on the Birkhoff polytope. For any permutation matrix $\sigma$, we have $\mathrm{Tr}(X \sigma) = \mathrm{Tr}(\vec{v} \vec{u}^T \sigma) = \mathrm{Tr}(\vec{u}^T \sigma \vec{v}) = \vec{u} \cdot \sigma(\vec{v})$.

If $\sigma$ maps the first coordinate into one of the first $n/2$ coordinates, the dot product of $\vec{u}$ and $\sigma(\vec{v})$ is $$\frac{1}{n\sqrt{n-1}} {\Big(} (n-1) - (n/2-1) + n/2 {\Big)} = \frac{n}{n \sqrt{n-1}} = \frac{1}{\sqrt{n-1}}.$$ If $\sigma$ maps the first coordinate into one of the last $n/2$ coordinates, then we get negative this.

So $\mathrm{Tr}(X\ \underline{\quad } )$ ranges from $\tfrac{1}{\sqrt{n-1}}$ to $- \tfrac{1}{\sqrt{n-1}}$ on the Birkhoff polytope, and the Brikhoff polytope has width $\leq \tfrac{2}{\sqrt{n-1}}$.

For the case where $n$ is odd, replace $\vec{u}$ by the vector $$\frac{1}{\sqrt{n^3-n}} (n+1,n+1,\ldots,n+1,-n+1,-n+1,\ldots,-n+1)$$ where there are $\tfrac{n+1}{2}$ negative terms and $\tfrac{n-1}{2}$ positive ones.

---

Lower bound: Here is the key lemma:

Lemma Let $X$ be an $n \times n$ matrix with row and column sum $0$, and $\sum_{ij} X_{ij}^2 = 1$. Then $$\sum_{\sigma \in S_n} \left( \mathrm{Tr}(\sigma X) \right)^2 = n (n-2)!.$$ Here the sum runs over all permutation matrices.

Proof Expanding the sum gives $$(n-1)! \sum_{ij} X_{ij}^2 + (n-2)! \sum_{i_1 \neq i_2,\ j_1 \neq j_2} X_{i_1 j_1} X_{i_2 j_2}.$$ Letting $J$ denote the $n \times n$ matrix which is all $1$'s, we have $$\sum_{i_1 \neq i_2,\ j_1 \neq j_2} X_{i_1 j_1} X_{i_2 j_2} = \mathrm{Tr}{\Big(} (J - \mathrm{Id}) X^T (J - \mathrm{Id}) X {\Big)}.$$ But $JX=XJ=0$ since the rows and columns of $X$ sum to $0$. So $$\mathrm{Tr}{\Big(} (J - \mathrm{Id}) X^T (J - \mathrm{Id}) X {\Big)} = \mathrm{Tr}(X^T X) = 1.$$

Our sum in total is thus $(n-1)! + (n-2)! = n (n-2)!$. $\square$

Also, $\sum_{\sigma \in S_n} \mathrm{Tr}(\sigma X) = (n-1)! \sum X_{ij} =0$. So, if $\sigma$ ranges uniformly over $S_n$, then $\mathrm{Tr}(\sigma X)$ has expected value $0$ and standard deviation $\sqrt{\tfrac{n(n-2)!}{n!}} = \tfrac{1}{\sqrt{n-1}}$. So the range between its greatest and least value is at least $\tfrac{2}{\sqrt{n-1}}$.