Is there any efficient way to tell whether two matrices $a,b$ are equivalent over the integers? That is, whether there exists some integer-valued matrix $c$ such that $$ a=c^Tbc,\qquad |\det(c)|=1 $$

I tried using FindInstance, but it is taking forever:

a = {{5, 0, 0, 0}, {0, 5, 0, 0}, {0, 0, -2, 0}, {0, 0, 0, -2}};
b = {{-5, 0, 0, 0}, {0, -5, 0, 0}, {0, 0, 3, 0}, {0, 0, 0, 1}};
c = Array[cc,{4,4}];
FindInstance[Flatten[a == Transpose[c].b.c // Thread // Map[Thread]],
             Flatten@c, Integers]

Note that this code does not even require c to have unit determinant. It is not too difficult to include that condition as well; but as this is already very inefficient as is, I don't think it is an approach worth pursuing.

Important: we do not require $c$ to be orthogonal, so $a,b$ need not have the same canonical (Jordan) form (they are not similar matrices). This is what makes the problem tricky.

Note: for my particular problem, it is enough to assume that $a,b,c$ are $4\times4$, and even diagonal; but, for the benefit of future readers, it would be nice to be able to solve the more general problem, where the matrices $a,b$ are in principle arbitrary.

  • $\begingroup$ Have you seen this? $\endgroup$ Oct 9, 2018 at 15:45
  • $\begingroup$ @J.M. Good find, thank you! I am already running a different piece of code on my laptop; when the computation is done, I will try Antonov's code and see if it works as expected. If so, I will close this question as duplicate (or, actually, delete it altogether). Cheers! $\endgroup$ Oct 9, 2018 at 15:53
  • $\begingroup$ see this mathematica.stackexchange.com/q/293896/95437 if any new thoughts. $\endgroup$
    – zeta
    Dec 10, 2023 at 15:23


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.