<p><span class="math-container">$\newcommand{\F}{\mathbb{F}}\newcommand{\R}{\mathbb{R}}$</span>
Question is in the title basically: does there exist a Boolean matrix <span class="math-container">$M$</span> where <span class="math-container">$\operatorname{rank}_{\F_2}(M)=r$</span> but <span class="math-container">$\operatorname{rank}_{\R}(M)=2^r$</span>? Does such a matrix exist for all positive <span class="math-container">$r$</span>? 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.</p>
<p>I’ve thought about the simplest case where Boolean and real rank differ, namely <span class="math-container">$A=\begin{bmatrix} 1&amp;1&amp;0\\1&amp;0&amp;1\\0&amp;1&amp;1\end{bmatrix}$</span> where the real rank is <span class="math-container">$3$</span> but the <span class="math-container">$\F_2$</span>-rank is <span class="math-container">$2$</span>. By taking successive tensor powers of <span class="math-container">$A$</span>, I can obtain matrices where real and Boolean rank achieve arbitrarily large multiplicative separation (a factor of <span class="math-container">$(2/3)^n$</span>) but I want logarithmic separation. I have some ideas about generalizing the construction of <span class="math-container">$A$</span> to get what I want (the list of all even parity elements of <span class="math-container">$\{0,1\}^n$</span> as a matrix has dimension <span class="math-container">$(n-1)$</span> in <span class="math-container">$\F_2$</span>) but there are some complications that arise. Would appreciate any ideas to proceed!</p>

CC BY-SA 4.0
2022-12-13T03:58:10.497Z
@NealYoung yeah my mistake, I edited my post to reflect that I'm looking for Boolean matrices, thanks
Ash
CC BY-SA 4.0
2022-12-13T05:21:06.110Z
Hadamard matrix, as mentioned in this related Q: https://cstheory.stackexchange.com/q/38381/129
Joshua Grochow
CC BY-SA 4.0
2022-12-15T17:38:57.807Z
@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
<linear-algebra><communication-complexity>
Boolean matrix $M$ with Boolean rank $r$ but real rank $2^r$
Ash
# Boolean matrix $M$ with Boolean rank $r$ but real rank $2^r$

(Asked by: username_0 on 2022-12-12)

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

**Tags:** linear-algebra, communication-complexity
> **Comments:**
> **username_0**: @NealYoung yeah my mistake, I edited my post to reflect that I'm looking for Boolean matrices, thanks  
> **username_1**: Hadamard matrix, as mentioned in this related Q: https://cstheory.stackexchange.com/q/38381/129  
> **username_0**: @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.  

---

## 0 answers

