%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%A  vecspace.tex                GAP documentation              J\"urgen Mnich
%%
%A  @(#)$Id: vecspace.tex,v 3.5 1993/02/19 10:48:42 gap Rel $
%%
%Y  Copyright 1990-1992,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
%%
%%  This file contains the description of the vector space record and
%%  polymorphic functions for vector spaces.
%%
%H  $Log: vecspace.tex,v $
%H  Revision 3.5  1993/02/19  10:48:42  gap
%H  adjustments in line length and spelling
%H
%H  Revision 3.4  1993/02/13  08:40:09  felsch
%H  examples adjusted to line length 72
%H
%H  Revision 3.3  1993/02/01  14:01:45  felsch
%H  examples fixed
%H
%H  Revision 3.2  1992/04/02  21:06:23  martin
%H  changed *domain functions* to *set theoretic functions*
%H
%H  Revision 3.1  1992/04/02  18:43:35  martin
%H  added a note about future changes
%H
%H  Revision 3.0  1992/03/03  09:53:52  sam
%H  Initial revision under RCS
%H
%%

\Chapter{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
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\"'.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{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) ) |

\vspace{5mm}
'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) ]
     ] ) |


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IsVectorSpace}

'IsVectorSpace( <obj> )'

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{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>.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Set Functions for Vector Spaces}%
\index{Elements!for vector spaces}%
\index{Size!of vector spaces}%
\index{IsFinite!for vector spaces}%
\index{Intersection!of 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.

\vspace{5mm}
'Elements( <V> )'

The elements of  a vector space <V> are computed  by producing all linear
combinations of the generators of <V>.

\vspace{5mm}
'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.

\vspace{5mm}
'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.

\vspace{5mm}
'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> )'.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{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.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Base}%
\index{Base!of vector space}

'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 |


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{AddBase}%
\index{AddBase!for vector space}

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Dimension}%
\index{Dimension!of vector space}

'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 |


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{LinearCombination}%
\index{LinearCombination!in vector space}

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Coefficients}%
\index{Coefficients!in vector space}

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Emacs setup
%E Local Variables:
%E mode:           outline
%E outline-regexp: "\\\\Chapter\\|\\\\Section\\|\\%Emacs"
%E fill-column:    73
%E eval:           (hide-body)
%E End:
%%
