🚀 go-pugleaf

As I understand it Michael Cohen's question is this:  Let A be
the anti-symmetric n x n matrix with all 1's above the diagonal
and all -1's below.  Let U be the convex hull of the orbit of
A under the action of conjugation by permutation matrices.
What are the codimension one faces of U?

I can't answer this question, but I have evidence that the answer
could be very complicated.  First, here are some properties of U:

U actually lives in a vector subspace of A because the k'th row of a
matrix in U must have the same sum as the k'th column.  However, since
the whole matrix adds to zero this is really only n-1 constraints, so
we've identified a subspace V of dimension (n-1)(n-2)/2 that contains
U.  But in this subspace U has content, because the linear span of U
must be a representation of the symmetric group, and V is an
irreducible respresentation.  Note also that U is a centrally symmetric
polytope, because conjugation by the antidiagonal negates the
matrix A.

There is a theorem due to Milman (and perhaps Bourgain?) that the
number of faces times the number of edges of a centrally symmetric
polytope in k dimensions is bounded below by some C^k.  Perhaps C=2 is
a viable value, but the proof only derives that C is 1 plus a small
number not worth worrying about.  For us, however, k=n^2, and C^n^2
grows much faster than n!.  There will asymptotically be a huge number
of orbits of faces under the action of the permutation group.
Therefore there is no a priori symmetry reason that the faces are
nice.

However, I do know of one example of a polytope with many more faces
than symmetries which is nevertheless nice.  It's the convex hull of
permutation matrices which are symmetric and have zeroes on the
diagonal.  Do you want to do linear programming?  For the polytope I
have just mentioned, there is a way to do linear programming in
guaranteed polynomial time where you never consider all faces at once,
only those you encounter.  It's possible that there is also such an
algorithm for your polytope.

				Greg