finding the basis of a kernel in a lattice

Question

Given a parity check matrix $A$ we define the $q$-ary lattice $$\Lambda(A) = \{x \in \mathbb Z^m\;:\;Ax\equiv0\pmod q\}$$ How to find the basis of the lattice and how to find its hermite normal form?

Answer 1

Let ${\bf A}$ be a $n\times m$ matrix with $n|m$ and rank $n$. Write down ${\bf A}$ as $m/n$ blocks of $m\times m$ matrices as follows: $${\bf A}=\left[{\bf A}_1|\cdots|{\bf A}_{m/n}\right].$$ If ${\bf x}\in\Lambda({\bf A})$, then $${\bf 0}={\bf A}{\bf x} = \sum_{i=1}^{m/n}{\bf A}_i{\bf x}_i,\pmod{q}$$ where ${\bf x} = \left[{\bf x}_1^T|\cdots|{\bf x}_{m/n}^T\right]^T$. Without loss of generality, suppose that ${\bf A}_1$ is invertible. hence the above equation can be written as: $${\bf x}_1=\sum_{j=2}^{m/n}{\bf B}_j{\bf x}_j,\pmod{q}$$ where ${\bf B}_j = -{\bf A}_1{\bf A}_j$, for $2\leq j \leq m/n$. Using the above equation and by replacing a standard basis as ${\bf x}_j$, $2\leq j \leq m/n$, one can find ${\bf x}_1$, which fully describes the lattice $\Lambda({\bf A})$.