Hongyi Zhao on Mon, 02 Jan 2023 04:29:44 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Solve an non-homogeneous system of equations mod Z. |
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