16
$\begingroup$

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?

Improve this question
$\endgroup$
8
  • $\begingroup$ Isnt this just the set of all matrices with entries between -1 and 1? Or is there a countwrexample? $\endgroup$
    – user35593
    Commented Mar 12, 2019 at 16:58
  • 4
    $\begingroup$ @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. $\endgroup$
    – user44191
    Commented Mar 12, 2019 at 17:10
  • 4
    $\begingroup$ 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.$$ $\endgroup$
    – Philipp Lampe
    Commented Mar 13, 2019 at 10:18
  • 1
    $\begingroup$ For the $m=n$ case, take a look at the vertices of the elliptope. $\endgroup$
    – Rodrigo de Azevedo
    Commented Mar 13, 2019 at 14:51
  • 4
    $\begingroup$ @PhilippLampe That's essentially the CHSH inequality, right? $\endgroup$
    – user44191
    Commented Mar 13, 2019 at 16:05

1 Answer 1

Reset to default
12
+50
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .