Quelle  semiffmat.gi   Sprache: unbekannt

#############################################################################
##
##  semigroups/semiffmat.gi
##  Copyright (C) 2015-2022                              James D. Mitchell
##                                                         Markus Pfeiffer
##
##  Licensing information can be found in the README file of this package.
##
#############################################################################
##

# Contents:
# 1. Isomorphisms for semigroups
# 2. Isomorphisms for monoids
# 3. Printing and viewing
# 4. Random
# 5. Methods for acting semigroup setup
# 6. Properties of matrix over finite field semigroups

#############################################################################
# 1. Isomorphisms for semigroups
#############################################################################

# fallback method: via a transformation semigroup

InstallMethod(IsomorphismSemigroup,
"for IsMatrixOverFiniteFieldSemigroup and a semigroup",
[IsMatrixOverFiniteFieldSemigroup, IsSemigroup],
SEMIGROUPS.DefaultIsomorphismSemigroup);

InstallMethod(IsomorphismSemigroup,
"for IsMatrixOverFiniteFieldSemigroup, a ring, and a semigroup",
[IsMatrixOverFiniteFieldSemigroup, IsRing, IsSemigroup],
function(filt, R, S)
  local iso1, inv1, iso2, inv2;

  if not (IsField(R) and IsFinite(R)) then
    ErrorNoReturn("the 2nd argument (a ring) must be a finite field");
  fi;

  iso1 := IsomorphismTransformationSemigroup(S);
  inv1 := InverseGeneralMapping(iso1);
  iso2 := IsomorphismSemigroup(filt, R, Range(iso1));
  inv2 := InverseGeneralMapping(iso2);

  return SemigroupIsomorphismByFunctionNC(S,
                                          Range(iso2),
                                          x -> (x ^ iso1) ^ iso2,
                                          x -> (x ^ inv2) ^ inv1);
end);

InstallMethod(IsomorphismSemigroup,
"for IsMatrixOverFiniteFieldSemigroup and a finite field matrix semigroup",
[IsMatrixOverFiniteFieldSemigroup, IsMatrixOverFiniteFieldSemigroup],
{filt, S} -> SemigroupIsomorphismByFunctionNC(S, S, IdFunc, IdFunc));

InstallMethod(IsomorphismSemigroup,
"for IsMatrixOverFiniteFieldSemigroup, ring, and matrix over ff semigroup",
[IsMatrixOverFiniteFieldSemigroup,
 IsRing,
 IsMatrixOverFiniteFieldSemigroup],
function(_, R, S)
  local D, map, inv, T;
  D := BaseDomain(Representative(S));
  if D = R then
    return SemigroupIsomorphismByFunctionNC(S, S, IdFunc, IdFunc);
  elif Size(D) <= Size(R) and IsIdenticalObj(FamilyObj(D), FamilyObj(R))
      and DegreeOverPrimeField(R) mod DegreeOverPrimeField(D) = 0 then
    map := x -> Matrix(R, x);
    inv := x -> Matrix(D, x);
    T   := Semigroup(List(GeneratorsOfSemigroup(S), map));
    return SemigroupIsomorphismByFunctionNC(S, T, map, inv);
  fi;
  TryNextMethod();  # take an isomorphism to a transformation semigroup
end);

# This is for converting semigroups of GAP library matrices over finite fields
# to IsMatrixOverFiniteFieldSemigroup
InstallMethod(IsomorphismSemigroup,
"for IsMatrixOverFiniteFieldSemigroup and a semigroup of matrices over a ff",
[IsMatrixOverFiniteFieldSemigroup,
 IsSemigroup and HasGeneratorsOfSemigroup and IsFFECollCollColl],
function(_, S)
  local R, map, T;
  # The following line is required because of the weirdness in constructor
  # method selection, if the method for IsMatrixOverFiniteFieldSemigroup was
  # after this method, then the next 3 lines wouldn't be required, but at the
  # same time that'd be less robust.
  if IsMatrixOverFiniteFieldSemigroup(S) then
    TryNextMethod();
  fi;
  R := DefaultFieldOfMatrix(Representative(S));
  map := x -> Matrix(R, x);
  T := Semigroup(List(GeneratorsOfSemigroup(S), map));
  return SemigroupIsomorphismByFunctionNC(S, T, map, AsList);
end);

