# Convex hull of all rank-$1$ $\{-1, 1\}$-matrices?

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?

• Isnt this just the set of all matrices with entries between -1 and 1? Or is there a countwrexample? – user35593 Mar 12 '19 at 16:58
• @user35593 for $m = n = 2$, it isn't; the $8$ given points (if we write them as $(a_{11}, a_{12}, a_{21}, a_{22})$, they are $(1, 1, 1, 1), (1, 1, -1, -1), (1, -1, 1, -1), (1, -1, -1, 1), (-1, -1, -1, -1),$ and their opposites) can't convexly generate $(1, -1, -1, -1) = \frac{1}{2}(-1, -1, -1, -1) + \frac{1}{2} (1, 1, -1, -1) + \frac{1}{2} (1, -1, 1, -1) + \frac{1}{2} (1, -1, -1, 1)$ (or any of the other rank 2 $\{-1, 1\}$ matrices. – user44191 Mar 12 '19 at 17:10
• Suppose that $X=u^Tv$ is an $m\times n$ matrix of rank $1$, given by vectors $u$ and $v$ with entries $\pm 1$. Fix indices $a,c\in [1,m]$ and $b,d\in [1,n]$ such that $a\neq c$ and $b\neq d$. Because of $X_{ab}X_{cd}=u_av_bu_cv_d=X_{ad}X_{cb}$, it cannot happen that exactly three of the four numbers $X_{ab}$, $X_{ad}$, $X_{cb}$, $X_{cd}$ are positive, or that exactly three of them are negative. Hence, besides the aforementioned family of inequalities of the form $-1\leq X_{ab}\leq 1$ we obtain another family of inequalities of the form $$-2\leq X_{ab}+X_{ad}+X_{cb}-X_{cd}\leq 2.$$ – Philipp Lampe Mar 13 '19 at 10:18
• For the $m=n$ case, take a look at the vertices of the elliptope. – Rodrigo de Azevedo Mar 13 '19 at 14:51
• @PhilippLampe That's essentially the CHSH inequality, right? – user44191 Mar 13 '19 at 16:05

## 1 Answer

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.