Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 Bib Ind
[Top of Book] [Contents] [Previous Chapter] [Next Chapter]

[MathJax on]

32 Mappings
32.1 Direct Products and their Elements
32.1-1 IsDirectProductElement
32.1-2 DirectProductElement
32.1-3 DirectProductFamily
32.2 Creating Mappings
32.2-1 GeneralMappingByElements
32.2-2 MappingByFunction
32.2-3 InverseGeneralMapping
32.2-4 RestrictedInverseGeneralMapping
32.2-5 CompositionMapping
32.2-6 CompositionMapping2
32.2-7 IsCompositionMappingRep
32.2-8 ConstituentsCompositionMapping
32.2-9 ZeroMapping
32.2-10 IdentityMapping
32.2-11 Embedding
32.2-12 Projection
32.2-13 RestrictedMapping
32.3 Properties and Attributes of (General) Mappings
32.3-1 IsTotal
32.3-2 IsSingleValued
32.3-3 IsMapping
32.3-4 IsInjective
32.3-5 IsSurjective
32.3-6 IsBijective
32.3-7 Range
32.3-8 Source
32.3-9 UnderlyingRelation
32.3-10 UnderlyingGeneralMapping
32.4 Images under Mappings
32.4-1 ImagesSource
32.4-2 ImagesRepresentative
32.4-3 ImagesElm
32.4-4 ImagesSet
32.4-5 ImageElm
32.4-6 Image
32.4-7 Images
32.5 Preimages under Mappings
32.5-1 PreImagesRange
32.5-2 PreImagesElm
32.5-3 PreImageElm
32.5-4 PreImagesRepresentative
32.5-5 PreImagesSet
32.5-6 PreImage
32.5-7 PreImages
32.6 Arithmetic Operations for General Mappings
32.7 Mappings which are Compatible with Algebraic Structures
32.8 Magma Homomorphisms
32.8-1 IsMagmaHomomorphism
32.8-2 MagmaHomomorphismByFunctionNC
32.8-3 NaturalHomomorphismByGenerators
32.9 Mappings that Respect Multiplication
32.9-1 RespectsMultiplication
32.9-2 RespectsOne
32.9-3 RespectsInverses
32.9-4 IsGroupGeneralMapping
32.9-5 KernelOfMultiplicativeGeneralMapping
32.9-6 CoKernelOfMultiplicativeGeneralMapping
32.10 Mappings that Respect Addition
32.10-1 RespectsAddition
32.10-2 RespectsAdditiveInverses
32.10-3 RespectsZero
32.10-4 IsAdditiveGroupGeneralMapping
32.10-5 KernelOfAdditiveGeneralMapping
32.10-6 CoKernelOfAdditiveGeneralMapping
32.11 Linear Mappings
32.11-1 RespectsScalarMultiplication
32.11-2 IsLeftModuleGeneralMapping
32.11-3 IsLinearMapping
32.12 Ring Homomorphisms
32.12-1 IsRingGeneralMapping
32.12-2 IsRingWithOneGeneralMapping
32.12-3 IsAlgebraGeneralMapping
32.12-4 IsAlgebraWithOneGeneralMapping
32.12-5 IsFieldHomomorphism
32.13 General Mappings
32.13-1 IsGeneralMapping
32.13-2 IsConstantTimeAccessGeneralMapping
32.13-3 IsEndoGeneralMapping
32.14 Technical Matters Concerning General Mappings
32.14-1 IsSPGeneralMapping
32.14-2 IsGeneralMappingFamily
32.14-3 FamilyRange
32.14-4 FamilySource
32.14-5 FamiliesOfGeneralMappingsAndRanges
32.14-6 GeneralMappingsFamily
32.14-7 TypeOfDefaultGeneralMapping

### 32 Mappings

A mapping in GAP is what is called a function in mathematics. GAP also implements generalized mappings in which one element might have several images, these can be imagined as subsets of the cartesian product and are often called relations.

Most operations are declared for general mappings and therefore this manual often refers to (general) mappings, unless you deliberately need the generalization you can ignore the general bit and just read it as mappings.

A general mapping F in GAP is described by its source S, its range R, and a subset Rel of the direct product S × R, which is called the underlying relation of F. S, R, and Rel are generalized domains (see 12.4). The corresponding attributes for general mappings are `Source` (32.3-8), `Range` (32.3-7), and `UnderlyingRelation` (32.3-9).

Note that general mappings themselves are not domains. One reason for this is that two general mappings with same underlying relation are regarded as equal only if also the sources are equal and the ranges are equal. Other, more technical, reasons are that general mappings and domains have different basic operations, and that general mappings are arithmetic objects (see 32.6); both should not apply to domains.

Each element of an underlying relation of a general mapping lies in the category of direct product elements (see `IsDirectProductElement` (32.1-1)).

For each s ∈ S, the set { r ∈ R | (s,r) ∈ Rel } is called the set of images of s. Analogously, for r ∈ R, the set { s ∈ S | (s,r) ∈ Rel } is called the set of preimages of r.

The ordering of general mappings via `<` is defined by the ordering of source, range, and underlying relation. Specifically, if the source and range domains of map1 and map2 are the same, then one considers the union of the preimages of map1 and map2 as a strictly ordered set. The smaller of map1 and map2 is the one whose image is smaller on the first point of this sequence where they differ.

For mappings which preserve an algebraic structure a kernel is defined. Depending on the structure preserved the operation to compute this kernel is called differently, see Section 32.7.

Some technical details of general mappings are described in section 32.14.

#### 32.1 Direct Products and their Elements

##### 32.1-1 IsDirectProductElement

`‣ IsDirectProductElement`( obj ) | ( category )

`IsDirectProductElement` is a subcategory of the meet of `IsDenseList` (21.1-2), `IsMultiplicativeElementWithInverse` (31.14-13), `IsAdditiveElementWithInverse` (31.14-7), and `IsCopyable` (12.6-1), where the arithmetic operations (addition, zero, additive inverse, multiplication, powering, one, inverse) are defined componentwise.

