Given a integer primitive matrix (i.e., a matrix can be extended to an 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 matrix extended from by appending other row vectors of dimension with entries chosen randomly and independently from the uniform distribution over 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 in the range . As an application, the authors prove that there exists a fast Las Vegas algorithm that completes a primitive matrix to an unimodular matrix within expected Õ bit operations, where Õ is big-O but without log factors, is the exponent on the arithmetic operations of matrix multiplication.
Abstract
Given a integer primitive matrix (i.e., a matrix can be extended to an 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 matrix extended from by appending other row vectors of dimension with entries chosen randomly and independently from the uniform distribution over 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 in the range . As an application, the authors prove that there exists a fast Las Vegas algorithm that completes a primitive matrix to an unimodular matrix within expected Õ bit operations, where Õ is big-O but without log factors, is the exponent on the arithmetic operations of matrix multiplication.
关键词
Integer matrix /
matrix completion /
probabilistic algorithm /
unimodular matrix
{{custom_keyword}} /
Key words
Integer matrix /
matrix completion /
probabilistic algorithm /
unimodular matrix
{{custom_keyword}} /
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[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.
{{custom_fnGroup.title_cn}}
脚注
{{custom_fn.content}}
基金
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.
{{custom_fund}}
PDF(269 KB)
