%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %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( , )' Let be a list of objects generating a vector space over the 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( , , )' 'VectorSpace' returns the vector space generated by over the field having as the uniquely determined neutral element. This call of 'VectorSpace' always is requested if 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( )' 'IsVectorSpace' returns 'true' if , 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 . 'generators': \\ a list of elements generating the vector space . 'field': \\ the field over which the vector space 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 , given as a list of elements of . 'dimension': \\ the dimension of which is the length of a base of . %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \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( )' The elements of a vector space are computed by producing all linear combinations of the generators of . \vspace{5mm} 'Size( )' The size of a vector space is determined by calculating the dimension of and looking at the field over which it is written. \vspace{5mm} 'IsFinite( )' 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( , )' 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 as another way to write 'Intersection( , )'. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{IsSubspace} 'IsSubspace( , )' 'IsSubspace' tests whether the vector space is a subspace of . It returns 'true' if lies in and 'false' if it does not. The answer to the question is obtained by testing whether all the generators of lie in , so that, for the general case of vector space handling, a list of all the elements of is constructed. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Base}% \index{Base!of vector space} 'Base( )' 'Base' computes a base of the given vector space . The result is returned as a list of elements of the vector space . The base of a vector space is defined to be a minimal generating set. It can be shown that for a given vector space each base has the same number of elements, which is called the dimension of (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( , )' 'AddBase' attaches a user-supplied base for the vector space to the record that represents . 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 for by overwriting any other base of the vector space that has been installed before. So after 'AddBase' has successfully been used, will be used whenever 'Base' is called with as argument. Calling 'AddBase' with a which is not a base for 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( )' 'Dimension' computes the dimension of the given vector space over its field. The dimension of a vector space is defined to be the length of a minimal generating set of , which is called a base of (see "Base"). The implementation of 'Dimension' strictly follows its above definition, so that this function will always determine a base of . | 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( , )' 'LinearCombination' computes the linear combination of the base elements of the vector space with coefficients . has to be a list of elements of .field, the field over which the vector space is written. Its length must be equal to the dimension of to make sure that one coefficient is specified for each element of the base. 'LinearCombination' will use that base of which is returned when applying the function 'Base' to (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( , )' 'Coefficients' computes the coefficients that have to be used to write as a linear combination in the base of . To make sure that this function produces the correct result, has to be an element of . If does not lie in the result is unpredictable. The result of 'Coefficients' is returned as a list of elements of the field over which the vector space is written. Of course, the length of this list equals the dimension of . | 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: %%