3
$\begingroup$

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.

$\endgroup$
23
  • 4
    $\begingroup$ It's a good question. $\endgroup$ Dec 11, 2023 at 20:32
  • 2
    $\begingroup$ 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 $\endgroup$
    – Bill
    Dec 11, 2023 at 22:29
  • 2
    $\begingroup$ @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. $\endgroup$
    – Bill
    Dec 11, 2023 at 22:51
  • 2
    $\begingroup$ @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. $\endgroup$
    – flinty
    Dec 11, 2023 at 23:18
  • 1
    $\begingroup$ Show us how the matrices A and B were created... $\endgroup$ Dec 12, 2023 at 13:13

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.