Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 A B C Bib Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

9 Affine Spaces
 9.1 Affine spaces and basic operations
 9.2 Subspaces of affine spaces
 9.3 Shadows of Affine Subspaces
 9.4 Iterators and enumerators
 9.5 Affine groups
 9.6 Low level operations

9 Affine Spaces

In this chapter we show how one can work with finite affine spaces in FinInG.

9.1 Affine spaces and basic operations

An affine space is a point-line incidence geometry, satisfying few well known axioms. An axiomatic treatment can e.g. be found in [VY65a] and [VY65b]. As is the case with projective spaces, affine spaces are axiomatically point-line geometries, but may contain higher dimensional affine subspaces too. An affine space can also be described as the "geometry you get" when you remove a hyperplane from a projective space. Conversely, each affine space can be extended to a projective space in a unique way (by "adding its hyperplane at infinity"). In FinInG, we deal with finite Desarguesian affine spaces, i.e. an affine space, such that its projective completion is Desarguesian. Other concepts can be easily defined using this projective completion. E.g. lines of the projective space which are concurrent in a point of the hyperplane at infinity, become now parallel in the affine space. In order to implement (Desarguesian) affine spaces in FinInG, we have to represent the elements of the affine space (the affine subspaces), in a standard way. By definition, the points (i.e. the elements of type 1) of the n-dimensional affine space AG(n,q) are the vectors of the underlying n-dimensional vector space over the finite field GF(q). The i-dimensional subspaces of AG(n,q) (i.e. the elements of type i-1) are defined as the cosets of the i-dimensional subspaces of the underlying vector space. Hence, the common representation of such a subspace is

v+S,

where v is a vector and S is a subspace of a vector space. Equivalently one can also think of a subspace of an affine space as consisting of: (i) an affine point, representing the coset, and and (ii) a "direction", which is an element of an n-1-dimensional projective space, representing the hyperplane at infinity. In FinInG, we represent an i-dimensional subspace, 1 ≤ i ≤ n-1 as

[v, mat]

where v is a row vector and mat is a matrix (representing a basis of the projective element representing the direction at infinity). For affine points, we simply use vectors.

9.1-1 IsAffineSpace
‣ IsAffineSpace( category )

This category is a subcategory of IsIncidenceGeometry, and contains all finite Desarguesian affine spaces.

9.1-2 AffineSpace
‣ AffineSpace( d, F )( operation )
‣ AffineSpace( d, q )( operation )
‣ AG( d, F )( operation )
‣ AG( d, q )( operation )

Returns: an affine space

d must be a positive integer. In the first form, F is a field and the function returns the affine space of dimension d over F. In the second form, q is a prime power specifying the size of the field. The user may also use an alias, namely, the common abbreviation AG(d, q).

gap> AffineSpace(3,GF(4));
AG(3, 4)
gap> AffineSpace(3,4);
AG(3, 4)
gap> AG(3,GF(4));
AG(3, 4)
gap> AG(3,4);
AG(3, 4)
 

9.1-3 Dimension
‣ Dimension( as )( attribute )
‣ Rank( as )( attribute )

Returns: the dimension of the affine space as (which is equal to its rank)

gap> Dimension(AG(5,7));
5
gap> Rank(AG(5,7));
5
 

9.1-4 BaseField
‣ BaseField( as )( operation )

Returns: returns the base field for the affine space as

gap> BaseField(AG(6,49));
GF(7^2)
 

9.1-5 UnderlyingVectorSpace
‣ UnderlyingVectorSpace( as )( operation )

Returns: a vector space

The underlying vectorspace of AG(n,q) is simply V(n,q).

gap> UnderlyingVectorSpace(AG(4,5));
( GF(5)^4 )
 

9.1-6 AmbientSpace
‣ AmbientSpace( as )( attribute )

Returns: an affine space

The ambient space of an affine space as is the affine space itself. Hence, simply as will be returned.

gap> AmbientSpace(AG(4,7));
AG(4, 7)
 

9.2 Subspaces of affine spaces

