2
$\begingroup$

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?

Thank you for your help.

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.

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

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()
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Canine360 Jun 9 at 16:20
  • $\begingroup$ 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). $\endgroup$ – darij grinberg Jun 11 at 16:59
  • $\begingroup$ 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)? $\endgroup$ – Canine360 Jun 17 at 12:25
  • $\begingroup$ Are you sure they are TUM when combined with the doubly stochastic matrix conditions? $\endgroup$ – darij grinberg Jun 17 at 12:34

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.