By Tigran Saluev


2019-03-12 16:45:28 8 Comments

Consider the set $\mathbb{R}^{m \times n}$ of $m \times n$ matrices. I am particularly interested in properties of polytope $P$ defined as a convex hull of all $\{-1,1\}$ matrices of rank $1$, that is,

$$ P = \mbox{conv} \{ uv^T : u \in \{-1,1\}^m, v \in \{-1,1\}^n \}. $$

In particular, I would like to know how all ($mn-1$)-dimensional faces of this polytope and the corresponding normals can be described. Is there any research on that? Maybe this polytope has a name or belongs to a nontrivial class I could find research on?

1 comments

@Guillaume Aubrun 2019-03-19 11:03:54

That polytope $P_{m,n}$ appears under many names : correlation polytope, Bell polytope, local hidden variable polytope, local polytope (sometimes these names refer to slightly different polytopes), and probably more. It is the unit ball for the projective norm on $\ell_{\infty}^m \otimes \ell_{\infty}^n$.

The facial structure of $P_{m,n}$ has attracted a lot of attention since 1-codimensional faces of $P_{m,n}$ are in 1-1 correspondance with Bell inequalities from quantum physics. See for example that website (restrict to $N=2$ if you want to consider only matrices and not higher order tensors).

Besides small values of $m$, $n$ a complete description of faces seems out of reach. It follows from general considerations on the complexity of polytopes that the number of faces of $P_{m,n}$ has to grow at least exponentially in $\min(m,n)$, which somehow explains that the facial structure is complicated. The order of growth of the number of faces of $P_{n,n}$ seems unknown (is it exponential in $n$, or super-exponential?). You can look at chapter 11.2 of our book "Alice and Bob meet Banach" for more information.

Related Questions

Sponsored Content

0 Answered Questions

Name for facet of a cone containing all but one edge

2 Answered Questions

1 Answered Questions

0 Answered Questions

intriguing Polytope

0 Answered Questions

2 Answered Questions

[SOLVED] Convex hull of total orders

Sponsored Content