On the probability of generating a primitive matrix

*Jingwei Chen (CIGIT, CAS)
Yong Feng (CIGIT, CAS)
Yang Liu (Chongqing Jiaotong University)
Wenyuan Wu (CIGIT, CAS)

Given a $k\times n$ integer \textit{primitive} matrix $\bm{A}$ (i.e., a matrix can be extended to an $n\times n$ unimodular matrix over the integers) with size of entries bounded by $\lambda$, we study the probability that the $m\times n$ matrix extended from $\bm{A}$ by choosing other $m-k$ vectors uniformly at random from $\{\to{0}{1}{\lambda-1}\}$ is still primitive. We present a complete and rigorous proof that the probability is at least a constant for the case of $m\le n-4$. Previously, only the limit case for $\lambda\rightarrow\infty$ with $k=0$ was analysed in Maze \textit{et al.} (2011), known as the natural density. Based on extensive computer simulations, we conjecture that a similar result holds as well for $n-4