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!

Improve this question
$\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$
    – Joshua Grochow
    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

Reset to default

Your Answer

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