3
$\begingroup$

Let $m$, $n$, and $q$ be positive integers, with $m \ge n$. Let $\mathbf{A} \in \mathbb{Z}^{n \times m}_q$ be a matrix.

Consider the following set: $S = \big\{ \mathbf{y} \in \mathbb{Z}^m \mid \mathbf{Ay} \equiv \mathbf{0} \pmod q \big\}$.

It can be easily shown that $S$ constitutes a lattice, because it is a discrete additive subgroup of $\mathbb{R}^m$.

I want to find the basis of this lattice. In other words, I want to find a matrix $\mathbf{B} \in \mathbb{Z}^{m \times m}$, such that the following holds: $S = \{\mathbf{Bx} \mid \mathbf{x} \in \mathbb{Z}^m \}$.

Let me give some examples:

  1. $q=2$, and $\mathbf{A} = [1,1]$ $\quad \xrightarrow{\qquad}\quad$ $\mathbf{B} = \left[ \begin{array}{cc} 2&1 \\ 0&1 \end{array} \right]$

  2. $q=3$, and $\mathbf{A} = \left[ \begin{array}{ccc} 0&1&2 \\ 2&0&1 \end{array} \right]$ $\quad \xrightarrow{\qquad}\quad$ $\mathbf{B} = \left[ \begin{array}{ccc} 3&0&1 \\ 0&3&1 \\ 0&0&1 \end{array} \right]$

  3. $q=4$, and $\mathbf{A} = \left[ \begin{array}{ccc} 0&2&3 \\ 3&1&2 \end{array} \right]$ $\quad \xrightarrow{\qquad}\quad$ $\mathbf{B} = \left[ \begin{array}{ccc} 4&2&1 \\ 0&2&1 \\ 0&0&2 \end{array} \right]$

Note that in all cases, $\mathbf{AB} =\mathbf{0} \pmod q$. However, $\mathbf{B}$ is not an arbitrary solution to this equivalence, since it must span $S$. For instance, in the example 1 above, matrix $\mathbf{\hat B} = \left[ \begin{array}{cc} 2&0\\ 0&2 \end{array} \right]$ satisfies $\mathbf{A \hat B} =\mathbf{0} \pmod 2$, but generates a sub-lattice of $S$.

Also note that if $\mathbf{B}$ is a basis of $S$, any other basis $\mathbf{\bar B}$ is also a basis of $S$, provided that there exists a unimodular matrix $\mathbf{U}$, for which $\mathbf{\bar B} = \mathbf{BU}$.

My questions:

  1. How to obtain $\mathbf{B}$ from $\mathbf{A}$ and $q$?
  2. Is it possible that $\mathbf{B}$ is not full rank, i.e. $\text{Rank}(\mathbf{B})< m$?
  3. Is there any difference between the case where $q$ is prime and the case where it is composite?

Side note: As far as I understood, $S$ is the solution space of a system of linear Diophantine equations. The solution has something to do with Hermite normal forms, but I can't figure out how.

  • 1
    There should be a way to work this out with ordinary linear algebra when $q$ is prime, as you are dealing with a field, every nonzero number has a multiplicative inverse. Other than that, i will need to think about it. The one article that comes to mind is George Leo Watson, Transformations of a Quadratic Form which do not increase the Class-Number, Proc. London Math. Soc. vol. 12 (1962) pages 577-587. Formulas 2.4 and 2.5, then Lemma 2 (ii) are related to your questions but may not be enough. Alright, I wrote "Smith Normal Form" at a few points on my copy, perhaps you should look that up.2012-08-16
  • 0
    @Will: Thanks for the answer. I found this paper: [explicit hard instances of the shortest vector problem](http://eprint.iacr.org/2008/333.pdf), which is trying to solve the same problem. Specially, section 4 describes how B is obtained from A (called Y and X in the paper). But I'm totally confused by their construction, since I can't apply it to any of my numerical examples. Could you please check that out?2012-08-17
  • 0
    @Will: Moreover, if you have any strategy to obtain B from A, given q is a prime, please write it out as an answer. It will be invaluable to me!2012-08-17
  • 0
    When you say that $B$ is not an *arbitrary* solution to $AB \equiv 0 \pmod{q},$ and then show an example of $\hat{B},$ did you notice that the example diag(2, 2) is $\hat{B} \equiv 0 \pmod{q}$? Does all non-zero (modulo $q$) solutions generate only a sub-lattice of S?2012-08-17
  • 0
    *Not sure if this useful.* By [linear algebra over the ring $\Bbb{Z}_q,$](http://books.google.ca/books/about/Linear_Algebra_over_Commutative_Rings.html?id=hkCgw_5wRq4C) we can find a *non-zero* nullspace basis matrix $N \in \mathbb{Z}_q^{m\times m}$ s.t. $A N \equiv 0 \pmod{q}.$ Then for any integer matrix $R,$ $N + qR$ is also a solution to the congruence. I'm not sure how to pick $R$ though, in order to make $N + qR$ a basis of $S$ (or at least to make $N + qR$ full rank & then invoke, say, LLL).2012-08-17
  • 1
    @Jennifer: Thanks for the answer. I checked your idea, but it apparently things are more complicated. Consider, for instance, the matrix $\mathbf{B'} = \left[ \begin{array}{cc} 3&2\\ 3&4 \end{array} \right]$. It is a solution for $\mathbf{AB'} \equiv 0 \pmod{2}$, and it's non-zero modulo 2. However, it generates a sub-lattice of $S$. (For example, the point $(1,1)$ is in the lattice $S$, but cannot be generated by $\mathbf{B'}$.)2012-08-17

3 Answers 3