4
$\begingroup$

$\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!

$\endgroup$
3
  • $\begingroup$ @NealYoung yeah my mistake, I edited my post to reflect that I'm looking for Boolean matrices, thanks $\endgroup$
    – Ash
    Dec 13, 2022 at 3:58
  • 5
    $\begingroup$ Hadamard matrix, as mentioned in this related Q: cstheory.stackexchange.com/q/38381/129 $\endgroup$ Dec 13, 2022 at 5:21
  • $\begingroup$ @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. $\endgroup$
    – Ash
    Dec 15, 2022 at 17:38

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.