4
$\begingroup$

I'm looking for the tightest upper bound on the number of different binary matrices $A \in {\{-1,1\}^{m \times n}}$ for which $\mathrm{rank}(A)\leq r$. I'm interested in the regime $1 \ll r \ll m \leq n$.

I wonder if there is a way to get a better bound than $2^{mr+nr-r^2} m !$, which is the best bound I could derive (I'll be happy to show this if needed).

Thanks in advance!

$\endgroup$
  • 2
    $\begingroup$ Although this sounds like a trivial rephrasing of the problem, one thing you could do is ask ``if $A \in \{-1, 1\}^{m \times n}$ is chosen uniformly at random, what's the probability that $rank(A) \leq r$?" The reasons you might want to do this are (i) random matrices [and this problem in particular] have gotten lots of attention, and (ii) it can help with heuristic arguments. $\endgroup$ – Pat Devlin Nov 12 '16 at 18:53
  • 1
    $\begingroup$ Thanks! That's a good point I probably should have mentioned. I originally started working on this using this probabilistic approach and tried to find relevant results along these lines (for example, J. Bourgain, V. H. Vu, and P. M. Wood, "On the singularity probability of discrete random matrices", 2010), but I couldn't improve the bound further. $\endgroup$ – Daniel Soudry Nov 12 '16 at 19:24
4
$\begingroup$

The following observation goes back to Komlos's work in the 1960's deriving bounds on the probability that a $(0,1)$ matrix is singular:

Any such $A$ must have a collection of $r$ rows that contain the remainder in their span. By paying a $\binom{m}{r}$ multiplicative factor, we can assume that they are the first $r$ rows. Once we've done this, by paying an additional $\binom{n}{r}$ factor we can assume that the upper left $r \times r$ matrix of $A$ is full rank.

We can now think of our matrix as being made up of blocks: $$A=\left(\begin{array}{dd} W & X \\ Y & Z \end{array}\right),$$ where $W$ is $r \times r$, and invertible. The fact that the last $m-r$ rows are contained in the span of the first $r$ means that we must have $$Z=YW^{-1}X$$ In other words, $W, X, $ and $Y$ uniquely determine $Z$. There's $2^{mr+nr-r^2}$ choices for the remaining $3$ blocks, so we get a final bound of $$\binom{m}{r} \binom{n}{r} 2^{(m+n)r-r^2}.$$

In probabilistic terms, this bound can be expressed as $$P(A \textrm{ has rank } r) \leq \binom{m}{r} \binom{n}{r} 2^{-(m-r)(n-r)}.$$

A natural lower bound corresponds to the event that $A$ has $m-r$ rows that are entirely $0$, which has probability $2^{-(m-r)n}$. I suspect this lower bound is close to tight, but don't know of any general upper bound better than the one given above (the reason why the upper bound is nowhere near tight is that for a typical $W,X,$ and $Y$, the matrix $Z$ will not actually have all entries equal to $1$ or $-1$).

The most studied special case of this (but one not in your range) has been when $m=n$ and $r=n-1$, which essentially corresponds to bounding the probability that an $n \times n$ matrix is singular. There the above argument gives nothing useful ($Z$ is only a single entry), the conjectured lower bound is proportional to $n^2 2^{-n}$ (the asymptotic probability two rows are equal) and the best known upper bound is roughly $2^{-n/2}$ (due to Bourgain, Vu, and Wood)

$\endgroup$
  • 1
    $\begingroup$ Thanks for the answer and detailed explanation. I used a similar reasoning to derive my bound, but you had additional insights which I did not think about. I was hoping for something closer to the lower bound you mentioned (from the same intuition), but it sounds like you think this would be hard to prove (please correct me if I'm wrong). $\endgroup$ – Daniel Soudry Nov 13 '16 at 7:31

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.