homogeneous-rees-mat.g

# In GAP 4.9.1 or higher, with the Semigroups package 3.0.16 or higher
LoadPackage("semigroups");

# A function for finding all the subsemigroups of a semigroup 
# (this will only work for extremely small semigroups, due it being a quick implementation, and due to the inherent complexity)

Subsemigroups := function(S)
  local foo, M, N;
  foo := function(M)
    return Unique(Concatenation(List(M, MaximalSubsemigroups)));
  end;
  M := MaximalSubsemigroups(S);
  N := foo(M);
  while M <> N do
    M := N;
    N := foo(M);
  od;

  return M;
end;

# A function for checking if an isomorphism 'map' is a restriction of an automorphism

IsRestrictedAutomorphism := function(S, map)
  return ForAny(AutomorphismGroup(S),
                x -> OnTuples(AsList(Source(map)), x) =
                     OnTuples(AsList(Source(map)), map));
end;

# A helper function
PartitionByFunc := function ( list, func )
    local lookup, nr, val, out, i, j;
    lookup := [  ];
    nr := 0;
    for i in [ 1 .. Length( list ) ] do
        if not IsBound( lookup[i] ) then
            nr := nr + 1;
            lookup[i] := nr;
            for j in [ i + 1 .. Length( list ) ] do
                if not IsBound( lookup[j] ) and func( list[i], list[j] ) then
                    lookup[j] := nr;
                fi;
            od;
        fi;
    od;
    out := List( [ 1 .. nr ], function ( x )
            return [  ];
        end );
    for i in [ 1 .. Length( list ) ] do
        Add( out[lookup[i]], list[i] );
    od;
    return out;
end

# The main function, which if the semigroup is not homogeneous returns a pair of isomorphic subsemigroups, and an isomorphism between them that does not extend to an automorphism

IsHomogeneous := function(S)
  local SS, i, map1, inv1, conj, map2, class, j, a;
  SS := PartitionByFunc(Subsemigroups(S), IsIsomorphicSemigroup);
  for class in SS do
    i    := PositionProperty(class, IsReesMatrixSemigroup);
    map1 := IsomorphismReesMatrixSemigroup(class[i]);
    inv1 := InverseGeneralMapping(map1);
    conj := auto -> CompositionMapping2(inv1, CompositionMapping2(auto, map1));
    for j in [1 .. Length(class)] do
      map2 := IsomorphismSemigroups(class[i], class[j]);
      for a in AutomorphismGroup(Range(map1)) do
        if not IsRestrictedAutomorphism(S,
                                        CompositionMapping2(map2, conj(a))) then
          return [class[i], class[j], CompositionMapping2(map2, conj(a))];
        fi;
      od;
    od;
  od;
  return true;
end;

# Define the cyclic group
G := CyclicGroup(IsPermGroup, 3);

# Let a be the first generator of G
a := G.1;

# Let e be the identity of G
e := One(G);

# Define the sandwich matrix of the semigroup from your email
mat := [[e, e, e], [e, a, a ^ 2], [e, a ^ 2, a]];

# Define the Rees matrix semigroups itself
S := ReesMatrixSemigroup(G, mat);
IsHomogeneous(S); # returns true