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

[Aurel Page <aurel.page@normalesup.org>]

    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.
    
    Cheers,
    Aurel

On 12/04/2023 05:22, Charles Greathouse wrote:

Sorry, I missed the determinant condition. That definitely makes it harder (that being a quartic condition).

On Tue, Apr 11, 2023 at 11:01 PM Charles Greathouse <crgreathouse@gmail.com> wrote:

Playing around  with linear algebra gives, as an example,

[4,-1,1,4; 4, 4, 0, 5; 4, -1, 5, 4; 4, 4, 0, 9]

There are 8 degrees of freedom here so you have lots of choices to make.

I'll let the real PARI experts suggest code here.

On Tue, Apr 11, 2023 at 9:21 PM Hongyi Zhao <hongyi.zhao@gmail.com> wrote:

Hi here,

I am trying to write a script to find a matrix that satisfies certain
conditions. Specifically, I am trying to find an n x n matrix M that
satisfies the following two conditions:

1. The determinant of M is either 1 or -1.
2. M1 * M = M * M2, where M1 and M2 are two pre-defined matrices.

I have written the following code, but it can't solve the problem:

```
/* Define the two matrices */
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];

/* Set the size of the matrix */
n = 4;

/* Initialize a flag variable to check if a solution has been found */
flag = 0;

/* Loop until a solution is found */
while(flag == 0,

    /* Generate a random integer matrix */
    M = matrix(n,n,i,j,random(-10,10));

    /* Check if the matrix satisfies the conditions */
    if(abs(Mat(det(M))) == 1 && Mat(M1 * M) == Mat(M * M2),

        /* If the conditions are satisfied, print the matrix and exit
the loop */
        print("Found solution:");
        print(M);
        flag = 1;
    );
);
```

In fact, this is a harder problem as described here [1], I'm not sure
whether it's possible to tackle it in PARI/GP? Thank you in advance
for your help.

[1] https://arxiv.org/abs/1811.06190

Best regards,
Zhao
--
Assoc. Prof. Hongsheng Zhao <hongyi.zhao@gmail.com>
Theory and Simulation of Materials
Hebei Vocational University of Technology and Engineering
No. 473, Quannan West Street, Xindu District, Xingtai, Hebei province