Quelle matrix.gi Sprache: unbekannt

#############################################################################
##
##  This file is part of recog, a package for the GAP computer algebra system
##  which provides a collection of methods for the constructive recognition
##  of groups.
##
##  This files's authors include Max Neunhöffer, Ákos Seress.
##
##  Copyright of recog belongs to its developers whose names are too numerous
##  to list here. Please refer to the COPYRIGHT file for details.
##
##  SPDX-License-Identifier: GPL-3.0-or-later
##
##
##  A collection of find homomorphism methods for matrix groups.
##
#############################################################################

RECOG.HomToScalars := function(data,el)
  return ExtractSubMatrix(el,data.poss,data.poss);
end;

#! @BeginChunk DiagonalMatrices
#! This method is successful if and only if all generators of a matrix group
#! <A>G</A> are diagonal matrices. Otherwise, it returns <K>NeverApplicable</K>.
#! @EndChunk
BindRecogMethod(FindHomMethodsMatrix, "DiagonalMatrices",
"check whether all generators are diagonal matrices",
function(ri, G)
  local H,d,f,gens,hom,i,isscalars,j,newgens,upperleft;

  d := ri!.dimension;
  if d = 1 then
      Info(InfoRecog,2,"Found dimension 1, going to Scalars method");
      return FindHomMethodsMatrix.Scalar(ri,G);
  fi;

  gens := GeneratorsOfGroup(G);
  if not ForAll(gens, IsDiagonalMat) then
      return NeverApplicable;
  fi;

  f := ri!.field;
  isscalars := true;
  i := 1;
  while isscalars and i <= Length(gens) do
      j := 2;
      upperleft := gens[i][1,1];
      while isscalars and j <= d do
          if upperleft <> gens[i][j,j] then
              isscalars := false;
          fi;
          j := j + 1;
      od;
      i := i + 1;
  od;

  if not isscalars then
      # We quickly know that we want to make a balanced tree:
      ri!.blocks := List([1..d],i->[i]);
      # Note that we cannot tell the upper levels that they should better
      # have made some more generators for the kernel!

      return FindHomMethodsMatrix.BlockScalar(ri,G);
  fi;

  # Scalar matrices, so go to dimension 1:
  newgens := List(gens,x->ExtractSubMatrix(x,[1],[1]));
  H := Group(newgens);
  hom := GroupHomByFuncWithData(G,H,RECOG.HomToScalars,rec(poss := [1]));
  SetHomom(ri,hom);
  findgensNmeth(ri).method := FindKernelDoNothing;

  # Hint to the image:
  AddMethod(InitialDataForImageRecogNode(ri).hints, FindHomMethodsMatrix.Scalar, 4000);

  return Success;
end);

#RECOG.DetWrapper := function(m)
#  local n;
#  n := ExtractSubMatrix(m,[1],[1]);
#  n[1][1] := DeterminantMat(m);
#  return n;
#end;

#FindHomMethodsMatrix.Determinant := function(ri, G)
#  local H,d,dets,gens,hom;
#  d := ri!.dimension;
#  if d = 1 then
#      Info(InfoRecog,2,"Found dimension 1, going to Scalar method");
#      return FindHomMethodsMatrix.Scalar(ri,G);
#  fi;
#
#  # check for a hint from above:
#  if IsBound(ri!.containedinsl) and ri!.containedinsl = true then
#      return false;  # will not succeed
#  fi;
#
#  gens := GeneratorsOfGroup(G);
#  dets := List(gens,RECOG.DetWrapper);
#  if ForAll(dets,IsOne) then
#      ri!.containedinsl := true;
#      return false;  # will not succeed
#  fi;
#
#  H := GroupWithGenerators(dets);
#  hom := GroupHomomorphismByFunction(G,H,RECOG.DetWrapper);
#
#  SetHomom(ri,hom);
#
#  # Hint to the kernel:
#  InitialDataForKernelRecogNode(ri).containedinsl := true;
#  return true;
#end;

SLPforElementFuncsMatrix.DiscreteLog := function(ri,x)
  local log;
  log := LogFFE(x[1,1],ri!.generator);
  if log = fail then
      return fail;
  fi;
  return StraightLineProgramNC([[1,log]],1);
end;

