Goto Chapter: Top 1 2 3 4 5 6 7 Bib Ind
 Top of Book   Previous Chapter   Next Chapter 

2 Transformations
 2.1 Creating Transformations
  2.1-1 TransformationByKernelAndImage

  2.1-2 AllTransformationsWithKerAndImg

  2.1-3 Idempotent

  2.1-4 RandomIdempotent

  2.1-5 RandomTransformation

  2.1-6 TransformationActionNC
 2.2 Properties & Attributes
  2.2-1 IsTransversal

  2.2-2 IsKerImgOfTransformation

  2.2-3 KerImgOfTransformation

  2.2-4 IsRegularTransformation

  2.2-5 IndexPeriodOfTransformation

  2.2-6 SmallestIdempotentPower

  2.2-7 InversesOfTransformation
 2.3 Changing Representation
  2.3-1 AsBooleanMatrix

  2.3-2 AsPermOfRange

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.

  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.

  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.

  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.

  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.

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.

  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.

  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.

  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.

  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.

  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.

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.

  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.

  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.

  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.

  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.

  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);
  ()
 Top of Book   Previous Chapter   Next Chapter 
Goto Chapter: Top 1 2 3 4 5 6 7 Bib Ind

generated by GAPDoc2HTML