Timeline for Birkhoff – von Neumann for "$k$-stochastic matrices"
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 27, 2019 at 3:15 | comment | added | Brendan McKay | Note to my previous comment: Each of these examples are the convex hulls of some set of permutation matrices. For example, the permutation matrices $A=1$, $B=1$ and $C=1$ in the first case. | |
| Jan 27, 2019 at 3:12 | comment | added | Brendan McKay | Examples are given by orthogonal arrays. For example, consider $k=3$ and the $3\times 3$ square shown at en.wikipedia.org/wiki/Graeco-Latin_square . Choose any $A,B,C$ summing to 1. Then as well as the rows and columns each summing to 1, the positions containing $\alpha$ sum to 1 and similarly for $\beta$ and $\gamma$. A projective plane will provide $p-1$ separate directions, such as the example for $p=5$ given in the section "Mutually orthogonal Latin squares". I suspect these examples are not representative of all examples. | |
| Jan 26, 2019 at 19:25 | history | edited | Seva | CC BY-SA 4.0 |
deleted 156 characters in body
|
| Jan 26, 2019 at 19:16 | comment | added | Seva | @GjergjiZaimi: I can neither prove nor disprove your conjecture, but if true, it implies that for $k>p/2$, every $k$-stochastic matrix is a convex combination of "linear matrices". That is, every function $w\colon\mathbb F_p^2\to\mathbb R^+$ with $(p+1)/2$ or more even directions is a convex combination of the indicator functions of lines. | |
| Jan 25, 2019 at 19:46 | comment | added | Gjergji Zaimi | 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. | |
| Jan 25, 2019 at 17:26 | comment | added | Seva | @GjergjiZaimi: Right, but this is the only exception. | |
| Jan 25, 2019 at 16:57 | comment | added | Gjergji Zaimi | Isn't the indicator function of an arbitrary line that's not parallel to any of our directions always such a permutation? | |
| Jan 25, 2019 at 8:05 | history | edited | Fedor Petrov | CC BY-SA 4.0 |
added 3 characters in body
|
| Jan 24, 2019 at 11:16 | comment | added | Seva | @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. | |
| Jan 23, 2019 at 22:04 | comment | added | Gjergji Zaimi | 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? | |
| Jan 23, 2019 at 20:59 | history | asked | Seva | CC BY-SA 4.0 |