Note that each of these operations will cause an error message if its result for at least one component cannot be formed.

For an object in the filter `IsDirectProductElement`, `ShallowCopy` (12.7-1) returns a mutable plain list with the same entries. The sum and the product of a direct product element and a list in `IsListDefault` (21.12-3) is the list of sums and products, respectively. The sum and the product of a direct product element and an object that is neither a list nor a collection is the direct product element of componentwise sums and products, respectively.

##### 32.1-2 DirectProductElement

`‣ DirectProductElement`( [fam, ]objlist ) | ( operation )

`‣ DirectProductElementNC`( fam, objlist ) | ( operation )

`DirectProductElement` returns a direct product element whose components are the entries of the list objlist. If the optional argument fam is given, it must be the family of direct product elements with the appropriate component families; otherwise the family is determined from objlist.

`DirectProductElementNC` does the same but omits the checks that fam is consistent with objlist.

Direct product elements behave like lists: they can be indexed with `elm[i]` to access the i-th component, and `Length` (21.17-5) returns the number of components. Arithmetic operations (multiplication, powering, one, inverse, addition, zero, additive inverse) are performed componentwise.

    gap> a := (1,2,3);; b := (1,2);;
    gap> elm := DirectProductElement([a, b]);
    DirectProductElement( [ (1,2,3), (1,2) ] )
    gap> elm[1];
    (1,2,3)
    gap> elm[2];
    (1,2)
    gap> Length(elm);
    2
    gap> elm2 := DirectProductElement([b, a]);;
    gap> elm * elm2;
    DirectProductElement( [ (2,3), (1,3) ] )
    gap> One(elm);
    DirectProductElement( [ (), () ] )
    gap> Inverse(elm);
    DirectProductElement( [ (1,3,2), (1,2) ] )

The following example shows `DirectProductElement` in the context of a direct product K = G × H built with `DirectProduct` (49.1-1), where G is a permutation group and H is a pc group. The projections of K are used to move between the direct product and its component groups.

    gap> G := DihedralGroup(IsPermGroup, 8);;
    gap> H := CyclicGroup(IsPcGroup, 4);;
    gap> K := DirectProduct(G, H);;
    gap> proj1 := Projection(K, 1);; proj2 := Projection(K, 2);;
    gap> g := (1,2,3,4);; h := GeneratorsOfGroup(H)[1];;
    gap> elm := DirectProductElement([g, h]);
    DirectProductElement( [ (1,2,3,4), f1 ] )
    gap> Image(proj1, elm) = g;
    true
    gap> Image(proj2, elm) = h;
    true

##### 32.1-3 DirectProductFamily

`‣ DirectProductFamily`( args ) | ( function )

args must be a dense list of `CollectionsFamily` (30.2-1) families, otherwise the function raises an error.

`DirectProductFamily` returns `fam`, a collections family of `IsDirectProductElement` (32.1-1) objects.

`fam` is the `CollectionsFamily` (30.2-1) of `IsDirectProductElement` (32.1-1) objects whose `i`-th component is in `ElementsFamily(args[i])`.

Note that a collection in `fam` may not itself be a direct product; it just is a subcollection of a direct product.

    gap> D8 := DihedralGroup(IsPermGroup, 8);;
    gap> FamilyObj(D8) = CollectionsFamily(PermutationsFamily);
    true
    gap> fam := DirectProductFamily([FamilyObj(D8), FamilyObj(D8)]);;
    gap> ComponentsOfDirectProductElementsFamily(ElementsFamily(fam));
    [ <Family: "PermutationsFamily">, <Family: "PermutationsFamily"> ]

Also note that not all direct products in GAP are created via these families. For example if the arguments to `DirectProduct` (49.1-1) are permutation groups, then it returns a permutation group as well, whose elements are not `IsDirectProductElement` (32.1-1) objects.

    gap> fam = FamilyObj(DirectProduct(D8, D8));
    false
    gap> D4 := DihedralGroup(IsPcGroup, 4);;
    gap> fam2 := DirectProductFamily([FamilyObj(D8), FamilyObj(D4)]);;
    gap> fam2 = FamilyObj(DirectProduct(D8, D4));
    true

#### 32.2 Creating Mappings

##### 32.2-1 GeneralMappingByElements

`‣ GeneralMappingByElements`( S, R, elms ) | ( function )

is the general mapping with source S and range R, and with underlying relation consisting of the collection elms of direct product elements.

##### 32.2-2 MappingByFunction

`‣ MappingByFunction`( S, R, fun[, invfun] ) | ( function )

`‣ MappingByFunction`( S, R, fun, false, prefun ) | ( function )

`MappingByFunction` returns a mapping `map` with source S and range R, such that each element s of S is mapped to the element fun( s ), where fun is a GAP function.

If the argument invfun is bound then `map` is a bijection between S and R, and the preimage of each element r of R is given by invfun( r ), where invfun is a GAP function.

If five arguments are given and the fourth argument is `false` then the GAP function prefun can be used to compute a single preimage also if `map` is not bijective.

The mapping returned by `MappingByFunction` lies in the filter `IsNonSPGeneralMapping` (32.14-1), see 32.14.

##### 32.2-3 InverseGeneralMapping

`‣ InverseGeneralMapping`( map ) | ( attribute )

The inverse general mapping of a general mapping map is the general mapping whose underlying relation (see `UnderlyingRelation` (32.3-9)) contains a pair (r,s) if and only if the underlying relation of map contains the pair (s,r).

Note that the inverse general mapping of a mapping map is in general only a general mapping. If map knows to be bijective, then its inverse general mapping will know to be a mapping. However, `Inverse` (31.10-8) works for a bijective general mapping map only if the source and range of map coincide. This behaviour agrees with the definition of Inverse.