InstallMethod(IsomorphismSemigroup,
"for IsMatrixOverFiniteFieldSemigroup, a ring, and a ff mat. semigroup",
[IsMatrixOverFiniteFieldSemigroup,
 IsRing,
 IsSemigroup and HasGeneratorsOfSemigroup and IsFFECollCollColl],
function(_, R, S)
  local D, map, T;
  # The following line is required because of the weirdness in constructor
  # method selection, if the method for IsMatrixOverFiniteFieldSemigroup was
  # after this method, then the next 3 lines wouldn't be required, but at the
  # same time that'd be less robust.
  if IsMatrixOverFiniteFieldSemigroup(S) then
    TryNextMethod();
  fi;
  D := BaseDomain(Representative(S));
  if Size(D) <= Size(R) and IsIdenticalObj(FamilyObj(D), FamilyObj(R))
      and DegreeOverPrimeField(R) mod DegreeOverPrimeField(D) = 0 then
    map := x -> Matrix(R, x);
    T := Semigroup(List(GeneratorsOfSemigroup(S), map));
    return SemigroupIsomorphismByFunctionNC(S, T, map, AsList);
  fi;
  TryNextMethod();
end);

InstallMethod(IsomorphismSemigroup,
"for IsMatrixOverFiniteFieldSemigroup and transformation semigroup with gens",
[IsMatrixOverFiniteFieldSemigroup,
 IsTransformationSemigroup and HasGeneratorsOfSemigroup],
 {filt, S} -> IsomorphismSemigroup(IsMatrixOverFiniteFieldSemigroup, GF(2), S));

InstallMethod(IsomorphismSemigroup,
"for IsMatrixOverFiniteFieldSemigroup, a ring, and a transformation semigroup",
[IsMatrixOverFiniteFieldSemigroup,
 IsRing,
 IsTransformationSemigroup and HasGeneratorsOfSemigroup],
function(_, R, S)
  local n, basis, map, iso, inv, gens;

  if not (IsField(R) and IsFinite(R)) then
    ErrorNoReturn("the 2nd argument (a ring) must be a finite field");
  fi;

  n := DegreeOfTransformationSemigroup(S);
  # TODO(later) when GAP allows 0-dimensional matrices and Semigroups requires
  # that version of GAP, then the following if-statement can be removed.
  if n = 0 then
    n := 1;
  fi;
  basis := IdentityMatrix(R, n);
  map := x -> Unpack(basis){ImageListOfTransformation(x, n)};
  iso := x -> Matrix(R, map(x));
  inv := x -> Transformation([1 .. n], i -> PositionNonZero(x[i]));
  gens := List(GeneratorsOfSemigroup(S), iso);

  return SemigroupIsomorphismByFunctionNC(S, Semigroup(gens), iso, inv);
end);

#############################################################################
# 2. Isomorphisms for monoids
#############################################################################

InstallMethod(AsMonoid, "for a matrix over finite field semigroup",
[IsMatrixOverFiniteFieldSemigroup],
function(S)
  if MultiplicativeNeutralElement(S) = fail then
    return fail;  # so that we do the same as the GAP/ref manual says
  fi;
  return Range(IsomorphismMonoid(IsMatrixOverFiniteFieldMonoid, S));
end);

InstallMethod(IsomorphismMonoid,
"for IsMatrixOverFiniteFieldMonoid and a semigroup",
[IsMatrixOverFiniteFieldMonoid, IsSemigroup],
SEMIGROUPS.DefaultIsomorphismMonoid);

InstallMethod(IsomorphismMonoid,
"for IsMatrixOverFiniteFieldMonoid, a ring, and a semigroup",
[IsMatrixOverFiniteFieldMonoid, IsRing, IsSemigroup],
function(filt, R, S)
  local iso1, inv1, iso2, inv2;

  iso1 := IsomorphismTransformationMonoid(S);
  inv1 := InverseGeneralMapping(iso1);
  iso2 := IsomorphismMonoid(filt, R, Range(iso1));
  inv2 := InverseGeneralMapping(iso2);

  return SemigroupIsomorphismByFunctionNC(S,
                                          Range(iso2),
                                          x -> (x ^ iso1) ^ iso2,
                                          x -> (x ^ inv2) ^ inv1);
end);

InstallMethod(IsomorphismMonoid,
"for IsMatrixOverFiniteFieldMonoid and a monoid",
[IsMatrixOverFiniteFieldMonoid, IsMonoid],
{filt, S} -> IsomorphismSemigroup(IsMatrixOverFiniteFieldSemigroup, S));

InstallMethod(IsomorphismMonoid,
"for IsMatrixOverFiniteFieldMonoid, a ring, and a monoid",
[IsMatrixOverFiniteFieldMonoid, IsRing, IsMonoid],
{filt, R, S} -> IsomorphismSemigroup(IsMatrixOverFiniteFieldSemigroup, R, S));

