Re: Solve Equations over Finite Group

*To*: mathgroup at smc.vnet.net*Subject*: [mg13742] Re: Solve Equations over Finite Group*From*: Daniel Lichtblau <danl>*Date*: Wed, 19 Aug 1998 01:38:31 -0400*Organization*: Wolfram Research, Inc.*References*: <6qp3dg$ajt@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

Alexander Craig Russell wrote: > > Is anyone familiar with a mathematica package which allows one to solve > equations over a finite group? Given > > (1 2 3) x (1 2 3)^(-1) x^(-1) = (1 3 2) > > (in S_3, say) I would like the package to respond with x = (1 2). > > For general groups (described as subgroups of S_n) I would like the > same. Do such things exist? > > Many thanks, > > Alex Russell > UT Dept. of Computer Sci. I do not have a very good answer. Below might be a start for handling these types of problems in general. First represent the permutations as matrices, impose a unitary condition, then find a Groebner basis. You may want to double-check that I got the permutations correct. mat1 = {{0,1,0},{0,0,1},{1,0,0}}; mat1inv = Inverse[mat]; mat2 = {{0,0,1},{1,0,0},{0,1,0}}; xx = Array[x, {3,3}]; vars = Flatten[xx]; expr1 = Flatten[mat1.xx.mat1inv - mat2.xx]; expr2 = Flatten[xx.Transpose[xx] - IdentityMatrix[3]]; expr = Join[expr1, expr2]; gb = GroebnerBasis[expr, vars]; Trial and error shows that this is not sufficient to get a solution, so we then allow the last matrix element in the permutation we seek to be either zero or one, and solve each case separately. It appears to work better modulo 2. dropMod = HoldPattern[Modulus->2] :> Sequence[] In[64]:= soln1 = xx /. (Union[Solve[Join[Thread[gb==0],{x[3,3]==0,Modulus==2}], vars, Sort->False]] /. dropMod) Out[64]= {{{0, 0, 1}, {0, 1, 0}, {1, 0, 0}}, > {{1, 0, 0}, {0, 0, 1}, {0, 1, 0}}} In[65]:= soln2 = xx /. (Union[Solve[Join[Thread[gb==0],{x[3,3]==1,Modulus==2}], vars, Sort->False]] /. dropMod) Out[65]= {{{0, 1, 0}, {1, 0, 0}, {0, 0, 1}}} It is realized that this is a very awkward Solve interface, and we plan to revamp it in a future release. In any case, it appears that we have three valid solutions, one of which (the one in soln2) is the permutation (1 2). In[67]:= Map[(mat1.#.mat1inv.Inverse[#]-mat2 === zeroMat)&, Join[soln1,soln2]] Out[67]= {True, True, True} I hope this is helpful in general, though I am by no means overly optimistic. But maybe you can see a better way to impose the "permutation matrix" conditions that will lead to simpler code. Daniel Lichtblau Wolfram Research