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:
-
$q=2$, and $\mathbf{A} = [1,1]$ $\quad \xrightarrow{\qquad}\quad$
$\mathbf{B} = \left[ \begin{array}{cc} 2&1 \\ 0&1 \end{array} \right]$ -
$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]$ -
$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:
- How to obtain $\mathbf{B}$ from $\mathbf{A}$ and $q$?
- Is it possible that $\mathbf{B}$ is not full rank, i.e. $\text{Rank}(\mathbf{B})< m$?
- 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.
Best Answer
Well, here is how it works over a field. We take $q=5.$ We will start with $A$ as a 2 by 4, $$ A \; = \; \left( \begin{array}{cccc} 2 & 3 & 4 & 1 \\ 3 & 4 & 0 & 1 \end{array} \right) $$ We begin a sequence of elementary row operations, first multiply the first row times 3 and the second by 2, $$ \left( \begin{array}{cccc} 1 & 4 & 2 & 3 \\ 1 & 3 & 0 & 2 \end{array} \right) $$ Next subtract row 1 from row 2. $$ \left( \begin{array}{cccc} 1 & 4 & 2 & 3 \\ 0 & 4 & 3 & 4 \end{array} \right) $$ then multiply the second row by 4, $$ \left( \begin{array}{cccc} 1 & 4 & 2 & 3 \\ 0 & 1 & 2 & 1 \end{array} \right) $$ Finally add row 2 to row 1, $$ \left( \begin{array}{cccc} 1 & 0 & 4 & 4 \\ 0 & 1 & 2 & 1 \end{array} \right). $$ This is the most favorable case. It allows us to place a little 2 by 2 identity matrix at the bottom when writing the null space we need $$ \left( \begin{array}{cc} ? & ? \\ ? & ? \\ 1 & 0 \\ 0 & 1 \end{array} \right) $$ which is then forced to become $$ \left( \begin{array}{cc} 1 & 1 \\ 3 & 4 \\ 1 & 0 \\ 0 & 1 \end{array} \right) $$ This can be readily filled in the way Buchmann, Lindner, Ruckert, Schneider demand at the bottom of page 2, $$ B \; = \; \left( \begin{array}{cccc} 5 & 0 & 1 & 1 \\ 0 & 5 & 3 & 4 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array} \right). $$ You can check that $AB \equiv 0 \pmod 5$ as the matrix of appropriate size.
What happens instead if the row echelon form comes out with staggered nontrivial 1's? Let us begin again with $$ A \; = \; \left( \begin{array}{cccc} 1 & 2 & 0 & 3 \\ 0 & 0 & 1 & 1 \end{array} \right) $$
It is first necessary to stagger the little 2 by 2 identity matrix in the same way, as in $$ \left( \begin{array}{cc} ? & ? \\ 1 & 0 \\ ? & ? \\ 0 & 1 \end{array} \right) $$ and forces us to the penultimate $$ \left( \begin{array}{cc} 3 & 2 \\ 1 & 0 \\ 0 & 4 \\ 0 & 1 \end{array} \right). $$ Note that it is impossible to just place this 4 by 2 as the final two columns of a 4 by 4, BLRS demand nonzero entries on the main diagonal. So what we do is simply stagger the columns with 5's in the same way, giving $$ B \; = \; \left( \begin{array}{cccc} 5 & 3 & 0 & 2 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 5 & 4 \\ 0 & 0 & 0 & 1 \end{array} \right). $$