9 Vector Spaces

The material described in this chapter is subject to change.

Vector spaces form another important domain in GAP3. 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 GAP3 library, handles the case where the elements are lists over a field. This type is the so called `RowSpace` (see 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"`.

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 GAP3 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 GAP3 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 GAP3 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 GAP3 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 ```

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

gap3-jm
11 Mar 2019