9.2-1 AffineSubspace
‣ AffineSubspace( geo, v )( operation )
‣ AffineSubspace( geo, v, M )( operation )

Returns: a subspace of an affine space

geo is an affine space, v is a row vector, and M is a matrix. There are two representations necessary for affine subspaces in FinInG: (i) points represented as vectors and (ii) subspaces of dimension at least 1 represented as a coset of a vector subspace:

v+S.

For the former, the underlying object is just a vector, whereas the second is a pair [v, M] where v is a vector and M is a matrix representing the basis of S. Now there is a canonical representative for the coset v+ S, and the matrix M is in semi-echelon form, therefore we can easily compare two affine subspaces. If no matrix is given in the arguments, then it is assumed that the user is constructing an affine point.

gap> ag := AffineSpace(3, 3);
AG(3, 3)
gap> x := [[1,1,0]]*Z(3)^0;
[ [ Z(3)^0, Z(3)^0, 0*Z(3) ] ]
gap> v := [0,-1,1] * Z(3)^0;
[ 0*Z(3), Z(3), Z(3)^0 ]
gap> line := AffineSubspace(ag, v, x);
<a line in AG(3, 3)>
 

9.2-2 ElementsOfIncidenceStructure
‣ ElementsOfIncidenceStructure( as, j )( operation )

Returns: the collection of elements of the affine space as of type j

For the affine space as of dimension d and the type j, 1 ≤ j ≤ d this operation returns the collection of j-1 dimensional subspaces. An error message is produced when the projective space ps has no elements of a required type.

gap> ag := AffineSpace(9, 64);
AG(9, 64)
gap> ElementsOfIncidenceStructure(ag,1);
<points of AG(9, 64)>
gap> ElementsOfIncidenceStructure(ag,2);
<lines of AG(9, 64)>
gap> ElementsOfIncidenceStructure(ag,3);
<planes of AG(9, 64)>
gap> ElementsOfIncidenceStructure(ag,4);
<solids of AG(9, 64)>
gap> ElementsOfIncidenceStructure(ag,6);
<affine. subspaces of dim. 5 of AG(9, 64)>
gap> ElementsOfIncidenceStructure(ag,9);
<affine. subspaces of dim. 8 of AG(9, 64)>
gap> ElementsOfIncidenceStructure(ag,10);
Error, <as> has no elements of type <j> called from
<function "unknown">( <arguments> )
 called from read-eval loop at line 15 of *stdin*
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue
brk> quit;
 

9.2-3 Short names for ElementsOfIncidenceStructure
‣ Points( ps )( operation )
‣ Lines( ps )( operation )
‣ Planes( ps )( operation )
‣ Solids( ps )( operation )
‣ Hyperplanes( ps )( operation )

Returns: The elements of ps of respective type 1, 2, 3, 4, and the hyperplanes

An error message is produced when the projective space ps has no elements of a required type.

gap> as := AG(5,4);
AG(5, 4)
gap> Points(as);
<points of AG(5, 4)>
gap> Lines(as);
<lines of AG(5, 4)>
gap> Planes(as);
<planes of AG(5, 4)>
gap> Solids(as);
<solids of AG(5, 4)>
gap> Hyperplanes(as);
<affine. subspaces of dim. 4 of AG(5, 4)>
gap> as := AG(2,8);
AG(2, 8)
gap> Hyperplanes(as);
<lines of AG(2, 8)>
 

9.2-4 Incidence and containment
‣ IsIncident( el1, el2 )( operation )
‣ \*( el1, el2 )( operation )
‣ \in( el1, el2 )( operation )

Returns: true or false

Recall that for affine spaces, incidence is symmetrized containment, where the whole affine space is excluded as one of the arguments for the operation IsIncident, since they it is not considered as an element of the geometry, but the whole affine space is allowed as one of the arguments for \in. The method for \* is using IsIncident.