#! @BeginChunk Scalar
#! TODO
#! @EndChunk
BindRecogMethod(FindHomMethodsMatrix, "Scalar",
"Hint TODO",
function(ri, G)
  local f,gcd,generator,gens,i,l,o,pows,q,rep,slp,subset,z;
  if ri!.dimension > 1 then
      return NotEnoughInformation;
  fi;

  # FIXME: FieldOfMatrixGroup
  f := ri!.field;
  o := One(f);
  gens := List(GeneratorsOfGroup(G),x->x[1,1]);
  subset := Filtered([1..Length(gens)], i -> not IsOne(gens[i]));
  if subset = [] then
      return FindHomMethodsGeneric.TrivialGroup(ri,G);
  fi;
  gens := gens{subset};
  q := Size(f);
  z := PrimitiveRoot(f);
  pows := [LogFFE(gens[1],z)];     # zero cannot occur!
  Add(pows,q-1);
  gcd := Gcd(Integers,pows);
  i := 2;
  while i <= Length(gens) and gcd > 1 do
      pows[i] := LogFFE(gens[i],z);
      Add(pows,q-1);
      gcd := Gcd(Integers,pows);
      i := i + 1;
  od;
  rep := GcdRepresentation(Integers,pows);
  l := [];
  for i in [1..Length(pows)-1] do
      if rep[i] <> 0 then
          Add(l,subset[i]);
          Add(l,rep[i]);
      fi;
  od;
  slp := StraightLineProgramNC([[l]],Length(GeneratorsOfGroup(G)));
  Setslptonice(ri,slp);   # this sets the nice generators
  Setslpforelement(ri,SLPforElementFuncsMatrix.DiscreteLog);
  ri!.generator := z^gcd;
  SetFilterObj(ri,IsLeaf);
  return Success;
end);

# Given a matrix `mat`, and a set of indices `poss`,
# check whether the projection to the block mat{poss}{poss}
# is valid -- that is, whether the rows and columns in
# the set poss contain only zero elements outside of the
# positions indicated by poss.
RECOG.IsDiagonalBlockOfMatrix := function(m, poss)
  local n, outside, z, i, j;
  Assert(1, NrRows(m) = NrCols(m) and IsSubset([1..NrRows(m)], poss));
  outside := Difference([1..NrRows(m)], poss);
  z := ZeroOfBaseDomain(m);
  for i in poss do
    for j in outside do
      if m[i,j] <> z or m[j,i] <> z then
        return false;
      fi;
    od;
  od;
  return true;
end;

# Homomorphism used by these recognition methods:
# - FindHomMethodsMatrix.BlockScalar
# - FindHomMethodsProjective.BlocksModScalars
RECOG.HomToDiagonalBlock := function(data,el)
  # Verify el is in the domain of definition of this homomorphism.
  # Assuming the recognition result is correct, this is of course always
  # the case if el is a group element. However, this function may also
  # be called for elements which are not contained in the group.
  # TODO: add a switch to optionally bypass this verification
  # when we definitely don't need it?
  if not RECOG.IsDiagonalBlockOfMatrix(el, data.poss) then
    return fail;
  fi;

  return ExtractSubMatrix(el,data.poss,data.poss);
end;

#! @BeginChunk BlockScalar
#! This method is only called by a hint. Alongside with the hint it gets
#! a block decomposition respected by the matrix group <A>G</A> to be recognised
#! and the promise that all diagonal blocks of all group elements
#! will only be scalar matrices. This method recursively builds a balanced tree
#! and does scalar recognition in each leaf.
#! @EndChunk
BindRecogMethod(FindHomMethodsMatrix, "BlockScalar",
"Hint TODO",
function(ri, G)
  # We assume that ri!.blocks is a list of ranges where the non-trivial
  # scalar blocks are. Note that their length does not have to sum up to
  # the dimension, because some blocks at the end might already be trivial.
  local H,data,hom,middle,newgens,nrblocks,topblock;
  nrblocks := Length(ri!.blocks);  # this is always >= 1
  if nrblocks <= 2 then   # the image is only one block
      # go directly to scalars in that case:
      data := rec(poss := ri!.blocks[nrblocks]);
      newgens := List(GeneratorsOfGroup(G),x->RECOG.HomToDiagonalBlock(data,x));
      H := GroupWithGenerators(newgens);
      hom := GroupHomByFuncWithData(G,H,RECOG.HomToDiagonalBlock,data);
      SetHomom(ri,hom);
      AddMethod(InitialDataForImageRecogNode(ri).hints, FindHomMethodsMatrix.Scalar, 2000);

      if nrblocks = 1 then     # no kernel:
          findgensNmeth(ri).method := FindKernelDoNothing;
      else   # exactly two blocks:
          # FIXME: why don't we just compute a precise set of generators of the kernel?
          # That should be easily and efficiently possible at this point, no?
          # The kernel is abelian, so we don't need to do normal closures.
          findgensNmeth(ri).method := FindKernelRandom;
          findgensNmeth(ri).args := [7];
          InitialDataForKernelRecogNode(ri).blocks := ri!.blocks{[1]};
          # We have to go to BlockScalar with 1 block because the one block
          # is only a part of the whole matrix:
          AddMethod(InitialDataForKernelRecogNode(ri).hints, FindHomMethodsMatrix.BlockScalar, 2000);
          Setimmediateverification(ri,true);
      fi;
      return Success;
  fi;

  # We hack away at least two blocks and leave at least one:
  middle := QuoInt(nrblocks,2)+1;   # the first one taken
  topblock := ri!.blocks[nrblocks];
  data := rec(poss := [ri!.blocks[middle][1]..topblock[Length(topblock)]]);
  newgens := List(GeneratorsOfGroup(G),x->RECOG.HomToDiagonalBlock(data,x));
  H := GroupWithGenerators(newgens);
  hom := GroupHomByFuncWithData(G,H,RECOG.HomToDiagonalBlock,data);
  SetHomom(ri,hom);

  # the image are the last few blocks:
  InitialDataForImageRecogNode(ri).blocks := List(ri!.blocks{[middle..nrblocks]},
                               x->x - (ri!.blocks[middle][1]-1));
  AddMethod(InitialDataForImageRecogNode(ri).hints, FindHomMethodsMatrix.BlockScalar, 2000);

  # the kernel is the first few blocks (can be only one!):
  # FIXME: why don't we just compute a precise set of generators of the kernel?
  # That should be easily and efficiently possible at this point, no?
  findgensNmeth(ri).args[1] := 3 + nrblocks;
  findgensNmeth(ri).args[2] := 5;
  InitialDataForKernelRecogNode(ri).blocks := ri!.blocks{[1..middle-1]};
  AddMethod(InitialDataForKernelRecogNode(ri).hints, FindHomMethodsMatrix.BlockScalar, 2000);
  Setimmediateverification(ri,true);
  return Success;
end);

