Determinant of lattice is $q^n$ with high probability?

148 Views Asked by At

Lemma: Let $\mathbf{A}\in\mathbb{Z}_q^{n\times m}$ be a uniformly random matrix and $\Lambda^\perp(\mathbf{A})=\lbrace x\in\mathbb{Z}^{m} : \mathbf{A}^Tx\equiv\mathbf{0}\ (\text{mod }q)\rbrace$ be a lattice. Then $\text{det}(\Lambda^\perp(\mathbf{A})) = q^n$ with high probability.

I have found this proof: If $m$ is large enough then rows of $\mathbf{A}$ are linearly independant over $\mathbb{Z}_q$ with high probability. Therefore there are $q^{m-n}$ vector of $\mathbf{Z}_q^{m}$ belonging to $\Lambda^\perp(\mathbf{A})$ since the kernel of $\mathbf{A}$ has dimension $m-n$. From this follows that $\text{vol}(\Lambda^\perp(\mathbf{A})) = \text{det}(\Lambda^\perp(\mathbf{A}))=q^n$.

Question 1 Can anybody please elaborate more on the last implication?

Question 2 How to estimate the probability that a matrix $\mathbf{A}\in\mathbb{Z}_q^{n\times m}$ (where $m> n$) picked uniformly at random has linearly independant rows?

Edit Thanks to the comments Question 2 is no longer a problem.

1

There are 1 best solutions below

12
On BEST ANSWER

I believe that the following argument can be made.

There are $q^{m-n}$ elements of $\Lambda^\perp(\mathbf A)$ modulo $q$. Equivalently, if we take $R$ to be the hypercube $$ R = \{x \in \Bbb R^m : 0 < x_i < q \text{ for } i=1,\dots,m\}, $$ then the set $\Lambda^\perp(\mathbf A) \cap R$ contains $q^{m-n}$ elements. It follows (this is the step I'm not sure about) that the volume of $R$ is equal to the volume of $q^{m-n}$ fundamental parallelograms of $\Lambda^\perp(\mathbf A)$. It follows that $$ \det \Lambda^\perp(\mathbf A) \cdot q^{m-n} = q^m \implies \det \Lambda^\perp(\mathbf A) = q^n. $$