How wide is the Birkhoff Polytope?

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?

• Let $X_{11} = (n-1)/n$, $X_{1j} = X_{j1} = -1/n$ and $X_{jk} = 1/(n(n-1))$ for $2 \leq j,k \leq n$. I get that $X$ is in the plane parallel to the Birkhoff polytope and has length $1$, and that $\langle X, \ \rangle$ ranges between $1$ and $-1/(n-1)$ on the Birkhoff polytope, for width $n/(n-1)$. Can anyone beat this? Aug 27 '19 at 21:13
• Cool, the answer is not 2 after all, thanks! What I really want to know is that the answer is not something like $1/n$ or $1/\sqrt n \ldots$ Aug 27 '19 at 21:17
• The Birkhoff polytope contains the ball of radius $1/n$ around the matrix all of whose entries are $1/n$, so a lower bound is $2/n$. Aug 27 '19 at 21:18
• Just to be clear, the scalar product that you are using on the space of $d\times d$ matrices is the trace one $\langle A,B\rangle= Tr(A^T B)$, right? Aug 28 '19 at 7:48

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

• Conceptual proof that $\sum_{\sigma \in S_n} (\mathrm{Tr}(\sigma X))^2$ is a scalar multiple of $\mathrm{Tr}(X^T X)$, given that the rows and columns of $X$ sum to $0$: The space of matrices with row and column sum $0$ is an irreducible $S_n \times S_n$ representation, so Schur's lemma tells us that there is only one invariant quadratic form on it up to scalar multiple. Aug 28 '19 at 10:08
• Gosh that Erdos probabilisic counting trick is pretty nifty! Thanks a million for the answer, I was way off. Aug 29 '19 at 10:47