# Counting the number of matrices which cause collision

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

-
So for $\,m=n\,$, "bad matrices" is just another name for singular matrices, whereas the good ones are the regular ones... – DonAntonio Aug 8 '12 at 2:08
@DonAntonio: no, not unless $q=2$ or $q=3$. – Robert Israel Aug 8 '12 at 2:10
For example, with $q=5$, $\pmatrix{3 & 1\cr 1 & 2\cr}$ is "good", because the only vector in its null space mod $5$ whose entries are all in $\{0,1,-1\}$ is $(0,0)$. – Robert Israel Aug 8 '12 at 2:18
I don't get it, @Robert: unless I misunderstood something, for the OP a square matrix $\,A\,$ is bad iff there exists $\,x\neq y\,$ s.t. $\,Ax=Ay\Longleftrightarrow x-y\in\ker A\Longleftrightarrow \ker A\neq \{0\}\Longleftrightarrow A\,$ isn't an isomorphism $\,\Longleftrightarrow\,$ A is singular...what has to do with what prime is q? – DonAntonio Aug 8 '12 at 2:21
@DonAntonio: The $x$ and $y$ aren't arbitrary; they must be binary vectors; hence the set $\{0,1,-1\}$ in Robert's comment. – joriki Aug 8 '12 at 2:22

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.

-

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.

-
Thanks a lot. This confirmed my guess based on programming experiments. I wish someone helps in the case where n and m are larger values, an the matrix isn't square... – M.S. Dousti Aug 8 '12 at 4:24
@Sadeq: This can immediately be generalized for $m\times2$ matrices, for which there are $q^m$ bad matrices in each of the four cases, for a total of $4q^m-3$. I suspect things will get more complicated for larger values of $n$. – joriki Aug 8 '12 at 4:43
@joriki, I'm not sure that it's much more complicated. I think that for any given non-zero $n$-vector (with entries $0,\pm1$), there will be $q^{mn-m}$ matrices having that vector in the nullspace. The number of such $n$-vectors, up to multiplication by $-1$, is $(1/2)(3^n-1)$, so we get $(1/2)(3^n-1)q^{mn-m}$ bad matrices. Now we've done some double-counting, but surely that's at a lower order of magnitude. At least for large $q$, it shouldn't affect the answer much. Well, OK, I've left a few things to check.... – Gerry Myerson Aug 8 '12 at 5:57
@Gerry: Yes, this should readily yield an upper bound (I'd forgotten that the question also asked for an upper bound), but undoing the double counting seems complicated. – joriki Aug 8 '12 at 6:24
@joriki, I think you're right. – Gerry Myerson Aug 8 '12 at 13:15