<p>Let $A$ be a boolean matrix (eg with $0,1$ entries). Assume that $A$ has rank $\le r$ both over $\mathbb{F}_2$ and over $\mathbb{F}_3$. Does this imply that $A$ has low rank over the reals? This seems highly unlikely to me, but I cannot find a counterexample.</p>

<p>Note that if we require that $A$ has low rank just over one characteristic (say $\mathbb{F}_2$) then the Hadamard matrix shows an exponential gap (i.e. rank $r$ over $\mathbb{F}_2$; rank $2^r$ over the reals), which is tight. However, this example does not seem to carry over when we require low rank in two different characteristics.</p>

<hr>

<p>Update 6/9:
Li Qian gave a super-polynomial separation: a matrix $A$ with rank $r$ modulo 2 and modulo 3, but rank approximately $r^{\log r}$ over the reals. So I guess the real question is: is this the largest separation?</p>

<p>To build it, consider first boolean functions $f:\{0,1\}^n \to \{0,1\}$. Take the $2^n \times 2^n$ matrix $A$ given by $A_{x,y} = f(x \wedge y)$, where $x \wedge y$ is the bit-wise AND. The rank of $A$ (in any field) equals the number of monomials in the polynomial representation of $f$, which is essentially controlled by the degree of $f$.</p>

<p>Let $n=k^2$. Take </p>

<p>$$f(x_1,\ldots,x_n)=MOD_2(MOD_3(x_1,\ldots,x_k),MOD_3(x_{k+1},\ldots,x_{2k}),\ldots,MOD_3(x_{n-k+1},\ldots,x_n))$$ </p>

<p>where $MOD_p(\cdot)$ is the boolean function which returns 1 if its input hamming weight is divisible by $p$. Then one can check that $f$ has degree $O(\sqrt{n})$ modulo 2 and modulo 3, but linear degree over the reals. This translates to a matrix $A$ with rank $n^{O(\sqrt{n})}$ modulo 2 and modulo 3, but rank $2^{\Omega(n)}$ over the reals.</p>

CC BY-SA 3.0
2017-06-08T07:03:35.300Z
FYI, some things found by computer experiment: exhaustive search through 5x5 revealed no matrices that are singular mod 2 and mod 3, but w/ rank mod 2 and rank mod 3 < rational rank. But 5 is very small. If instead we take a random $n \times n$ matrix mod 2 with rank at most $r$, we find that very frequently the matrix is singular mod 3 but has much higher rank mod 3 than mod 2. Sometimes, though rarely, the real rank is higher than the mod 3 rank, but I haven't found examples where the two differ by a lot (I've looked at matrices up to 128 x 128).
Joshua Grochow
CC BY-SA 3.0
2017-06-08T11:46:06.963Z
Just a trivial observation, If one can find some gap in ranks in $\mathbb{Z}_6$ and $\mathbb{R}$ then one can boost to arbitray gaps by Kronecker product or direct sum of of matrices.
Gorav Jindal
CC BY-SA 3.0
2017-06-08T15:31:56.867Z
@GoravJindal: Indeed, given $s \times s$ matrices with mod 6 rank $c$ and real rank $d > c$, using Kronecker product one gets size $N=s^k$ matrices with mod 6 rank $c^k = N^{\log_s c}$ and real rank $N^{\log_s d}$, so the gap is only polynomial in the size of the matrices; I don't know if Shachar is looking for a bigger gap than this?
Joshua Grochow
CC BY-SA 3.0
2017-06-09T02:59:58.907Z
One small explicit example where the real rank is strictly larger than the mod 2 and mod 3 rank is given by taking a 7x7 all-ones matrix and zeroing the diagonal. It has full rank over the reals, but is singular mod 2 and mod 3. In general, if the characteristic polynomial's lowest degree term (with a nonzero coefficient) has a coefficient divisible by 6, then the rank will drop mod 2 and mod 3.
Andrew Morgan
CC BY-SA 3.0
2017-06-09T17:15:35.763Z
Do you know what the answer is for the query complexity analogue of this question, i.e., the maximum separation between the maximum of $F_2$ degree and $F_3$ degree vs real degree? Is quadratic the best possible separation in that setting?
Robin Kothari
CC BY-SA 3.0
2017-06-10T18:47:34.583Z
Perhaps circulant matrices could provide a larger gap?  Recall that the rank of a circulant matrix C is $n-d$, where $d=gcd(f(x),x^n-1)$ and $f(x)$ is a polynomial with coefficients taken from the first row of $C$.  Maybe someone more knowledgeable about cyclotomic polynomials could actually develop this idea :)
Bill Bradley
CC BY-SA 3.0
2017-06-11T16:44:30.023Z
Robin - the question about degree was the motivation for the matrix question. The largest separation I know of is quadratic, given by this example.
Shachar Lovett
CC BY-SA 4.0
2018-08-24T12:37:56.587Z
As you've answered the original question, you could move the update into an answer...
Neal Young
<linear-algebra><matrices><boolean-matrix>
Rank mod 6 vs rank over the reals
Shachar Lovett
# Rank mod 6 vs rank over the reals

