$\newcommand{\Q}{\Bbb Q} \newcommand{\N}{\Bbb N} \newcommand{\R}{\Bbb R} \newcommand{\Z}{\Bbb Z} \newcommand{\C}{\Bbb C} \newcommand{\A}{\Bbb A} \newcommand{\GL}{\mathrm{GL}} \newcommand{\Gal}{\mathrm{Gal}} \newcommand{\matr}[2]{\begin{pmatrix} #1 \\ #2 \end{pmatrix}} $ Let $M, M' \in M_{2 \times 2}(\Z)$ be two matrices with $|\det(M)| = |\det(M')| \neq 0$. Assume that $$\forall \lambda, \mu \in \Bbb Z, \quad \exists U_{\lambda, \mu} \in \GL_2(\Z) \qquad M' \matr{\lambda}{\mu} = U_{\lambda, \mu} M \matr{\lambda}{\mu} \tag{*} $$
Is it true that there is a matrix $U \in \GL_2(\Z)$ such that $M' = UM$ ?
Thoughts:
The condition $M' v = U_{\lambda, \mu} M v$, where $v = \matr{\lambda}{\mu}$, just means that the two vectors $\matr{x}{y} := M v , \; \matr{x'}{y'} := M' v \in \Z^2$ have the same gcd of coefficients (that is, $\gcd(x,y) = \gcd(x',y')$).
The converse obviously holds (if $M' = UM$ then clearly (*) holds).
If we take $$M = \matr{ 5 & 1 }{ 0 & 5 }, M' = \matr{ 5 & 2 }{ 0 & 5 },$$ the condition (*) above holds for $(\lambda, \mu) = (1,0), (0,1), (1,-1), (1,1),...$ but not for $(1, -5)$. We easily check that indeed $M'$ cannot be written as $UM$.
I checked experimentally that we indeed have $M'=UM$ whenever (*) is satisfied, it worked for thousands of random matrices $M,M'$.
Yes. By assumption, there exist two integer matrices $U_1$ and $U_2$ such that $M'\left(\operatorname{adj}(M)e_i\right)=U_iM\left(\operatorname{adj}(M)e_i\right)=\det(M)U_ie_i$. Therefore \begin{aligned} M'\operatorname{adj}(M)&=\det(M)\pmatrix{U_1e_1&U_2e_2},\\ M'\operatorname{adj}(M)M&=\det(M)\pmatrix{U_1e_1&U_2e_2}M,\\ \det(M)M'&=\det(M)\pmatrix{U_1e_1&U_2e_2}M,\\ M'&=\pmatrix{U_1e_1&U_2e_2}M=:UM. \end{aligned} Taking absolute values of determinants on both sides, we get $|\det(M)|=|\det(U)||\det(M)|$. Therefore $\det(U)=\pm1$.