home *** CD-ROM | disk | FTP | other *** search
/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / doc / vecspace.tex < prev    next >
Encoding:
Text File  |  1993-05-05  |  13.4 KB  |  381 lines
  1. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  2. %%
  3. %A  vecspace.tex                GAP documentation              J\"urgen Mnich
  4. %%
  5. %A  @(#)$Id: vecspace.tex,v 3.5 1993/02/19 10:48:42 gap Exp $
  6. %%
  7. %Y  Copyright 1990-1992,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
  8. %%
  9. %%  This file contains the description of the vector space record and
  10. %%  polymorphic functions for vector spaces.
  11. %%
  12. %H  $Log: vecspace.tex,v $
  13. %H  Revision 3.5  1993/02/19  10:48:42  gap
  14. %H  adjustments in line length and spelling
  15. %H
  16. %H  Revision 3.4  1993/02/13  08:40:09  felsch
  17. %H  examples adjusted to line length 72
  18. %H
  19. %H  Revision 3.3  1993/02/01  14:01:45  felsch
  20. %H  examples fixed
  21. %H
  22. %H  Revision 3.2  1992/04/02  21:06:23  martin
  23. %H  changed *domain functions* to *set theoretic functions*
  24. %H
  25. %H  Revision 3.1  1992/04/02  18:43:35  martin
  26. %H  added a note about future changes
  27. %H
  28. %H  Revision 3.0  1992/03/03  09:53:52  sam
  29. %H  Initial revision under RCS
  30. %H
  31. %%
  32.  
  33. \Chapter{Vector Spaces}
  34.  
  35. *The material described in this chapter is subject to change.*
  36.  
  37. Vector spaces form another important domain in  {\GAP}. They may be given
  38. in  any representation whenever  the  underlying  set of elements forms a
  39. vector  space in  terms of  linear  algebra. Thus, for  example, one  may
  40. construct  a vector space by defining generating matrices over a field or
  41. by using  the base  of a  field  extension  as  generators. More  complex
  42. constructions may  fake elements of a vector space  by specifying records
  43. with  appropriate operations.   A  special type of vector space,  that is
  44. implemented in  the {\GAP} library,  handles the case where  the elements
  45. are  lists over a field. This type is  the so called 'RowSpace' (see "Row
  46. Spaces" for details).
  47.  
  48. General  vector spaces  are created using the function 'VectorSpace' (see
  49. "VectorSpace")  and  they are  represented as  records  that contain  all
  50. necessary information to deal  with  the  vector  space.  The  components
  51. listed  in "Vector Space Records" are common for  all vector spaces,  but
  52. special  types  of  vector  spaces,  such  as  the  row  spaces, may  use
  53. additional entries to store specific data.
  54.  
  55. The following sections contain descriptions  of  functions and operations
  56. defined for vector spaces.
  57.  
  58. The next sections  describe functions to compute a base  (see "Base") and
  59. the dimension (see "Dimension") of a vector space over its field.
  60.  
  61. The  next sections describe  how to calculate linear combinations  of the
  62. elements  of  a  base  (see  "LinearCombination")  and how  to  find  the
  63. coefficients of  an element of a vector space when expressed  as a linear
  64. combination in the current base (see "Coefficients").
  65.  
  66. The functions described  in  this  chapter  are implemented  in the  file
  67. 'LIBNAME/\"vecspace.g\"'.
  68.  
  69.  
  70. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  71. \Section{VectorSpace}
  72.  
  73. 'VectorSpace( <generators>, <field> )'
  74.  
  75. Let <generators> be a list of objects generating a vector space  over the
  76. field <field>. Then 'VectorSpace'  returns this  vector space represented
  77. as a {\GAP} record.
  78.  
  79. |    gap> f := GF( 3^2 );
  80.     GF(3^2)
  81.     gap> m := [ [ f.one, f.one ], [ f.zero, f.zero ] ];
  82.     [ [ Z(3)^0, Z(3)^0 ], [ 0*Z(3), 0*Z(3) ] ]
  83.     gap> n := [ [ f.one, f.zero ], [ f.zero, f.one ] ];
  84.     [ [ Z(3)^0, 0*Z(3) ], [ 0*Z(3), Z(3)^0 ] ]
  85.     gap> VectorSpace( [ m, n ], f );
  86.     VectorSpace( [ [ [ Z(3)^0, Z(3)^0 ], [ 0*Z(3), 0*Z(3) ] ], 
  87.       [ [ Z(3)^0, 0*Z(3) ], [ 0*Z(3), Z(3)^0 ] ] ], GF(3^2) ) |
  88.  
  89. \vspace{5mm}
  90. 'VectorSpace( <generators>, <field>, <zero> )'
  91.  
  92. 'VectorSpace' returns the vector space generated by <generators> over the
  93. field <field> having <zero> as  the uniquely determined  neutral element.
  94. This call  of  'VectorSpace' always is  requested if <generators> is  the
  95. empty list.
  96.  
  97. |    gap> VectorSpace( [], f, [ [ f.zero, f.zero ], [ f.zero, f.zero ] ] );
  98.     VectorSpace( [  ], GF(3^2), [ [ 0*Z(3), 0*Z(3) ], [ 0*Z(3), 0*Z(3) ]
  99.      ] ) |
  100.  
  101.  
  102. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  103. \Section{IsVectorSpace}
  104.  
  105. 'IsVectorSpace( <obj> )'
  106.  
  107. 'IsVectorSpace' returns  'true'  if  <obj>, which  can  be  an object  of
  108. arbitrary type, is a vector space and 'false' otherwise.
  109.  
  110.  
  111. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  112. \Section{Vector Space Records}
  113.  
  114. A vector space is  represented as a {\GAP} record  having several entries
  115. to hold some necessary information about the vector space.
  116.  
  117. Basically  a  vector  space  record  is constructed  using  the  function
  118. 'VectorSpace' although one may create such a  record by hand. Furthermore
  119. vector  space records  may be  returned  by functions  described  here or
  120. somewhere else in this manual.
  121.  
  122. Once a vector space record is created you are free to add components, but
  123. you should never alter existing entries, especially 'generators', 'field'
  124. and 'zero'.
  125.  
  126. The following list  mentions  all components  that  are requested  for  a
  127. vector space <V>.
  128.  
  129. 'generators': \\
  130.         a list of elements generating the vector space <V>.
  131.  
  132. 'field': \\
  133.         the field over which the vector space <V> is written.
  134.  
  135. 'zero': \\
  136.         the zero element of the vector space.
  137.  
  138. 'isDomain': \\
  139.         always 'true', because vector spaces are domains.
  140.  
  141. 'isVectorSpace': \\
  142.         always 'true', for obvious reasons.
  143.  
  144.  
  145. There are as well some optional components for a vector space record.
  146.  
  147. 'base': \\
  148.         a base for <V>, given as a list of elements of <V>.
  149.  
  150. 'dimension': \\
  151.         the dimension of <V> which is the length of a base of <V>.
  152.  
  153.  
  154. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  155. \Section{Set Functions for Vector Spaces}%
  156. \index{Elements!for vector spaces}%
  157. \index{Size!of vector spaces}%
  158. \index{IsFinite!for vector spaces}%
  159. \index{Intersection!of vector spaces}
  160.  
  161. As  mentioned before,  vector spaces are  domains. So all  functions that
  162. exist for domains may  also be  applied to vector  spaces.  This  and the
  163. following chapters  give  further  information on  the implementation  of
  164. these  functions  for  vector  spaces, as far  as  they  differ in  their
  165. implementation from the general functions.
  166.  
  167. \vspace{5mm}
  168. 'Elements( <V> )'
  169.  
  170. The elements of  a vector space <V> are computed  by producing all linear
  171. combinations of the generators of <V>.
  172.  
  173. \vspace{5mm}
  174. 'Size( <V> )'
  175.  
  176. The size of a vector space <V> is determined by calculating the dimension
  177. of <V> and looking at the field over which it is written.
  178.  
  179. \vspace{5mm}
  180. 'IsFinite( <V> )'
  181.  
  182. A vector space in  {\GAP} is finite if it contains  only its zero element
  183. or if the field over which it is written is finite. This characterisation
  184. is true here, as in {\GAP} all vector spaces have a finite dimension.
  185.  
  186. \vspace{5mm}
  187. 'Intersection( <V>, <W> )'
  188.  
  189. The intersection of  vector  spaces is computed by finding a base for the
  190. intersection  of  the  sets  of  their  elements.  One  may consider  the
  191. algorithm  for finding a base of  a vector  space <V> as  another  way to
  192. write 'Intersection( <V>, <V> )'.
  193.  
  194.  
  195. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  196. \Section{IsSubspace}
  197.  
  198. 'IsSubspace( <V>, <W> )'
  199.  
  200. 'IsSubspace' tests whether the  vector space <W> is a subspace of <V>. It
  201. returns 'true' if <W> lies in <V> and 'false' if it does not.
  202.  
  203. The  answer to  the question  is  obtained by  testing  whether  all  the
  204. generators of <W> lie in <V>, so  that, for  the general  case of  vector
  205. space handling, a list of all the elements of <V> is constructed.
  206.  
  207.  
  208. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  209. \Section{Base}%
  210. \index{Base!of vector space}
  211.  
  212. 'Base( <V> )'
  213.  
  214. 'Base' computes  a  base  of the  given vector space <V>.  The  result is
  215. returned as a list of elements of the vector space <V>.
  216.  
  217. The base of a vector space is defined to be a minimal generating set.  It
  218. can be  shown  that for a given vector space  <V> each base has  the same
  219. number   of  elements,  which  is  called   the  dimension  of  <V>  (see
  220. "Dimension").
  221.  
  222. Unfortunately, no better algorithm  is known to compute a base in general
  223. than to browse  through the list of all elements  of the vector space. So
  224. be careful when using this command on plain vector spaces.
  225.  
  226. |    gap> f := GF(3);
  227.     GF(3)
  228.     gap> m1 := [[ f.one, f.one, f.zero, f.zero ]];
  229.     [ [ Z(3)^0, Z(3)^0, 0*Z(3), 0*Z(3) ] ]
  230.     gap> m2 := [[ f.one, f.one, f.one, f.zero ]]; 
  231.     [ [ Z(3)^0, Z(3)^0, Z(3)^0, 0*Z(3) ] ]
  232.     gap> V := VectorSpace( [ m1, m2, m1+m2 ], GF(3) );
  233.     VectorSpace( [ [ [ Z(3)^0, Z(3)^0, 0*Z(3), 0*Z(3) ] ], 
  234.       [ [ Z(3)^0, Z(3)^0, Z(3)^0, 0*Z(3) ] ], 
  235.       [ [ Z(3), Z(3), Z(3)^0, 0*Z(3) ] ] ], GF(3) )
  236.     gap> Base( V );
  237.     [ [ [ Z(3)^0, Z(3)^0, 0*Z(3), 0*Z(3) ] ], 
  238.       [ [ Z(3)^0, Z(3)^0, Z(3)^0, 0*Z(3) ] ] ]
  239.     gap> Dimension( V );
  240.     2 |
  241.  
  242.  
  243. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  244. \Section{AddBase}%
  245. \index{AddBase!for vector space}
  246.  
  247. 'AddBase( <V>, <base> )'
  248.  
  249. 'AddBase' attaches a  user-supplied base for the  vector space <V> to the
  250. record that represents <V>.
  251.  
  252. Most  of  the  functions  for  vector  spaces make  use of  a  base  (see
  253. "LinearCombination", "Coefficients"). These  functions  get  access to  a
  254. base using  the function 'Base', which  normally computes a base for  the
  255. vector  space using an appropriate algorithm.  Once a base is computed it
  256. will always be reused, no matter whether there is a more interesting base
  257. available or not.
  258.  
  259. 'AddBase' installs a given  <base> for  <V> by overwriting any other base
  260. of the  vector space that has been installed  before.  So after 'AddBase'
  261. has successfully been used, <base> will be used whenever 'Base' is called
  262. with <V> as argument.
  263.  
  264. Calling 'AddBase' with a <base> which is not a base for <V> might produce
  265. unpredictable results in following computations.
  266.  
  267. |    gap> f := GF(3);
  268.     GF(3)
  269.     gap> m1 := [[ f.one, f.one, f.zero, f.zero ]];
  270.     [ [ Z(3)^0, Z(3)^0, 0*Z(3), 0*Z(3) ] ]
  271.     gap> m2 := [[ f.one, f.one, f.one, f.zero ]]; 
  272.     [ [ Z(3)^0, Z(3)^0, Z(3)^0, 0*Z(3) ] ]
  273.     gap> V := VectorSpace( [ m1, m2, m1+m2 ], GF(3) );
  274.     VectorSpace( [ [ [ Z(3)^0, Z(3)^0, 0*Z(3), 0*Z(3) ] ], 
  275.       [ [ Z(3)^0, Z(3)^0, Z(3)^0, 0*Z(3) ] ], 
  276.       [ [ Z(3), Z(3), Z(3)^0, 0*Z(3) ] ] ], GF(3) )
  277.     gap> Base( V );
  278.     [ [ [ Z(3)^0, Z(3)^0, 0*Z(3), 0*Z(3) ] ], 
  279.       [ [ Z(3)^0, Z(3)^0, Z(3)^0, 0*Z(3) ] ] ]
  280.     gap> AddBase( V, [ m1, m1+m2 ] );
  281.     gap> Base( V );
  282.     [ [ [ Z(3)^0, Z(3)^0, 0*Z(3), 0*Z(3) ] ], 
  283.       [ [ Z(3), Z(3), Z(3)^0, 0*Z(3) ] ] ] |
  284.  
  285.  
  286. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  287. \Section{Dimension}%
  288. \index{Dimension!of vector space}
  289.  
  290. 'Dimension( <V> )'
  291.  
  292. 'Dimension' computes the dimension of the given vector space <V> over its
  293. field.
  294.  
  295. The dimension of  a vector space <V> is defined to  be  the length  of  a
  296. minimal generating set  of <V>,  which  is  called  a  base  of  <V> (see
  297. "Base").
  298.  
  299. The implementation of 'Dimension' strictly  follows its above definition,
  300. so that this function will always determine a base of <V>.
  301.  
  302. |    gap> f := GF( 3^4 );
  303.     GF(3^4)
  304.     gap> f.base;
  305.     [ Z(3)^0, Z(3^4), Z(3^4)^2, Z(3^4)^3 ]
  306.     gap> V := VectorSpace( f.base, GF( 3 ) );
  307.     VectorSpace( [ Z(3)^0, Z(3^4), Z(3^4)^2, Z(3^4)^3 ], GF(3) )
  308.     gap> Dimension( V );
  309.     4 |
  310.  
  311.  
  312. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  313. \Section{LinearCombination}%
  314. \index{LinearCombination!in vector space}
  315.  
  316. 'LinearCombination( <V>, <cf> )'
  317.  
  318. 'LinearCombination' computes the linear combination  of the base elements
  319. of the vector space <V> with coefficients <cf>.
  320.  
  321. <cf> has to  be a list of elements of <V>.field, the field over which the
  322. vector space is written. Its length must be equal to the dimension of <V>
  323. to make sure that one coefficient is  specified  for each element  of the
  324. base.
  325.  
  326. 'LinearCombination'  will use that base  of  <V> which  is returned  when
  327. applying  the function  'Base' to  <V>  (see  "Base"). To  perform linear
  328. combinations  of different  bases use  'AddBase'  to  specify  which base
  329. should be used (see "AddBase").
  330.  
  331. |    gap> f := GF( 3^4 );
  332.     GF(3^4)
  333.     gap> f.base;
  334.     [ Z(3)^0, Z(3^4), Z(3^4)^2, Z(3^4)^3 ]
  335.     gap> V := VectorSpace( f.base, GF( 3 ) );
  336.     VectorSpace( [ Z(3)^0, Z(3^4), Z(3^4)^2, Z(3^4)^3 ], GF(3) )
  337.     gap> LinearCombination( V, [ Z(3), Z(3)^0, Z(3), 0*Z(3) ] );
  338.     Z(3^4)^16
  339.     gap> Coefficients( V, f.root ^ 16 );
  340.     [ Z(3), Z(3)^0, Z(3), 0*Z(3) ] |
  341.  
  342.  
  343. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  344. \Section{Coefficients}%
  345. \index{Coefficients!in vector space}
  346.  
  347. 'Coefficients( <V>, <v> )'
  348.  
  349. 'Coefficients' computes the coefficients that  have to  be used  to write
  350. <v> as a linear combination in the base of <V>.
  351.  
  352. To make sure that this function produces the  correct result, <v>  has to
  353. be  an  element  of  <V>. If  <v>  does not  lie in  <V>  the  result  is
  354. unpredictable.
  355.  
  356. The  result  of  'Coefficients'  is returned as a list of elements of the
  357. field  over which the vector space <V> is written. Of course,  the length
  358. of this list equals the dimension of <V>.
  359.  
  360. |    gap> f := GF( 3^4 );
  361.     GF(3^4)
  362.     gap> f.base;
  363.     [ Z(3)^0, Z(3^4), Z(3^4)^2, Z(3^4)^3 ]
  364.     gap> V := VectorSpace( f.base, GF( 3 ) );
  365.     VectorSpace( [ Z(3)^0, Z(3^4), Z(3^4)^2, Z(3^4)^3 ], GF(3) )
  366.     gap> Dimension( V );
  367.     4
  368.     gap> Coefficients( V, f.root ^ 16 );
  369.     [ Z(3), Z(3)^0, Z(3), 0*Z(3) ] |
  370.  
  371.  
  372. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  373. %Emacs setup
  374. %E Local Variables:
  375. %E mode:           outline
  376. %E outline-regexp: "\\\\Chapter\\|\\\\Section\\|\\%Emacs"
  377. %E fill-column:    73
  378. %E eval:           (hide-body)
  379. %E End:
  380. %%
  381.