Counting the number of matrices which cause collision

Question

Let $m,n \in \mathbb{N}$, and $q$ be a prime number.

Let $\mathbf{A} \in \mathbb{Z}^{m \times n}_q$ be a matrix. In the following, assume that all additions and multiplications are performed modulo $q$.

We call $\mathbf{A}$ a "bad" matrix if there exist two distinct binary vectors $\mathbf{x}, \mathbf{y} \in \{0,1\}^{n \times 1}$ such that $\mathbf{Ax} \equiv \mathbf{Ay} \pmod q$. In other words, a matrix for which there exists a collision is bad. Otherwise, $\mathbf{A}$ is called a "good" matrix.

Example: For $m=n=2$ and $q=11$, the matrices $\mathbf{A_1} = \left[\begin{smallmatrix} 0&0\\ 0&0 \end{smallmatrix} \right]$ and $\mathbf{A_2} = \left[\begin{smallmatrix} 1&2\\ 3&4 \end{smallmatrix} \right]$ are bad and good, respectively.

There are a total of $q^{mn}$ possible matrices $\mathbf{A} \in \mathbb{Z}^{m \times n}_q$. The question is to count the number of bad matrices.

Question: How many matrices $\mathbf{A} \in \mathbb{Z}^{m \times n}_q$ are bad?

A tight upper-bound will do as well.

PS: Programming experiments with $2 \times 2$ matrices show that about $4q^2$ of the matrices are bad.

Edit (8/9/2012): In my problem, I have the following requirement on the parameters $n \ge 3m \lceil \lg q \rceil$. For a practical implementation, one can take $m=100$ and $q=257$, resulting in $n=2700$.

Answer 1

With a view to the additional information from the edit, we can make an attempt to correct for the double counting (discussed in the comments under Gerry's answer).

There are $s=(3^n-1)/2$ non-zero ternary vectors of length $n$ (up to a sign). Each of them has an orthogonal complement of dimension $n-1$ containing $q^{n-1}$ vectors, and thus lies in the null space of $q^{m(n-1)}$ matrices.

A set of $k$ linearly independent vectors shares an orthogonal complement of dimension $n-k$, and thus lies in the null space of $q^{m(n-k)}$ matrices. The ternary vectors aren't all linearly independent, but all pairs and most triples are, so we can try to get an estimate by assuming linear independence. Then inclusion–exclusion yields

$$ \sum_{k=0}^s\binom skq^{m(n-k)}(-1)^k=q^{mn}\sum_{k=0}^s\binom sk\left(-q^{-m}\right)^k=q^{mn}\left(1-q^{-m}\right)^s $$

for the number of good matrices, or $\left(1-q^{-m}\right)^s$ for the proportion of good matrices. With $n\approx3m\log q$, the logarithm of this proportion is

$$ \frac12\left(3^{3m\log q}-1\right)\log\left(1-q^{-m}\right) \approx -\frac123^{3m\log q}q^{-m}= -\frac12q^{3m\log3}q^{-m} =-\frac12q^{(3\log3-1)m}\;. $$

Since this goes to $-\infty$ for large $q$ and/or $m$, based on this estimate we might expect almost all matrices to be bad. More generally, if $n\gg m\log q/\log3=m\log_3q$, almost all matrices should be bad, whereas for $n\ll m\log_3q$ almost all matrices should be good. Again, this ignores the linear dependence of the ternary vectors, so it should be taken with a grain of salt.

Answer 2

Let's look at the $2\times2$ case.

A matrix has $(1,0)$ in its nullspace (equivalently, $(-1,0)$) if and only if it's of the form $$\pmatrix{0&a\cr0&b\cr}$$ and there are $q^2$ of those. It has $(0,1)$ (equivalently, $(0,-1)$) in its nullspace if and only if it's of the form $$\pmatrix{a&0\cr b&0\cr}$$ another $q^2$ matrices. It has $(1,1)$ (and $(-1,-1)$) if it's $$\pmatrix{a&-a\cr b&-b\cr}$$ another $q^2$, and $(1,-1)$ (and $(-1,1)$) if it's $$\pmatrix{a&a\cr b&b\cr}$$ another $q^2$. If $q$ is an odd prime, we haven't done any double-counting, except that the zero matrix has been counted 4 times, so I get $4q^2-3$ bad $2\times2$ matrices.

It might be possible to extend this line of argument to bigger matrices.