2 Transformations
  
  The  functions  described  in  this  section extend the functionality of GAP
  relating to transformations.
  
  
  2.1 Creating Transformations
  
  
  2.1-1 TransformationByKernelAndImage
  
  > TransformationByKernelAndImage( ker, img ) ______________________operation
  > TransformationByKernelAndImageNC( ker, img ) ____________________operation
  
  returns the transformation f with kernel ker and image img where (x)f=img[i]
  for all x in ker[i]. The argument ker should be a set of sets that partition
  the set 1,...n for some n and img should be a sublist of 1,...n.
  
  TransformationByKernelAndImage  first  checks  that ker and img describe the
  kernel       and       image      of      a      transformation      whereas
  TransformationByKernelAndImageNC performs no such check.
  
  ---------------------------  Example  ----------------------------
      gap> TransformationByKernelAndImageNC([[1,2,3,4],[5,6,7],[8]],[1,2,8]);
      Transformation( [ 1, 1, 1, 1, 2, 2, 2, 8 ] )
      gap> TransformationByKernelAndImageNC([[1,6],[2,5],[3,4]], [4,5,6]);
      Transformation( [ 4, 5, 6, 6, 5, 4 ] )
  ------------------------------------------------------------------
  
  
  2.1-2 AllTransformationsWithKerAndImg
  
  > AllTransformationsWithKerAndImg( ker, img ) _____________________operation
  > AllTransformationsWithKerAndImgNC( ker, img ) ___________________operation
  
  returns  a  list  of  all transformations with kernel ker and image img. The
  argument  ker should be a set of sets that partition the set 1,...n for some
  n and img should be a sublist of 1,...n.
  
  AllTransformationsWithKerAndImg  first  checks that ker and img describe the
  kernel       and       image      of      a      transformation      whereas
  AllTransformationsWithKerAndImgNC performs no such check.
  
  ---------------------------  Example  ----------------------------
      gap> AllTransformationsWithKerAndImg([[1,6],[2,5],[3,4]], [4,5,6]);
      [ Transformation( [ 4, 5, 6, 6, 5, 4 ] ), 
        Transformation( [ 6, 5, 4, 4, 5, 6 ] ), 
        Transformation( [ 6, 4, 5, 5, 4, 6 ] ), 
        Transformation( [ 4, 6, 5, 5, 6, 4 ] ), 
        Transformation( [ 5, 6, 4, 4, 6, 5 ] ), 
        Transformation( [ 5, 4, 6, 6, 4, 5 ] ) ]
  ------------------------------------------------------------------
  
  
  2.1-3 Idempotent
  
  > IdempotentNC( ker, img ) _________________________________________function
  > Idempotent( ker, img ) ___________________________________________function
  
  IdempotentNC  returns  an  idempotent  with kernel ker and image img without
  checking IsTransversal (2.2-1) with arguments ker and im.
  
  Idempotent  returns  an  idempotent  with  kernel  ker  and  image img after
  checking that IsTransversal (2.2-1) with arguments ker and im returns true.
  
  ---------------------------  Example  ----------------------------
      gap> g1:=Transformation([2,2,4,4,5,6]);;
      gap> g2:=Transformation([5,3,4,4,6,6]);;
      gap> ker:=KernelOfTransformation(g2*g1);;
      gap> im:=ImageListOfTransformation(g2);;
      gap> Idempotent(ker, im);
      Error,  the image must be a transversal of the kernel
      [ ... ]
      gap> Idempotent([[1,2,3],[4,5],[6,7]], [1,5,6]);
      Transformation( [ 1, 1, 1, 5, 5, 6, 6 ] )
      gap> IdempotentNC([[1,2,3],[4,5],[6,7]], [1,5,6]);
      Transformation( [ 1, 1, 1, 5, 5, 6, 6 ] )
  ------------------------------------------------------------------
  
  
  2.1-4 RandomIdempotent
  
  > RandomIdempotent( arg ) _________________________________________operation
  > RandomIdempotentNC( arg ) _______________________________________operation
  
  If  the  argument  is  a kernel, then a random idempotent is return that has
  that  kernel.  A  kernel  is a set of sets that partition the set 1,...n for
  some n and an image is a sublist of 1,...n.
  
  If  the  first argument is an image img and the second a positive integer n,
  then a random idempotent of degree n is returned with image img.
  
  The no check version does not check that the arguments can be the kernel and
  image of an idempotent.
  
  ---------------------------  Example  ----------------------------
      gap> RandomIdempotent([[1,2,3], [4,5], [6,7,8]], [1,2,3]);;
      fail
      gap> RandomIdempotent([1,2,3],5);
      Transformation( [ 1, 2, 3, 1, 3 ] )
      gap> RandomIdempotent([[1,6], [2,4], [3,5]]);
      Transformation( [ 1, 2, 5, 2, 5, 1 ] )
  ------------------------------------------------------------------
  
  
  2.1-5 RandomTransformation
  
  > RandomTransformation( arg ) _____________________________________operation
  > RandomTransformationNC( arg ) ___________________________________operation
  
  These are new methods for the existing library function RandomTransformation
  (Reference: RandomTransformation).
  
  If  the  first  argument  is a kernel and the second an image, then a random
  transformation  is  returned with this kernel and image.A kernel is a set of
  sets  that  partition the set 1,...n for some n and an image is a sublist of
  1,...n.
  
  If  the  argument is a kernel, then a random transformation is returned that
  has that kernel.
  
  If  the  first argument is an image img and the second a positive integer n,
  then a random transformation of degree n is returned with image img.
  
  The no check version does not check that the arguments can be the kernel and
  image of a transformation.
  
  ---------------------------  Example  ----------------------------
      gap> RandomTransformation([[1,2,3], [4,5], [6,7,8]], [1,2,3]);;
      Transformation( [ 2, 2, 2, 1, 1, 3, 3, 3 ] )
      gap> RandomTransformation([[1,2,3],[5,7],[4,6]]); 
      Transformation( [ 3, 3, 3, 6, 1, 6, 1 ] )
      gap> RandomTransformation([[1,2,3],[5,7],[4,6]]);
      Transformation( [ 4, 4, 4, 7, 3, 7, 3 ] )
      gap> RandomTransformationNC([[1,2,3],[5,7],[4,6]]);
      Transformation( [ 1, 1, 1, 7, 5, 7, 5 ] )
      gap> RandomTransformation([1,2,3], 6);             
      Transformation( [ 2, 1, 2, 1, 1, 2 ] )
      gap> RandomTransformationNC([1,2,3], 6);
      Transformation( [ 3, 1, 2, 2, 1, 2 ] )
  ------------------------------------------------------------------
  
  2.1-6 TransformationActionNC
  
  > TransformationActionNC( list, act, elm ) ________________________operation
  
  returns the list list acted on by elm via the action act.
  
  ---------------------------  Example  ----------------------------
      gap> mat:=OneMutable(GeneratorsOfGroup(GL(3,3))[1]);
      [ [ Z(3)^0, 0*Z(3), 0*Z(3) ], [ 0*Z(3), Z(3)^0, 0*Z(3) ], 
        [ 0*Z(3), 0*Z(3), Z(3)^0 ] ]
      gap> mat[3][3]:=Z(3)*0; 
      0*Z(3)
      gap> F:=BaseDomain(mat);
      GF(3)
      gap> TransformationActionNC(Elements(F^3), OnRight, mat);
      Transformation( [ 1, 1, 1, 4, 4, 4, 7, 7, 7, 10, 10, 10, 13, 13, 13, 16, 16, 
        16, 19, 19, 19, 22, 22, 22, 25, 25, 25 ] )
  ------------------------------------------------------------------
  
  
  2.2 Properties & Attributes
  
  2.2-1 IsTransversal
  
  > IsTransversal( list1, list2 ) ____________________________________function
  
  returns  true if the list list2 is a transversal of the list of lists list1.
  That is, if every list in list1 contains exactly one element in list2.
  
  ---------------------------  Example  ----------------------------
      gap> g1:=Transformation([2,2,4,4,5,6]);;
      gap> g2:=Transformation([5,3,4,4,6,6]);;
      gap> ker:=KernelOfTransformation(g2*g1);
      [ [ 1 ], [ 2, 3, 4 ], [ 5, 6 ] ] 
      gap> im:=ImageListOfTransformation(g2);
      [ 5, 3, 4, 4, 6, 6 ]
      gap> IsTransversal(ker, im);
      false
      gap> IsTransversal([[1,2,3],[4,5],[6,7]], [1,5,6]);
      true
      
  ------------------------------------------------------------------
  
  2.2-2 IsKerImgOfTransformation
  
  > IsKerImgOfTransformation( ker, img ) _____________________________function
  
  returns  true  if the arguments ker and img can be the kernel and image of a
  single  transformation,  respectively.  The  argument ker should be a set of
  sets that partition the set 1,...n for some n and img should be a sublist of
  1,...n.
  
  ---------------------------  Example  ----------------------------
      gap> ker:=[[1,2,3],[5,6],[8]];
      [ [ 1, 2, 3 ], [ 5, 6 ], [ 8 ] ]
      gap> img:=[1,2,9];
      [ 1, 2, 9 ]
      gap> IsKerImgOfTransformation(ker,img);
      false
      gap> ker:=[[1,2,3,4],[5,6,7],[8]];
      [ [ 1, 2, 3, 4 ], [ 5, 6, 7 ], [ 8 ] ]
      gap> IsKerImgOfTransformation(ker,img);
      false
      gap> img:=[1,2,8];
      [ 1, 2, 8 ]
      gap> IsKerImgOfTransformation(ker,img);
      true
  ------------------------------------------------------------------
  
  2.2-3 KerImgOfTransformation
  
  > KerImgOfTransformation( f ) _____________________________________operation
  
  returns  the  kernel and image set of the transformation f. These attributes
  of  f  can  be  obtain  separately  using KernelOfTransformation (Reference:
  KernelOfTransformation)     and     ImageSetOfTransformation     (Reference:
  ImageSetOfTransformation), respectively.
  
  ---------------------------  Example  ----------------------------
      gap> t:=Transformation( [ 10, 8, 7, 2, 8, 2, 2, 6, 4, 1 ] );;
      gap> KerImgOfTransformation(t);
      [ [ [ 1 ], [ 2, 5 ], [ 3 ], [ 4, 6, 7 ], [ 8 ], [ 9 ], [ 10 ] ], 
        [ 1, 2, 4, 6, 7, 8, 10 ] ]
  ------------------------------------------------------------------
  
  2.2-4 IsRegularTransformation
  
  > IsRegularTransformation( S, f ) _________________________________operation
  
  if  f  is  a regular element of the transformation semigroup S, then true is
  returned. Otherwise false is returned.
  
  A transformation f is regular inside a transformation semigroup S if it lies
  inside  a regular D-class. This is equivalent to the orbit of the image of f
  containing a transversal of the kernel of f.
  
  ---------------------------  Example  ----------------------------
    gap> g1:=Transformation([2,2,4,4,5,6]);;
    gap> g2:=Transformation([5,3,4,4,6,6]);;
    gap> m1:=Monoid(g1,g2);;
    gap> IsRegularTransformation(m1, g1);
    true
    gap> img:=ImageSetOfTransformation(g1);
    [ 2, 4, 5, 6 ]
    gap> ker:=KernelOfTransformation(g1);
    [ [ 1, 2 ], [ 3, 4 ], [ 5 ], [ 6 ] ]
    gap> ForAny(MonoidOrbit(m1, img), x-> IsTransversal(ker, x));
    true
    gap> IsRegularTransformation(m1, g2);
    false
    gap> IsRegularTransformation(FullTransformationSemigroup(6), g2);
    true
    	
  ------------------------------------------------------------------
  
  2.2-5 IndexPeriodOfTransformation
  
  > IndexPeriodOfTransformation( f ) ________________________________attribute
  
  returns  the  minimum numbers m, r such that f^(m+r)=f^m; known as the index
  and period of the transformation.
  
  ---------------------------  Example  ----------------------------
      gap> f:=Transformation( [ 3, 4, 4, 6, 1, 3, 3, 7, 1 ] );;
      gap> IndexPeriodOfTransformation(f);
      [ 2, 3 ]
      gap> f^2=f^5;
      true
  ------------------------------------------------------------------
  
  2.2-6 SmallestIdempotentPower
  
  > SmallestIdempotentPower( f ) ____________________________________attribute
  
  returns  the  least  natural number n such that the transformation f^n is an
  idempotent.
  
  ---------------------------  Example  ----------------------------
      gap> t:=Transformation( [ 6, 7, 4, 1, 7, 4, 6, 1, 3, 4 ] );;
      gap> SmallestIdempotentPower(t);
      6
      gap> t:=Transformation( [ 6, 6, 6, 2, 7, 1, 5, 3, 10, 6 ] );;
      gap> SmallestIdempotentPower(t);
      4
  ------------------------------------------------------------------
  
  
  2.2-7 InversesOfTransformation
  
  > InversesOfTransformation( S, f ) ________________________________operation
  > InversesOfTransformationNC( S, f ) ______________________________operation
  
  returns a list of the inverses of the transformation f in the transformation
  semigroup  S.  The function InversesOfTransformationNC does not check that f
  is an element of S.
  
  ---------------------------  Example  ----------------------------
      gap> S:=Semigroup([ Transformation( [ 3, 1, 4, 2, 5, 2, 1, 6, 1 ] ), 
        Transformation( [ 5, 7, 8, 8, 7, 5, 9, 1, 9 ] ), 
        Transformation( [ 7, 6, 2, 8, 4, 7, 5, 8, 3 ] ) ]);;
      gap> f:=Transformation( [ 3, 1, 4, 2, 5, 2, 1, 6, 1 ] );;
      gap> InversesOfTransformationNC(S, f);
      [  ]
      gap> IsRegularTransformation(S, f);
      false
      gap> f:=Transformation( [ 1, 9, 7, 5, 5, 1, 9, 5, 1 ] );;
      gap> inv:=InversesOfTransformation(S, f);
      [ Transformation( [ 1, 5, 1, 1, 5, 1, 3, 1, 2 ] ), 
        Transformation( [ 1, 5, 1, 2, 5, 1, 3, 2, 2 ] ), 
        Transformation( [ 1, 2, 3, 5, 5, 1, 3, 5, 2 ] ) ]
      gap> IsRegularTransformation(S, f);
      true
  ------------------------------------------------------------------
  
  
  2.3 Changing Representation
  
  2.3-1 AsBooleanMatrix
  
  > AsBooleanMatrix( f[, n] ) _______________________________________operation
  
  returns the transformation or permutation f represented as an n by n Boolean
  matrix where i,f(i)th entries equal 1 and all other entries are 0.
  
  If f is a transformation, then n is the size of the domain of f.
  
  If f is a permutation, then n is the number of points moved by f.
  
  ---------------------------  Example  ----------------------------
      gap> t:=Transformation( [ 4, 2, 2, 1 ] );;
      gap> AsBooleanMatrix(t);
      [ [ 0, 0, 0, 1 ], [ 0, 1, 0, 0 ], [ 0, 1, 0, 0 ], [ 1, 0, 0, 0 ] ]
      gap> t:=(1,4,5);;
      gap> AsBooleanMatrix(t);
      [ [ 0, 0, 0, 1, 0 ], [ 0, 1, 0, 0, 0 ], [ 0, 0, 1, 0, 0 ], [ 0, 0, 0, 0, 1 ],
        [ 1, 0, 0, 0, 0 ] ]
      gap> AsBooleanMatrix(t,3);
      fail
      gap> AsBooleanMatrix(t,5);
      [ [ 0, 0, 0, 1, 0 ], [ 0, 1, 0, 0, 0 ], [ 0, 0, 1, 0, 0 ], [ 0, 0, 0, 0, 1 ],
        [ 1, 0, 0, 0, 0 ] ]
      gap> AsBooleanMatrix(t,6);
      [ [ 0, 0, 0, 1, 0, 0 ], [ 0, 1, 0, 0, 0, 0 ], [ 0, 0, 1, 0, 0, 0 ], 
        [ 0, 0, 0, 0, 1, 0 ], [ 1, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 1 ] ]
  ------------------------------------------------------------------
  
  2.3-2 AsPermOfRange
  
  > AsPermOfRange( x ) ______________________________________________operation
  
  converts  a  transformation  x  that is a permutation of its image into that
  permutation.
  
  ---------------------------  Example  ----------------------------
      gap> t:=Transformation([1,2,9,9,9,8,8,8,4]);
      Transformation( [ 1, 2, 9, 9, 9, 8, 8, 8, 4 ] )
      gap> AsPermOfRange(t);
      (4,9)
      gap> t*last;
      Transformation( [ 1, 2, 4, 4, 4, 8, 8, 8, 9 ] )
      gap> AsPermOfRange(last);
      ()
  ------------------------------------------------------------------