# Proof involving the Birkhoff polytope

Setup:

Fix $$n$$. Let $$\mathcal{B}$$ denote the $$n$$-dimensional Birkhoff polytope, i.e. the set of all $$n \times n$$ doubly stochastic matrices. There is a fixed natural number $$N(n)$$. We drop the argument $$n$$ of $$N$$ for the rest of the question.

Suppose $$\Gamma=\mathcal{B}^N$$, i.e. the set of all ordered sets of $$N$$ points, each chosen independently from the Birkhoff polytope. Let a typical element of $$\Gamma$$ be denoted by $$x \equiv (x^1,\cdots,x^N)$$, where $$x^1,\cdots,x^N$$ are bistochastic matrices. Let $$x^k_{ij}$$ denote the $$(i,j)$$-th entry of the bistochastic matrix $$x^k$$.

Now we define $$S=\{x \in \Gamma: Ax=0, Bx \geq 0\}$$, where $$A$$ and $$B$$ are given linear transformations ($$A$$ and $$B$$ depend on $$n$$). Each row of each of $$A$$ and $$B$$ is of the form $$[0, \cdots, 0, 1, -1, 0, \cdots 0]$$, i.e. each linear restriction imposed by $$A$$ and $$B$$ only involve difference between two terms. It may also be worth mentioning that each of the difference-based restrictions contained in $$A$$ ($$B$$) is of the form $$x^k_{ij}-x^l_{ij}=0\;(\geq 0)$$, i.e. difference between corresponding entries of two bistochastic matrices from $$\Gamma$$. Other than these restrictions, $$A$$ and $$B$$ can be completely general.

What I'm trying to prove:

$$S$$ is obviously a polytope. I'm trying to prove it has integral extreme points, i.e. its extreme points consist only of entries in $$\{0,1\}$$. It is my conjecture that this holds for any $$A$$ and $$B$$ of the form described above.

My approach:

Consider $$I=\{x \in \Gamma: Ax=0\}$$. Clearly $$S \subseteq I$$. Then I have used the exact same logic as given in the proof of the Birkhoff-von Neumann theorem here to argue that $$I$$ cannot have fractional extreme points. Essentially the logic is as follows: If there exists any entry of any element of $$\Gamma$$ which is in $$(0,1)$$, then there has to exist a cycle - of even length - of entries in $$(0,1)$$, such that each of the entries in this cycle can be increased and decreased by the same $$\epsilon$$ amount, while still staying inside $$\Gamma$$. In my case I know the cycle has to be of even length because the part of the cycle inside each bistochastic matrix has to be of even length, by the Birkhoff-von Neumann proof, and each point $$x \in \Gamma$$ is just an ordered set of bistochastic matrices. Therefore $$I$$ has integral extreme points.

By the above logic, any subset of $$\Gamma$$, defined by equalities of the form $$x^k_{ij}-x^l_{ij}=0$$ has extreme points consisting only of entries in $$\{0,1\}$$.

Questions:

First question - is this argument correct?

Secondly, how do we bring the inequality constraints, $$Bx \geq 0$$, into this framework and make any conclusions about integral or fractional extreme points?

EDIT1:

Subsequently I've thought as follows (basically continuing the above approach but trying to incorporate the $$Bx \geq 0$$ constraints). Suppose there exists a point $$x \in S$$ with a fractional element somewhere. Suppose at this point some of the $$Bx \geq 0$$ inequalities hold with equality (zero of the $$Bx \geq 0$$ inequalities can also hold with equality). Then just include those equalities in the set of equality constraints in $$I$$ and repeat the same argument. The $$Bx \geq 0$$ inequalities which do not bind don't pose any difficulty because by finiteness of the system (number of coordinates and number of constraints) we can always choose $$\epsilon$$ small enough to make the proof work.

Again, I'm not sure if this is correct. Thanks in advance everyone.

EDIT2:

If you want to impose additional assumptions on $$A$$ or $$B$$ (but they have to satisfy the properties already specified) that's fine too, for the time being.

• Also posted to MO, without notification to either site: mathoverflow.net/questions/333059/… – Gerry Myerson Jun 2 at 1:11
• Yes, correct. Is that not allowed? – Canine360 Jun 2 at 1:37
• Would you call two different stores at the same time to order a pizza? – Gerry Myerson Jun 2 at 5:59

