3
$\begingroup$

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

  • 0
    So for $\,m=n\,$, "bad matrices" is just another name for singular matrices, whereas the good ones are the regular ones...2012-08-08
  • 0
    @DonAntonio: no, not unless $q=2$ or $q=3$.2012-08-08
  • 0
    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)$.2012-08-08
  • 0
    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?2012-08-08
  • 3
    @DonAntonio: The $x$ and $y$ aren't arbitrary; they must be binary vectors; hence the set $\{0,1,-1\}$ in Robert's comment.2012-08-08
  • 0
    Great @joriki: I "just" misread, not only misunderstood. Thanks.2012-08-08
  • 0
    Reason for deleting my comment to which Robert referred: it was based on misreading the question.2012-08-08
  • 0
    I guess the way I would phrase it, is that a matrix is bad if its nullspace contains a binary vector.2012-08-08
  • 0
    @Jacob: No, a difference between two binary vectors.2012-08-08
  • 0
    @joriki Yeah, I guess you also need $-1$.2012-08-08
  • 0
    I edited the notation. Sadeq: The set $\mathbb{Z}_2$ is **NOT** a subset of $\mathbb{Z}_q$, so you cannot denote it like that. I assume that you mean by a *binary vector* a vector with components zero or one only.2012-08-09

2 Answers 2

3

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.

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.

  • 0
    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...2012-08-08
  • 0
    @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$.2012-08-08
  • 1
    @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....2012-08-08
  • 0
    @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.2012-08-08
  • 0
    @joriki, I think you're right.2012-08-08
  • 0
    @ Gerry @joriki: Thanks for the insightful discussion. I noted that in my problem, the following inequality should hold: $n \ge 3m \lg q$ (see the modified question). The upper bound given here becomes extremely loose if we apply this inequality: Using the upper bound, the ratio of bad matrices to all matrices is $(1/2)(3^n-1)/q^m \approx (1/2)q^{15m/4}$, which is extremely larger than 1. Am I right? If so, can we do better given this inequality?2012-08-08
  • 0
    @Gerry: I made an attempt to correct for the double counting after all (see my answer) -- I wonder whether it's possible to go beyond that and estimate the proportion of linearly dependent tuples of ternary vectors.2012-08-09