gap> as := AG(3,16);
AG(3, 16)
gap> p := AffineSubspace(as,[1,0,0]*Z(16)^0);
<a point in AG(3, 16)>
gap> l := AffineSubspace(as,[1,0,0]*Z(16),[[0,1,1]]*Z(16)^0);
<a line in AG(3, 16)>
gap> plane := AffineSubspace(as,[1,0,0]*Z(16)^0,[[1,0,0],[0,1,1]]*Z(16)^0);
<a plane in AG(3, 16)>
gap> p in p;
true
gap> p in l;
false
gap> l in p;
false
gap> l in plane;
true
gap> plane in l;
false
gap> p in plane;
true
gap> p in as;
true
gap> l in as;
true
gap> plane in as;
true
gap> as in p;
false
gap> IsIncident(p,l);
false
gap> IsIncident(l,p);
false
gap> IsIncident(l,plane);
true
gap> IsIncident(plane,l);
true
gap> IsIncident(p,plane);
true
gap> IsIncident(plane,p);
true
 

9.2-5 AmbientSpace
‣ AmbientSpace( el )( operation )

Returns: returns the ambient space of an element el of an affine space

gap> as := AG(5,7);
AG(5, 7)
gap> solid := AffineSubspace(as,[1,0,0,1,0]*Z(7)^3,[[1,0,0,0,0],[0,1,1,1,0]]*Z(7)^0);
<a plane in AG(5, 7)>
gap> AmbientSpace(solid);
AG(5, 7)
 

9.2-6 BaseField
‣ BaseField( el )( operation )

Returns: returns the base field of an element el of an affine space

gap> as := AG(5,11);
AG(5, 11)
gap> sub := AffineSubspace(as,[1,4,3,1,0]*Z(11)^5,[[1,0,0,0,0],[0,1,1,1,0],
> [0,0,0,0,1]]*Z(11)^0);
<a solid in AG(5, 11)>
gap> BaseField(sub);
GF(11)
 

9.2-7 Span
‣ Span( u, v )( operation )

Returns: a subspace

u and v are subspaces of an affine space. This function returns the span of the two subspaces.

gap> ag := AffineSpace(4,5);
AG(4, 5)
gap> p := AffineSubspace(ag, [1,0,0,0] * One(GF(5)) );
<a point in AG(4, 5)>
gap> r := AffineSubspace(ag, [0,1,0,0] * One(GF(5)) );
<a point in AG(4, 5)>
gap> l := Span(p, r);
<a line in AG(4, 5)>
gap> l^_;
[ [ 0*Z(5), Z(5)^0, 0*Z(5), 0*Z(5) ], [ [ Z(5)^0, Z(5)^2, 0*Z(5), 0*Z(5) ] ] ]
gap> Display(l);
Affine line:
Coset representative: [ 0*Z(5), Z(5)^0, 0*Z(5), 0*Z(5) ]
Coset (direction): [ [ Z(5)^0, Z(5)^2, 0*Z(5), 0*Z(5) ] ]
 

9.2-8 Meet
‣ Meet( u, v )( operation )

Returns: an affine subspace or the empty list

u and v are subspaces of an affine space. This function returns the meet of the two subspaces. If the two subspaces are disjoint, then Meet returns the empty list.

gap> ag := AffineSpace(4,5);
AG(4, 5)
gap> p := AffineSubspace(ag, [1,0,0,0] * One(GF(5)), 
>        [[1,0,0,-1], [0,1,0,0],[0,0,1,3]] * One(GF(5)));
<a solid in AG(4, 5)>
gap> l := AffineSubspace(ag, [0,0,0,0] * One(GF(5)), [[1,1,0,0]] * One(GF(5)) );
<a line in AG(4, 5)>
gap> x := Meet(p, l);
<a point in AG(4, 5)>
gap> x^_;
[ Z(5)^0, Z(5)^0, 0*Z(5), 0*Z(5) ]
gap> Display(x);
Affine point:  1 1 . .
 

9.2-9 IsParallel
‣ IsParallel( u, v )( operation )

Returns: true or false

The arguments u and v must be affine subspaces of a common affine space. Two subspaces are parallel if and only if the direction space of the first is contained in the direction space of the second or viceversa.