# A helper function for base changes:
RECOG.HomDoBaseChange := function(data,el)
  return data.t*el*data.ti;
end;

RECOG.CleanRow := function( basis, vec, extend, dec)
  local c,firstnz,i,j,lc,len,lev,mo,newpiv,pivs;
  # INPUT
  # basis: record with fields
  #        pivots   : integer list of pivot columns of basis matrix
  #        vectors : matrix of basis vectors in semi echelon form
  # vec  : vector of same length as basis vectors
  # extend : boolean value indicating whether the basis will we extended
  #          note that for the greased case also the basis vectors before
  #          the new one may be changed
  # OUTPUT
  # returns decomposition of vec in the basis, if possible.
  # otherwise returns 'fail' and adds cleaned vec to basis and updates
  # pivots
  # NOTES
  # destructive in both arguments

  # Clear dec vector if given:
  if dec <> fail then
    MultRowVector(dec,Zero(dec[1]));
  fi;

  # First a little shortcut:
  firstnz := PositionNonZero(vec);
  if firstnz > Length(vec) then
      return true;
  fi;

  len := Length(basis.vectors);
  i := 1;

  for j in [i..len] do
    if basis.pivots[j] >= firstnz then
      c := vec[ basis.pivots[ j ] ];
      if not IsZero( c ) then
        if dec <> fail then
          dec[ j ] := c;
        fi;
        AddRowVector( vec, basis.vectors[ j ], -c );
      fi;
    fi;
  od;

  newpiv := PositionNonZero( vec );
  if newpiv = Length( vec ) + 1 then
    return true;
  else
    if extend then
      c := vec[newpiv]^-1;
      MultRowVector( vec, vec[ newpiv ]^-1 );
      if dec <> fail then
        dec[len+1] := c;
      fi;
      Add( basis.vectors, vec );
      Add( basis.pivots, newpiv );
    fi;
    return false;
  fi;
end;

RECOG.FindAdjustedBasis := function(l)
  # l must be a list of matrices coming from MTX.BasesCompositionSeries.
  local blocks,i,pos,seb,v;
  blocks := [];
  seb := rec( vectors := [], pivots := [] );
  pos := 1;
  for i in [2..Length(l)] do
      for v in l[i] do
          RECOG.CleanRow(seb,ShallowCopy(v),true,fail);
      od;
      Add(blocks,[pos..Length(seb.vectors)]);
      pos := Length(seb.vectors)+1;
  od;
  ConvertToMatrixRep(seb.vectors);
  return rec(base := seb.vectors, baseinv := seb.vectors^-1, blocks := blocks);
end;

