# Communication complexity: fooling set bound for inner product function

I am trying to prove that the fooling set method does not give a good lower bound for the communication complexity of the inner product function. Specifically, I am trying to show that the best bound we get using the fooling set method is $$D(IP) \geq \Omega(\log n)$$

$$D(IP)$$ is the deterministic communication complexity of the inner product function. This implies that any fooling set for the inner product cannot have more than $$n^2$$ elements. How do I show this? I can verify the statement for specific instances, but I have no intuition for the proof.

Let $$(x_i,y_i)$$ be a fooling set for inner product, of size $$m$$. Construct an $$m \times n$$ matrix $$X$$ whose rows are $$x_i$$ and an $$n \times m$$ matrix $$Y$$ whose columns are $$y_i$$, and consider the matrix $$M = XY$$ (arithmetic is over the field $$\mathbb{F}_2$$). The decomposition $$M=XY$$ shows that $$M$$ has rank at most $$n$$.
Suppose first that $$\mathrm{IP}(x_i,y_i) = 1$$ for all $$i$$, and so for each $$i \neq j$$, either $$\mathrm{IP}(x_i,y_j) = 0$$ or $$\mathrm{IP}(x_j,y_i) = 0$$. Consider the Hadamard (entrywise) product of $$M$$ and $$M^T$$. It is known that rank is submultiplicative with respect to entrywise product, and so the rank of $$M \circ M^T$$ is at most $$n^2$$. On the other hand, $$M \circ M^T$$ is the identity matrix, and so has rank $$m$$. We conclude that $$m \leq n^2$$.
When $$\mathrm{IP}(x_i,y_i) = 0$$ for all $$i$$, we consider the matrix $$M' = M+J$$, where $$J$$ is the all ones matrix. Since $$J$$ has rank 1, the rank of $$M'$$ is at most $$n+1$$, and so the argument in the preceding paragraph shows that $$m \leq (n+1)^2$$.