On the probability of generating a primitive matrix

Given a $k\times n$ integer primitive matrix $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 $A$ by choosing other $m-k$ vectors uniformly at random from $\{0, 1, \ldots, \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 et al. (2011), known as the natural density. As an application, we prove that there exists a fast Las Vegas algorithm that completes a $k\times n$ primitive matrix $A$ to an $n\times n$ unimodular matrix within expected $\tilde{O}(n^{\omega}\log \|A\|)$ bit operations, where $\tilde{O}$ is big-$O$ but without log factors, $\omega$ is the exponent on the arithmetic operations of matrix multiplication and $\|A\|$ is the maximal absolute value of entries of $A$.