Re: Solve an non-homogeneous system of equations mod Z.

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

On Thu, Jan 5, 2023 at 1:00 PM Hongyi Zhao <hongyi.zhao@gmail.com> wrote:
>
> On Thu, Jan 5, 2023 at 5:18 AM Bill Allombert
> <Bill.Allombert@math.u-bordeaux.fr> wrote:
> >
> > On Mon, Jan 02, 2023 at 11:28:25AM +0800, Hongyi Zhao wrote:
> > > > > I want to find a common set of solutions, a.k.a., x, for the above
> > > > > matrices and their corresponding vectors, which satisfy the following
> > > > > conditions:
> > > > >
> > > > >   mat * x = vec  (mod Z). \forall mat \in mats, and \forall vec \in
> > > > > vecs in the corresponding order.
> > > >
> > > > What is Z ?
> > >
> > > I mean the set of integers [1], which is often denoted by the
> > > \textbf{Z} or \mathbb{Z}.
> > >
> > > In my case, the actual meaning is that the mod 1 of each component of
> > > the vector vec, a.k.a.,
> > >
> > > mat * x = vec  (mod 1 for all components of the vector)
> >
> > So you mean (mod Z^n) where n is the dimension.
> >
> > The set of solutions is an affine lattice.
>
> Thank you for pointing this out.
>
> In my case, all the matrices are unimodular integral and the group
> generated by them is finite. Thus the set of solutions should be an
> affine unimodular lattice Λ, with its linear part, denoted by g, \in
> GL(d, Z) and its translation part, denoted by x, in Q^d. This is the
> orbit of a point x \in Q^d under translations by an unimodular
> integral lattice, a.k.a., the affine unimodular lattice Λ has the form
>
>   Λ = g * Z^d + x,
>
> where g \in GL(d, Z) and x is well-defined up to translation by g *
> Z^d, that is, it can be
> viewed as an element of the d-torus Q^d / (g * Z^d).
>
> Due to my number theory foundation is very poor, if there are any
> problems in my above description, please point out or correct them.
>
> > You can embbed the affine space to a n+1 dimensional linear space and
> > compute the intersection of your affine lattices there.
>
> Thank you again for your wonderful tips.
>
> In fact, the motivation behind my question is as follows: I have two
> unimodular integral affine matrix groups and they each have two
> generators as shown below:
>
> ? gen1=[ [ 0, -1, 0, 2; -31, -31, -32, 2; 30, 31, 31, -61/16; 0, 0, 0,
> 1], [ -120, -109, -120, -15/4; -101, -90, -100, -25/8; 210, 189, 209,
> 13/2; 0, 0, 0, 1 ]  ]
> %33 = [[0, -1, 0, 2; -31, -31, -32, 2; 30, 31, 31, -61/16; 0, 0, 0,
> 1], [-120, -109, -120, -15/4; -101, -90, -100, -25/8; 210, 189, 209,
> 13/2; 0, 0, 0, 1]]
> ? gen2=[ [ 131, 121, 132, 1/2; 101, 90, 100, 3/4; -221, -201, -221,
> -19/16; 0, 0, 0, 1 ], [ -101, -90, -100, 91/8; -131, -121, -132, 85/8;
> 221, 201, 221, -21; 0, 0, 0, 1 ] ]
> %34 = [[131, 121, 132, 1/2; 101, 90, 100, 3/4; -221, -201, -221,
> -19/16; 0, 0, 0, 1], [-101, -90, -100, 91/8; -131, -121, -132, 85/8;
> 221, 201, 221, -21; 0, 0, 0, 1]]
>
> My goal is to find the generators of the affine unimodular lattice,
> which serves as the solutions set of the conjugators between the above
> two groups, and if no such lattice exists, how can this fact be
> quickly determined?
>
>
> > If GAP has a function SolveInhomEquationsModZ, this will be probably easier
> > with GAP.
>
> Though GAP has the above function, but it was developed more than a
> decade ago and the implementation is not based on a strictly
> systematic lattice related number theory method. Therefore, it is
> impossible to determine the generators of the affine lattice through
> the solution set.
>
> > With PARI you can use matkerint and mathnf.
>
> I have tried as follows, but still not sure what the exact steps are
> for the problem discussed here:
>
> The matrices used here are:
>
> mat1 = [ -210, -210, -220; -221, -222, -232; 410, 411, 430 ]
> mat2 = [-132, -121, -132;  -120, -110, -120; 240, 220, 240]
>
> The corresponding vectors are:
>
> vec1 = [ -27, -28, 105/2 ]
> vec2 = [ -47/8, -29/4, 25/2 ]]
>
> So I try to embed the affine space in an n+1 dimensional linear space
> and then compute the intersection of your affine lattices as follows:
>
> ? m1=[ -210, -210, -220, -27; -221, -222, -232, -28; 410, 411, 430,
> 105/2; 0, 0, 0, 1 ]
> %25 =
> [-210 -210 -220   -27]
>
> [-221 -222 -232   -28]
>
> [ 410  411  430 105/2]
>
> [   0    0    0     1]
>
> ? m2=[-132, -121, -132, -47/8;  -120, -110, -120, -29/4; 240, 220,
> 240, 25/2; 0, 0, 0,1]
> %23 =
> [-132 -121 -132 -47/8]
>
> [-120 -110 -120 -29/4]
>
> [ 240  220  240  25/2]
>
> [   0    0    0     1]
>
>
> ? mathnf( matkerint(m1) )
> %26 =
> [-12]
>
> [-10]
>
> [ 21]
>
> [  0]
>
> ? mathnf( matkerint(m2) )
> %27 =
> [-11 -1]
>
> [ 12  0]
>
> [  0  1]
>
> [  0  0]

I also tried the following, but still failed:

? mat1 = [ -210, -210, -220; -221, -222, -232; 410, 411, 430 ]
%8 =
[-210 -210 -220]

[-221 -222 -232]

[ 410  411  430]

? vec1 = [ -27, -28, 105/2 ]
%9 = [-27, -28, 105/2]

? matsolvemod(mat1,[1,1,1],vec1~,1)
  ***   at top-level: matsolvemod(mat1,[1,1,1],vec1~,1)
  ***                 ^---------------------------------
  *** matsolvemod: incorrect type in matsolvemod (D) (t_VEC).
  ***   Break loop: type 'break' to go back to GP prompt


> So far, as you can see, I still haven't seen any clues and information
> related to the final solution set.
>
> > Cheers,
> > Bill
>
> Best,
> Zhao