#! @BeginChunk ReducibleIso
#! This method determines whether a matrix group <A>G</A> acts irreducibly.
#! If yes, then it returns <K>NeverApplicable</K>. If <A>G</A> acts reducibly then
#! a composition series of the underlying module is computed and a base
#! change is performed to write <A>G</A> in a block lower triangular form.
#! Also, the method passes a hint to the image group that it is in
#! block lower triangular form, so the image immediately can make
#! recursive calls for the actions on the diagonal blocks, and then to the
#! lower <M>p</M>-part. For the image the method
#! <Ref Subsect="BlockLowerTriangular" Style="Text"/> is used.
#!
#! Note that this method is implemented in a way such that it can also be
#! used as a method for a projective group <A>G</A>. In that case the
#! recognition node has the <C>!.projective</C> component bound
#! to <K>true</K> and this information is passed down to image and kernel.
#! @EndChunk
BindRecogMethod(FindHomMethodsMatrix, "ReducibleIso",
"use the MeatAxe to find invariant subspaces",
# alternative comment:
#"use MeatAxe to find a composition series, do base change",
function(ri,G)
  # First we use the MeatAxe to find an invariant subspace:
  local H,bc,compseries,f,hom,isirred,m,newgens;

  RECOG.SetPseudoRandomStamp(G,"ReducibleIso");

  if IsBound(ri!.isabsolutelyirred) and ri!.isabsolutelyirred then
      # this information is coming from above
      return NeverApplicable;
  fi;

  # FIXME:
  f := ri!.field;
  m := GModuleByMats(GeneratorsOfGroup(G),f);
  isirred := MTX.IsIrreducible(m);

  # Save the MeatAxe module for later use:
  ri!.meataxemodule := m;
  # Report enduring failure if irreducible:
  if isirred then
      return NeverApplicable;
  fi;

  # Now compute a composition series:
  compseries := MTX.BasesCompositionSeries(m);
  bc := RECOG.FindAdjustedBasis(compseries);

  Info(InfoRecog,2,"Found composition series with block sizes ",
       List(bc.blocks,Length)," (dim=",ri!.dimension,")");

  # Do the base change:
  newgens := List(GeneratorsOfGroup(G),x->bc.base*x*bc.baseinv);
  H := GroupWithGenerators(newgens);
  hom := GroupHomByFuncWithData(G,H,RECOG.HomDoBaseChange,
                                rec(t := bc.base,ti := bc.baseinv));

  # Now report back:
  SetHomom(ri,hom);
  findgensNmeth(ri).method := FindKernelDoNothing;

  # Inform authorities that the image can be recognised easily:
  InitialDataForImageRecogNode(ri).blocks := bc.blocks;
  AddMethod(InitialDataForImageRecogNode(ri).hints, FindHomMethodsMatrix.BlockLowerTriangular, 4000);

  return Success;
end);

# Given a matrix `mat` and a list of index sets `blocks`,
# verify that the matrix has block lower triangular shape
# with respect to the given blocks.
RECOG.IsBlockLowerTriangularWithBlocks := function(mat, blocks)
  local z, b, col, row;
  Assert(0, Concatenation(blocks) = [1..Length(mat)]);
  z := ZeroOfBaseDomain(mat);
  for b in blocks do
    # Verify that there are only zeros above each block
    for row in [1..b[1]-1] do
      for col in b do
        if mat[row,col] <> z then
          return false;
        fi;
      od;
    od;
  od;
  return true;
end;

# Homomorphism method used by FindHomMethodsMatrix.BlockLowerTriangular.
RECOG.HomOntoBlockDiagonal := function(data,el)
  local m, x;

  # Verify el is in the domain of definition of this homomorphism.
  # Assuming the recognition result is correct, this is of course always
  # the case if el is a group element. However, this function may also
  # be called for elements which are not contained in the group.
  if not RECOG.IsBlockLowerTriangularWithBlocks(el,data.blocks) then
    return fail;
  fi;

  m := ZeroMutable(el);
  for x in data.blocks do
    CopySubMatrix(el, m, x, x, x, x);
  od;
  return m;
end;

#! @BeginChunk BlockLowerTriangular
#! This method is only called when a hint was passed down from the method
#! <Ref Subsect="ReducibleIso" Style="Text"/>. In that case, it knows that a
#! base change to block lower triangular form has been performed. The method
#! can then immediately find a homomorphism by mapping to the diagonal blocks.
#! It sets up this homomorphism and gives hints to image and kernel. For the
#! image, the method <Ref Subsect="BlockDiagonal" Style="Text"/> is used and
#! for the kernel, the method <Ref Subsect="LowerLeftPGroup" Style="Text"/>
#! is used.
#!
#! Note that this method is implemented in a way such that it can also be
#! used as a method for a projective group <A>G</A>. In that case the
#! recognition node has the <C>!.projective</C> component bound
#! to <K>true</K> and this information is passed down to image and kernel.
#! @EndChunk
BindRecogMethod(FindHomMethodsMatrix, "BlockLowerTriangular",
"for a group generated by block lower triangular matrices",
function(ri,G)
  # This is only used coming from a hint, we know what to do:
  # A base change was done to get block lower triangular shape.
  # We first do the diagonal blocks, then the lower p-part:
  local H,data,hom,newgens;
  data := rec( blocks := ri!.blocks );
  newgens := List(GeneratorsOfGroup(G),
                  x->RECOG.HomOntoBlockDiagonal(data,x));
  Assert(0, not fail in newgens);
  H := GroupWithGenerators(newgens);
  hom := GroupHomByFuncWithData(G,H,RECOG.HomOntoBlockDiagonal,data);
  SetHomom(ri,hom);

  # Now give hints downward:
  InitialDataForImageRecogNode(ri).blocks := ri!.blocks;
  AddMethod(InitialDataForImageRecogNode(ri).hints, FindHomMethodsMatrix.BlockDiagonal, 2000);
  findgensNmeth(ri).method := FindKernelLowerLeftPGroup;
  findgensNmeth(ri).args := [];
  AddMethod(InitialDataForKernelRecogNode(ri).hints, FindHomMethodsMatrix.LowerLeftPGroup, 2000);
  InitialDataForKernelRecogNode(ri).blocks := ri!.blocks;
  return Success;
end);

