On the probability of generating a primitive matrix

Abstract

Given a $k\times n$ integer primitive matrix $\mathbf{A}$ (i.e., a matrix can be extended to an $n\times n$ unimodular matrix over the integers) with the maximal absolute value of entries $\Vert \mathbf{A}\Vert$ bounded by {an integer} $\lambda$ from above, we study the probability that the $m\times n$ matrix extended from $\mathbf{A}$ by appending other $m-k$ row vectors of dimension $n$ with entries chosen randomly and independently from the uniform distribution over $\{0,1,\dots ,\lambda -1\}$ is still primitive. We present a complete and rigorous proof of a lower bound on the probability, which is at least a constant for fixed $m$ in the range $[k+1,n-4]$. As an application, we prove that there exists a fast Las Vegas algorithm that completes a $k\times n$ primitive matrix $\mathbf{A}$ to an $n\times n$ unimodular matrix within expected $\tilde{O}(n^{\omega }\log \Vert \mathbf{A}\Vert )$ bit operations, where $\tilde{O}$ is big-$O$ but without log factors, $\omega$ is the exponent on the arithmetic operations of matrix multiplication.

References in corpus (1)

• On the Probability of Generating a Lattice