gap> as := AffineSpace(3, 3);
AG(3, 3)
gap> l := AffineSubspace(as,[0,0,0]*Z(3)^0,[[1,0,0]]*Z(3)^0);
<a line in AG(3, 3)>
gap> m := AffineSubspace(as,[1,0,0]*Z(3)^0,[[1,0,0]]*Z(3)^0);
<a line in AG(3, 3)>
gap> n := AffineSubspace(as,[1,0,0]*Z(3)^0,[[0,1,0]]*Z(3)^0);
<a line in AG(3, 3)>
gap> IsParallel(l,m);
true
gap> IsParallel(m,n);
false
gap> IsParallel(l,n);
false
 

9.2-10 ParallelClass
‣ ParallelClass( as, v )( operation )
‣ ParallelClass( v )( operation )

Returns: a collection of affine subspaces

The argument v is an affine subspace of as. This operation returns a collection for which an iterator is installed. The collection represents the set of elements of as of the same type as v which are parallel to v; they have the same direction. If v is a point, then this operation returns the collection of all points of as. If one argument is given, then it is assumed that the affine space which we are working with is the ambient space of v.

gap> as := AffineSpace(3, 3);
AG(3, 3)
gap> l := Random( Lines( as ) );
<a line in AG(3, 3)>
gap> pclass := ParallelClass( l );
<parallel class of lines in AG(3, 3)>
gap> AsList(pclass);
[ <a line in AG(3, 3)>, <a line in AG(3, 3)>, <a line in AG(3, 3)>, 
  <a line in AG(3, 3)>, <a line in AG(3, 3)>, <a line in AG(3, 3)>, 
  <a line in AG(3, 3)>, <a line in AG(3, 3)>, <a line in AG(3, 3)> ]
 

9.3 Shadows of Affine Subspaces

9.3-1 ShadowOfElement
‣ ShadowOfElement( as, v, type )( operation )

Returns: the subspaces of the affine space as of dimension type which are incident with v

as is an affine space and v is an element of as. This operation computes and returns the subspaces of dimension type which are incident with v. In fact, this operation returns a collection which is only computed when iterated (e.g. when applying AsList to the collection). Some shorthand notation for ShadowOfElement is available for affine spaces: Points(as,v), Points(v), Lines(v), etc.

gap> as := AffineSpace(3, 3);
AG(3, 3)
gap> l := Random( Lines( as ) );
<a line in AG(3, 3)>
gap> planesonl := Planes(l);
<shadow planes in AG(3, 3)>
gap> AsList(planesonl);
[ <a plane in AG(3, 3)>, <a plane in AG(3, 3)>, <a plane in AG(3, 3)>, 
  <a plane in AG(3, 3)> ]
 

9.3-2 ShadowOfFlag
‣ ShadowOfFlag( as, list, type )( operation )

Returns: the subspaces of the affine space as of dimension type which are incident with each element of list

as is an affine space and list is a list of pairwise incident elements of as. This operation computes and returns the subspaces of dimension type which are incident with every element of list. In fact, this operation returns a collection which is only computed when iterated (e.g. when applying AsList to the collection).

gap> as := AffineSpace(3, 3);
AG(3, 3)
gap> l := Random( Lines( as ) );
<a line in AG(3, 3)>
gap> x := Random( Points( l ) );
<a point in AG(3, 3)>
gap> flag := FlagOfIncidenceStructure(as,[x,l]);
<a flag of AffineSpace(3, 3)>
gap> shadow := ShadowOfFlag( as, flag, 3 );
<shadow planes in AG(3, 3)>
gap> AsList(shadow);
Iterators of shadows of flags in affine spaces are not complete in this versio
n
[ <a plane in AG(3, 3)>, <a plane in AG(3, 3)>, <a plane in AG(3, 3)>, 
  <a plane in AG(3, 3)> ]
 

9.4 Iterators and enumerators

Recall from Section 4.4 ("Enumerating subspaces of a projective space", Chapter 4), that an iterator allows us to obtain elements from a collection one at a time in sequence, whereas an enumerator for a collection give us a way of picking out the i-th element. In FinInG we have enumerators and iterators for subspace collections of affine spaces.