#! @BeginChunk BlockDiagonal
#! This method is only called when a hint was passed down from the method
#! <Ref Subsect="BlockLowerTriangular" Style="Text"/>.
#! In that case, it knows that the group is in block diagonal form.
#! The method is used both in the matrix- and the projective case.
#!
#! The method immediately delegates to projective methods handling
#! all the diagonal blocks projectively. This is done by giving a hint
#! to the image to use the method
#! <Ref Subsect="BlocksModScalars" Style="Text"/>.
#! The method for the kernel then has to deal with only scalar blocks,
#! either projectively or with scalars, which is again done by giving a hint
#! to either use <Ref Subsect="BlockScalar" Style="Text"/> or
#! <Ref Subsect="BlockScalarProj" Style="Text"/> respectively.
#!
#! Note that this method is implemented in a way such that it can also be
#! used as a method for a projective group <A>G</A>. In that case the
#! recognition node has the <C>!.projective</C> component bound
#! to <K>true</K> and this information is passed down to image and kernel.
#! @EndChunk
BindRecogMethod(FindHomMethodsMatrix, "BlockDiagonal",
"for groups generated by block diagonal matrices",
function(ri,G)
  # This is only called by a hint, so we know what we have to do:
  # We do all the blocks projectively and thus are left with scalar blocks.
  # In the projective case we still do the same, the BlocksModScalars
  # will automatically take care of the projectiveness!
  SetHomom(ri, IdentityMapping(G));
  # Now give hints downward:
  InitialDataForImageRecogNode(ri).blocks := ri!.blocks;
  AddMethod(InitialDataForImageRecogNode(ri).hints, FindHomMethodsProjective.BlocksModScalars, 2000);
  # We go to projective, although it would not matter here, because we
  # gave a working hint anyway:
  Setmethodsforimage(ri,FindHomDbProjective);

  # the kernel:
  # The kernel is abelian, so we don't need to do normal closures.
  findgensNmeth(ri).method := FindKernelRandom;
  findgensNmeth(ri).args := [Length(ri!.blocks)+10];
  # In the projective case we have to do a trick: We use an isomorphism
  # to a matrix group by multiplying things such that the last block
  # becomes an identity matrix:
  if ri!.projective then
      AddMethod(InitialDataForKernelRecogNode(ri).hints,
                FindHomMethodsProjective.BlockScalarProj,
                2000);
  else
      AddMethod(InitialDataForKernelRecogNode(ri).hints, FindHomMethodsMatrix.BlockScalar, 2000);
  fi;
  InitialDataForKernelRecogNode(ri).blocks := ri!.blocks;
  Setimmediateverification(ri, true);
  return Success;
end);

