6
$\begingroup$

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:

enter image description here

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?

$\endgroup$
4
  • 2
    $\begingroup$ 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? $\endgroup$ Aug 27, 2019 at 21:13
  • $\begingroup$ 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 $ $\endgroup$
    – Daron
    Aug 27, 2019 at 21:17
  • 1
    $\begingroup$ 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$. $\endgroup$ Aug 27, 2019 at 21:18
  • 1
    $\begingroup$ 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? $\endgroup$ Aug 28, 2019 at 7:48

1 Answer 1

8
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$ Aug 28, 2019 at 10:08
  • $\begingroup$ Gosh that Erdos probabilisic counting trick is pretty nifty! Thanks a million for the answer, I was way off. $\endgroup$
    – Daron
    Aug 29, 2019 at 10:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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