Are there any graphic portrayals of von Neumann polytopes in low dimensions?
$\begingroup$
$\endgroup$
3
-
2$\begingroup$ Is it the same as the Birkhoff polytope? $\endgroup$– Igor KhavkineCommented Sep 17, 2014 at 19:03
-
2$\begingroup$ The Birkoff-vonNeumann polytope (if that's what you mean) lives in $\mathbb{R}^{n^2}$, so it is difficult to picture for $n>1$. I think for $n=2$, it is a segment in $\mathbb{R}^4$. $\endgroup$– Joseph O'RourkeCommented Sep 17, 2014 at 19:11
-
14$\begingroup$ As a general good practice, I recommend including a definition of the terminology needed to understand a question (specially if the question is very short, as is the case here). $\endgroup$– André HenriquesCommented Sep 17, 2014 at 22:29
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
0
One can get some intuition for what this polytope $\mathcal{B}_n$ looks like from the fact that the face lattice of $\mathcal{B}_n$ is isomorphic to the set of all subsets $S$ of $[n]\times[n]$ (where $[n]=\lbrace 1,2,\dots,n\rbrace$), ordered by inclusion, such that $S$ is the support of a doubly-stochastic matrix, together with the empty face. For instance, when $n=3$ the 3-dimensional faces correspond to removing a single element from $[3]\times [3]$ (so there are nine of them), the 2-faces correspond to removing two elements, no two in the same row or column (so 18 of them), the 1-faces (edges) from removing three elements, no two in the same row or column (six of them), or by choosing an element $(i,j)\in [3]\times[3]$ and removing the two elements in the same row and the two elements in the same column as $(i,j)$ (so nine of them). The 0-faces (vertices) are of course the supports of the six permutation matrices. The $f$-vector is thus $(6, 15,18,9)$. A graphical portrayal of this 4-dimensional polytope would be messy.
answered Sep 17, 2014 at 23:22
$\begingroup$
$\endgroup$
0
This answer is meant to supplement the second part of Richard Stanley's answer.
Given a natural number $n$, the von Neumann (or Birkhoff) polytope is defined as the convex hull of $n \times n$ permutation matrices. Its ambient space is therefore $\mathbb{R}^{n^2}$ as Joseph O'Rourke points out in his comment. However, its dimension is $(n-1)^2$. So for $n = 3$ you get a $4$-dimensional polytope whose Schlegel diagram looks as follows:
The vertices I used are: $0 = (1, 0, 0, 1)$, $1 = (0, 0, 0, 1)$, $2 = (0, 0, 1, 0)$, $3 = (0, 1, 1, 0)$, $4 = (0, 1, 0, 0)$, $5 = (1, 0, 0, 0)$ (sorry for the awkward notation, it was chosen by Polymake).
$\begingroup$
$\endgroup$
The set of doubly stochastic matrices is a subset of the set of nonnegative $n \times n$ matrices whose sum of entries is $n$.
These matrices form an $(n^2-1)$-dimensional simplex in $\mathbb{R}^{n^2}$, whose vertices are the $n^2$ matrices (written as row vectors of length $n^2$) $(n,0,0,...,0)$, $(0,n,0,...,0)$, ..., $(0,0,... 0,n)$.
The vertices of the Birkhoff polytope are the arithmetic means of $n$ of these - suitably chosen - matrices.
For $n=2$ the Birkhoff polytope lies within a tetrahedron, between the midpoints of the edges that connect points $1 = (2, 0, 0, 0)$ and $4 = (0, 0, 0, 2)$ and points $2 = (0, 2, 0, 0)$ and $3 = (0, 0, 2, 0)$.
answered Jul 16, 2017 at 0:25