How to find a unimodular integer matrix $T$ satisfying $T^\top A T=B$ given symmetric integer matrices $A,B$?

Question

Given two unimodular symmetric integer matrices $A$ and $B$, I asked how to find a unimodular integer $T$ that satisfies this nonlinear relation between $T$ and $A,B$ like this in Mathematica:

Transpose[T].A.T == B

This means that we have the following conditions: $$A_{ij}=A_{ji}, B_{ij}=B_{ji},$$ and $$\det A, \det B, \det T \in \{+1,-1\}.$$

I asked on Mathematica StackExchange here, but the unsolved question was wrongly closed as a duplicate. Specifically this post does not solve the problem given the above constraints.

You can tell the answer cited there does not work -- it does not produce an integer $T$ matrix. In general, Mathematica output for the claimed answer in the previous post like B.MatrixPower[Inverse[B].Inverse[A], 1/2] and $(B^{-1}A^{-1})^{1/2}$ gives a non-integer matrix, failing to satisfy the above conditions. In fact the quoted answer does not even solve a rank-2 toy model correctly.

Let me provide a different $A$ and the same $B$:

A = {{2, -1, 0, 0, 0, 0, 0, 0, 0, 0},
     {-1, 2, -1, 0, 0, 0, -1, 0, 0, 0},
     {0, -1, 2, -1, 0, 0, 0, 0, 0, 0},
     {0, 0, -1, 2, -1, 0, 0, 0, 0, 0},
     {0, 0, 0, -1, 2, -1, 0, 0, 0, 0},
     {0, 0, 0, 0, -1, 2, 0, 0, 0, 0},
     {0, -1, 0, 0, 0, 0, 2, -1, 0, 0},
     {0, 0, 0, 0, 0, 0, -1, 2, 0, 0},
     {0, 0, 0, 0, 0, 0, 0, 0, 1, 0},
     {0, 0, 0, 0, 0, 0, 0, 0, 0, -1}};
     
B = {{1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
     {0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
     {0, 0, 1, 0, 0, 0, 0, 0, 0, 0},
     {0, 0, 0, 1, 0, 0, 0, 0, 0, 0},
     {0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
     {0, 0, 0, 0, 0, 1, 0, 0, 0, 0},
     {0, 0, 0, 0, 0, 0, 1, 0, 0, 0},
     {0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
     {0, 0, 0, 0, 0, 0, 0, 0, 1, 0},
     {0, 0, 0, 0, 0, 0, 0, 0, 0, -1}};

Hint

There indeed exists an integer $T$ matrix solve the equation Transpose[T].A.T == B:

T = {{-5, -5, -5, 5, 5, 5, 5, 5, 8, 16},
     {-10, -10, -10, 9, 9, 9, 9, 9, 15, 30},
     {-8, -8, -8, 8, 7, 7, 7, 7, 12, 24},
     {-6, -6, -6, 6, 6, 5, 5, 5, 9, 18},
     {-4, -4, -4, 4, 4, 4, 3, 3, 6, 12},
     {-2, -2, -2, 2, 2, 2, 2, 1, 3, 6},
     {-7, -7, -6, 6, 6, 6, 6, 6, 10, 20},
     {-4, -3, -3, 3, 3, 3, 3, 3, 5, 10},
     {1, 1, 1, -1, -1, -1, -1, -1, -3, -4},
     {-2, -2, -2, 2, 2, 2, 2, 2, 4, 7}};

My question now is: Could you provide an algorithm to search for the integer matrix $T$ efficiently for a large-rank matrix? (in this case, it is a rank-10 matrix)

I believe ResourceFunction["GramianReduce"] may help.

Answer 1

If you implement your example by $$\text{Table}[A_{ik} == \sum_{st}T_{si}\ B_{st}\ T_{tk},\{i,1,n\},\{k,1,n\}]$$ you get $n^2$ quadratic constant forms for n^2 variables, that, by elimination, produce algebraic expressions with powers higher than 4.

So even exact complex valued solutions are not at hand, if the system does not factor into a complete chain of solvable subgroups. Numerical complex solutions are fast.

The minors of T given, range up to 300. There will be no other way as brute force search over a lattice of 300^8.

On the other hand, a search for working examples is not faster, the determinant condition is only a reduction of complexity by 1 equation of order x^n.