Probability for an uniform matrix $A \in \mathbb{Z}_q^{n\times m}$ to have $A \mathbb{Z}^m_q = \mathbb{Z}^n_q$ (q power of a prime $b>2$)

Question

I will note $\mathbb{Z}_q = \mathbb{Z}/q\mathbb{Z}$. I read in a lecture of Micciancio about lattices (exercice 5), that for any $q, m, n \in \mathbb{Z}$, we have $\mathbb{P}_{A \in \mathbb{Z}_q^{n \times m}}(A \mathbb{Z}_q^m = \mathbb{Z}_q^n) \geq 1 - \frac{1}{q^{m - n}}$

But I have no idea of how to prove it. Could you help me to find the way to show it? I am particulary interested in the situation where $q = b^k$ for $b>2$ a prime.

Answer 1

$q=p^k$ is the power of a prime and $m\ge n$.

• If $A \mathbb{Z}^m_q = \mathbb{Z}^n_q$ then $A \mathbb{Z}^m_p = \mathbb{Z}^n_p$.

  Conversely if $A \mathbb{Z}^m_p = \mathbb{Z}^n_p$ then for all $v\in p^r\mathbb{Z}^n_q$ there is $w\in p^r\mathbb{Z}^m_q$ such that $v-A w\in p^{r+1} \mathbb{Z}^n_q$.

So $A \mathbb{Z}^m_q = \mathbb{Z}^n_q$ iff $A \mathbb{Z}^m_p = \mathbb{Z}^n_p$ ie. the probability doesn't depend on $k$.

• To construct all the matrices $A\in \Bbb{Z}_p^{n\times m}$ such that $A \mathbb{Z}^m_p = \mathbb{Z}^n_p$:

  Take a subspace $V\subset \mathbb{Z}^m_p$ with $\dim(V)=m-n$.

  Take some $C_V\in \mathbb{Z}_p^{n\times m}$ such that $C_V\mathbb{Z}^m_p = \mathbb{Z}^n_p$ and $\ker(C_V)=V$.

Then [$A\mathbb{Z}^m_p = \mathbb{Z}^n_p$ and $\ker(A)=V$] iff [$A = B C_V$ for some $B\in GL_n(\mathbb{Z}_p)$].

Moreover once the $C_V$ are chosen for each subspace of dimension $m-n$ this decomposition of $A$ is unique.

• The number of $GL_n(\Bbb{Z}_p)$ matrices is $$\alpha=\prod_{l=0}^{n-1} (p^{n}-p^l)$$

• The number of $m-n$ dimensional subspaces of $\Bbb{Z}_p^m$ is $$\beta=\frac{\prod_{l=0}^{m-n-1} (p^m-p^l)}{\prod_{l=0}^{m-n-1} (p^{m-n}-p^l)}$$

• Your probability is $$\frac{\alpha \beta}{p^{nm}}$$