On the Probability of Generating a Primitive Matrix

CHEN Jingwei, FENG Yong, LIU Yang, WU Wenyuan

Journal of Systems Science & Complexity ›› 2024, Vol. 37 ›› Issue (4) : 1755-1771.

PDF(269 KB)
中国科学院数学与系统科学研究院期刊网
JSSC
PDF(269 KB)
Journal of Systems Science & Complexity ›› 2024, Vol. 37 ›› Issue (4) : 1755-1771. DOI: 10.1007/s11424-024-1313-6

On the Probability of Generating a Primitive Matrix

Author information +
History +

Abstract

Given a k×n integer primitive matrix \bmA (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 \bmA 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 \bmA to an n×n unimodular matrix within expected Õ (nwlog⁡||A||) bit operations, where Õ is big-O but without log factors, ω is the exponent on the arithmetic operations of matrix multiplication.

Key words

Integer matrix / matrix completion / probabilistic algorithm / unimodular matrix

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations
CHEN Jingwei , FENG Yong , LIU Yang , WU Wenyuan. On the Probability of Generating a Primitive Matrix. Journal of Systems Science & Complexity, 2024, 37(4): 1755-1771 https://doi.org/10.1007/s11424-024-1313-6

References

[1] Maze G, Rosenthal J, and Wagner U, Natural density of rectangular unimodular integer matrices, Linear Algebra and Its Applications, 2011, 434(5):1319-1324.
[2] Eberly W, Giesbrecht M, and Villard G, On computing the determinant and Smith form of an integer matrix, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, 2000, 675-685.
[3] Storjohann A, High-order lifting and integrality certification, Journal of Symbolic Computation, 2003, 36(3):613-648.
[4] Storjohann A, The shifted number system for fast linear algebra on integer matrices, Journal of Complexity, 2005, 21(4):609-650.
[5] Phoong S M and Lin Y P, Application of unimodular matrices to signal compression, Proceedings of 2002 IEEE International Symposium on Circuits and Systems, IEEE, Piscataway, 2002, 837-840.
[6] Lenstra A K, Lenstra H W, and Lovász L, Factoring polynomials with rational coefficients, Mathematische Annalen, 1982, 261(4):515-534.
[7] Schnorr C P, A hierarchy of polynomial time lattice basis reduction algorithms, Theoretical Computer Science, 1987, 53(2-3):201-224.
[8] Reiner I, Unimodular complements, The American Mathematical Monthly, 1956, 63(4):246-247.
[9] Zhan X, Completion of a partial integral matrix to a unimodular matrix, Linear Algebra and Its Applications, 2006, 414(1):373-377.
[10] Fang M, On the completion of a partial integral matrix to a unimodular matrix, Linear Algebra and Its Applications, 2007, 422(1):291-294.
[11] Duffner M G and Silva F C, On the existence of unimodular matrices with a prescribed submatrix, Linear Algebra and Its Applications, 2017, 515:321-330.
[12] Guo X, Hou F, and Liu X, Natural density of integral matrices that can be extended to invertible integral matrices, Linear and Multilinear Algebra, 2016, 64(9):1878-1886.
[13] Fontein F and Wocjan P, On the probability of generating a lattice, Journal of Symbolic Computation, 2014, 64:3-15.
[14] Aggarwal D and Regev O, A note on discrete gaussian combinations of lattice vectors, Chicago Journal of Theoretical Computer Science, 2013, 2016:1-11.
[15] Kirshanova E, Nguyen H, Stehlé D, et al., On the smoothing parameter and last minimum of random orthogonal lattices, Designs, Codes and Cryptography, 2020, 88(5):931-950.
[16] Randall D, Efficient Generation of Random Nonsingular Matrices, Technical Report UCB/CSD-91-658, EECS Department, University of California, Berkeley, 1991.
[17] Kalaimani R K, Belur M N, and Sivasubramanian S, Generic pole assignability, structurally constrained controllers and unimodular completion, Linear Algebra and Its Applications, 2013, 439(12):4003-4022.
[18] Zhou W and Labahn G, Unimodular completion of polynomial matrices, Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, Ed. by Katsusuke Nabeshima, ACM, New York, 2014, 413-420.
[19] Babai L, On Lovász'lattice reduction and the nearest lattice point problem, Proceedings STACS'85, Lecture Notes in Computer Science, Ed. by Mehlhorn K, Springer, Heidelberg, 1985, 182:13-20.
[20] Mulders T and Storjohann A, Certified dense linear system solving, Journal of Symbolic Computation, 2004, 37(4):485-510.

Funding

This research was supported by the National Key Research and Development Project under Grant No. 2020YFA0712303, National Science Foundational of China under Grant No. 61903053, Youth Innovation Promotion Association of CAS, Guizhou Science and Technology Program under Grant No. [2020]4Y056 and Chongqing Science and Technology Program under Grant Nos. cstc2021jcyj-msxmX0821, cstc2020yszxjcyjX0005, cstc2021yszx-jcyjX0004, and 2022YSZX-JCX0011CSTB.
PDF(269 KB)

223

Accesses

0

Citation

Detail
Sections
Recommended

/

〈 〉