Re: Find an invertible integer matrix that satisfies given conditions.

[Hongyi Zhao <hongyi.zhao@gmail.com>]

On Wed, Apr 12, 2023 at 5:34 PM Bill Allombert
<Bill.Allombert@math.u-bordeaux.fr> wrote:
>
> On Wed, Apr 12, 2023 at 09:24:45AM +0200, Aurel Page wrote:
> > Dear Zhao,
> >
> > Your problem is equivalent to finding an isomorphism between two
> > Z[t]-lattices. This is a nontrivial task, but there are algorithms for it,
> > if you want an efficient solution. You can look at the work of Tommy
> > Hofmann, he has several papers on this topic. If you don't care too much
> > about efficiency, I think a solution that is reasonable to implement is to
> > first parametrise the set of solutions of the linear equation (with mathnf
> > or matsolvemod), and then backtrack the coefficients, for instance column by
> > column, using the fact that for k columns to admit an extension to an nxn
> > invertible matrix over Z, a necessary and sufficient condition is that their
> > HNF must have k pivots equal to 1. There are also many quick necessary
> > conditions, for instance M1 and M2 must be conjugate over Q and mod p for
> > every p.
>
> For 2x2 matrices, the program in attachment solves it.
>
> M=[1,2;3,4];
> N=[5,-2;-1,0];
> P=isom(M,N)
> M*P-P*N
> matdet(P)
>
> ? P=isom(M,N)
> %3 = [1,0;2,-1]
> ? M*P-P*N
> %4 = [0,0;0,0]
> ? matdet(P)
> %5 = -1
>
> Over the rationals, the problem can be solved with matfrobenius(,1). Sometime
> we are lucky and get an integral matrix.
>
> M1 = [0, 1, 0, 0; -4, 0, 0, 0; 0, 0, 0, 1; 0, 0, -4, 0];
> M2 = [0, 1, 4, 0; -4, 0, 0, -4; 0, 0, 0, 1; 0, 0, -4, 0];
> [F1,P1]=matfrobenius(M1,2)
> [F2,P2]=matfrobenius(M2,2)
> P = P1^-1*P2
> matdet(P)
> M1*P-P*M2
>
> ? P = P1^-1*P2
> %5 = [1,0,0,1;0,1,0,0;0,0,1,0;0,0,0,1]
> ? matdet(P)
> %6 = 1
> ? M1*P-P*M2
> %7 = [0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0]
>
> So here P is the solution.
>
> In general:
> 1) compute the matrix of the linear map P -> M1*P-P*M2
> 2) compute a basis of its integral kernel (K_1,...,K_r) with matkerint
> 3) solve the Diophantine equation matdet(sum x_i*K_i) = ą1 (with unknown x_1,...,x_r).
> 4) Return P = sum x_i*K_i
>
> The difficult part is obviously 3).
> For n=2, the Diophantine equation is a binary quadratic form, so can be solved by PARI.
> Hofmann shows that solving the equation can be reduced to solve a set of
> norm equations in orders of number fields.

I am very grateful to Bill Allombert and Aurel Page for providing me
with valuable information and algorithm implementations.

Based on the clues here, I checked the works done by Tommy Hofmann
[1], and it seems that there are no publically available
implementations of his method, such as in open source codes, like GAP
or PARI/GP. So, I'm still not sure if it's possible to implement his
algorithms based on open source tools solely, and then use them as a
starting point to do the further study.

After all, this is a very complex matter. To independently implement
it relying solely on the algorithm description in the paper, one
requires a strong mathematical foundation and proficient mastery of
the corresponding software.

[1] https://www.thofma.com/research/

> Cheers,
> Bill

Best,
Zhao