10 General Functions
  
  Some  of  the  functions  provided by HAPprime are not specifically aimed at
  homological  algebra  or  extending  the  HAP package. The functions in this
  chapter,  which  are used internally by HAPprime extend some of the standard
  GAP functions and datatypes.
  
  
  10.1 Matrices
  
  For  details of the standard GAP vector and matrix functions, see 'Tutorial:
  matrices'  and  'Reference:  Matrices'  in  the  GAP  tutorial and reference
  manuals.  HAPprime provides improved versions of a couple of standard matrix
  operations, and two small helper functions.
  
  10.1-1 SumIntersectionMatDestructive
  
  > SumIntersectionMatDestructive( U, V ) ___________________________operation
  > SumIntersectionMatDestructiveSE( Ubasis, Uheads, Vbasis, Vheads ) operation
  
  Returns  a  list  of  length  2  with, at the first position, the sum of the
  vector spaces generated by the rows of U and V, and, at the second position,
  the intersection of the spaces.
  
  Like     the    GAP    core    function    SumIntersectionMat    (Reference:
  SumIntersectionMat),  this  performs  Zassenhaus' algorithm to compute bases
  for the sum and the intersection. However, this version operates directly on
  the  input matrices (thus corrupting them), and is rewritten to require only
  approximately  1.5  times  the  space  of  the  original  input matrices. By
  contrast,  the  original  GAP  version  uses  three  times the memory of the
  original  matrices  to  perform the calculation, and since it doesn't modify
  the  input  matrices  will  require  a  total of four times the space of the
  original matrices.
  
  The  function  SumIntersectionMatDestructiveSE takes as arguments not a pair
  of  generating  matrices,  but a pair of semi-echelon basis matrices and the
  corresponding   head   locations,   such   as  is  returned  by  a  call  to
  SemiEchelonMatDestructive   (Reference:   SemiEchelonMatDestructive)  (these
  arguments must all be mutable, so SemiEchelonMat (Reference: SemiEchelonMat)
  cannot    be    used).    This    function    is    used    internally    by
  SumIntersectionMatDestructive,  and  is  provided for the occasions when the
  user might already have the semi-echelon versions available, in which case a
  small amount of time will be saved.
  
  10.1-2 SolutionMat
  
  > SolutionMat( M, V ) _____________________________________________operation
  > SolutionMatDestructive( M, V ) __________________________________operation
  
  Calculates, for each row vector v_i in the matrix V, a solution to x_i x M =
  v_i,  and  returns these solutions in a matrix X, whose rows are the vectors
  x_i.  If  there  is not a solution for a v_i, then fail is returned for that
  row.
  
  These   functions   are   identical  to  the  kernel  functions  SolutionMat
  (Reference:     SolutionMat)    and    SolutionMatDestructive    (Reference:
  SolutionMatDestructive), but are provided for cases where multiple solutions
  using the same matrix M are required. In these cases, using this function is
  far faster, since the matrix is only decomposed once.
  
  The  Destructive  version  corrupts  both  the  input  matrices,  while  the
  non-Destructive version operates on copies of these.
  
  10.1-3 IsSameSubspace
  
  > IsSameSubspace( U, V ) __________________________________________operation
  
  Returns  true  if the subspaces spanned by the rows of U and V are the same,
  false otherwise.
  
  This  function  treats the rows of the two matrices as vectors from the same
  vector  space  (with the same basis), and tests whether the subspace spanned
  by the two sets of vectors is the same.
  
  10.1-4 PrintDimensionsMat
  
  > PrintDimensionsMat( M ) _________________________________________operation
  
  Returns  a  string  containing  the  dimensions  of the matrix M in the form
  "mxn",  where  m  is  the number of rows and n the number of columns. If the
  matrix is empty, the returned string is "empty".
  
  
  10.1-5 Example: matrices and vector spaces
  
  GAP  uses rows of a matrix to represent basis vectors for a vector space. In
  this  example we have two matrics U and V that we suspect represent the same
  subspace.  Using  SolutionMat  (10.1-2)  we  can  see  that V lies in U, but
  IsSameSubspace  (10.1-3)  shows  that  they  are  the  same  subspace, as is
  confirmed by having identical sums and intersections.
  
  ---------------------------  Example  ----------------------------
    gap> U := [[1,2,3],[4,5,6]];;
    gap> V := [[3,3,3],[5,7,9]];;
    gap> SolutionMat(U, V);
    [ [ -1, 1 ], [ 1, 1 ] ]
    gap> IsSameSubspace(U, V);
    true
    gap> SumIntersectionMatDestructive(U, V);
    [ [ [ 1, 2, 3 ], [ 0, 1, 2 ] ], [ [ 0, 1, 2 ], [ 1, 0, -1 ] ] ]
    gap> IsSameSubspace(last[1], last[2]);
    true
    gap> PrintDimensionsMat(V);
    "2x3"
  ------------------------------------------------------------------
  
  
  10.2 Polynomials
  
  GAP  provides  some  functions  for  manipulating polynomials and polynomial
  ideals  -  see 'Reference: Polynomials and Rational Functions'. The HAPprime
  packages  adds  further  functions  to  decompose polynomials into terms and
  monomials, and some functions for tidying up polynomial ideals.
  
  10.2-1 TermsOfPolynomial
  
  > TermsOfPolynomial( poly ) _______________________________________attribute
  Returns:  List of pairs
  
  Returns  a list of the terms in the polynomial. This list is a list of pairs
  of  the  form  [mon,  coeff]  where  mon  is  a  monomial  and  coeff is the
  coefficient  of  that  monomial  in the polynomial. The monomials are sorted
  according  to  the  total  degree/lexicographic  order  (the  same as the in
  MonomialGrLexOrdering (Reference: MonomialGrlexOrdering)).
  
  10.2-2 IsMonomial
  
  > IsMonomial( poly ) ______________________________________________attribute
  Returns:  Boolean
  
  Returns  true  if  poly is a monomial, i.e. the polynomial contains only one
  term.
  
  10.2-3 UnivariateMonomialsOfMonomial
  
  > UnivariateMonomialsOfMonomial( mon ) ____________________________attribute
  Returns:  List
  
  Returns  a  list  of  the  univariate  monomials  of the largest order whose
  product  equals  mon. The univariate monomials are sorted according to their
  indeterminate number.
  
  10.2-4 IndeterminateAndExponentOfUnivariateMonomial
  
  > IndeterminateAndExponentOfUnivariateMonomial( mon ) _____________attribute
  Returns:  List
  
  Returns  a  list  [indet,  exp]  where  indet  is  the  indeterminate of the
  univariate monomial mon and exp is the exponent of that indeterminate in the
  monomial.  If  mon  is an element in the coefficient ring (i.e. the monomial
  contains  no  indeterminates)  then  the  first  element will be mon with an
  exponent  of  zero.  If  mon  is  not  a  univariate  monomial, then fail is
  returned.
  
  10.2-5 IndeterminatesOfPolynomial
  
  > IndeterminatesOfPolynomial( poly ) ______________________________attribute
  Returns:  List
  
  Returns a list of the indeterminates used in the polynomial poly.
  
  
  10.2-6 ReduceIdeal
  
  > ReduceIdeal( I, O ) _____________________________________________operation
  > ReduceIdeal( rels, O ) __________________________________________operation
  Returns:  Ideal or list
  
  For  an ideal I returns an ideal containing a reduced generating set for the
  ideal,  i.e. one in which no monomial in a relation in I is divisible by the
  leading term of another polynomial in I. The monomial ordering to be used is
  specified  by O (see 'Reference: Monomial Orderings'). The ideal can instead
  be  specified  by  a list of relations rels, in which case a reduced list of
  relations is returned.
  
  10.2-7 ReducedPolynomialRingPresentation
  
  > ReducedPolynomialRingPresentation( R, I[, avoid] ) ______________operation
  > ReducedPolynomialRingPresentationMap( R, I[, avoid] ) ___________operation
  Returns:  List
  
  For  a  polynomial  ring R and a list of relations I in that ring, returns a
  list  [S, J] representing a polynomial quotient ring S/J which is isomorphic
  to   the   ring   R/I,  but  which  involves  the  minimal  number  of  ring
  indeterminates.  The  indeterminates  in S will be distinct from thise in R,
  and  an  optional  argument  avoid  can  be  used  to give a list of further
  indeterminates to avoid when creating the ring S.
  
  The extended version of this function, ReducedPolynomialRingPresentationMap,
  returns  an  additional  third element to the list, which contains two lists
  giving  the  mapping  between  the  new ring indeterminates and the old ring
  indeterminates.   The   first   list  is  of  polynomials  in  the  original
  indeterminates,  the  second  the  equivalent  polynomials  in  the new ring
  indeterminates.
  
  
  10.2-8 Example: monomials, polynomials and ring presentations
  
  A  monomial is some product of ring indeterminates. A polynomial is a sum of
  monomials, where each monomial may also be multiplied by an element from the
  field  of  the  polynomial.  It  can  be  useful to decompose polynomials as
  follows:
  
  --    decompose  a  polynomial  into its individual terms (where a term is a
        product   of   a   monomial   and   a  field  element).  The  function
        TermsOfPolynomial (10.2-1) does this.
  
  --    decompose  a monomial into its component univariate monomials, each of
        which  is  some  (power of) a single indeterminates. This operation is
        performed by UnivariateMonomialsOfMonomial (10.2-3).
  
  --    decompose  a  univariate  monomial  into  it  the  indeterminates  and
        exponent (IndeterminateAndExponentOfUnivariateMonomial (10.2-4)).
  
  In the example below, we decompose x + xy^2 + 3y^3 into its three terms, and
  then further decompose the xy^2 term.
  
  ---------------------------  Example  ----------------------------
    gap> R := PolynomialRing(Integers, 2);;
    gap> x := R.1;; y := R.2;;
    gap> poly := x + x*y^2 + 3*y^3;
    x_1*x_2^2+3*x_2^3+x_1
    gap> terms := TermsOfPolynomial(poly);
    [ [ x_1, 1 ], [ x_2^3, 3 ], [ x_1*x_2^2, 1 ] ]
    gap> UnivariateMonomialsOfMonomial(terms[3][1]);
    [ x_1, x_2^2 ]
    gap> IndeterminateAndExponentOfUnivariateMonomial(last[2]);
    [ x_2, 2 ]
  ------------------------------------------------------------------
  
  HAPprime  also  provides  some  functions  to  help  the  generation of ring
  presentations.  In  the  following  example  we consider the polynomial ring
  Z[w,x,y,z]  an  an  ideal  I = < w^2 + x, w^3 + x^3 >. We first convert this
  ideal  into  reduced form (where no monomial in a polynomial is divisible by
  the  leading term of any other polynomial). Then we calculate a reduced ring
  presentation for the quotient ring R/I, where we find that the indeterminate
  x  is can be removed and a new ring S/J = Z[w,y,z]/< w^6-w^3 > is isomorphic
  to R/I
  
  ---------------------------  Example  ----------------------------
    gap> R := PolynomialRing(Integers, 4);;
    gap> w := R.1;; x := R.2;;
    gap> I := [w^2 + x, w^3 + x^3];
    [ x_1^2+x_2, x_1^3+x_2^3 ]
    gap> ReduceIdeal(I, MonomialLexOrdering());
    [ x_1^2+x_2, -x_2^3+x_1*x_2 ]
    gap> 
    gap> ReducedPolynomialRingPresentation(R, I);
    [ Integers[x_5,x_6,x_7], [ x_5^6-x_5^3 ] ]
  ------------------------------------------------------------------
  
  
  10.3 Singular
  
  10.3-1 SingularSetNormalFormIdeal
  
  > SingularSetNormalFormIdeal( I ) _________________________________operation
  > SingularSetNormalFormIdealNC( I ) _______________________________operation
  Returns:  nothing
  
  Sets  the  ideal  to  be  used  by  singular  for  any  subsequent  calls to
  SingularPolynomialNormalForm  (10.3-2) to be I. After calling this function,
  the  singular  base  ring and term ordering (see SingularBaseRing (singular:
  SingularBaseRing)  and TermOrdering (singular: TermOrdering)) will be set to
  be   that   of   the   ring   containing   I,   so  an  additional  call  to
  SingularSetBaseRing (singular: SingularSetBaseRing) is not necessary.
  
  The standard form of this function ensures that I is a reduced Gröbner basis
  with  respect  to the value of TermOrdering (singular: TermOrdering) for the
  ring  containing  the  ideal,  while the NC assumes that I is already such a
  Gröbner basis.
  
  10.3-2 SingularPolynomialNormalForm
  
  > SingularPolynomialNormalForm( poly[, I] ) _______________________operation
  Returns:  Polynomial
  
  Returns  the normal form of the polynomial poly after reduction by the ideal
  I.  The  ideal  can  either  be passed to this function, in which case it is
  converted  to  a  Gröbner  basis  (with  respect to the term ordering of the
  ideal's  ring  - see TermOrdering (singular: TermOrdering)), or the ideal to
  use  can  be set first be calling SingularSetNormalFormIdeal (10.3-1), which
  is  more  efficient  for  repeated use of this function (the latter function
  also sets the base ring and term ordering).
  
  10.3-3 SingularGroebnerBasis
  
  > SingularGroebnerBasis( I ) ______________________________________attribute
  Returns:  List
  
  Returns a list of relations which form a Gröbner basis for the ideal I given
  the   TermOrdering   (singular:   TermOrdering)  associated  with  the  ring
  containing   I.   This  function  is  the  same  as  the  singular  function
  GroebnerBasis  (singular:  GroebnerBasis),  but  fixes a bug in that package
  when using unusual term ordering.
  
  10.3-4 SingularReducedGroebnerBasis
  
  > SingularReducedGroebnerBasis( I ) _______________________________attribute
  Returns:  List
  
  Returns a list of relations which form a reduced Gröbner basis for the ideal
  I  given  the TermOrdering (singular: TermOrdering) associated with the ring
  containing  I.  This  function  is  the  equivalent of the singular function
  GroebnerBasis  (singular:  GroebnerBasis)  (and  uses  that  function),  but
  ensures that a reduced basis is returned.
  
  
  10.4 Groups
  
  Small  groups  in  GAP  can  be indexed by their small groups library number
  'Reference:  Small  Groups'. An alternative indexing scheme, the Hall-Senior
  number,  is  used by Jon Carlson to publish his cohomology ring calculations
  at http://www.math.uga.edu/~lvalero/cohointro.html. To allow comparison with
  these results, we provide a function that converts from the GAP small groups
  library  numbers to Hall-Senior number for the groups of order 8, 16, 32 and
  64.
  
  
  10.4-1 HallSeniorNumber
  
  > HallSeniorNumber( order, i ) ____________________________________attribute
  > HallSeniorNumber( G ) ___________________________________________attribute
  Returns:  Integer
  
  Returns the Hall-Senior number for a small group (of order 8, 16, 32 or 64).
  The  group  can be specified an order, i pair from the GAP 'Reference: Small
  Groups'  library,  or  as  a group G, in which case IdSmallGroup (Reference:
  IdSmallGroup) is used to identify the group.
  
  ---------------------------  Example  ----------------------------
    gap> HallSeniorNumber(32, 5);
    20
    gap> HallSeniorNumber(SmallGroup(64, 1));
    11
  ------------------------------------------------------------------