#RECOG.HomInducedOnFactor := function(data,el)
#  local dim,m;
#  dim := Length(el);
#  m := ExtractSubMatrix(el,[data.subdim+1..dim],[data.subdim+1..dim]);
#  # FIXME: no longer necessary when vectors/matrices are in place:
#  ConvertToMatrixRep(m);
#  return m;
#end;
#
#FindHomMethodsMatrix.InducedOnFactor := function(ri,G)
#  local H,dim,gens,hom,newgens,gen,data;
#  # Are we applicable?
#  if not IsBound(ri!.subdim) then
#      return NotEnoughInformation;
#  fi;
#
#  # Project onto image:
#  gens := GeneratorsOfGroup(G);
#  dim := ri!.dimension;
#  data := rec(subdim := ri!.subdim);
#  newgens := List(gens, x->RECOG.HomInducedOnFactor(data,x));
#  H := GroupWithGenerators(newgens);
#  hom := GroupHomByFuncWithData(G,H,RECOG.HomInducedOnFactor,data);
#
#  # Now report back:
#  SetHomom(ri,hom);
#
#  # Inform authorities that the kernel can be recognised easily:
#  InitialDataForKernelRecogNode(ri).subdim := ri!.subdim;
#  AddMethod(InitialDataForKernelRecogNode(ri).hints, FindHomMethodsMatrix.InducedOnSubspace, 2000);
#
#  return true;
#end;
#
RECOG.ExtractLowStuff := function(m,layer,blocks,lens,basisOfFieldExtension)
  local block,i,j,k,l,pos,v,what,where;
  v := ZeroVector(lens[layer],m[1]);
  pos := 0;
  i := layer+1;
  l := Length(blocks);
  # Extract the blocks with block coordinates (i,1)..(l,l-i+1):
  for j in [1..l-i+1] do
      block := [j+i-1,j];
      what := blocks[block[2]];
      for k in blocks[block[1]] do
          where := [pos+1..pos+Length(what)];
          CopySubVector(m[k],v,what,where);
          pos := pos + Length(what);
      od;
  od;
  if basisOfFieldExtension <> fail then
      # needed because we assume for example in
      # SLPforElementFuncsMatrix.LowerLeftPGroup that we work
      # over a field of order p (not a p power)
      return BlownUpVector(basisOfFieldExtension, v);
  fi;
  return v;
end;

RECOG.ComputeExtractionLayerLengths := function(blocks)
  local block,i,j,l,len,lens;
  lens := [];
  l := Length(blocks);
  for i in [2..Length(blocks)] do
      len := 0;
      for j in [1..l-i+1] do
          block := [j+i-1,j];
          len := len + Length(blocks[block[1]]) * Length(blocks[block[2]]);
      od;
      Add(lens,len);
  od;
  return lens;
end;

InstallGlobalFunction( FindKernelLowerLeftPGroup,
  function(ri)
    local basisOfFieldExtension,curlay,done,el,f,i,l,lens,lvec,nothingnew,pivots,pos,ready,
          rifac,s,v,x,y;

    Info(InfoRecog, 2, "Running FindKernelLowerLeftPGroup...");
    f := ri!.field;
    l := [];       # here we collect generators of N
    lvec := [];    # the linear part of the layer cleaned out by the gens
    pivots := [];  # pairs of numbers indicating the layer and pivot columns
                   # this will stay strictly increasing (lexicographically)
    lens := RECOG.ComputeExtractionLayerLengths(ri!.blocks);

    if not IsPrimeField(f) then
        basisOfFieldExtension := CanonicalBasis(f);  # a basis over the prime field
        lens := lens * Length(basisOfFieldExtension);
    else
        basisOfFieldExtension := fail;
    fi;

    nothingnew := 0;   # we count until we produced 10 new generators
                       # giving no new dimension
    rifac := ImageRecogNode(ri);
    while nothingnew < 10 do
        x := RandomElm(ri,"KERNEL",true).el;
        Assert(2, ValidateHomomInput(ri, x));
        s := SLPforElement(rifac,ImageElm( Homom(ri), x!.el ));
        y := ResultOfStraightLineProgram(s, ri!.pregensfacwithmem);
        x := x^-1 * y;   # this is in the kernel

        # Now clean out this vector and remember what we did:
        curlay := 1;
        v := RECOG.ExtractLowStuff(x,curlay,ri!.blocks,lens,basisOfFieldExtension);
        pos := PositionNonZero(v);
        i := 1;
        done := 0*[1..Length(lvec)];   # this refers to the current gens
        ready := false;
        while not ready do
            # Find out where there is something left:
            while pos > Length(v) and not ready do
                curlay := curlay + 1;
                if curlay <= Length(lens) then
                    v := RECOG.ExtractLowStuff(x,curlay,ri!.blocks,lens,basisOfFieldExtension);
                    pos := PositionNonZero(v);
                else
                    ready := true;   # x is now equal to the identity!
                fi;
            od;
            # Either there is something left in this layer or we are done
            if ready then break; fi;

            # Clean out this layer:
            while i <= Length(l) and pivots[i][1] <= curlay do
                if pivots[i][1] = curlay then
                    # we might have jumped over a layer
                    done := -v[pivots[i][2]];
                    if not IsZero(done) then
                        AddRowVector(v,lvec[i],done);
                        x := x * l[i]^IntFFE(done);
                    fi;
                fi;
                i := i + 1;
            od;
            pos := PositionNonZero(v);
            if pos <= Length(v) then  # something left here!
                ready := true;
            fi;
        od;
        # Now we have cleaned out x until one of the following happened:
        #   x is the identity (<=> curlay > Length(lens))
        #   x has been cleaned up to some layer and is not yet zero
        #     in that layer (<=> pos <= Length(v))
        #     then a power of x will be a new generator in that layer and
        #     has to be added in position i in the list of generators
        if curlay <= Length(lens) then   # a new generator
            # Now find a new pivot:
            el := v[pos]^-1;
            MultRowVector(v,el);
            x := x ^ IntFFE(el);
            Add(l,x,i);
            Add(lvec,v,i);
            Add(pivots,[curlay,pos],i);
            nothingnew := 0;
        else
            nothingnew := nothingnew + 1;
        fi;
    od;
    # Now make sure those things get handed down to the kernel:
    InitialDataForKernelRecogNode(ri).gensNvectors := lvec;
    InitialDataForKernelRecogNode(ri).gensNpivots := pivots;
    InitialDataForKernelRecogNode(ri).blocks := ri!.blocks;
    InitialDataForKernelRecogNode(ri).lens := lens;
    InitialDataForKernelRecogNode(ri).basisOfFieldExtension := basisOfFieldExtension;
    # this is stored on the upper level:
    SetgensN(ri,l);
    ri!.leavegensNuntouched := true;
    return true;
  end );