##### 32.2-4 RestrictedInverseGeneralMapping

`‣ RestrictedInverseGeneralMapping`( map ) | ( attribute )

The restricted inverse general mapping of a general mapping map is the general mapping whose underlying relation (see `UnderlyingRelation` (32.3-9)) contains a pair (r,s) if and only if the underlying relation of map contains the pair (s,r), and whose domain is restricted to the image of map and whose range is the domain of map.

##### 32.2-5 CompositionMapping

`‣ CompositionMapping`( map1, map2, ... ) | ( function )

`CompositionMapping` allows one to compose arbitrarily many general mappings, and delegates each step to `CompositionMapping2` (32.2-6). The result is a map that maps an element first under the last argument, then under the penultimate argument and so forth.

Additionally, the properties `IsInjective` (32.3-4) and `IsSingleValued` (32.3-2) are maintained. If the range of the i+1-th argument is identical to the range of the i-th argument, also `IsTotal` (32.3-1) and `IsSurjective` (32.3-5) are maintained. (So one should not call `CompositionMapping2` (32.2-6) directly if one wants to maintain these properties.)

Depending on the types of map1 and map2, the returned mapping might be constructed completely new (for example by giving domain generators and their images, this is for example the case if both mappings preserve the same algebraic structures and GAP can decompose elements of the source of map2 into generators) or as an (iterated) composition (see `IsCompositionMappingRep` (32.2-7)).

    gap> f := GroupHomomorphismByImages(CyclicGroup(IsPermGroup, 2),
    >                                   CyclicGroup(IsPermGroup, 1));
    [ (1,2) ] -> [ () ]
    gap> g := GroupHomomorphismByImages(CyclicGroup(IsPermGroup, 6),
    >                                   CyclicGroup(IsPermGroup, 2));
    [ (1,2,3,4,5,6) ] -> [ (1,2) ]
    gap> CompositionMapping(f, g);
    [ (1,2,3,4,5,6) ] -> [ () ]
    gap> CompositionMapping(g, f);
    [ (1,2) ] -> [ () ]

##### 32.2-6 CompositionMapping2

`‣ CompositionMapping2`( map2, map1 ) | ( operation )

`‣ CompositionMapping2General`( map2, map1 ) | ( function )

`CompositionMapping2` returns the composition of map2 and map1, this is the general mapping that maps an element first under map1, and then maps the images under map2.