InstallMethod(IsomorphismMonoid,
"for IsMatrixOverFiniteFieldMonoid and a matrix over finite field monoid",
[IsMatrixOverFiniteFieldMonoid, IsMatrixOverFiniteFieldMonoid],
{filt, S} -> SemigroupIsomorphismByFunctionNC(S, S, IdFunc, IdFunc));

InstallMethod(IsomorphismMonoid,
"for IsMatrixOverFiniteFieldMonoid, a ring, and a matrix over ff monoid",
[IsMatrixOverFiniteFieldMonoid, IsRing, IsMatrixOverFiniteFieldMonoid],
{filt, R, S} -> IsomorphismSemigroup(IsMatrixOverFiniteFieldSemigroup, R, S));

#############################################################################
# 3. Viewing and printing
#############################################################################

InstallMethod(SemigroupViewStringSuffix,
"for a matrix over finite field semigroup",
[IsMatrixOverFiniteFieldSemigroup],
function(S)
  local n;
  if UserPreference("semigroups", "ViewObj") <> "semigroups-pkg" then
    TryNextMethod();
  fi;
  n := ViewString(NrRows(Representative(S)));
  return Concatenation("\>\>", n, "x", n, "\< \>matrices\< \>over\< \>",
                       ViewString(BaseDomain(S)), "\<\< ");
end);

InstallMethod(ViewObj, "for a general linear monoid",
[IsGeneralLinearMonoid],
Maximum(RankFilter(IsMonoid and HasGeneratorsOfMonoid),
        RankFilter(IsMatrixOverFiniteFieldSemigroup
                   and HasGeneratorsOfSemigroup))
- RankFilter(IsGeneralLinearMonoid) + 1,
function(S)
  PrintFormatted("<general linear monoid {1}x{1} over {2}>",
                 NrRows(Representative(S)),
                 BaseDomain(S));
end);

InstallMethod(PrintString, "for general linear monoid",
[IsGeneralLinearMonoid],
7,  # to beat the method for monoids with generators
function(M)
  local rep, str;

  rep := Representative(M);
  str := Concatenation("GLM(",
                       String(NrRows(rep)),
                       ", ",
                       String(Characteristic(BaseDomain(M))));
  if Characteristic(BaseDomain(M)) <> 1 then
    Append(str, " ^ ");
    Append(str, String(Log(Size(BaseDomain(M)),
                           Characteristic(BaseDomain(M)))));
  fi;
  Append(str, ")");
  return str;
end);

InstallMethod(PrintObj, "for general linear monoid",
[IsGeneralLinearMonoid],
7,  # to beat the method for monoids with generators
function(M)
  Print(PrintString(M));
end);

#############################################################################
# 4. Random
#############################################################################

InstallMethod(SEMIGROUPS_ProcessRandomArgsCons,
[IsMatrixOverFiniteFieldSemigroup, IsList],
function(_, params)

  if Length(params) < 1 then  # nr gens
    params[1] := Random(1, 20);
  elif not IsPosInt(params[1]) then
    return "the 2nd argument (number of generators) is not a pos int";
  fi;
  if Length(params) < 2 then  # dimension
    params[2] := Random(1, 20);
  elif not IsPosInt(params[2]) then
    return "the 3rd argument (matrix dimension) is not a pos int";
  fi;
  if Length(params) < 3 then  # field
    params[3] := GF(Random(Primes), Random(1, 9));
  elif not IsField(params[3]) or not IsFinite(params[3]) then
    return "the 4th argument is not a finite field";
  fi;
  if Length(params) < 4 then  # ranks
    params[4] := [1 .. params[2]];
  elif not IsList(params[4])
      or not ForAll(params[4], x -> IsPosInt(x) and x <= params[2]) then
    return "the 5th argument (matrix ranks) is not a list of pos ints";
  fi;

  if Length(params) > 4 then
    return "there must be at most 5 arguments";
  fi;

  return params;
end);

InstallMethod(SEMIGROUPS_ProcessRandomArgsCons,
[IsMatrixOverFiniteFieldMonoid, IsList],
{filt, params} ->
SEMIGROUPS_ProcessRandomArgsCons(IsMatrixOverFiniteFieldSemigroup, params));

InstallMethod(RandomSemigroupCons,
"for IsMatrixOverFiniteFieldSemigroup and list",
[IsMatrixOverFiniteFieldSemigroup, IsList],
function(_, params)  # params = [nrgens, dim, field, ranks]
  return Semigroup(List([1 .. params[1]], i -> RandomMatrix(params[3],
                                                            params[2],
                                                            params[4])));
end);

