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

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

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]


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