# computes a straight line program (SLP) for an element <g> of a p-group
# described by <ri> (that corresponds to a matrix group consisting of lower
# triangular matrices).
# The SLP is constructed by using matrices forming a pcgs (polycyclic
# generating sequence) to cancel out the
# entries in <g>. The coefficents of the process create the SLP.
# TODO Max H. wants to rewrite the code to work row-by-row
# instead of blockwise; that should result in both simple and faster code.
SLPforElementFuncsMatrix.LowerLeftPGroup := function(ri,g)
  # First project and calculate the vector:
  local done,h,i,l,layer,pow;
  # Take care of the projective case:
  if ri!.projective and not IsOne(g[1,1]) then
      g := (g[1,1]^-1) * g;
  fi;
  l := [];
  i := 1;
  for layer in [1..Length(ri!.lens)] do
      h := RECOG.ExtractLowStuff(g,layer,ri!.blocks,ri!.lens,
                                 ri!.basisOfFieldExtension);
      while i <= Length(ri!.gensNvectors) and ri!.gensNpivots[i][1] = layer do
          done := h[ri!.gensNpivots[i][2]];
          if not IsZero(done) then
              AddRowVector(h,ri!.gensNvectors[i],-done);
              pow := IntFFE(done);
              g := NiceGens(ri)[i]^(-pow) * g;
              Add(l,i);
              Add(l,IntFFE(done));
          fi;
          i := i + 1;
      od;
      if not IsZero(h) then
          return fail;
      fi;
  od;
  if Length(l) = 0 then
      l := [1, 0];
  fi;
  return StraightLineProgramNC([l], Length(ri!.gensNvectors));
end;

#! @BeginChunk LowerLeftPGroup
#! This method is only called by a hint from <Ref Subsect="BlockLowerTriangular" Style="Text"/>
#! as the kernel of the homomorphism mapping to the diagonal blocks.
#! The method uses the fact that this kernel is a <M>p</M>-group where
#! <M>p</M> is the characteristic of the underlying field. It exploits
#! this fact and uses this special structure to find nice generators
#! and a method to express group elements in terms of these.
#! @EndChunk
BindRecogMethod(FindHomMethodsMatrix, "LowerLeftPGroup",
"Hint TODO",
function(ri,G)
  local f,p;
  # Do we really have our favorite situation?
  if not (IsBound(ri!.blocks) and
          IsBound(ri!.lens) and
          IsBound(ri!.basisOfFieldExtension) and
          IsBound(ri!.gensNvectors) and
          IsBound(ri!.gensNpivots)) then
      return NotEnoughInformation;
  fi;
  # We are done, because we can do linear algebra:
  f := ri!.field;
  p := Characteristic(f);
  SetFilterObj(ri,IsLeaf);
  Setslpforelement(ri,SLPforElementFuncsMatrix.LowerLeftPGroup);
  SetSize(ri,p^Length(ri!.gensNvectors));
  return Success;
end);

#! @BeginChunk GoProjective
#! This method defines a homomorphism from a matrix group <A>G</A>
#! into the projective group <A>G</A> modulo scalar matrices. In fact, since
#! projective groups in &GAP; are represented as matrix groups, the
#! homomorphism is the identity mapping and the only difference is that in
#! the image the projective group methods can be applied.
#! The bulk of the work in matrix recognition is done in the projective group
#! setting.
#! @EndChunk
BindRecogMethod(FindHomMethodsMatrix, "GoProjective",
"divide out scalars and recognise projectively",
function(ri,G)
  local hom,q;
  Info(InfoRecog,2,"Going projective...");
  hom := IdentityMapping(G);
  SetHomom(ri,hom);
  # Now give hints downward:
  Setmethodsforimage(ri,FindHomDbProjective);
  # Make sure that immediate verification is performed to safeguard against the
  # kernel being too small.
  Setimmediateverification(ri, true);
  # note that RecogniseGeneric detects the use of FindHomDbProjective and
  # sets ri!.projective := true for the image
  # the kernel:
  q := Size(ri!.field);
  findgensNmeth(ri).method := FindKernelRandom;
  findgensNmeth(ri).args := [Length(Factors(q-1))+5];
  return Success;
end);

