home *** CD-ROM | disk | FTP | other *** search
/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / doc / rowspace.tex < prev    next >
Encoding:
Text File  |  1993-05-05  |  5.7 KB  |  182 lines
  1. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  2. %%
  3. %A  rowspace.tex                GAP documentation              J\"urgen Mnich
  4. %%
  5. %A  @(#)$Id: rowspace.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 descriptions of the row space datatype, the operations
  10. %%  and functions for this type.
  11. %%
  12. %H  $Log: rowspace.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  1992/04/03  13:15:38  fceller
  17. %H  chnaged 'Shifted...' into 'Sifted...'
  18. %H
  19. %H  Revision 3.3  1992/04/02  21:06:23  martin
  20. %H  changed *domain functions* to *set theoretic functions*
  21. %H
  22. %H  Revision 3.2  1992/04/02  18:43:35  martin
  23. %H  added a note about future changes
  24. %H
  25. %H  Revision 3.1  1992/04/01  13:41:22  jmnich
  26. %H  fixed some references
  27. %H
  28. %H  Revision 3.0  1992/03/03  09:55:50  sam
  29. %H  Initial revision under RCS
  30. %H
  31. %%
  32. \Chapter{Row Spaces}
  33.  
  34. *The material described in this chapter is subject to change.*
  35.  
  36. Row spaces are a subcategory of vector spaces (see "Vector Spaces").
  37.  
  38. The  following  sections  describe  how  row  spaces   are  created  (see
  39. "RowSpace" ) and how factorspaces of row spaces are constructed (see "Row
  40. Space Operations").
  41.  
  42. The following sections describe the additional functions for factorspaces
  43. of row spaces.
  44.  
  45. The  functions  described in this  chapter  are implemented  in  the file
  46. 'LIBNAME/\"rowspace.g\"'.
  47.  
  48.  
  49. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  50. \Section{RowSpace}
  51.  
  52. 'RowSpace( <generators>, <field> )'
  53.  
  54. 'RowSpace' returns  the  row  space  that  is  generated  by  the vectors
  55. <generators> over  the field <field>. It is highly recommended  that  the
  56. elements in <generators> in fact are {\GAP} vectors.
  57.  
  58.  
  59. 'RowSpace( <generators>, <field>, <zero> )'
  60.  
  61. Whenever the list <generators> is empty,  this call of 'RowSpace'  has to
  62. be used. In that case the necessary components in the record representing
  63. the row space are set up using the third argument <zero> as well.
  64.  
  65.  
  66. 'RowSpace( <dimension>, <field> )'
  67.  
  68. The standard row space of dimension <dimension> over the field <field> is
  69. constructed  and  returned  when  using  this  version  of  the  call  to
  70. 'RowSpace'.  The elements of  the returned row space are all the lists of
  71. length <dimension> with entries in <field>.
  72.  
  73.  
  74. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  75. \Section{IsRowSpace}
  76.  
  77. 'IsRowSpace( <obj> )'
  78.  
  79. 'IsRowSpace' returns 'true' if <obj>, which can be an object of arbitrary
  80. type, is a row space and 'false' otherwise.
  81.  
  82.  
  83. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  84. \Section{Row Space Records}
  85.  
  86. In addition to  the record components described in "Vector Space Records"
  87. the following components may be present in the record of a row space <V>.
  88.  
  89. 'isRowSpace': \\
  90.         is always 'true'.
  91.  
  92.  
  93. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  94. \Section{Set Functions for Row Spaces}%
  95. \index{in!for row spaces}%
  96. \index{Intersection!for row spaces}
  97.  
  98. \vspace{5mm}
  99. '<v> in <V>'
  100.  
  101. Membership is tested using 'SiftedVector' (see
  102. "SiftedVector").
  103.  
  104.  
  105. \vspace{5mm}
  106. 'Intersection( <V>, <W> )'
  107.  
  108. The   intersection   of   two   row   spaces   is   computed  using   the
  109. Zassenhaus-algorithm, thus avoiding the generation of the set of elements
  110. of <V> and <W>.
  111.  
  112.  
  113. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  114. \Section{VectorSpace Functions for Row Spaces}
  115.  
  116. Row  spaces  are  a  special  type  of  vector spaces  for  which  better
  117. algorithms  may  be  known.  The  following  functions  differ  in  their
  118. implementation from their equivalent for general vector spaces.
  119.  
  120. 'Base( <V> )'
  121.  
  122. The base of a row space is determined with the Gauss algorithm (see "Base
  123. for Row Spaces").
  124.  
  125.  
  126. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  127. \Section{Base for Row Spaces}
  128.  
  129. 'RowSpaceOps.Base( <V> )'
  130.  
  131. If <V>  is  a  row  space,  a  base might  be  computed  using  the  full
  132. Gauss-algorithm  on  the  matrix  that  is built  row  by  row  from  the
  133. generators of <V>. The non-zero rows of the resulting  matrix form a base
  134. for <V>, which even is a canonical one.
  135.  
  136. 'RowSpaceOps.Base'  computes and returns such  a  base using the function
  137. 'BaseMat' (see "BaseMat").
  138.  
  139.  
  140. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  141. \Section{SiftedVector}
  142.  
  143. 'SiftedVector( <V>, <v> )'
  144.  
  145. 'SiftedVector' shifts  the given vector <v> through the base of <V> which
  146. is obtained using the function 'Base'.
  147.  
  148. For  the default  function 'RowSpaceOps.SiftedVector',  shifting a vector
  149. through  a  base  assumes  that  the  matrix of  that base  is  in  upper
  150. triangular form so that the entries at the heads of the base elements may
  151. successively be  extinguished  by subtracting an appropriate  multiple of
  152. the base vector.
  153.  
  154. 'RowSpaceOps.SiftedVector' returns the result of this process.
  155.  
  156. This function is used to decide whether a given vector <v> lies in  a row
  157. space <V>, as <v> lies in <V>, iff the residuum is equal to <V>.zero. The
  158. residuum is the result of the shifting process.
  159.  
  160.  
  161. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  162. \Section{Row Space Operations}
  163.  
  164. The following operator can be used for row spaces.
  165.  
  166. '<V> mod <W>'
  167.  
  168. 'mod' returns a record representing a factorspace, which can be used as an
  169. argument to some of the functions that are applicable for row spaces
  170. (see "Coefficients").
  171.  
  172.  
  173. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  174. %Emacs setup
  175. %E Local Variables:
  176. %E mode:           outline
  177. %E outline-regexp: "\\\\Chapter\\|\\\\Section\\|\\%Emacs"
  178. %E fill-column:    73
  179. %E eval:           (hide-body)
  180. %E End:
  181. %%
  182.