Let n≥2 be a positive integer and, for all vectors with integer entries X=(x1x2⋮xn)let δ(X)≥0 be the greatest common divisor of x1,x2,…,xn. Also, consider A∈Mn(Z). Prove that the following statements are equivalent: i) |det \textbf{ii) } \delta(AX)=\delta(X), for all vectors X \in \mathcal{M}_{n,1}(\mathbb{Z}). Romeo Raicu
Problem
Source: Romania NMO - 2018
Tags: greatest common divisor, vector, linear algebra, matrix
07.04.2018 22:54
i) \Rightarrow ii): It is enough to prove that if \delta(v) = 1 then \delta(Av) = 1. Suppose that \delta(v) = 1 and \delta(Av) = d > 1. Consider the matrix A^{-1} = \frac{1}{\det A} \cdot \text{adj} A. From that equation we obtain that entries of A^{-1} are all integers too. We have 1 = \delta(v) = \delta(A^{-1}(Av)) \geq d - contradiction. ii) \Rightarrow i): If A is not invertible, then as operator it has kernel. in order to find kernel we have to solve system of linear equations with integer coeffitients, thus kernel is some vector space over \mathbb{Q}, not \mathbb{Z}, but we can scale any vector over \mathbb{Q} to obtain vector with integral entries, so i just want to say that there is v \in M_{n, 1}(\mathbb{Z}) such that Av = 0 so it doesnt even have correctly defined \delta(Av). Now we can suppose that A is invertible and that |\det A| = d > 1, and by the statement for any vector v we have \delta(Av) = \delta(v). Consider again the matrix A^{-1} = \frac{1}{\det A} \cdot \text{adj} A, it's determinant is fractional, thus it has some fractional entries. Choose any column with fractional entries, wlog we can say that it is column numer 1. Define m as lcm of denomenators of fractions in this column. Consider vector v = (m, 0, 0,..., 0)^{t}. Then we will have vector w = A^{-1}(v) with integral components, and by definition, \gcd(m, \delta(w)) = 1. But then \delta(Aw) = \delta(v) = m - contradiction with the equality \delta(w) = \delta(Aw)
24.07.2022 04:56
This isn't really a number theory problem. First dispel of the case \det A = 0. In this case, choose some vector X in the nullspace of A; then \delta(X) is nonzero but \delta(AX) = 0. Henceforth assume \det A \neq 0. Now suppose p\mid \det A for some prime p. In the vector space \mathbb F_p^n, it follows that \det A = 0, so A has a nontrivial nullspace. Choose some nontrivial vector X\in\operatorname{Null}(A); then p\mid \delta(AX) but p\nmid \delta(X). The other direction is analogous. Suppose p\mid \delta(AX) for some vector X\in\mathcal M_{n,1}(\mathbb Z), where by scaling we may assume \delta(X) = 1. In the vector space \mathbb F_p^n, it follows that \operatorname{Null}(A) is nontrivial, so p\mid \det A.