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 /.
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 /.
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[] ?