9 Vector Spaces

The material described in this chapter is subject to change.

Vector spaces form another important domain in GAP. They may be given in any representation whenever the underlying set of elements forms a vector space in terms of linear algebra. Thus, for example, one may construct a vector space by defining generating matrices over a field or by using the base of a field extension as generators. More complex constructions may fake elements of a vector space by specifying records with appropriate operations. A special type of vector space, that is implemented in the GAP library, handles the case where the elements Row Spaces for details).

General vector spaces are created using the function VectorSpace (see VectorSpace) and they are represented as records that contain all necessary information to deal with the vector space. The components listed in Vector Space Records are common for all vector spaces, but special types of vector spaces, such as the row spaces, may use additional entries to store specific data.

The following sections contain descriptions of functions and operations defined for vector spaces.

The next sections describe functions to compute a base (see Base) and the dimension (see Dimension) of a vector space over its field.

The next sections describe how to calculate linear combinations of the elements of a base (see LinearCombination) and how to find the coefficients of an element of a vector space when expressed as a linear combination in the current base (see Coefficients).

The functions described in this chapter are implemented in the file LIBNAME/"vecspace.g".

Subsections

  1. VectorSpace
  2. IsVectorSpace
  3. Vector Space Records
  4. Set Functions for Vector Spaces
  5. IsSubspace
  6. Base
  7. AddBase
  8. Dimension
  9. LinearCombination
  10. Coefficients

9.1 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) ]
     ] ) 

9.2 IsVectorSpace

IsVectorSpace( obj )

IsVectorSpace returns true if obj, which can be an object of arbitrary type, is a vector space and false otherwise.

9.3 Vector Space Records

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:

a list of elements generating the vector space V.

field:

the field over which the vector space V is written.

zero:

the zero element of the vector space.

isDomain:

always true, because vector spaces are domains.

isVectorSpace:

always true, for obvious reasons.

There are as well some optional components for a vector space record.

base:

a base for V, given as a list of elements of V.

dimension:

the dimension of V which is the length of a base of V.

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 ).

9.5 IsSubspace

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.

9.6 Base

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 

9.7 AddBase

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) ] ] ] 

9.8 Dimension

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 

9.9 LinearCombination

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) ] 

9.10 Coefficients

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) ] 

Previous Up Next
Index

GAP 3.4.4
April 1997