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.

Improve this question
$\endgroup$
8
  • 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, 2017 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, 2017 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, 2017 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, 2017 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, 2017 at 16:44

0

Reset to default

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.