Search

Given a set X of n x n matrices and a positive integer m, we consider the problem of estimating the cardinalities of the product sets A1 … Am, where Ai ∈ X. When X = Mn(ℤ; H), the set of n x n matrices with integer elements of size at most H, we give several bounds on the cardinalities of the product sets and solution sets of related equations such as A1 … Am = C and A1 … Am = B1 … Bm. We also consider the case where X is the subset of matrices in Mn(픽), where 픽 is a field with bounded rank k ≤ n. In this case, we completely classify the related product set. [ABSTRACT FROM AUTHOR]

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 Õ(nω log ∥A∥) bit operations, where Õ is big-O but without log factors, ω is the exponent on the arithmetic operations of matrix multiplication. [ABSTRACT FROM AUTHOR]

A Las Vegas randomized algorithm is given to compute the Hermite normal form of a nonsingular integer matrix A of dimension n. The algorithm uses quadratic integer multiplication and cubic matrix multiplication and has running time bounded by O(n³ (logn + log ||A||)² (logn)² ) bit operations, where ||A|| = maxi j |Ai j | denotes the largest entry of A in absolute value. A variant of the algorithm that uses pseudo-linear integer multiplication is given that has running time (n³ log ||A||)1+o(1) bit operations, where the exponent "+o(1)" captures additional factors c1 (logn)c² (loglog ||A||)c³ for positive real constants c1, c2, c3. [ABSTRACT FROM AUTHOR]

Let a , b and n be positive integers with n ≥ 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 a th 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 a th 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 with 2 ≤ 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. [ABSTRACT FROM AUTHOR]

Fillmore's theorem is a matrix completion problem that states that if A is a nonscalar matrix over a field F and γ1, . . ., γn ∈ F so that γ1+. . .+γn = tr(A) then there is a matrix similar to A with diagonal (γ1, . . ., γn). Borobia [1] extended Fillmore's Theorem to the matrices over the ring of integers and Soto, Julio and Collao [3] studied it with the nonnegativity hypothesis. In this paper we prove the same result by modifying the initial proof of Fillmore, a subsequent new algorithm is proposed and some new information about the final matrix will be given. [ABSTRACT FROM AUTHOR]

A matrix A is said to be an integer matrix if all its entries are integers. In this article, we characterize the nonsingular integer matrices with integer eigenvalues in an expressible form of their corresponding inverse matrices. It is proved that a nonsingular integer matrix A has integer eigenvalues if and only if A − 1 can be written as the sum of n rank-one matrices that meet certain requirements. A method for constructing integer matrices with integer eigenvalues using the Hadamard product is also provided. Let S represent an n -tuple of nonnegative integers. If there is an n × n integer matrix A whose spectrum (the collection of eigenvalues) is S , we say that S is realisable by an integer matrix. In Fallat et al. (2005) [7] , the authors posed a conjecture that " there is no simple graph on n ≥ 2 vertices whose Laplacian spectrum is given by (0 , 1 , ... , n − 1)." We provide a characterization of threshold graphs using the spectra of quotient matrices of its G -join graphs. As a consequence, we prove that given any n − 1 positive integers λ 2 , ... , λ n such that λ 2 ≤ ⋯ ≤ λ n , the n -tuple (0 , λ 2 , ... , λ n) is realizable by the Laplacian matrix of a multidigraph. In particular, we show that (0 , 1 , ... , n − 1) can be realizable by the Laplacian matrix of a multidigraph. [ABSTRACT FROM AUTHOR]

We study topological properties of automorphisms of a 6-dimensional torus T 6 generated by integer matrices with simple eigenvalues being symplectic with respect to either the standard symplectic structure in R 6 or a nonstandard symplectic structure given by an integer skew-symmetric non-degenerate matrix. Such a symplectic matrix generates a partially hyperbolic automorphism of the torus, if its eigenvalues lie both outside and on the unit circle. We study transitive and decomposable cases possible here and present a classification in both cases. [ABSTRACT FROM AUTHOR]