Upper bound on the number of binary matrices with small rank 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!
 A: 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)