(Asked by: username_0 on 2017-06-07)

Let $A$ be a boolean matrix (eg with $0,1$ entries). Assume that $A$ has rank $\le r$ both over $\mathbb{F}\_2$ and over $\mathbb{F}\_3$. Does this imply that $A$ has low rank over the reals? This seems highly unlikely to me, but I cannot find a counterexample.

Note that if we require that $A$ has low rank just over one characteristic (say $\mathbb{F}\_2$) then the Hadamard matrix shows an exponential gap (i.e. rank $r$ over $\mathbb{F}\_2$; rank $2^r$ over the reals), which is tight. However, this example does not seem to carry over when we require low rank in two different characteristics.

---

Update 6/9:
Li Qian gave a super-polynomial separation: a matrix $A$ with rank $r$ modulo 2 and modulo 3, but rank approximately $r^{\log r}$ over the reals. So I guess the real question is: is this the largest separation?

To build it, consider first boolean functions $f:\{0,1\}^n \to \{0,1\}$. Take the $2^n \times 2^n$ matrix $A$ given by $A\_{x,y} = f(x \wedge y)$, where $x \wedge y$ is the bit-wise AND. The rank of $A$ (in any field) equals the number of monomials in the polynomial representation of $f$, which is essentially controlled by the degree of $f$.

Let $n=k^2$. Take

$$f(x\_1,\ldots,x\_n)=MOD\_2(MOD\_3(x\_1,\ldots,x\_k),MOD\_3(x\_{k+1},\ldots,x\_{2k}),\ldots,MOD\_3(x\_{n-k+1},\ldots,x\_n))$$

where $MOD\_p(\cdot)$ is the boolean function which returns 1 if its input hamming weight is divisible by $p$. Then one can check that $f$ has degree $O(\sqrt{n})$ modulo 2 and modulo 3, but linear degree over the reals. This translates to a matrix $A$ with rank $n^{O(\sqrt{n})}$ modulo 2 and modulo 3, but rank $2^{\Omega(n)}$ over the reals.

**Tags:** linear-algebra, matrices, boolean-matrix
> **Comments:**
> **username_1**: FYI, some things found by computer experiment: exhaustive search through 5x5 revealed no matrices that are singular mod 2 and mod 3, but w/ rank mod 2 and rank mod 3 < rational rank. But 5 is very small. If instead we take a random $n \times n$ matrix mod 2 with rank at most $r$, we find that very frequently the matrix is singular mod 3 but has much higher rank mod 3 than mod 2. Sometimes, though rarely, the real rank is higher than the mod 3 rank, but I haven't found examples where the two differ by a lot (I've looked at matrices up to 128 x 128).  
> **username_2**: Just a trivial observation, If one can find some gap in ranks in $\mathbb{Z}_6$ and $\mathbb{R}$ then one can boost to arbitray gaps by Kronecker product or direct sum of of matrices.  
> **username_1**: @GoravJindal: Indeed, given $s \times s$ matrices with mod 6 rank $c$ and real rank $d > c$, using Kronecker product one gets size $N=s^k$ matrices with mod 6 rank $c^k = N^{\log_s c}$ and real rank $N^{\log_s d}$, so the gap is only polynomial in the size of the matrices; I don't know if Shachar is looking for a bigger gap than this?  
> **username_3**: One small explicit example where the real rank is strictly larger than the mod 2 and mod 3 rank is given by taking a 7x7 all-ones matrix and zeroing the diagonal. It has full rank over the reals, but is singular mod 2 and mod 3. In general, if the characteristic polynomial's lowest degree term (with a nonzero coefficient) has a coefficient divisible by 6, then the rank will drop mod 2 and mod 3.  
> **username_4**: Do you know what the answer is for the query complexity analogue of this question, i.e., the maximum separation between the maximum of $F_2$ degree and $F_3$ degree vs real degree? Is quadratic the best possible separation in that setting?  
> **username_5**: Perhaps circulant matrices could provide a larger gap?  Recall that the rank of a circulant matrix C is $n-d$, where $d=gcd(f(x),x^n-1)$ and $f(x)$ is a polynomial with coefficients taken from the first row of $C$.  Maybe someone more knowledgeable about cyclotomic polynomials could actually develop this idea :)  
> **username_0**: Robin - the question about degree was the motivation for the matrix question. The largest separation I know of is quadratic, given by this example.  
> **username_6**: As you've answered the original question, you could move the update into an answer...  

---

## 0 answers