I cannot follow your logic. Why do you get a full cycle? It may well happen that some entry in a matrix $$x^i$$ can be increased/decreased, but no other entries in its row or column have this freedom, since they are constrained by conditions coming from $$A$$ or $$B$$ that link them to corresponding entries of other matrices $$x^j$$.

I also think the claim of your question is false, even if $$B$$ has no rows (so the $$n$$-tuple is only restricted by equalities between some entries, not by inequalities). Here is a counterexample: Set $$n = 3$$ and $$N = 2$$, and let our two bistochastic matrices be $$x^1 = \begin{pmatrix} a & b & c \\ d & e & f \\ g & h & i \end{pmatrix}$$ and $$x^2 = \begin{pmatrix} A & B & C \\ D & E & F \\ G & H & I \end{pmatrix}$$ (sorry for re-using the letters $$A$$ and $$B$$). Further constrain them by requiring $$f = F$$ and $$g = G$$. (This yields a $$2$$-row matrix $$A$$ and a $$0$$-row matrix $$B$$.) Then, the resulting polytope (in an $$18$$-dimensional space) has $$(1/2, 0, 1/2, 0, 1/2, 1/2, 1/2, 1/2, 0, 1/2, 1/2, 0, 0, 1/2, 1/2, 1/2, 0, 1/2)$$ as one of its vertices. This vertex corresponds to the two matrices $$x^1 = \begin{pmatrix} 1/2 & 0 & 1/2 \\ 0 & 1/2 & 1/2 \\ 1/2 & 1/2 & 0 \end{pmatrix}$$ and $$x^2 = \begin{pmatrix} 1/2 & 1/2 & 0 \\ 0 & 1/2 & 1/2 \\ 1/2 & 0 & 1/2 \end{pmatrix}$$. There is a Sudoku-style manual proof of the fact that this is indeed a vertex; alternatively, here is a SageMath program that computes all the $$18$$ vertices:

Q.<a,b,c,d,e,f,g,h,i,A,B,C,D,E,F,G,H,I> = PolynomialRing(QQ)

vars = Q.gens()

def ieq(p):
# Transform a degree-1 polynomial like a + 2b - c - 5
# into a tuple of coefficients that can later be
# entered into the ieqs or eqns attributes of
# the Polyhedron constructor, where it will be
# interpreted as a + 2b - c \geq 5 or
# a + 2b - c = 5, respectively.
return map(QQ, tuple([p.coefficient({j: 0 for j in vars})] + [p.coefficient({j: int(j==i) for j in vars}) for i in vars]))

birk1ieqs = [a, b, c, d, e, f, g, h, i]
birk1eqs = [a+b+c-1, d+e+f-1, g+h+i-1, a+d+g-1, b+e+h-1, c+f+i-1]
birk2ieqs = [A, B, C, D, E, F, G, H, I]
birk2eqs = [A+B+C-1, D+E+F-1, G+H+I-1, A+D+G-1, B+E+H-1, C+F+I-1]
extraeqs = [f-F, g-G]

full_ieqs = map(ieq, birk1ieqs) + map(ieq,birk2ieqs)
full_eqs = map(ieq, birk1eqs) + map(ieq,birk2eqs) + map(ieq,extraeqs)

print Polyhedron(ieqs=full_ieqs, eqns=full_eqs).vertices()

• Thank you so much. This is very useful. As I said, we can impose additional restrictions on $A$ and $B$. Let me add that two matrices $x^k$ and $x^l$ can be linked through equalities only along the same column. Two different matrices cannot have equalities running between them across more than one different columns. But more importantly - I later realized - aren't A and B totally unimodular and hence extreme points should be integral anyway? Rather what conditions do we need to impose on the type of equalities/inqualities to ensure that it is? – Canine360 Jun 9 at 16:20
• So you want to restrict yourself to two bistochastic matrices linked by equalities, all in one column? That looks like it has a better chance at being true (I checked the $3\times 3$ and $4\times 4$ cases). – darij grinberg Jun 11 at 16:59
• The number of matrices doesn't have to be two, of course. But the nature of $A$ and $B$ are such that no two matrices are linked by equalities/inequalities across columns. But as I mentioned, if we try the TUM approach, why would that not work? I thought A and B are TUM. If not, would they become TUM with this additional condition (no two matrices are linked by equalities/inequalities across columns)? – Canine360 Jun 17 at 12:25
• Are you sure they are TUM when combined with the doubly stochastic matrix conditions? – darij grinberg Jun 17 at 12:34