26

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.

Shachar Lovett
  • 756
  • 6
  • 7
  • 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). – Joshua Grochow Jun 08 '17 at 07:03
  • 1
    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 Jun 08 '17 at 11:46
  • @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 Jun 08 '17 at 15:31
  • 4
    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 Jun 09 '17 at 02:59
  • 3
    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 Jun 09 '17 at 17:15
  • 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 Jun 10 '17 at 18:47
  • 1
    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 Jun 11 '17 at 16:44
  • 1
    As you've answered the original question, you could move the update into an answer... – Neal Young Aug 24 '18 at 12:37

0 Answers0