InstallMethod(RandomMonoidCons,
"for IsMatrixOverFiniteFieldMonoid and list",
[IsMatrixOverFiniteFieldMonoid, IsList],
function(_, params)  # params = [nrgens, dim, field, ranks]
  return Monoid(List([1 .. params[1]], i -> RandomMatrix(params[3],
                                                         params[2],
                                                         params[4])));
end);

InstallMethod(RandomInverseSemigroupCons,
"for IsMatrixOverFiniteFieldSemigroup and list",
[IsMatrixOverFiniteFieldSemigroup, IsList],
function(filt, params)
  return AsSemigroup(filt,
                     params[3],
                     RandomInverseSemigroup(IsPartialPermSemigroup,
                                            params[1],
                                            params[2]));
end);

InstallMethod(RandomInverseMonoidCons,
"for IsMatrixOverFiniteFieldMonoid and list",
[IsMatrixOverFiniteFieldMonoid, IsList],
function(filt, params)
    return AsMonoid(filt,
                    params[3],
                    RandomInverseMonoid(IsPartialPermMonoid,
                                        params[1],
                                        params[2]));
end);

InstallMethod(BaseDomain, "for a matrix over finite field semigroup",
[IsMatrixOverFiniteFieldSemigroup], S -> BaseDomain(Representative(S)));

InstallMethod(IsGeneratorsOfInverseSemigroup,
"for an ffe coll coll coll ",
[IsFFECollCollColl],
coll -> IsGeneratorsOfSemigroup(coll) and ForAll(coll, x -> x ^ -1 <> fail));

#############################################################################
# 5. Methods for acting semigroups setup
#############################################################################

InstallGlobalFunction(MatrixOverFiniteFieldRowSpaceRightAction,
function(_, vsp, m)
  local nvsp, deg, i;

  Assert(1, IsRowBasisOverFiniteField(vsp));
  Assert(1, IsMatrixObjOverFiniteField(m));
  Assert(1, Rank(vsp) > 0);

  # This takes care of the token element
  if Rank(vsp) > NrRows(m) then
    return RowSpaceBasis(m);
  else
    nvsp := Unpack(vsp!.rows * m);
  fi;
  TriangulizeMat(nvsp);

  deg := Length(nvsp);
  for i in [deg, deg - 1 .. 1] do
    if IsZero(nvsp[i]) then
      Remove(nvsp, i);
    fi;
  od;

  return NewRowBasisOverFiniteField(IsPlistRowBasisOverFiniteFieldRep,
                                    BaseDomain(vsp),
                                    nvsp);
end);

InstallGlobalFunction(MatrixOverFiniteFieldLocalRightInverse,
function(S, V, mat)
  local n, k, W, se, zv, u, j, i;

  Assert(1, IsMatrixOverFiniteFieldSemigroup(S));
  Assert(1, IsRowBasisOverFiniteField(V));
  Assert(1, IsMatrixObjOverFiniteField(mat));
  Assert(1, NrRows(mat) > 0);
  Assert(1, Rank(V) > 0);

  n := NrRows(mat);
  k := Rank(V);

  W := Unpack(V!.rows * mat);

  for i in [1 .. k] do
    Append(W[i], V!.rows[i]);
  od;
  se := SemiEchelonMat(W);
  # If the matrix does not act injectively on V, then there is no right inverse
  # TODO(later) I think we can now simplify things below
  if Number(se.heads{[1 .. n]}, IsZero) > n - k then
    return fail;
  fi;

  for i in [1 .. Length(se.vectors)] do
    W[i] := ShallowCopy(se.vectors[i]);
  od;

  zv := [1 .. 2 * n] * Zero(BaseDomain(mat));
  for i in [1 .. n - Length(W)] do
    Add(W, ShallowCopy(zv));
  od;

  # add missing heads
  u := One(BaseDomain(mat));
  j := k + 1;
  for i in [1 .. n] do
    if se.heads[i] = 0 then
      W[j][i] := u;
      W[j][n + i] := u;
      j := j + 1;
    fi;
  od;
  TriangulizeMat(W);

  return Matrix(W{[1 .. n]}{[n + 1 .. 2 * n]}, mat);
end);

