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 autho...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 O(n^(ω)log‖A‖)bit operations,where O is big-O but without log factors,ω is the exponent on the arithmetic operations of matrix multiplication.展开更多
Let a,b and n be positive integers withn≥2,f be an integer-valued arithmetic function,and the set S={x_(1),…,x_(n)}of n distinct positive integers be a divisor chain such that x_(1)|x_(2)|⋯|x_(n).We first show that ...Let a,b and n be positive integers withn≥2,f be an integer-valued arithmetic function,and the set S={x_(1),…,x_(n)}of n distinct positive integers be a divisor chain such that x_(1)|x_(2)|⋯|x_(n).We first show that the matrix(f_(a)(S))having f evaluated at the ath power(x_(i),x_(j))^(a) of the greatest common divisor of x_(i) and x_(j) as its i,j-entry divides the GCD matrix(f^(b)(S))in the ring M_(n)(Z)of n×n matrices over integers if and only if f^(b−a)(x_(1))∈Z and(f^(a)(x_(i))−f^(a)(x_(i−1)))divides(f^(b)(x_(i))−f^(b)(x_(i−1)))for any integer i with 2≤i≤n.Consequently,we show that the matrix(f^(a)[S])having f evaluated at the ath power[x_(i),x_(j)]^(a) of the least common multiple of x_(i) and x_(j) as its i,j-entry divides the matrix(f^(b)[S])in the ring M_(n)(Z)if and only if f^(b−a)(x_(n))∈Z and(f^(a)(x_(i))−f^(a)(x_(i−1)))divides(f^(b)(x_(i))−f^(b)(x_(i−1)))for any integer i with2≤i≤n.Finally,we prove that the matrix(f^(a)(S))divides the matrix(f^(b)[S])in the ring M_(n)(Z)if and only if f^(a)(x_(1))|f^(b)(x_(i))and(f^(a)(x_(i))−f^(a)(x_(i−1)))|(f^(b)(x_(i))−f^(b)(x_(i−1)))for any integer i with 2≤i≤n.Our results extend and strengthen the theorems of Hong obtained in 2008.展开更多
基金supported by the National Key Research and Development Project under Grant No.2020YFA0712303National Science Foundational of China under Grant No.61903053+1 种基金Youth Innovation Promotion Association of CAS,Guizhou Science and Technology Program under Grant No.[2020]4Y056Chongqing Science and Technology Program under Grant Nos.cstc2021jcyj-msxm X0821,cstc2020yszxjcyj X0005,cstc2021yszx-jcyj X0004,and 2022YSZX-JCX0011CSTB。
文摘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 O(n^(ω)log‖A‖)bit operations,where O is big-O but without log factors,ω is the exponent on the arithmetic operations of matrix multiplication.
基金supported partially by Doctoral Research Initiation FundProjectof PanzhihuaUniversity(bkqj2019050).
文摘Let a,b and n be positive integers withn≥2,f be an integer-valued arithmetic function,and the set S={x_(1),…,x_(n)}of n distinct positive integers be a divisor chain such that x_(1)|x_(2)|⋯|x_(n).We first show that the matrix(f_(a)(S))having f evaluated at the ath power(x_(i),x_(j))^(a) of the greatest common divisor of x_(i) and x_(j) as its i,j-entry divides the GCD matrix(f^(b)(S))in the ring M_(n)(Z)of n×n matrices over integers if and only if f^(b−a)(x_(1))∈Z and(f^(a)(x_(i))−f^(a)(x_(i−1)))divides(f^(b)(x_(i))−f^(b)(x_(i−1)))for any integer i with 2≤i≤n.Consequently,we show that the matrix(f^(a)[S])having f evaluated at the ath power[x_(i),x_(j)]^(a) of the least common multiple of x_(i) and x_(j) as its i,j-entry divides the matrix(f^(b)[S])in the ring M_(n)(Z)if and only if f^(b−a)(x_(n))∈Z and(f^(a)(x_(i))−f^(a)(x_(i−1)))divides(f^(b)(x_(i))−f^(b)(x_(i−1)))for any integer i with2≤i≤n.Finally,we prove that the matrix(f^(a)(S))divides the matrix(f^(b)[S])in the ring M_(n)(Z)if and only if f^(a)(x_(1))|f^(b)(x_(i))and(f^(a)(x_(i))−f^(a)(x_(i−1)))|(f^(b)(x_(i))−f^(b)(x_(i−1)))for any integer i with 2≤i≤n.Our results extend and strengthen the theorems of Hong obtained in 2008.
