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

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

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));
[ 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