(Note the reverse ordering of arguments in the composition via the multiplication `\*` (31.12-1).

`CompositionMapping2General` is the method that forms a composite mapping with two constituent mappings. (This is used in some algorithms.)

##### 32.2-7 IsCompositionMappingRep

`‣ IsCompositionMappingRep`( map ) | ( representation )

Mappings in this representation are stored as composition of two mappings, (pre)images of elements are computed in a two-step process. The constituent mappings of the composition can be obtained via `ConstituentsCompositionMapping` (32.2-8).

##### 32.2-8 ConstituentsCompositionMapping

`‣ ConstituentsCompositionMapping`( map ) | ( function )

If map is stored in the representation `IsCompositionMappingRep` (32.2-7) as composition of two mappings map1 and map2, this function returns the two constituent mappings in a list `[ map1, map2 ]`.

##### 32.2-9 ZeroMapping

`‣ ZeroMapping`( S, R ) | ( operation )

A zero mapping is a total general mapping that maps each element of its source to the zero element of its range.

(Each mapping with empty source is a zero mapping.)

##### 32.2-10 IdentityMapping

`‣ IdentityMapping`( D ) | ( attribute )

is the bijective mapping with source and range equal to the collection D, which maps each element of D to itself.

##### 32.2-11 Embedding

`‣ Embedding`( S, T ) | ( operation )

`‣ Embedding`( S, i ) | ( operation )

returns the embedding of the domain S in the domain T, or in the second form, some domain indexed by the positive integer i. The precise natures of the various methods are described elsewhere: for Lie algebras, see `LieFamily` (64.1-3); for group products, see 49.6 for a general description, or for examples see 49.1 for direct products, 49.2 for semidirect products, or 49.4 for wreath products; or for magma rings see 65.3.

##### 32.2-12 Projection

`‣ Projection`( S, T ) | ( operation )

`‣ Projection`( S, i ) | ( operation )

`‣ Projection`( S ) | ( operation )

returns the projection of the domain S onto the domain T, or in the second form, some domain indexed by the positive integer i, or in the third form some natural quotient domain of S. Various methods are defined for group products; see 49.6 for a general description, or for examples see 49.1 for direct products, 49.2 for semidirect products, 49.3 for subdirect products, or 49.4 for wreath products.

##### 32.2-13 RestrictedMapping

`‣ RestrictedMapping`( map, subdom ) | ( operation )

If subdom is a subdomain of the source of the general mapping map, this operation returns the restriction of map to subdom.

#### 32.3 Properties and Attributes of (General) Mappings

##### 32.3-1 IsTotal

`‣ IsTotal`( map ) | ( property )

is `true` if each element in the source S of the general mapping map has images, i.e., s^map ≠ ∅ for all s ∈ S, and `false` otherwise.

##### 32.3-2 IsSingleValued

`‣ IsSingleValued`( map ) | ( property )

is `true` if each element in the source S of the general mapping map has at most one image, i.e., |s^map| ≤ 1 for all s ∈ S, and `false` otherwise.

Equivalently, `IsSingleValued( map )` is `true` if and only if the preimages of different elements in R are disjoint.

##### 32.3-3 IsMapping

`‣ IsMapping`( map ) | ( filter )

A mapping map is a general mapping that assigns to each element `elm` of its source a unique element `Image( map, elm )` of its range.

Equivalently, the general mapping map is a mapping if and only if it is total and single-valued (see `IsTotal` (32.3-1), `IsSingleValued` (32.3-2)).

##### 32.3-4 IsInjective

`‣ IsInjective`( map ) | ( property )

is `true` if the images of different elements in the source S of the general mapping map are disjoint, i.e., x^map ∩ y^map = ∅ for x ≠ y ∈ S, and `false` otherwise.

Equivalently, `IsInjective( map )` is `true` if and only if each element in the range of map has at most one preimage in S.

##### 32.3-5 IsSurjective

`‣ IsSurjective`( map ) | ( property )

is `true` if each element in the range R of the general mapping map has preimages in the source S of map, i.e., { s ∈ S ∣ x ∈ s^map } ≠ ∅ for all x ∈ R, and `false` otherwise.

##### 32.3-6 IsBijective

`‣ IsBijective`( map ) | ( property )

A general mapping map is bijective if and only if it is an injective and surjective mapping (see `IsMapping` (32.3-3), `IsInjective` (32.3-4), `IsSurjective` (32.3-5)).

##### 32.3-7 Range

`‣ Range`( map ) | ( attribute )

The range of a general mapping.

##### 32.3-8 Source

`‣ Source`( map ) | ( attribute )

The source of a general mapping.

##### 32.3-9 UnderlyingRelation

`‣ UnderlyingRelation`( map ) | ( attribute )

The underlying relation of a general mapping map is the domain of pairs (s,r), with s in the source and r in the range of map (see `Source` (32.3-8), `Range` (32.3-7)), and r ∈ `ImagesElm( map,` s`)`.

Each element of the underlying relation is represented by a direct product element (see `IsDirectProductElement` (32.1-1)).

##### 32.3-10 UnderlyingGeneralMapping

`‣ UnderlyingGeneralMapping`( map ) | ( attribute )

attribute for underlying relations of general mappings

#### 32.4 Images under Mappings

##### 32.4-1 ImagesSource

`‣ ImagesSource`( map ) | ( attribute )

is the set of images of the source of the general mapping map.

`ImagesSource` delegates to `ImagesSet` (32.4-4), it is introduced only to store the image of map as attribute value.

##### 32.4-2 ImagesRepresentative

`‣ ImagesRepresentative`( map, elm ) | ( operation )

If elm is an element of the source of the general mapping map then `ImagesRepresentative` returns either a representative of the set of images of elm under map or `fail`, the latter if and only if elm has no images under map.

Anything may happen if elm is not an element of the source of map.

##### 32.4-3 ImagesElm

`‣ ImagesElm`( map, elm ) | ( operation )

If elm is an element of the source of the general mapping map then `ImagesElm` returns the set of all images of elm under map.

Anything may happen if elm is not an element of the source of map.

##### 32.4-4 ImagesSet

`‣ ImagesSet`( map, elms ) | ( operation )

If elms is a subset of the source of the general mapping map then `ImagesSet` returns the set of all images of elms under map.

The result will be either a proper set or a domain. Anything may happen if elms is not a subset of the source of map.

##### 32.4-5 ImageElm

`‣ ImageElm`( map, elm ) | ( operation )

If elm is an element of the source of the total and single-valued mapping map then `ImageElm` returns the unique image of elm under map.

Anything may happen if elm is not an element of the source of map.

##### 32.4-6 Image

`‣ Image`( map ) | ( function )

`‣ Image`( map, elm ) | ( function )

`‣ Image`( map, coll ) | ( function )

`Image( map )` is the image of the general mapping map, i.e., the subset of elements of the range of map that are actually values of map. Note that in this case the argument may also be multi-valued.

`Image( map, elm )` is the image of the element elm of the source of the mapping map under map, i.e., the unique element of the range to which map maps elm. This can also be expressed as elm`^`map or as map`(` elm`)`.

Note that map must be total and single valued, a multi valued general mapping is not allowed (see `Images` (32.4-7)).

`Image( map, coll )` is the image of the subset coll of the source of the mapping map under map, i.e., the subset of the range to which map maps elements of coll.

coll may be a proper set or a domain. The result will be either a proper set or a domain. Note that in this case map may also be multi-valued. (If coll and the result are lists then the positions of entries do in general not correspond.)

`Image( map, coll )` can also be expressed as `map(coll)` and `Image( map, elm )` as `map(elm)`. Those using this notation should remember that composition of mappings in GAP still follows the conventions appropriate for mapping acting from the right, so that `(map1*map2)(x)` is equivalent to `map2(map1(x))`

`Image` delegates to `ImagesSource` (32.4-1) when called with one argument, and to `ImageElm` (32.4-5) resp. `ImagesSet` (32.4-4) when called with two arguments.

If the second argument is not an element or a subset of the source of the first argument, an error is signalled.

##### 32.4-7 Images

`‣ Images`( map ) | ( function )

`‣ Images`( map, elm ) | ( function )

`‣ Images`( map, coll ) | ( function )

`Images( map )` is the image of the general mapping map, i.e., the subset of elements of the range of map that are actually values of map.

`Images( map, elm )` is the set of images of the element elm of the source of the general mapping map under map, i.e., the set of elements of the range to which map maps elm.

`Images( map, coll )` is the set of images of the subset coll of the source of the general mapping map under map, i.e., the subset of the range to which map maps elements of coll. coll may be a proper set or a domain. The result will be either a proper set or a domain. (If coll and the result are lists then the positions of entries do in general not correspond.)

`Images` delegates to `ImagesSource` (32.4-1) when called with one argument, and to `ImagesElm` (32.4-3) resp. `ImagesSet` (32.4-4) when called with two arguments.

If the second argument is not an element or a subset of the source of the first argument, an error is signalled.

#### 32.5 Preimages under Mappings

##### 32.5-1 PreImagesRange

`‣ PreImagesRange`( map ) | ( attribute )

is the set of preimages of the range of the general mapping map.

`PreImagesRange` delegates to `PreImagesSet` (32.5-5), it is introduced only to store the preimage of map as attribute value.

##### 32.5-2 PreImagesElm

`‣ PreImagesElm`( map, elm ) | ( operation )

If elm is an element of the range of the general mapping map then `PreImagesElm` returns the set of all preimages of elm under map.

Anything may happen if elm is not an element of the range of map.

##### 32.5-3 PreImageElm

`‣ PreImageElm`( map, elm ) | ( operation )

If elm is an element of the range of the injective and surjective general mapping map then `PreImageElm` returns the unique preimage of elm under map.

Anything may happen if elm is not an element of the range of map.

##### 32.5-4 PreImagesRepresentative

`‣ PreImagesRepresentative`( map, elm ) | ( operation )

If elm is an element of the range of the general mapping map then `PreImagesRepresentative` returns either a representative of the set of preimages of elm under map or `fail`, the latter if and only if elm has no preimages under map.

Anything may happen if elm is not an element of the range of map.

##### 32.5-5 PreImagesSet

`‣ PreImagesSet`( map, elms ) | ( operation )

If elms is a subset of the range of the general mapping map then `PreImagesSet` returns the set of all preimages of elms under map.

Anything may happen if elms is not a subset of the range of map.

##### 32.5-6 PreImage

`‣ PreImage`( map ) | ( function )

`‣ PreImage`( map, elm ) | ( function )

`‣ PreImage`( map, coll ) | ( function )

`PreImage( map )` is the preimage of the general mapping map, i.e., the subset of elements of the source of map that actually have values under map. Note that in this case the argument may also be non-injective or non-surjective.

`PreImage( map, elm )` is the preimage of the element elm of the range of the injective and surjective mapping map under map, i.e., the unique element of the source which is mapped under map to elm. Note that map must be injective and surjective (see `PreImages` (32.5-7)).

`PreImage( map, coll )` is the preimage of the subset coll of the range of the general mapping map under map, i.e., the subset of the source which is mapped under map to elements of coll. coll may be a proper set or a domain. The result will be either a proper set or a domain. Note that in this case map may also be non-injective or non-surjective. (If coll and the result are lists then the positions of entries do in general not correspond.)

`PreImage` delegates to `PreImagesRange` (32.5-1) when called with one argument, and to `PreImageElm` (32.5-3) resp. `PreImagesSet` (32.5-5) when called with two arguments.

If the second argument is not an element or a subset of the range of the first argument, an error is signalled.

##### 32.5-7 PreImages

`‣ PreImages`( map ) | ( function )

`‣ PreImages`( map, elm ) | ( function )

`‣ PreImages`( map, coll ) | ( function )

`PreImages( map )` is the preimage of the general mapping map, i.e., the subset of elements of the source of map that have actually values under map.

`PreImages( map, elm )` is the set of preimages of the element elm of the range of the general mapping map under map, i.e., the set of elements of the source which map maps to elm.

`PreImages( map, coll )` is the set of images of the subset coll of the range of the general mapping map under map, i.e., the subset of the source which map maps to elements of coll. coll may be a proper set or a domain. The result will be either a proper set or a domain. (If coll and the result are lists then the positions of entries do in general not correspond.)

`PreImages` delegates to `PreImagesRange` (32.5-1) when called with one argument, and to `PreImagesElm` (32.5-2) resp. `PreImagesSet` (32.5-5) when called with two arguments.

If the second argument is not an element or a subset of the range of the first argument, an error is signalled.

#### 32.6 Arithmetic Operations for General Mappings

General mappings are arithmetic objects. One can form groups and vector spaces of general mappings provided that they are invertible or can be added and admit scalar multiplication, respectively.

For two general mappings with same source, range, preimage, and image, the sum is defined pointwise, i.e., the images of a point under the sum is the set of all sums with first summand in the images of the first general mapping and second summand in the images of the second general mapping.

Scalar multiplication of general mappings is defined likewise.

The product of two general mappings is defined as the composition. This multiplication is always associative. In addition to the composition via `*`, general mappings can be composed –in reversed order– via `CompositionMapping` (32.2-5).

General mappings are in the category of multiplicative elements with inverses. Similar to matrices, not every general mapping has an inverse or an identity, and we define the behaviour of `One` (31.10-2) and `Inverse` (31.10-8) for general mappings as follows. `One` (31.10-2) returns `fail` when called for a general mapping whose source and range differ, otherwise `One` (31.10-2) returns the identity mapping of the source. (Note that the source may differ from the preimage). `Inverse` (31.10-8) returns `fail` when called for a non-bijective general mapping or for a general mapping whose source and range differ; otherwise `Inverse` (31.10-8) returns the inverse mapping.

Besides the usual inverse of multiplicative elements, which means that `Inverse( g ) * g = g * Inverse( g ) = One( g )`, for general mappings we have the attribute `InverseGeneralMapping` (32.2-3). If F is a general mapping with source S, range R, and underlying relation Rel then `InverseGeneralMapping( F )` has source R, range S, and underlying relation { (r,s) ∣ (s,r) ∈ Rel }. For a general mapping that has an inverse in the usual sense, i.e., for a bijection of the source, of course both concepts coincide.

`Inverse` (31.10-8) may delegate to `InverseGeneralMapping` (32.2-3). `InverseGeneralMapping` (32.2-3) must not delegate to `Inverse` (31.10-8), but a known value of `Inverse` (31.10-8) may be fetched. So methods to compute the inverse of a general mapping should be installed for `InverseGeneralMapping` (32.2-3).

(Note that in many respects, general mappings behave similar to matrices, for example one can define left and right identities and inverses, which do not fit into the current concepts of GAP.)

#### 32.7 Mappings which are Compatible with Algebraic Structures

From an algebraical point of view, the most important mappings are those which are compatible with a structure. For Magmas, Groups and Rings, GAP supports the following four types of such mappings:

1. General mappings that respect multiplication

2. General mappings that respect addition

3. General mappings that respect scalar mult.

4. General mappings that respect multiplicative and additive structure

(Very technical note: GAP defines categories `IsSPGeneralMapping` and `IsNonSPGeneralMapping`. The distinction between these is orthogonal to the structure compatibility described here and should not be confused.)

#### 32.8 Magma Homomorphisms

##### 32.8-1 IsMagmaHomomorphism

`‣ IsMagmaHomomorphism`( mapp ) | ( filter )

A magma homomorphism is a total single valued mapping which respects multiplication.

##### 32.8-2 MagmaHomomorphismByFunctionNC

`‣ MagmaHomomorphismByFunctionNC`( G, H, fn ) | ( function )

Creates the homomorphism from G to H without checking that fn is a homomorphism.

##### 32.8-3 NaturalHomomorphismByGenerators

`‣ NaturalHomomorphismByGenerators`( f, s ) | ( operation )

returns a mapping from the magma f with n generators to the magma s with n generators, which maps the i-th generator of f to the i-th generator of s.

#### 32.9 Mappings that Respect Multiplication

##### 32.9-1 RespectsMultiplication

`‣ RespectsMultiplication`( mapp ) | ( property )

Let mapp be a general mapping with underlying relation F ⊆ S × R, where S and R are the source and the range of mapp, respectively. Then `RespectsMultiplication` returns `true` if S and R are magmas such that (s_1,r_1), (s_2,r_2) ∈ F implies (s_1 * s_2,r_1 * r_2) ∈ F, and `false` otherwise.

If mapp is single-valued then `RespectsMultiplication` returns `true` if and only if the equation `s1^mapp * s2^mapp = (s1 * s2)^mapp` holds for all s1, s2 in S.

##### 32.9-2 RespectsOne

`‣ RespectsOne`( mapp ) | ( property )

Let mapp be a general mapping with underlying relation F ⊆ S × R, where S and R are the source and the range of mapp, respectively. Then `RespectsOne` returns `true` if S and R are magmas-with-one such that (`One(S)`,`One(R)`) ∈ F, and `false` otherwise.

If mapp is single-valued then `RespectsOne` returns `true` if and only if the equation `One( S )^mapp = One( R )` holds.

##### 32.9-3 RespectsInverses

`‣ RespectsInverses`( mapp ) | ( property )

Let mapp be a general mapping with underlying relation F ⊆ S × R, where S and R are the source and the range of mapp, respectively. Then `RespectsInverses` returns `true` if S and R are magmas-with-inverses such that, for s ∈ S and r ∈ R, (s,r) ∈ F implies (s^{-1},r^{-1}) ∈ F, and `false` otherwise.

If mapp is single-valued then `RespectsInverses` returns `true` if and only if the equation `Inverse( s )^mapp = Inverse( s^mapp )` holds for all s in S.

##### 32.9-4 IsGroupGeneralMapping

`‣ IsGroupGeneralMapping`( mapp ) | ( filter )

`‣ IsGroupHomomorphism`( mapp ) | ( filter )

A group general mapping is a mapping which respects multiplication and inverses. If it is total and single valued it is called a group homomorphism.

Chapter 40 explains group homomorphisms in more detail.

##### 32.9-5 KernelOfMultiplicativeGeneralMapping

`‣ KernelOfMultiplicativeGeneralMapping`( mapp ) | ( attribute )

Let mapp be a general mapping. Then `KernelOfMultiplicativeGeneralMapping` returns the set of all elements in the source of mapp that have the identity of the range in their set of images.

(This is a monoid if mapp respects multiplication and one, and if the source of mapp is associative.)

##### 32.9-6 CoKernelOfMultiplicativeGeneralMapping

`‣ CoKernelOfMultiplicativeGeneralMapping`( mapp ) | ( attribute )

Let mapp be a general mapping. Then `CoKernelOfMultiplicativeGeneralMapping` returns the set of all elements in the range of mapp that have the identity of the source in their set of preimages.

(This is a monoid if mapp respects multiplication and one, and if the range of mapp is associative.)

#### 32.10 Mappings that Respect Addition

##### 32.10-1 RespectsAddition

`‣ RespectsAddition`( mapp ) | ( property )

Let mapp be a general mapping with underlying relation F ⊆ S × R, where S and R are the source and the range of mapp, respectively. Then `RespectsAddition` returns `true` if S and R are additive magmas such that (s_1,r_1), (s_2,r_2) ∈ F implies (s_1 + s_2,r_1 + r_2) ∈ F, and `false` otherwise.

If mapp is single-valued then `RespectsAddition` returns `true` if and only if the equation `s1^mapp + s2^mapp = (s1+s2)^mapp` holds for all s1, s2 in S.

##### 32.10-2 RespectsAdditiveInverses

`‣ RespectsAdditiveInverses`( mapp ) | ( property )

Let mapp be a general mapping with underlying relation F ⊆ S × R, where S and R are the source and the range of mapp, respectively. Then `RespectsAdditiveInverses` returns `true` if S and R are additive-magmas-with-inverses such that (s,r) ∈ F implies (-s,-r) ∈ F, and `false` otherwise.

If mapp is single-valued then `RespectsAdditiveInverses` returns `true` if and only if the equation `AdditiveInverse( s )^mapp = AdditiveInverse( s^mapp )` holds for all s in S.

##### 32.10-3 RespectsZero

`‣ RespectsZero`( mapp ) | ( property )

Let mapp be a general mapping with underlying relation F ⊆ S × R, where S and R are the source and the range of mapp, respectively. Then `RespectsZero` returns `true` if S and R are additive-magmas-with-zero such that (`Zero(S)`,`Zero(R)`) ∈ F, and `false` otherwise.

If mapp is single-valued then `RespectsZero` returns `true` if and only if the equation `Zero( S )^mapp = Zero( R )` holds.

##### 32.10-4 IsAdditiveGroupGeneralMapping

`‣ IsAdditiveGroupGeneralMapping`( mapp ) | ( filter )

`‣ IsAdditiveGroupHomomorphism`( mapp ) | ( filter )

`IsAdditiveGroupGeneralMapping` specifies whether a general mapping mapp respects addition (see `RespectsAddition` (32.10-1)) and respects additive inverses (see `RespectsAdditiveInverses` (32.10-2)).

`IsAdditiveGroupHomomorphism` is a synonym for the meet of `IsAdditiveGroupGeneralMapping` and `IsMapping` (32.3-3).

##### 32.10-5 KernelOfAdditiveGeneralMapping

`‣ KernelOfAdditiveGeneralMapping`( mapp ) | ( attribute )

Let mapp be a general mapping. Then `KernelOfAdditiveGeneralMapping` returns the set of all elements in the source of mapp that have the zero of the range in their set of images.

##### 32.10-6 CoKernelOfAdditiveGeneralMapping

`‣ CoKernelOfAdditiveGeneralMapping`( mapp ) | ( attribute )

Let mapp be a general mapping. Then `CoKernelOfAdditiveGeneralMapping` returns the set of all elements in the range of mapp that have the zero of the source in their set of preimages.

#### 32.11 Linear Mappings

Also see Sections 32.9, 32.10, and `KernelOfMultiplicativeGeneralMapping` (32.9-5), `CoKernelOfMultiplicativeGeneralMapping` (32.9-6).

##### 32.11-1 RespectsScalarMultiplication

`‣ RespectsScalarMultiplication`( mapp ) | ( property )

Let mapp be a general mapping, with underlying relation F ⊆ S × R, where S and R are the source and the range of mapp, respectively. Then `RespectsScalarMultiplication` returns `true` if S and R are left modules with the left acting domain D of S contained in the left acting domain of R and such that (s,r) ∈ F implies (c * s,c * r) ∈ F for all c ∈ D, and `false` otherwise.

If mapp is single-valued then `RespectsScalarMultiplication` returns `true` if and only if the equation `c * s^mapp = (c * s)^mapp` holds for all c in D and s in S.

##### 32.11-2 IsLeftModuleGeneralMapping

`‣ IsLeftModuleGeneralMapping`( mapp ) | ( filter )

`‣ IsLeftModuleHomomorphism`( mapp ) | ( filter )

`IsLeftModuleGeneralMapping` specifies whether a general mapping mapp satisfies the property `IsAdditiveGroupGeneralMapping` (32.10-4) and respects scalar multiplication (see `RespectsScalarMultiplication` (32.11-1)).

`IsLeftModuleHomomorphism` is a synonym for the meet of `IsLeftModuleGeneralMapping` and `IsMapping` (32.3-3).

##### 32.11-3 IsLinearMapping

`‣ IsLinearMapping`( F, mapp ) | ( operation )

For a field F and a general mapping mapp, `IsLinearMapping` returns `true` if mapp is an F-linear mapping, and `false` otherwise.

A mapping f is a linear mapping (or vector space homomorphism) if the source and range are vector spaces over the same division ring D, and if f( a + b ) = f(a) + f(b) and f( s * a ) = s * f(a) hold for all elements a, b in the source of f and s ∈ D.

#### 32.12 Ring Homomorphisms

##### 32.12-1 IsRingGeneralMapping

`‣ IsRingGeneralMapping`( mapp ) | ( filter )

`‣ IsRingHomomorphism`( mapp ) | ( filter )

`IsRingGeneralMapping` specifies whether a general mapping mapp satisfies the property `IsAdditiveGroupGeneralMapping` (32.10-4) and respects multiplication (see `RespectsMultiplication` (32.9-1)).

`IsRingHomomorphism` is a synonym for the meet of `IsRingGeneralMapping` and `IsMapping` (32.3-3).

##### 32.12-2 IsRingWithOneGeneralMapping

`‣ IsRingWithOneGeneralMapping`( mapp ) | ( filter )

`‣ IsRingWithOneHomomorphism`( mapp ) | ( filter )

##### 32.12-3 IsAlgebraGeneralMapping

`‣ IsAlgebraGeneralMapping`( mapp ) | ( filter )

`‣ IsAlgebraHomomorphism`( mapp ) | ( filter )

`IsAlgebraGeneralMapping` specifies whether a general mapping mapp satisfies both properties `IsRingGeneralMapping` (32.12-1) and (see `IsLeftModuleGeneralMapping` (32.11-2)).

`IsAlgebraHomomorphism` is a synonym for the meet of `IsAlgebraGeneralMapping` and `IsMapping` (32.3-3).

##### 32.12-4 IsAlgebraWithOneGeneralMapping

`‣ IsAlgebraWithOneGeneralMapping`( mapp ) | ( filter )

`‣ IsAlgebraWithOneHomomorphism`( mapp ) | ( filter )

`IsAlgebraWithOneGeneralMapping` specifies whether a general mapping mapp satisfies both properties `IsAlgebraGeneralMapping` (32.12-3) and `RespectsOne` (32.9-2).

`IsAlgebraWithOneHomomorphism` is a synonym for the meet of `IsAlgebraWithOneGeneralMapping` and `IsMapping` (32.3-3).

##### 32.12-5 IsFieldHomomorphism

`‣ IsFieldHomomorphism`( mapp ) | ( property )

A general mapping is a field homomorphism if and only if it is a ring homomorphism with source a field.

#### 32.13 General Mappings

##### 32.13-1 IsGeneralMapping

`‣ IsGeneralMapping`( map ) | ( category )

Each general mapping lies in the category `IsGeneralMapping`. It implies the categories `IsMultiplicativeElementWithInverse` (31.14-13) and `IsAssociativeElement` (31.15-1); for a discussion of these implications, see 32.6.

##### 32.13-2 IsConstantTimeAccessGeneralMapping

`‣ IsConstantTimeAccessGeneralMapping`( map ) | ( property )

is `true` if the underlying relation of the general mapping map knows its `AsList` (30.3-8) value, and `false` otherwise.

In the former case, map is allowed to use this list for calls to `ImagesElm` (32.4-3) etc.

##### 32.13-3 IsEndoGeneralMapping

`‣ IsEndoGeneralMapping`( obj ) | ( property )

If a general mapping has this property then its source and range are equal.

#### 32.14 Technical Matters Concerning General Mappings

`Source` (32.3-8) and `Range` (32.3-7) are basic operations for general mappings. `UnderlyingRelation` (32.3-9) is secondary, its default method sets up a domain that delegates tasks to the general mapping. (Note that this allows one to handle also infinite relations by generic methods if source or range of the general mapping is finite.)

The distinction between basic operations and secondary operations for general mappings may be a little bit complicated. Namely, each general mapping must be in one of the two categories `IsNonSPGeneralMapping` (32.14-1), `IsSPGeneralMapping` (32.14-1). (The category `IsGeneralMapping` (32.13-1) is defined as the disjoint union of these two.)

For general mappings of the first category, `ImagesElm` (32.4-3) and `PreImagesElm` (32.5-2) are basic operations. (Note that in principle it is possible to delegate from `PreImagesElm` (32.5-2) to `ImagesElm` (32.4-3).) Methods for the secondary operations `ImageElm` (32.4-5), `PreImageElm` (32.5-3), `ImagesSet` (32.4-4), `PreImagesSet` (32.5-5), `ImagesRepresentative` (32.4-2), and `PreImagesRepresentative` (32.5-4) may use `ImagesElm` (32.4-3) and `PreImagesElm` (32.5-2), respectively, and methods for `ImagesElm` (32.4-3), `PreImagesElm` (32.5-2) must not call the secondary operations. In particular, there are no generic methods for `ImagesElm` (32.4-3) and `PreImagesElm` (32.5-2).

Methods for `ImagesSet` (32.4-4) and `PreImagesSet` (32.5-5) must not use `PreImagesRange` (32.5-1) and `ImagesSource` (32.4-1), e.g., compute the intersection of the set in question with the preimage of the range resp. the image of the source.

For general mappings of the second category (which means structure preserving general mappings), the situation is different. The set of preimages under a group homomorphism, for example, is either empty or can be described as a coset of the (multiplicative) kernel. So it is reasonable to have `ImagesRepresentative` (32.4-2), `PreImagesRepresentative` (32.5-4), `KernelOfMultiplicativeGeneralMapping` (32.9-5), and `CoKernelOfMultiplicativeGeneralMapping` (32.9-6) as basic operations here, and to make `ImagesElm` (32.4-3) and `PreImagesElm` (32.5-2) secondary operations that may delegate to these.

In order to avoid infinite recursions, we must distinguish between the two different types of mappings.

(Note that the basic domain operations such as `AsList` (30.3-8) for the underlying relation of a general mapping may use either `ImagesElm` (32.4-3) or `ImagesRepresentative` (32.4-2) and the appropriate cokernel. Conversely, if `AsList` (30.3-8) for the underlying relation is known then `ImagesElm` (32.4-3) resp. `ImagesRepresentative` (32.4-2) may delegate to it, the general mapping gets the property `IsConstantTimeAccessGeneralMapping` (32.13-2) for this; note that this is not allowed if only an enumerator of the underlying relation is known.)

Secondary operations are `IsInjective` (32.3-4), `IsSingleValued` (32.3-2), `IsSurjective` (32.3-5), `IsTotal` (32.3-1); they may use the basic operations, and must not be used by them.

Methods for the operations `ImagesElm` (32.4-3), `ImagesRepresentative` (32.4-2), `ImagesSet` (32.4-4), `ImageElm` (32.4-5), `PreImagesElm` (32.5-2), `PreImagesRepresentative` (32.5-4), `PreImagesSet` (32.5-5), and `PreImageElm` (32.5-3) take two arguments, a general mapping map and an element or collection of elements elm. These methods must not check whether elm lies in the source or the range of map. In the case that elm does not, `fail` may be returned as well as any other GAP object, and even an error message is allowed. Checks of the arguments are done only by the functions `Image` (32.4-6), `Images` (32.4-7), `PreImage` (32.5-6), and `PreImages` (32.5-7), which then delegate to the operations listed above.

##### 32.14-1 IsSPGeneralMapping

`‣ IsSPGeneralMapping`( map ) | ( category )

`‣ IsNonSPGeneralMapping`( map ) | ( category )

##### 32.14-2 IsGeneralMappingFamily

`‣ IsGeneralMappingFamily`( obj ) | ( category )

The family category of the category of general mappings.

##### 32.14-3 FamilyRange

`‣ FamilyRange`( Fam ) | ( attribute )

is the elements family of the family of the range of each general mapping in the family Fam.

##### 32.14-4 FamilySource

`‣ FamilySource`( Fam ) | ( attribute )

is the elements family of the family of the source of each general mapping in the family Fam.

##### 32.14-5 FamiliesOfGeneralMappingsAndRanges

`‣ FamiliesOfGeneralMappingsAndRanges`( Fam ) | ( attribute )

is a list that stores at the odd positions the families of general mappings with source in the family Fam, at the even positions the families of ranges of the general mappings.

##### 32.14-6 GeneralMappingsFamily

`‣ GeneralMappingsFamily`( sourcefam, rangefam ) | ( function )

All general mappings with same source family FS and same range family FR lie in the family `GeneralMappingsFamily( FS, FR )`.

##### 32.14-7 TypeOfDefaultGeneralMapping

`‣ TypeOfDefaultGeneralMapping`( source, range, filter ) | ( function )

is the type of mappings with `IsDefaultGeneralMappingRep` with source source and range range and additional categories filter.

[Top of Book] [Contents] [Previous Chapter] [Next Chapter]
Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 Bib Ind

generated by GAPDoc2HTML