I have group elements, that I'd like to condense down according to group rules. Take the modular group. This has generators $S,T$ that satisfy the groups relations $S^2 = I, (ST)^3 = I$.

So given a group element as a list of generators (for instance, $S T^2 S$ I'd write as {S,T,T,S} in Mathematica), I'd like to collapse the expression down according to group rules.

For instance, in our example, we'd have

Collapse[{S,T,S,S,T}] = {S,T,T}

I've tried using ReplaceAll, but can't get it to match substrings. StringReplace seems to have the correct functionality, but only works on actual strings.

How would one go about doing this?

  • 1
    $\begingroup$ In general, this is sort of a hard problem. My take on it in the past has been to choose a "normal order", since writing group elements in terms of generators is not unique in general. Maybe start with this question and answer. I know there are many more on this site. The real question is, what do you want to do with this? Do you want to have a list of all the group elements in terms of the generators? How do you decide when you're done? $\endgroup$
    – march
    Jan 31, 2016 at 18:52
  • $\begingroup$ By the way, does this particular presentation lead to a finite group? $\endgroup$
    – march
    Jan 31, 2016 at 19:04

2 Answers 2


Using replacement Rules

collapse[lst_?VectorQ] := lst //. {
   {b___, S, S, e___} :> {b, e},
   {b___, S, T, S, T, S, T, e___} :> {b, e}}

collapse[{S, T, S, S, T}]

(*  {S, T, T}  *)

collapse[{S, S, T, S, T, S, T, S, T, S, S, T}]

(*  {T, T}  *)
  • 2
    $\begingroup$ I think I would go with {b___, T, S, T, S, T, e___} :> {b, S, e} instead of the second one. It along with the first rule makes your second rule, but this one will get more cases. +1 $\endgroup$
    – march
    Jan 31, 2016 at 19:21

Using SubstitutionSystem:

collapse[lst_?VectorQ, rule_] := Module[{
    str = StringJoin @@ ToString /@ lst},
   Characters@SubstitutionSystem[rule, str]

vecs = {{S, T, S, S, T}, {S, S, T, S, T, S, T, S, T, S, S, T}};

rule = {"SS" -> "", "STSTST" -> ""}


collapse[#, rule] & /@ vecs


{{"S", "T", "T"}, {"T", "T"}}

Here I have assumed that the input vector has Symbols, so a conversion to String is necessary. If the input vectors already have String characters, then another function with the same name but a different input can be defined. To get symbols back, one can additionally run ToExpression on the output of the function.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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