One of the most fundamental datatypes in every programming language is the integer type. GAP is no exception.
GAP integers are entered as a sequence of digits optionally preceded
by a + sign for positive integers or a - sign for negative integers.
The size of integers in GAP is only limited by the amount of available
memory, so you can compute with integers having thousands of digits.
gap> -1234;
-1234
gap> 123456789012345678901234567890123456789012345678901234567890;
123456789012345678901234567890123456789012345678901234567890
The first sections in this chapter describe the operations applicable to integers (see Comparisons of Integers, Operations for Integers, QuoInt and RemInt).
The next sections describe the functions that test whether an object is an integer (see IsInt) and convert objects of various types to integers (see Int).
The next sections describe functions related to the ordering of integers (see AbsInt, SignInt).
The next section describes the function that computes a Chinese remainder (see ChineseRem).
The next sections describe the functions related to the ordering of integers, logarithms, and roots (LogInt, RootInt, SmallestRootInt).
The GAP object Integers is the ring domain of all integers. So all
set theoretic functions are also applicable to this domain (see chapter
Domains and Set Functions for Integers). The only serious use of
this however seems to be the generation of random integers.
Since the integers form a Euclidean ring all the ring functions are Ring Functions for Integers, Primes, IsPrimeInt, IsPrimePowerInt, NextPrimeInt, PrevPrimeInt, FactorsInt, DivisorsInt, Sigma, Tau, and MoebiusMu).
Since the integers are naturally embedded in the field of rationals all the field functions are applicable to integers (see chapter Fields and Field Functions for Rationals).
Many more functions that are mainly related to the prime residue group of integers modulo an integer are described in chapter VectorSpace
VectorSpace( generators, field )
Let generators be a list of objects generating a vector space over the
field field. Then VectorSpace returns this vector space represented
as a GAP record.
gap> f := GF( 3^2 );
GF(3^2)
gap> m := [ [ f.one, f.one ], [ f.zero, f.zero ] ];
[ [ Z(3)^0, Z(3)^0 ], [ 0*Z(3), 0*Z(3) ] ]
gap> n := [ [ f.one, f.zero ], [ f.zero, f.one ] ];
[ [ Z(3)^0, 0*Z(3) ], [ 0*Z(3), Z(3)^0 ] ]
gap> VectorSpace( [ m, n ], f );
VectorSpace( [ [ [ Z(3)^0, Z(3)^0 ], [ 0*Z(3), 0*Z(3) ] ],
[ [ Z(3)^0, 0*Z(3) ], [ 0*Z(3), Z(3)^0 ] ] ], GF(3^2) )
VectorSpace( generators, field, zero )
VectorSpace returns the vector space generated by generators over the
field field having zero as the uniquely determined neutral element.
This call of VectorSpace always is requested if generators is the
empty list.
gap> VectorSpace( [], f, [ [ f.zero, f.zero ], [ f.zero, f.zero ] ] );
VectorSpace( [ ], GF(3^2), [ [ 0*Z(3), 0*Z(3) ], [ 0*Z(3), 0*Z(3) ]
] )
IsVectorSpace( obj )
IsVectorSpace returns true if obj, which can be an object of
arbitrary type, is a vector space and false otherwise.
A vector space is represented as a GAP record having several entries to hold some necessary information about the vector space.
Basically a vector space record is constructed using the function
VectorSpace although one may create such a record by hand. Furthermore
vector space records may be returned by functions described here or
somewhere else in this manual.
Once a vector space record is created you are free to add components, but
you should never alter existing entries, especially generators, field
and zero.
The following list mentions all components that are requested for a vector space V.
generators:
field:
zero:
isDomain:true, because vector spaces are domains.
isVectorSpace:true, for obvious reasons.
There are as well some optional components for a vector space record.
base:
dimension:
9.4 Set Functions for Vector Spaces
As mentioned before, vector spaces are domains. So all functions that exist for domains may also be applied to vector spaces. This and the following chapters give further information on the implementation of these functions for vector spaces, as far as they differ in their implementation from the general functions.
Elements( V )
The elements of a vector space V are computed by producing all linear combinations of the generators of V.
Size( V )
The size of a vector space V is determined by calculating the dimension of V and looking at the field over which it is written.
IsFinite( V )
A vector space in GAP is finite if it contains only its zero element or if the field over which it is written is finite. This characterisation is true here, as in GAP all vector spaces have a finite dimension.
Intersection( V, W )
The intersection of vector spaces is computed by finding a base for the
intersection of the sets of their elements. One may consider the
algorithm for finding a base of a vector space V as another way to
write Intersection( V, V ).
IsSubspace( V, W )
IsSubspace tests whether the vector space W is a subspace of V. It
returns true if W lies in V and false if it does not.
The answer to the question is obtained by testing whether all the generators of W lie in V, so that, for the general case of vector space handling, a list of all the elements of V is constructed.
Base( V )
Base computes a base of the given vector space V. The result is
returned as a list of elements of the vector space V.
The base of a vector space is defined to be a minimal generating set. It can be shown that for a given vector space V each base has the same number of elements, which is called the dimension of V (see Dimension).
Unfortunately, no better algorithm is known to compute a base in general than to browse through the list of all elements of the vector space. So be careful when using this command on plain vector spaces.
gap> f := GF(3);
GF(3)
gap> m1 := [[ f.one, f.one, f.zero, f.zero ]];
[ [ Z(3)^0, Z(3)^0, 0*Z(3), 0*Z(3) ] ]
gap> m2 := [[ f.one, f.one, f.one, f.zero ]];
[ [ Z(3)^0, Z(3)^0, Z(3)^0, 0*Z(3) ] ]
gap> V := VectorSpace( [ m1, m2, m1+m2 ], GF(3) );
VectorSpace( [ [ [ Z(3)^0, Z(3)^0, 0*Z(3), 0*Z(3) ] ],
[ [ Z(3)^0, Z(3)^0, Z(3)^0, 0*Z(3) ] ],
[ [ Z(3), Z(3), Z(3)^0, 0*Z(3) ] ] ], GF(3) )
gap> Base( V );
[ [ [ Z(3)^0, Z(3)^0, 0*Z(3), 0*Z(3) ] ],
[ [ Z(3)^0, Z(3)^0, Z(3)^0, 0*Z(3) ] ] ]
gap> Dimension( V );
2
AddBase( V, base )
AddBase attaches a user-supplied base for the vector space V to the
record that represents V.
Most of the functions for vector spaces make use of a base (see
LinearCombination, Coefficients). These functions get access to a
base using the function Base, which normally computes a base for the
vector space using an appropriate algorithm. Once a base is computed it
will always be reused, no matter whether there is a more interesting base
available or not.
AddBase installs a given base for V by overwriting any other base
of the vector space that has been installed before. So after AddBase
has successfully been used, base will be used whenever Base is called
with V as argument.
Calling AddBase with a base which is not a base for V might produce
unpredictable results in following computations.
gap> f := GF(3);
GF(3)
gap> m1 := [[ f.one, f.one, f.zero, f.zero ]];
[ [ Z(3)^0, Z(3)^0, 0*Z(3), 0*Z(3) ] ]
gap> m2 := [[ f.one, f.one, f.one, f.zero ]];
[ [ Z(3)^0, Z(3)^0, Z(3)^0, 0*Z(3) ] ]
gap> V := VectorSpace( [ m1, m2, m1+m2 ], GF(3) );
VectorSpace( [ [ [ Z(3)^0, Z(3)^0, 0*Z(3), 0*Z(3) ] ],
[ [ Z(3)^0, Z(3)^0, Z(3)^0, 0*Z(3) ] ],
[ [ Z(3), Z(3), Z(3)^0, 0*Z(3) ] ] ], GF(3) )
gap> Base( V );
[ [ [ Z(3)^0, Z(3)^0, 0*Z(3), 0*Z(3) ] ],
[ [ Z(3)^0, Z(3)^0, Z(3)^0, 0*Z(3) ] ] ]
gap> AddBase( V, [ m1, m1+m2 ] );
gap> Base( V );
[ [ [ Z(3)^0, Z(3)^0, 0*Z(3), 0*Z(3) ] ],
[ [ Z(3), Z(3), Z(3)^0, 0*Z(3) ] ] ]
Dimension( V )
Dimension computes the dimension of the given vector space V over its
field.
The dimension of a vector space V is defined to be the length of a minimal generating set of V, which is called a base of V (see Base).
The implementation of Dimension strictly follows its above definition,
so that this function will always determine a base of V.
gap> f := GF( 3^4 );
GF(3^4)
gap> f.base;
[ Z(3)^0, Z(3^4), Z(3^4)^2, Z(3^4)^3 ]
gap> V := VectorSpace( f.base, GF( 3 ) );
VectorSpace( [ Z(3)^0, Z(3^4), Z(3^4)^2, Z(3^4)^3 ], GF(3) )
gap> Dimension( V );
4
LinearCombination( V, cf )
LinearCombination computes the linear combination of the base elements
of the vector space V with coefficients cf.
cf has to be a list of elements of V.field, the field over which the vector space is written. Its length must be equal to the dimension of V to make sure that one coefficient is specified for each element of the base.
LinearCombination will use that base of V which is returned when
applying the function Base to V (see Base). To perform linear
combinations of different bases use AddBase to specify which base
should be used (see AddBase).
gap> f := GF( 3^4 );
GF(3^4)
gap> f.base;
[ Z(3)^0, Z(3^4), Z(3^4)^2, Z(3^4)^3 ]
gap> V := VectorSpace( f.base, GF( 3 ) );
VectorSpace( [ Z(3)^0, Z(3^4), Z(3^4)^2, Z(3^4)^3 ], GF(3) )
gap> LinearCombination( V, [ Z(3), Z(3)^0, Z(3), 0*Z(3) ] );
Z(3^4)^16
gap> Coefficients( V, f.root ^ 16 );
[ Z(3), Z(3)^0, Z(3), 0*Z(3) ]
Coefficients( V, v )
Coefficients computes the coefficients that have to be used to write
v as a linear combination in the base of V.
To make sure that this function produces the correct result, v has to be an element of V. If v does not lie in V the result is unpredictable.
The result of Coefficients is returned as a list of elements of the
field over which the vector space V is written. Of course, the length
of this list equals the dimension of V.
gap> f := GF( 3^4 );
GF(3^4)
gap> f.base;
[ Z(3)^0, Z(3^4), Z(3^4)^2, Z(3^4)^3 ]
gap> V := VectorSpace( f.base, GF( 3 ) );
VectorSpace( [ Z(3)^0, Z(3^4), Z(3^4)^2, Z(3^4)^3 ], GF(3) )
gap> Dimension( V );
4
gap> Coefficients( V, f.root ^ 16 );
[ Z(3), Z(3)^0, Z(3), 0*Z(3) ]
GAP 3.4.4