# Matrix equivalence over the integers

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.

• Have you seen this? Oct 9, 2018 at 15:45
• @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! Oct 9, 2018 at 15:53
• see this mathematica.stackexchange.com/q/293896/95437 if any new thoughts.
– zeta
Dec 10, 2023 at 15:23