A certain submatrix of the correlation polytope

Question

I am kind of confused by the argument at the top of page 5 here, http://homes.cs.washington.edu/~jrl/notes/bonn-lecture-notes.pdf

• Firstly given that the author wanted to look at quadratic multilinear functions on $\{0,1\}^n$ why is he finding it enough to look at functions of the form, $f(x) = a_0 + \sum_{i,j} A_{ij}(xx^T)_{ij}$ for some real symmetric matrix $A$ and a real number $a_0$?

  These $f$s won't have any linear term and doesn't that mean a loss of generality?

• The author defines the set $QML_n^+$ as the set of functions of the above type which are non-negative on the Boolean hypercube. Isn't this set an uncountably infinite set?

  Because I don't understand how the author now hopes to define a matrix $M_n$ whose rows seem indexes by $f \in QML_n^+$ and the columns seem indexed by $x \in \{0,1\}^n$ and the entries are $M_n(f,x) = f(x)$.

  How does this make sense as a matrix (of finite dimensions!)?

• Given everything above how is it obvious that this matrix $M_n$ is a submatrix of some slack matrix of the correlation polytope $conv(\{ xx^T \vert x \in\{0,1\}^n \})$ ?

Answer 1

Every quadratic multilinear polynomial can be written as $$ a_0 + \sum_i a_{ii} x_i + \sum_{i \neq j} a_{ij} x_i x_j = a_0 + \sum_i a_{ii} x_i^2 + \sum_{i \neq j} a_{ij} x_i x_j, $$ using the fact that $x_i^2 = x_i$ for every $x_i \in \{0,1\}$. This clearly equals $a_0 + \sum_{ij} A_{ij} x_i x_j$, which in turn is the same as what you wrote.

Regarding the matrix $M_n$, it is indeed infinite. For the proof that it is a submatrix of some slack matrix of the correlation polytope, see Lemma 2.8 of these lecture notes by James Lee.

If you have any more questions on the Bonn lecture notes, I suggest looking in the cited lecture notes, which seem to be more thorough.