KMS Chongqing Institute of Green and Intelligent Technology, CAS
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 |
DOI | 10.1007/s11424-024-1313-6 |
发表期刊 | JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY |
ISSN | 1009-6124 |
页码 | 17 |
通讯作者 | Liu, Yang(liuyang13@cqjtu.edu.cn) |
收录类别 | SCI |
WOS记录号 | WOS:001157131000002 |
语种 | 英语 |