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<m\le n-1$. If the conjecture is true, then there exists a Las Vegas algorithm that completes a $k\times n$ primitive matrix to an $n\times n$ unimodular matrix and runs in expected $\tilde{O}(n^{\omega}\log \norm{\bm{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 $\norm{\bm{A}}$ is the maximal absolute value of entries of $\bm{A}$.