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

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.

• It's a good question. Dec 11, 2023 at 20:32
• In an earlier version of this question you gave two smaller examples. Try A={{0,1},{1,0}};B={{0,1},{1,2}};T={{t1,t2},{t3,t4}};FindInstance[Transpose[T].A.T==B&&(Det[T]==1||Det[T] ==-1),Flatten[T],Integers,5] and A={{0,1},{1,0}};B={{2,5},{5,12}};T={{t1,t2},{t3,t4}};FindInstance[Transpose[T].A.T==B&&(Det[T]==1||Det[T]==-1),Flatten[T], Integers,5] both of which quickly give you multiple integer unimodular matricies T which satisfy your equations. Time those. Then time 5x5 and 6x6 and ... and see if you can estimate the amount of time it will take to find solutions for 10x10. Then you are done
– Bill
Dec 11, 2023 at 22:29
• @DanielLichtblau I ALWAYS assume there is someone much much brighter than I who can see a slick algorithmic solutions that I will never find. My tiny offering here was only to present to him that there was at least one way in Mathematica to get a few small solutions.
– Bill
Dec 11, 2023 at 22:51
• @DanielLichtblau I can't fully back this up, but I'm of the opinion that there isn't a slick (read efficient) way to do this beyond just using a sat-solver / NLIP. Because an efficient solution to this would appear to greatly simplify the lattice isomorphism problem which is known to be difficult in higher dimensions. Dec 11, 2023 at 23:18
• Show us how the matrices A and B were created... Dec 12, 2023 at 13:13

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.