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$.