26
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ 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). $\endgroup$ – Joshua Grochow Jun 8 '17 at 7:03
  • 1
    $\begingroup$ 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. $\endgroup$ – Gorav Jindal Jun 8 '17 at 11:46
  • 4
    $\begingroup$ 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. $\endgroup$ – Andrew Morgan Jun 9 '17 at 2:59
  • 3
    $\begingroup$ 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? $\endgroup$ – Robin Kothari Jun 9 '17 at 17:15
  • 1
    $\begingroup$ Robin - the question about degree was the motivation for the matrix question. The largest separation I know of is quadratic, given by this example. $\endgroup$ – Shachar Lovett Jun 11 '17 at 16:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.