# Returns an invertible matrix.
# TODO(later): make pretty and efficient (in that order).  In particular the
# setup for the matrix should be much more efficient.
InstallGlobalFunction(MatrixOverFiniteFieldSchutzGrpElement,
function(_, x, y)
  local deg, n, eqs, idx, col, row, res;

  Assert(1, IsMatrixObjOverFiniteField(x));
  Assert(1, IsMatrixObjOverFiniteField(y));

  n := Rank(x);
  deg := NrRows(x);

  eqs := TransposedMatMutable(Concatenation(TransposedMat(x),
                                            TransposedMat(y)));
  TriangulizeMat(eqs);

  idx := [];
  col := 1;
  row := 1;

  while col <= deg do
    while IsZero(eqs[row, col]) and col <= deg do
      col := col + 1;
    od;
    if col <= deg then
      Add(idx, col);
      row := row + 1;
      col := col + 1;
    fi;
  od;
  res := Matrix(BaseDomain(x), eqs{[1 .. n]}{idx + deg});
  Assert(1, res ^ (-1) <> fail);
  return res;
end);

# StabilizerAction
InstallGlobalFunction(MatrixOverFiniteFieldStabilizerAction,
function(_, x, m)
  local n, k, rsp, zv, i;
  Assert(1, IsMatrixObjOverFiniteField(x));
  Assert(1, IsFFECollColl(m));
  Assert(1, not IsZero(x));
  Assert(1, not IsZero(m));

  n := NrRows(m);
  k := Rank(x);
  rsp := ShallowCopy(m * RowSpaceBasis(x)!.rows);

  zv := [1 .. n] * Zero(BaseDomain(x));
  for i in [1 .. n - k] do
    Add(rsp, ShallowCopy(zv));
  od;

  return Matrix(RowSpaceTransformationInv(x) * rsp, x);
end);

# This should be doable in a much more efficient way
InstallGlobalFunction(MatrixOverFiniteFieldLambdaConjugator,
function(_, x, y)
  local xse, h, p, yse, q;
  Assert(1, IsMatrixObjOverFiniteField(x));
  Assert(1, IsMatrixObjOverFiniteField(y));
  xse := SemiEchelonMat(Unpack(x));
  h := Filtered(xse.heads, x -> x <> 0);
  p := One(BaseDomain(x))
       * PermutationMat(SortingPerm(h), Length(h), BaseDomain(x));
  yse := SemiEchelonMat(Unpack(y));
  h := Filtered(yse.heads, x -> x <> 0);
  q := One(BaseDomain(y))
       * PermutationMat(SortingPerm(h), Length(h), BaseDomain(y));
  return p * q ^ (-1);
end);

# Is there a complete direct way of testing whether this idempotent exists
# (without constructing it)?  The method below is already pretty efficient.

InstallGlobalFunction(MatrixOverFiniteFieldIdempotentTester,
function(_, x, y)
  Assert(1, IsPlistRowBasisOverFiniteFieldRep(x));
  Assert(1, IsPlistRowBasisOverFiniteFieldRep(y));
  return MatrixOverFiniteFieldIdempotentCreator(_, x, y) <> fail;
end);

# Attempt to construct an idempotent m with RowSpace(m) = x
# ColumnSpace(m) = y

InstallGlobalFunction(MatrixOverFiniteFieldIdempotentCreator,
function(S, x, y)
  local m, inv;

  Assert(1, IsMatrixOverFiniteFieldSemigroup(S));
  Assert(1, IsRowBasisOverFiniteField(x));
  Assert(1, Rank(x) <> 0);
  Assert(1, IsRowBasisOverFiniteField(y));
  Assert(1, Rank(y) <> 0);
  Assert(1, Length(x!.rows[1]) = Length(y!.rows[1]));

  m := Matrix(BaseDomain(S), TransposedMat(y!.rows) * x!.rows);
  inv := MatrixOverFiniteFieldLocalRightInverse(S, x, m);
  if inv = fail then
    return fail;
  fi;
  return m * inv;
end);

InstallMethod(IsGeneratorsOfSemigroup, "for an ffe coll coll coll",
[IsFFECollCollColl],
function(coll)
  local rep;
  Assert(1, not IsEmpty(coll));
  rep := Representative(coll);
  if IsMatrixObjOverFiniteField(rep) then
    return ForAll(coll, x -> NrRows(x) = NrRows(coll[1])
                             and BaseDomain(x) = BaseDomain(coll[1])
                             and NrRows(x) = NrCols(x));
  fi;
  TryNextMethod();
end);

#############################################################################
# 6. Properties of matrix over finite field semigroups
#############################################################################

# FIXME(later) this method is not correct (although it works as documented)
# This should check whether <S> = GLM of the right dimensions/field

InstallMethod(IsFullMatrixMonoid, "for a semigroup",
[IsSemigroup], ReturnFalse);

[ zur Elbe Produktseite wechseln0.38Quellennavigators  Analyse erneut starten  ]