1
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ Have you seen this? $\endgroup$
    – J. M.'s missing motivation ♦
    Commented 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$
    – AccidentalFourierTransform
    Commented Oct 9, 2018 at 15:53
  • $\begingroup$ see this mathematica.stackexchange.com/q/293896/95437 if any new thoughts. $\endgroup$
    – zeta
    Commented Dec 10, 2023 at 15:23

0

Reset to default

Browse other questions tagged or ask your own question.