# Birkhoff – von Neumann for “$k$-stochastic matrices”

Recall that a doubly-stochastic matrix is a square matrix with non-negative elements such the sum of the elements in every row, as well as in every column, is $$1$$. The set of doubly-stochastic matrices is described by the Birkhoff – von Neumann theorem. For the matrices of prime order $$p\ge 3$$, this theorem can be interpreted to describe the set of all functions $$w\colon\mathbb F_p^2\to\mathbb R^+$$ such that for some pair of fixed directions in $$\mathbb F_p^2$$, every line $$l$$ in any of these directions gets its exact share of the total mass of $$w$$: $$\sum_{x\in l} w(x) = \frac1p\,\sum_{x\in\mathbb F_p^2 } w(x). \tag{*}$$

Let's say that a line $$l\in\mathbb F_p^2$$ is even if it satisfies ($$*$$), and that a direction in $$\mathbb F_p^2$$ is even if all $$p$$ lines in this directions are even. Suppose that, instead of just two even directions (as in the Birkhoff – von Neumann theorem), there are $$k\ge 3$$ even directions. Intuitively, one can expect much more structure in this case.

For a prime $$p$$ and integer $$3\le k\le p$$, what is the set of all functions $$w\colon\mathbb F_p^2\to\mathbb R^+$$ possessing at least $$k$$ even directions?

In particular, isn't this set of functions the matching polytope of some graph?

• The naive conjecture is that it's given by the convex hull of special permutation matrices (those that have a 1 in every line paralel to any of the given directions). Is this known to be false? – Gjergji Zaimi Jan 23 at 22:04
• @GjergjiZaimi: this is hardly the case; at least, not for large values of $k$. For $k>p/2$, for instance, there do not exist any permutation matrices with $k$ even directions. – Seva Jan 24 at 11:16
• Isn't the indicator function of an arbitrary line that's not parallel to any of our directions always such a permutation? – Gjergji Zaimi Jan 25 at 16:57
• @GjergjiZaimi: Right, but this is the only exception. – Seva Jan 25 at 17:26
• Another equivalent way of phrasing my conjecture is that the vertices of this polytope (assuming we normalize the sum to 1 on each direction) are all lattice points. – Gjergji Zaimi Jan 25 at 19:46