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: enter image description here

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?


Have you tried using Lagrange Multipliers?

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!

  • $\begingroup$ With this method, all you can do is prove our guess is a critical point. In general those guys can be minima, maxima or "saddlepoints". So you need a way of ruling out that you have not just found the maximiser for example. $\endgroup$ – Daron Aug 26 '19 at 17:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.