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

  • $\begingroup$ So for $\,m=n\,$, "bad matrices" is just another name for singular matrices, whereas the good ones are the regular ones... $\endgroup$ – DonAntonio Aug 8 '12 at 2:08
  • $\begingroup$ @DonAntonio: no, not unless $q=2$ or $q=3$. $\endgroup$ – Robert Israel Aug 8 '12 at 2:10
  • $\begingroup$ 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)$. $\endgroup$ – Robert Israel Aug 8 '12 at 2:18
  • $\begingroup$ 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? $\endgroup$ – DonAntonio Aug 8 '12 at 2:21
  • 3
    $\begingroup$ @DonAntonio: The $x$ and $y$ aren't arbitrary; they must be binary vectors; hence the set $\{0,1,-1\}$ in Robert's comment. $\endgroup$ – 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.

  • $\begingroup$ 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... $\endgroup$ – M.S. Dousti Aug 8 '12 at 4:24
  • $\begingroup$ @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$. $\endgroup$ – joriki Aug 8 '12 at 4:43
  • 1
    $\begingroup$ @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.... $\endgroup$ – Gerry Myerson Aug 8 '12 at 5:57
  • $\begingroup$ @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. $\endgroup$ – joriki Aug 8 '12 at 6:24
  • $\begingroup$ @joriki, I think you're right. $\endgroup$ – Gerry Myerson Aug 8 '12 at 13:15

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.