Given a k × n integer primitive matrix A (i.e., a matrix can be extended to an n × n unimodular matrix over the integers) with the maximal absolute value of entries ∥A∥ bounded by an integer λ from above, the authors study the probability that the m × n matrix extended from A by appending other m − k row vectors of dimension n with entries chosen randomly and independently from the uniform distribution over {0, 1, ⋯, λ − 1} is still primitive. The authors 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, the authors prove that there exists a fast Las Vegas algorithm that completes a k × n primitive matrix A to an n × n unimodular matrix within expected Õ(nω log ∥A∥) bit operations, where Õ is big-O but without log factors, ω is the exponent on the arithmetic operations of matrix multiplication.
