中文版 | English
CSpace
On the Probability of Generating a Primitive Matrix
Chen, Jingwei1,2,3; Feng, Yong1,2; Liu, Yang4; Wu, Wenyuan1,2
2024-02-07
摘要Given a k x n integer primitive matrix A (i.e., a matrix can be extended to an n x n unimodular matrix over the integers) with the maximal absolute value of entries parallel to A parallel to bounded by an integer lambda from above, the authors study the probability that the m x 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, MIDLINE HORIZONTAL ELLIPSIS, lambda - 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 x n primitive matrix A to an n x n unimodular matrix within expected ?(n omega log parallel to A parallel to) bit operations, where ? is big-O but without log factors, omega is the exponent on the arithmetic operations of matrix multiplication.
关键词Integer matrix matrix completion probabilistic algorithm unimodular matrix
DOI10.1007/s11424-024-1313-6
发表期刊JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY
ISSN1009-6124
页码17
通讯作者Liu, Yang(liuyang13@cqjtu.edu.cn)
收录类别SCI
WOS记录号WOS:001157131000002
语种en