# Bipartite formula complexity lower bound

I'm trying to understand the paper The Bipartite Formula Complexity of Inner Product is Quadratic, by Avishay Tal. The argument is recapped here. I am having trouble understanding the proof Theorem 3 from that page.

The approach is to construct an polynomial approximation $$p$$ for the function $$f$$, and then show that the matrix $$M_f$$ is equal to the matrix consisting of sign$$(p(x,y))$$ for each entry $$x,y$$.

My question is regarding the following sentence, found on the very last paragraph of the page:

Each summand on the right-hand side corresponds to a matrix of rank 1 over the reals.

I do understand why this must be true. If I construct a matrix with coordinates corresponding to, say, the first summand evaluated at $$x,y$$ for each row/column $$x,y$$, I don't see why it must be rank-one.

• Rank is 1, because every row is a scalar multiple of any fixed row. These scalars are determined by the values of the $f_i$s on the corresponding rows. The same holds also for columns: here scalars are determined by the values of the $g_i$s. – Stasys Jul 6 '19 at 17:06
• You can now write $M=\sum_{S\subseteq[s]:|S|\leq d} c_S A_S B_S$, where $A_S \in \mathbb{R}^{N\times 1}$ and $B_S \in \mathbb{R}^{1\times N}$ are vectors defined as $A_S[x]=\prod_{i\in S} f_i(x), B_S[y]=\prod_{i\in S} g_i(y)$. From the dimension of $A_S$, $\textrm{rank}(A_S)\leq 1$, and, thus, $\textrm{rank}(c_S A_S B_S)\leq 1$. From sub-additivity of rank, the rank of the whole sum is now bounded from above by the total number of terms $s^{O(d)}$. – Alex Golovnev Jul 9 '19 at 18:31