Volume $q^n$ of a dual q-ary lattice in MR09

Question

Given a matrix $\mathbf{A} \in \mathbb{Z}^{n \times m}$, $m$ sufficiently large with respect to $n$ and prime $q$. The rows of $\mathbf{A}$ are linearly independent with high probability. In MR09 the authors state that the number of vectors in $\mathbb{Z}_q^m$ belonging to the $q$-ary lattice $\Lambda_q^\intercal(\mathbf{A})$ is $q^{m-n}$ and therefore it follows that $\text{det}(\Lambda_q^\intercal(\mathbf{A})) = q^n$.

I understand that the dimension of the kernel of $\mathbf{A}$ (which is equivalent to the the dimension of the dual lattice) is $m-n$. However, I don't understand how the volume immediatley follows and would be thankful for an explanation.

Answer 1

Note that for a lattice $L\subseteq\mathbb{R}^n$, $\det(L)$ is the volume of a fundamental domain. There are often many of these objects, but there are two that are typically of primary interest:

1. The Voronoi Cell $\mathcal{V}(L) = \{x\in\mathbb{R}^n\mid \forall \ell\in L\setminus\{0\}, \lVert x\rVert_2\leq \lVert x-\ell\rVert_2\}$, e.g. it is the points in $\mathbb{R}^n$ that are closer to 0 than any other lattice point.
2. The Fundamental Parallelpiped --- for a basis $\mathbf{B}$ of the lattice, this is the set $\mathbf{B}[0,1)^n$ (or sometimes $\mathbf{B}[-1/2,1/2)^n$.

Up to some issues on the boundary, a fundamental domain "tiles space", meaning that the sum

$$L + D = \mathbb{R}^n$$

is a partition. If we assume the lattice is $q$-ary, we can reduce everything mod $q$ to get that $(L\bmod q) + (D\bmod q) = \mathbb{R}/q\mathbb{R}^n$ is a partition as well [1]. Taking volumes, we get that $$|L\bmod q||D\bmod q| = q^n\implies |L\bmod q| = \frac{q^n}{|D|} = \frac{q^n}{\det L}.$$ What you want then follows from using that the lattice is $m$-dimensional, and has $|L\bmod q| = q^{m-n}$ points, so the determinant must be $q^n$.

---

[1] There may be some issues with particularly irregular fundamental domains $D$ here (in particular fundamental domains that are not contained in $[-q/2, q/2)^n$, but if you let $D$ be the Voronoi cell everything seems fine, and I am not even sure if this worry I mention is for a particular reason.