3 Transformations

A transformation of degree n is a map from the set {1, ... , n} into itself. Thus a transformation alpha of degree n associates a positive integer i^alpha less than or equal to n to each number i between 1 and n.

The degree of a transformation may not be larger than 2^{28}-1 which is (currently) the highest index that can be accessed in a list.

Special cases of transformations are permutations (see chapter "Permutations"). However, a permutation must be converted to a transformation before most of the functions in this chapter are applicable.

The product of transformations is defined via composition of maps. Here transformations are multiplied in such a way that they act from the right on the set {1, ... , n}. That is, the product of the transformations alpha and beta of degree n is defined by [ i^(alphabeta) = (i^alpha)^betaquadmboxfor all i = 1, ... ,n. ] With respect to this multiplication the set of all transformations of degree n forms a monoid: the full transformation monoid of degree n (see chapter Transformation Monoids).

Each transformation of degree n is considered an element of the full transformation monoid of degree n although it is not necessary to construct a full transformation monoid before working with transformations. But you can only multiply two transformations if they have the same degree. You can, however, multiply a transformation of degree n by a permutation of degree n.

Transformations are entered and displayed by giving their lists of images as an argument to the function Transformation.

    gap> Transformation( [ 3, 3, 4, 2, 5 ] );
    Transformation( [ 3, 3, 4, 2, 5 ] )
    gap> Transformation( [ 3, 3, 2 ] ) * Transformation( [ 1, 2, 1 ] );
    Transformation( [ 1, 1, 2 ] )

This chapter describes functions that deal with transformations. The first sections describe the representation of a transformation in GAP (see More about Transformations) and how a transformation is constructed as a GAP object (see Transformation). The next sections describe the comparisons and the operations which are available for Operations for Transformations). There are a function to test whether an arbitrary object is a transformation (see IsTransformation) and a function to construct the identity transformation of a given degree (see IdentityTransformation). Then there are functions that compute Kernel of a Transformation). Finally, there are a function that converts a permutation to a transformation (see TransPerm) and a function that, if possible converts a transformation to a permutation (see PermTrans).

The functions described here are in the file "transfor.g".


  1. More about Transformations
  2. Transformation
  3. IdentityTransformation
  4. Comparisons of Transformations
  5. Operations for Transformations
  6. IsTransformation
  7. Degree of a Transformation
  8. Rank of a Transformation
  9. Image of a Transformation
  10. Kernel of a Transformation
  11. PermLeftQuoTrans
  12. TransPerm
  13. PermTrans
[Previous] [Up] [Next] 

Version 2.4 (May 1998)