9.4-1 Iterator
‣ Iterator( subs )( operation )

Returns: an iterator for the given subspaces collection

subs is a collection of subspaces of an affine space, such as Points( AffineSpace(3, 3) ).

gap> ag := AffineSpace(3, 3);
AG(3, 3)
gap> lines := Lines( ag );
<lines of AG(3, 3)>
gap> iter := Iterator( lines );
<iterator>
gap> l := NextIterator( iter );
<a line in AG(3, 3)>
 

9.4-2 Enumerator
‣ Enumerator( subs )( operation )

Returns: an enumerator for the given subspaces collection

subs is a collection of subspaces of an affine space, such as Points( AffineSpace(3, 3) ).

gap> ag := AffineSpace(3, 3);
AG(3, 3)
gap> lines := Lines( ag );
<lines of AG(3, 3)>
gap> enum := Enumerator( lines );
<enumerator of <lines of AG(3, 3)>>
gap> l := enum[20];
<a line in AG(3, 3)>
gap> Display(l);
Affine line:
Coset representative: [ 0*Z(3), 0*Z(3), Z(3)^0 ]
Coset (direction): [ [ Z(3)^0, 0*Z(3), Z(3) ] ]
 

9.5 Affine groups

A collineation of an affine space is a permutation of the points which preserves the relation of collinearity within the affine space. The fundamental theorem of affine geometry states that the group AΓL(n,q) of collineations of an affine space AG(n,q) is generated by the translations T, the matrices of GL(n,q) and the automorphisms of the field GF(q). The translations T form a normal subgroup of AΓL(n,q), and AΓL(n,q) is the semidirect product of T and ΓL(n,q).

Suppose we have an affine transformation of the form x+A where x is a vector representing a translation, and A is a matrix in GL(n,q) Then by using the natural embedding of AGL(n,q) in PGL(n+1,q), we can write this collineation as a matrix:

 
0
A 0
0
--- x --- 1
 

We can extend this idea to the full affine collineation group by adjoining the field automorphisms as we would for projective collineations. Here is an example:

gap> ag := AffineSpace(3,3);
AG(3, 3)
gap> g := AffineGroup(ag);
AGL(3,3)
gap> x:=Random(g);;
gap> Display(x);
<a collineation , underlying matrix:
 . 1 1 .
 2 2 . .
 2 1 . .
 1 2 1 1
, F^0>
 

Here we see that this affine transformation is

 
1 2 1
 
+
 
0 1 1
2 2 0
2 1 0
 

