On the Probability of Generating a Primitive Matrix

• Published in: Journal of systems science and complexity 2024, Vol.37 (4), p.1755-1771
• Main Authors: Chen, Jingwei, Feng, Yong, Liu, Yang, Wu, Wenyuan
• Format: Article
• Language: English
• Subjects: Algorithms; Complex Systems; Control; Integers; Lower bounds; Mathematics; Mathematics and Statistics; Mathematics of Computing; Matrices (mathematics); Matrix algebra; Multiplication; Operations Research/Decision Theory; Statistics; Systems Theory
• ISSN: 1009-6124; 1559-7067
• DOI: 10.1007/s11424-024-1313-6

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.