Hongyi Zhao on Fri, 06 Jan 2023 15:16:59 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Solve an non-homogeneous system of equations mod Z. |
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