#! @BeginChunk KnownStabilizerChain
#! If a stabilizer chain is already known, then the kernel node is given
#! knowledge about this known stabilizer chain, and the image node is told to
#! use homomorphism methods from the database for permutation groups.
#! If a stabilizer chain of a parent node is already known this is used for
#! the computation of a stabilizer chain of this node. This stabilizer chain
#! is then used in the same way as above.
#! @EndChunk
BindRecogMethod(FindHomMethodsMatrix, "KnownStabilizerChain",
"use an already known stabilizer chain for this group",
function(ri,G)
  local S,hom;
  if HasStoredStabilizerChain(G) then
      Info(InfoRecog,2,"Already know stabilizer chain, using 1st orbit.");
      S := StoredStabilizerChain(G);
      hom := OrbActionHomomorphism(G,S!.orb);
      SetHomom(ri,hom);
      Setmethodsforimage(ri,FindHomDbPerm);
      InitialDataForKernelRecogNode(ri).StabilizerChainFromAbove := S;
      return Success;
  elif IsBound(ri!.StabilizerChainFromAbove) then
      Info(InfoRecog,2,"Know stabilizer chain for super group, using base.");
      S := StabilizerChain(G,rec( Base := ri!.StabilizerChainFromAbove ));
      Info(InfoRecog,2,"Computed stabilizer chain, size=",Size(S));
      hom := OrbActionHomomorphism(G,S!.orb);
      SetHomom(ri,hom);
      Setmethodsforimage(ri,FindHomDbPerm);
      InitialDataForKernelRecogNode(ri).StabilizerChainFromAbove := S;
      return Success;
  fi;
  return NeverApplicable;
end);

#FindHomMethodsMatrix.SmallVectorSpace := function(ri,G)
#  local d,f,hom,l,method,o,q,r,v,w;
#  d := ri!.dimension;
#  f := ri!.field;
#  q := Size(f);
#  if q^d > 10000 then
#      return false;
#  fi;
#
#  # Now we will for sure find a rather short orbit:
#  # FIXME: adjust to new vector/matrix interface:
#  v := FullRowSpace(f,d);
#  repeat
#      w := Random(v);
#  until not IsZero(w);
#  o := Orbit(G,w,OnRight);
#  hom := ActionHomomorphism(G,o,OnRight);
#
#  Info(InfoRecog,2,"Found orbit of length ",Length(o),".");
#  if Length(o) >= d then
#      l := Minimum(Length(o),3*d);
#      r := RankMat(o{[1..l]});
#      if r = d then
#          # We proved that it is an isomorphism:
#          findgensNmeth(ri).method := FindKernelDoNothing;
#          Info(InfoRecog,2,"Spans rowspace ==> found isomorphism.");
#      else
#          Info(InfoRecog,3,"Rank of o{[1..3*d]} is ",r,".");
#      fi;
#  fi;
#
#  SetHomom(ri,hom);
#  Setmethodsforimage(ri,FindHomDbPerm);
#  return true;
#end;
#
#FindHomMethodsMatrix.IsomorphismPermGroup := function(ri,G)
#  SetHomom(ri,IsomorphismPermGroup(G));
#  findgensNmeth(ri).method := FindKernelDoNothing;
#  Setmethodsforimage(ri,FindHomDbPerm);
#  return true;
#end;

#! @BeginCode AddMethod_Matrix_FindHomMethodsGeneric.TrivialGroup
AddMethod(FindHomDbMatrix, FindHomMethodsGeneric.TrivialGroup, 3100);
#! @EndCode

AddMethod(FindHomDbMatrix, FindHomMethodsMatrix.DiagonalMatrices, 1100);

AddMethod(FindHomDbMatrix, FindHomMethodsMatrix.KnownStabilizerChain, 1175);

AddMethod(FindHomDbPerm, FindHomMethodsGeneric.FewGensAbelian, 1050);

AddMethod(FindHomDbMatrix, FindHomMethodsMatrix.ReducibleIso, 1000);

AddMethod(FindHomDbMatrix, FindHomMethodsMatrix.GoProjective, 900);

###AddMethod( FindHomDbMatrix, FindHomMethodsMatrix.SmallVectorSpace,
###           700, "SmallVectorSpace",
###           "for small vector spaces directly compute an orbit" );

Quelle matrix.gi Sprache: unbekannt

[ Dauer der Verarbeitung: 0.47 Sekunden (vorverarbeitet) ]