9
$\begingroup$

Are there any graphic portrayals of von Neumann polytopes in low dimensions?

$\endgroup$
  • 2
    $\begingroup$ Is it the same as the Birkhoff polytope? $\endgroup$ – Igor Khavkine Sep 17 '14 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'Rourke Sep 17 '14 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é Henriques Sep 17 '14 at 22:29
11
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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:

enter image description here

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).

$\endgroup$
3
$\begingroup$

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)$.

$\endgroup$

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.