As we have seen, in FinInG, we represent an element of an affine collineation group as a projective semilinear element, i.e. as an object in the category ProjElsWithFrob, so that we can use all the functionality that exists for such objects. However, an affine collineation group (i.e. a group of collineations of the affine space AG(n,q) is not by default constructed as a subgroup of PΓL(n+1,q), but the compatibility between the elements of both groups enables testing for such relations.

gap> G := CollineationGroup(AG(3,27));
AGammaL(3,27)
gap> H := CollineationGroup(PG(3,27));
The FinInG collineation group PGammaL(4,27)
gap> g := Random(G);
< a collineation: [ [ Z(3^3)^25, Z(3^3)^11, Z(3^3)^23, 0*Z(3) ], 
  [ Z(3^3)^20, 0*Z(3), Z(3^3), 0*Z(3) ], 
  [ Z(3^3)^16, Z(3^3)^15, Z(3^3)^21, 0*Z(3) ], 
  [ Z(3^3)^20, Z(3^3)^4, 0*Z(3), Z(3)^0 ] ], F^3>
gap> g in H;
true
gap> IsSubgroup(H,G);
true
 

9.5-1 AffineGroup
‣ AffineGroup( as )( operation )

Returns: a group

If as is the affine space AG(n,q) This operation returnes the affine linear group AGL(n,q) acting on as. The elements of this group are projectivities of the associated projective space. In order to get the full group of collineations of the affine space, one needs to use the operation CollineationGroup.

gap> as := AffineSpace(4,7);
AG(4, 7)
gap> g := AffineGroup(as);
AGL(4,7)
gap> as := AffineSpace(4,8);
AG(4, 8)
gap> g := AffineGroup(as);
AGL(4,8)
 

9.5-2 CollineationGroup
‣ CollineationGroup( as )( operation )

Returns: a group

If as is the affine space AG(n,q), then this operation returns the affine semilinear group AΓL(n,q). The elements of this group are collineations of the associated projective space. Note that if the defining field has prime order, then the groups AΓL(n,q) and AGL(n,q) coincide.

gap> as := AffineSpace(4,8);
AG(4, 8)
gap> g := CollineationGroup(as);
AGammaL(4,8)
gap> h := AffineGroup(as);
AGL(4,8)
gap> IsSubgroup(g,h);
true
gap> as := AffineSpace(4,7);
AG(4, 7)
gap> g := CollineationGroup(as);
AGL(4,7)
 

9.5-3 OnAffineSpaces
‣ OnAffineSpaces( subspace, el )( operation )
‣ \^( subspace, el )( operation )

Returns: an element of an affine space

subspace must be an element of an affine space and el a collineation of an affine space (which is in fact also a collineation of an associated projective space). This is the action one should use for collineations of affine spaces, and it acts on subspaces of all types of affine spaces: points, lines, planes, etc.

gap> as := AG(3,27);
AG(3, 27)
gap> p := Random(Points(as));
<a point in AG(3, 27)>
gap> g := Random(CollineationGroup(as));
< a collineation: [ [ Z(3^3)^25, Z(3^3)^11, Z(3^3)^23, 0*Z(3) ], 
  [ Z(3^3)^20, 0*Z(3), Z(3^3), 0*Z(3) ], 
  [ Z(3^3)^16, Z(3^3)^15, Z(3^3)^21, 0*Z(3) ], 
  [ Z(3^3)^20, Z(3^3)^4, 0*Z(3), Z(3)^0 ] ], F^3>
gap> OnAffineSubspaces(p,g);
<a point in AG(3, 27)>
gap> p^g;
<a point in AG(3, 27)>
gap> l := Random(Lines(as));
<a line in AG(3, 27)>
gap> OnAffineSubspaces(l,g);
<a line in AG(3, 27)>
gap> l^g;
<a line in AG(3, 27)>
 

9.6 Low level operations

One technical aspect of the design behind affine spaces in FinInG is having canonical transversals for subspaces of vector spaces. We provide some documentation below for the interested user.

9.6-1 IsVectorSpaceTransversal
‣ IsVectorSpaceTransversal( filter )

The category IsVectorSpaceTransversal represents a special object in FinInG which carries a record with two components: space and subspace. This category is a subcategory of IsSubspacesOfVectorSpace, however, we do not recommend the user to apply methods to objects in IsVectorSpaceTransversal, which are normally used for the category IsSubspacesOfVectorSpace (they won't work!). The objects in IsVectorSpaceTransversal are only used in order to facilitate computing enumerators of subspace collections.

9.6-2 VectorSpaceTransversal
‣ VectorSpaceTransversal( space, mat )( operation )

Returns: a collection for representing a transversal of a subspaces of a vector space

space is a vector space V and mat is a matrix whose rows are a basis for a subspace U of V. A transversal for U in V is a set of coset representatives for the quotient V/U. This collection comes equipped with an enumerator operation.

9.6-3 VectorSpaceTransversalElement
‣ VectorSpaceTransversalElement( space, mat, vector )( operation )

Returns: a canonical coset representative

space is a vector space V, mat is a matrix whose rows are a basis for a subspace U of V, and vector is a vector v of V. A canonical representative v' is returned for the coset U+v.

9.6-4 ComplementSpace
‣ ComplementSpace( space, mat )( operation )

Returns: a collection for representing a transversal of a subspaces of a vector space

space is a vector space V and mat is a matrix whose rows are a basis for a subspace U of V. The operation is almost a complete copy of the function BaseSteinitzVector except that just a basis for the complement of U is returned instead of a full record.

 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 A B C Bib Ind

generated by GAPDoc2HTML