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

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

On Fri, Jan 6, 2023 at 10:09 PM Loïc Grenié <loic.grenie@gmail.com> wrote:
>
>
>
> Le ven. 6 janv. 2023 à 05:49, Hongyi Zhao <hongyi.zhao@gmail.com> a écrit :
>>
>> 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
>
>
>   vec1 should be a column, either use
>
> vec1 = [ -27, -28, 105/2 ]~
>
>   or
>
> vec1 = Col([ -27, -28, 105/2 ])

Thank you for your correction.

>    (same thing for [1,1,1]). Additionally, vec1 has non integral entries, and
>   it is not permissible for matsolvemod.

But in my case, I must tackle non-integral entries, as you've seen. Is
there no way to solve the problem?

>        Hope this helps,
>
>            Loïc

Best,
Zhao