5
$\begingroup$

It seems that Mathematica only has group functionality for permutation groups? Then there is a step to transform the abstract finite one to a permutation one.

As an example, consider the following problem

Suppose $G=<a,b|a^2=1,b^3=1,(ab)^2=1>$, try to compute $ab^2ab^2a$.

It can proceed by viewing the elements of group just as a string, and the rule of group can be view as a rule of string replace. Any way, I would like to use NonCommutativeMultiply instead:

Firstly, let us define the rule, basically, we only need to define the rule for $ab$ and $ba$, since whenever we know how to commute these two generators, then we can use the fact $a^2=1=b^3$ to simplify our expression. It is not hard to compute $ab=b^2a$, $ba=ab^2$:

rel = {c___ ** a ** a ** d___ :> c ** i ** d, 
  c___ ** b ** b ** b ** d___ :> c ** i ** d, 
  c___ ** a ** b ** d___ :> c ** b ** b ** a ** d, 
  c___ ** b ** a ** d___ :> c ** a ** b ** b ** d , a___ ** i :> a, 
  i ** a___ :> a}

Now, let us define the set of group elements. Since $a$ is a order 2 element and $b$ is order $3$, we know that $G$ must be a subgroup of order $6=o(a)\times o(b)$, thus the elements can be expressed by

set = {i, a, b, b ** b, a ** b, b ** a}

Lastly, we can compute what's the results of $a$ multiply from left:

a ** # & /@ set/.rel

The problem: It seems my rule has not do the function of simplify the expression, as you can see the results is

{a, NonCommutativeMultiply[i], b ** b ** a, b ** b ** a ** b, i ** b, 
   b ** b ** a ** a}

the element b**b**a**a should be b**b, so please help me to correct the rule?

The correct result should be

aset = {a, i, a ** b, b ** a, b, b ** b}

form which we can find the permutation by

FindPermutation[set, aset]

which gives

Cycles[{{1, 2}, {3, 5}, {4, 6}}]
$\endgroup$
4
$\begingroup$

For simplicity, let's set

ncm[a__] := NonCommutativeMultiply[a]

My recommendation for this problem is to choose a "normal order" for the group elements. That is, I would choose to represent the group elements in such a way that all the a's are to the left of the b's. To do this, we define our set of replacements in such a way that b's always move to the right:

rel = {ncm[c___, a, a, d___] :> ncm[c, i, d]
  , ncm[c___, b, b, b, d___] :> ncm[c,i, d]
  , ncm[c___, b, b, a, d___] :> ncm[c, a, b, d]
  , ncm[c___, b, a, d___] :> ncm[c, a, b, b, d]
  , ncm[a__, i] :> ncm[a]
  , ncm[i, a__] :> ncm[a]
  , ncm[a_] :> a
 }

This guarantees that when we apply the rules repeatedly (which we have to do), the process will eventually terminate.

Then, we get the group elements into normal order by using ReplaceRepeated with the replacement rules rel:

set = {i, a, b, b ** b, a ** b, b ** a} //. rel
(* {i, a, b, b ** b, a ** b, a ** b ** b} *)

So, instead of using b ** a as one of the elements, we use the slightly more complicated (but it turns out easier to use) a ** b ** b.

Finally, then, multiplication on the left by a results in

aset = a ** # & /@ set //. rel
(* {a, i, a ** b, a ** b ** b, b, b ** b} *)

and

FindPermutation[set, aset]
(* Cycles[{{1, 2}, {3, 5}, {4, 6}}] *)

Brief explanation

To answer your questions:

  • NonCommutativeMultiply has very little rules associated with it. In particular, ncm[a] doesn't evaluate, i.e. it just evaluates to ncm[a]. So we have to add the rule that if we have ncm[i], for instance, this will evaluate to i.

  • _ is Blank. It is a pattern that will match any single expression. __ is BlankSequence. It is a pattern will match any sequence of one or more expressions. ___ is BlankNullSequence. It will match any sequence of expressions, including the Null Sequence. Meditate on the results of these three evaluations:

    {f[], f[a], f[a, b]} /. f[_] :> f[1]

    {f[], f[a], f[a, b]} /. f[__] :> f[1]

    {f[], f[a], f[a, b]} /. f[___] :> f[1]

$\endgroup$
  • $\begingroup$ Nice answer, +1 $\endgroup$ – ciao Oct 4 '15 at 4:46
  • $\begingroup$ thanks a lot, the idea to move b to right is great!! Could you please explain why we need ncm[a_]:>a to stop the loop of replacement? And what's the difference of a_, a__, and a___ in this answer? I have read the manual, but still confused when I try to use it, if possible, please explain it to me the difference, Thanks again! $\endgroup$ – van abel Oct 4 '15 at 5:39
  • $\begingroup$ by the way, the second rule should be replaced to be ncm[c,i,d], or it may produce ncm[]. $\endgroup$ – van abel Oct 5 '15 at 1:21
  • $\begingroup$ @vanabel: Yes absolutely, thanks for pointing that out! I'll fix it now. $\endgroup$ – march Oct 5 '15 at 1:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.