# Rank of a particular matrix

Denote $P_{2n}$ to be collection of homogeneous total degree $2$ real polynomials in exactly $2n$ variables such that coefficient of every monomial is either $1$ or $-1$.

Split variable set into disjoint $S_r$, $S_c$ such that each of $S_r$, $S_c$ contains ${n}$ variables each.

Take an $f$ from $P_{2n}$.

Consider $n\times n$ matrix $M_f$ indexed by assigning row labels from variables in $S_r$, column labels from variables in $S_c$ with $(i,j)$ matrix entry given by evaluating polynomial on $\{0,1\}^{2n}$ such that only indices $i$ and $j$ of evaluation vector is $1$. Naturally $M_f$ is $\pm1$ valued.

What is good upper bound on $rank(M_f)$ if $\max_{\{0,1\}^{2n}}|f|=d$?

• Your notation is unclear. What is $|f|$? – kodlu Sep 10 '15 at 22:21
• Maximum absolute value over all points on the cube – Brout Sep 10 '15 at 22:42