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