# Boolean matrix $M$ with Boolean rank $r$ but real rank $2^r$

$$\newcommand{\F}{\mathbb{F}}\newcommand{\R}{\mathbb{R}}$$ Question is in the title basically: does there exist a Boolean matrix $$M$$ where $$\operatorname{rank}_{\F_2}(M)=r$$ but $$\operatorname{rank}_{\R}(M)=2^r$$? Does such a matrix exist for all positive $$r$$? This relates to questions I have about the log-rank conjecture for real rank potentially generalizing to Boolean rank, which I’m fairly sure doesn’t, but I want to be convinced.

I’ve thought about the simplest case where Boolean and real rank differ, namely $$A=\begin{bmatrix} 1&1&0\\1&0&1\\0&1&1\end{bmatrix}$$ where the real rank is $$3$$ but the $$\F_2$$-rank is $$2$$. By taking successive tensor powers of $$A$$, I can obtain matrices where real and Boolean rank achieve arbitrarily large multiplicative separation (a factor of $$(2/3)^n$$) but I want logarithmic separation. I have some ideas about generalizing the construction of $$A$$ to get what I want (the list of all even parity elements of $$\{0,1\}^n$$ as a matrix has dimension $$(n-1)$$ in $$\F_2$$) but there are some complications that arise. Would appreciate any ideas to proceed!

• @NealYoung yeah my mistake, I edited my post to reflect that I'm looking for Boolean matrices, thanks
– Ash
Dec 13, 2022 at 3:58
• Hadamard matrix, as mentioned in this related Q: cstheory.stackexchange.com/q/38381/129 Dec 13, 2022 at 5:21
• @JoshuaGrochow Thanks, yeah in hindsight this makes a lot of sense as the inner-product matrix is sort of constructed to be a subspace of $\{0,1\}^n$, and it's real rank is high through a relabeling and tensoring argument.
– Ash
Dec 15, 2022 at 17:38