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

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

On Mon, Jan 2, 2023 at 11:28 AM Hongyi Zhao <hongyi.zhao@gmail.com> wrote:
>
> On Sun, Jan 1, 2023 at 11:42 PM Bill Allombert
> <Bill.Allombert@math.u-bordeaux.fr> wrote:
> >
> > On Sun, Jan 01, 2023 at 11:17:52PM +0800, Hongyi Zhao wrote:
> > > Hi here,
> > >
> > > I've a set of matrices and vectors as follows:
> > >
> > > mats:= [
> > > [ [ -2, 0, 0 ], [ 0, -2, 0 ], [ 1, 1, 0 ] ],
> > > [ [ -2, 0, 0 ], [ 0, 0, 0 ], [ 0, -1, -2 ] ],
> > > [ [ 0, 1, 2 ], [ 1, -1, 0 ], [ -1, 0, -2 ] ],
> > > [ [ -1, 1, 0 ], [ 1, -1, 0 ], [ -1, -1, -2 ] ],
> > > [ [ -2, 0, 0 ], [ 0, -2, 0 ], [ 0, 0, -2 ] ]
> > > ];
> > > vecs:=  [
> > > [ -23/8, 17/8, -9/8 ],
> > > [ 17/8, 1, -3 ],
> > > [ 0, 0, 0 ],
> > > [ 1, -2, -15/16 ],
> > > [ 1/8, -23/8, 15/16 ]
> > > ];
> >
> > When posting to this list, please use PARI/GP syntax, not GAP syntax.
> > GAP does not use the same convention for matrix action than PARI,
> > mixing the two can only lead to confusion.
>
> Thank you for your advice. I'm a real newbie of PARI/GP. Therefore,
> the above writing is only the purpose of laziness and rapid
> description of the problem. I will pay attention to this problem in
> the future and use PARI/GP syntax.
>
> > > 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)
>
> The above description is still quite incomprehensible. Therefore, I am
> helpless and take the following example based on GAP to illustrate
> this problem, because I really don't know how to explain this problem
> through PARI/GP:
>
> gap> mat:=[ [ -2, 0, 0 ], [ 0, -2, 0 ], [ 1, 1, 0 ] ];
> [ [ -2, 0, 0 ], [ 0, -2, 0 ], [ 1, 1, 0 ] ]
> gap> vec1:=[ -23/8, 17/8, -9/8 ];
> [ -23/8, 17/8, -9/8 ]
> gap> vec2:=List(vec, x -> FractionModOne(x));

Sorry for my typo. The above line should be written as:

vec2:=List(vec1, x -> FractionModOne(x));

> [ 1/8, 1/8, 7/8 ]
> gap> # false means acting on left, a.k.a,
> gap> # compute the set of solutions of the equation
> gap> # M * x = b  (mod Z).
> gap> sol1:=SolveInhomEquationsModZ(mat, vec1, false);
> [ [ [ 15/16, 15/16, 0 ], [ 7/16, 7/16, 0 ] ], [ [ 0, 0, 1 ] ] ]
> gap> sol2:=SolveInhomEquationsModZ(mat, vec2, false);
> [ [ [ 15/16, 15/16, 0 ], [ 7/16, 7/16, 0 ] ], [ [ 0, 0, 1 ] ] ]
> gap> sol1=sol2;
> true
> gap> # These soloutions are all on the interger lattice spanned by vec2:
> gap> List(Union(sol1), x -> VectorModL(mat * x, [vec2] ));
> [ [ 0, 0, 0 ], [ 0, 0, 7 ], [ 0, 0, 15 ] ]
>
> > > Any tips for tackling this problem?
> >
> > I suggest you look up matrixqz.
>
> Based on the document of this command, I tried the following, but
> still don't know how to tackle the problem discussed here:
>
> ? mat=[-2, 0, 0; 0, -2, 0; 1, 1, 0]
> %21 =
> [-2  0 0]
>
> [ 0 -2 0]
>
> [ 1  1 0]
>
> ? vec=[ -23/8, 17/8, -9/8 ]
> %22 = [-23/8, 17/8, -9/8]
> ? matrixqz(mat~,{p=-1})
> %23 =
> [2 1]
>
> [0 1]
>
> [0 0]
>
>
> [1] https://en.wikipedia.org/wiki/Integer
>
> > Cheers,
> > Bill.
>
> Best,
> Zhao