MathGroup Archive 1998

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: Re: Fourier Transform
  • Next by Date: Re: Dimensions and Variables
  • Previous by thread: Re: Solve Equations over Finite Group
  • Next by thread: High precision numbers and Plot[] ?