Finding a basis for the solution space of a system of Diophantine equations 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.

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