[1X10 General Functions[0X Some of the functions provided by [5XHAPprime[0m are not specifically aimed at homological algebra or extending the [5XHAP[0m package. The functions in this chapter, which are used internally by [5XHAPprime[0m extend some of the standard [5XGAP[0m functions and datatypes. [1X10.1 Matrices[0X For details of the standard [5XGAP[0m vector and matrix functions, see [14X'Tutorial: matrices'[0m and [14X'Reference: Matrices'[0m in the [5XGAP[0m tutorial and reference manuals. [5XHAPprime[0m provides improved versions of a couple of standard matrix operations, and two small helper functions. [1X10.1-1 SumIntersectionMatDestructive[0m [2X> SumIntersectionMatDestructive( [0X[3XU, V[0X[2X ) ___________________________[0Xoperation [2X> SumIntersectionMatDestructiveSE( [0X[3XUbasis, Uheads, Vbasis, Vheads[0X[2X ) [0Xoperation Returns a list of length 2 with, at the first position, the sum of the vector spaces generated by the rows of [3XU[0m and [3XV[0m, and, at the second position, the intersection of the spaces. Like the [5XGAP[0m core function [2XSumIntersectionMat[0m ([14XReference: SumIntersectionMat[0m), 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 [5XGAP[0m 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 [9XSumIntersectionMatDestructiveSE[0m 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 [2XSemiEchelonMatDestructive[0m ([14XReference: SemiEchelonMatDestructive[0m) (these arguments must all be mutable, so [2XSemiEchelonMat[0m ([14XReference: SemiEchelonMat[0m) cannot be used). This function is used internally by [9XSumIntersectionMatDestructive[0m, 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. [1X10.1-2 SolutionMat[0m [2X> SolutionMat( [0X[3XM, V[0X[2X ) _____________________________________________[0Xoperation [2X> SolutionMatDestructive( [0X[3XM, V[0X[2X ) __________________________________[0Xoperation Calculates, for each row vector v_i in the matrix [3XV[0m, 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 [9Xfail[0m is returned for that row. These functions are identical to the kernel functions [2XSolutionMat[0m ([14XReference: SolutionMat[0m) and [2XSolutionMatDestructive[0m ([14XReference: SolutionMatDestructive[0m), but are provided for cases where multiple solutions using the same matrix [3XM[0m are required. In these cases, using this function is far faster, since the matrix is only decomposed once. The [10XDestructive[0m version corrupts both the input matrices, while the non-[10XDestructive[0m version operates on copies of these. [1X10.1-3 IsSameSubspace[0m [2X> IsSameSubspace( [0X[3XU, V[0X[2X ) __________________________________________[0Xoperation Returns [9Xtrue[0m if the subspaces spanned by the rows of [3XU[0m and [3XV[0m are the same, [9Xfalse[0m 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. [1X10.1-4 PrintDimensionsMat[0m [2X> PrintDimensionsMat( [0X[3XM[0X[2X ) _________________________________________[0Xoperation Returns a string containing the dimensions of the matrix [3XM[0m in the form [10X"mxn"[0m, where [9Xm[0m is the number of rows and [9Xn[0m the number of columns. If the matrix is empty, the returned string is [10X"empty"[0m. [1X10.1-5 Example: matrices and vector spaces[0X [5XGAP[0m 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 [2XSolutionMat[0m ([14X10.1-2[0m) we can see that V lies in U, but [2XIsSameSubspace[0m ([14X10.1-3[0m) shows that they are the same subspace, as is confirmed by having identical sums and intersections. [4X--------------------------- Example ----------------------------[0X [4Xgap> U := [[1,2,3],[4,5,6]];;[0X [4Xgap> V := [[3,3,3],[5,7,9]];;[0X [4Xgap> SolutionMat(U, V);[0X [4X[ [ -1, 1 ], [ 1, 1 ] ][0X [4Xgap> IsSameSubspace(U, V);[0X [4Xtrue[0X [4Xgap> SumIntersectionMatDestructive(U, V);[0X [4X[ [ [ 1, 2, 3 ], [ 0, 1, 2 ] ], [ [ 0, 1, 2 ], [ 1, 0, -1 ] ] ][0X [4Xgap> IsSameSubspace(last[1], last[2]);[0X [4Xtrue[0X [4Xgap> PrintDimensionsMat(V);[0X [4X"2x3"[0X [4X------------------------------------------------------------------[0X [1X10.2 Polynomials[0X [5XGAP[0m provides some functions for manipulating polynomials and polynomial ideals - see [14X'Reference: Polynomials and Rational Functions'[0m. The [5XHAPprime[0m packages adds further functions to decompose polynomials into terms and monomials, and some functions for tidying up polynomial ideals. [1X10.2-1 TermsOfPolynomial[0m [2X> TermsOfPolynomial( [0X[3Xpoly[0X[2X ) _______________________________________[0Xattribute [6XReturns:[0X List of pairs Returns a list of the terms in the polynomial. This list is a list of pairs of the form [10X[mon, coeff][0m where [10Xmon[0m is a monomial and [10Xcoeff[0m 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 [2XMonomialGrLexOrdering[0m ([14XReference: MonomialGrlexOrdering[0m)). [1X10.2-2 IsMonomial[0m [2X> IsMonomial( [0X[3Xpoly[0X[2X ) ______________________________________________[0Xattribute [6XReturns:[0X Boolean Returns [9Xtrue[0m if [3Xpoly[0m is a monomial, i.e. the polynomial contains only one term. [1X10.2-3 UnivariateMonomialsOfMonomial[0m [2X> UnivariateMonomialsOfMonomial( [0X[3Xmon[0X[2X ) ____________________________[0Xattribute [6XReturns:[0X List Returns a list of the univariate monomials of the largest order whose product equals [3Xmon[0m. The univariate monomials are sorted according to their indeterminate number. [1X10.2-4 IndeterminateAndExponentOfUnivariateMonomial[0m [2X> IndeterminateAndExponentOfUnivariateMonomial( [0X[3Xmon[0X[2X ) _____________[0Xattribute [6XReturns:[0X List Returns a list [10X[indet, exp][0m where [10Xindet[0m is the indeterminate of the univariate monomial [3Xmon[0m and [10Xexp[0m is the exponent of that indeterminate in the monomial. If [3Xmon[0m is an element in the coefficient ring (i.e. the monomial contains no indeterminates) then the first element will be [3Xmon[0m with an exponent of zero. If [3Xmon[0m is not a univariate monomial, then [9Xfail[0m is returned. [1X10.2-5 IndeterminatesOfPolynomial[0m [2X> IndeterminatesOfPolynomial( [0X[3Xpoly[0X[2X ) ______________________________[0Xattribute [6XReturns:[0X List Returns a list of the indeterminates used in the polynomial [3Xpoly[0m. [1X10.2-6 ReduceIdeal[0X [2X> ReduceIdeal( [0X[3XI, O[0X[2X ) _____________________________________________[0Xoperation [2X> ReduceIdeal( [0X[3Xrels, O[0X[2X ) __________________________________________[0Xoperation [6XReturns:[0X Ideal or list For an ideal [3XI[0m returns an ideal containing a reduced generating set for the ideal, i.e. one in which no monomial in a relation in [3XI[0m is divisible by the leading term of another polynomial in [3XI[0m. The monomial ordering to be used is specified by [3XO[0m (see [14X'Reference: Monomial Orderings'[0m). The ideal can instead be specified by a list of relations [3Xrels[0m, in which case a reduced list of relations is returned. [1X10.2-7 ReducedPolynomialRingPresentation[0m [2X> ReducedPolynomialRingPresentation( [0X[3XR, I[, avoid][0X[2X ) ______________[0Xoperation [2X> ReducedPolynomialRingPresentationMap( [0X[3XR, I[, avoid][0X[2X ) ___________[0Xoperation [6XReturns:[0X List For a polynomial ring [3XR[0m and a list of relations [3XI[0m in that ring, returns a list [10X[S, J][0m 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 [10XS[0m will be distinct from thise in [3XR[0m, and an optional argument [3Xavoid[0m can be used to give a list of further indeterminates to avoid when creating the ring [10XS[0m. The extended version of this function, [2XReducedPolynomialRingPresentationMap[0m, 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. [1X10.2-8 Example: monomials, polynomials and ring presentations[0X 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 [2XTermsOfPolynomial[0m ([14X10.2-1[0m) 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 [2XUnivariateMonomialsOfMonomial[0m ([14X10.2-3[0m). -- decompose a univariate monomial into it the indeterminates and exponent ([2XIndeterminateAndExponentOfUnivariateMonomial[0m ([14X10.2-4[0m)). In the example below, we decompose x + xy^2 + 3y^3 into its three terms, and then further decompose the xy^2 term. [4X--------------------------- Example ----------------------------[0X [4Xgap> R := PolynomialRing(Integers, 2);;[0X [4Xgap> x := R.1;; y := R.2;;[0X [4Xgap> poly := x + x*y^2 + 3*y^3;[0X [4Xx_1*x_2^2+3*x_2^3+x_1[0X [4Xgap> terms := TermsOfPolynomial(poly);[0X [4X[ [ x_1, 1 ], [ x_2^3, 3 ], [ x_1*x_2^2, 1 ] ][0X [4Xgap> UnivariateMonomialsOfMonomial(terms[3][1]);[0X [4X[ x_1, x_2^2 ][0X [4Xgap> IndeterminateAndExponentOfUnivariateMonomial(last[2]);[0X [4X[ x_2, 2 ][0X [4X------------------------------------------------------------------[0X [5XHAPprime[0m 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 [4X--------------------------- Example ----------------------------[0X [4Xgap> R := PolynomialRing(Integers, 4);;[0X [4Xgap> w := R.1;; x := R.2;;[0X [4Xgap> I := [w^2 + x, w^3 + x^3];[0X [4X[ x_1^2+x_2, x_1^3+x_2^3 ][0X [4Xgap> ReduceIdeal(I, MonomialLexOrdering());[0X [4X[ x_1^2+x_2, -x_2^3+x_1*x_2 ][0X [4Xgap> [0X [4Xgap> ReducedPolynomialRingPresentation(R, I);[0X [4X[ Integers[x_5,x_6,x_7], [ x_5^6-x_5^3 ] ][0X [4X------------------------------------------------------------------[0X [1X10.3 Singular[0X [1X10.3-1 SingularSetNormalFormIdeal[0m [2X> SingularSetNormalFormIdeal( [0X[3XI[0X[2X ) _________________________________[0Xoperation [2X> SingularSetNormalFormIdealNC( [0X[3XI[0X[2X ) _______________________________[0Xoperation [6XReturns:[0X nothing Sets the ideal to be used by singular for any subsequent calls to [2XSingularPolynomialNormalForm[0m ([14X10.3-2[0m) to be [3XI[0m. After calling this function, the singular base ring and term ordering (see [2XSingularBaseRing[0m ([14Xsingular: SingularBaseRing[0m) and [2XTermOrdering[0m ([14Xsingular: TermOrdering[0m)) will be set to be that of the ring containing [3XI[0m, so an additional call to [2XSingularSetBaseRing[0m ([14Xsingular: SingularSetBaseRing[0m) is not necessary. The standard form of this function ensures that [3XI[0m is a reduced Gröbner basis with respect to the value of [2XTermOrdering[0m ([14Xsingular: TermOrdering[0m) for the ring containing the ideal, while the [10XNC[0m assumes that [3XI[0m is already such a Gröbner basis. [1X10.3-2 SingularPolynomialNormalForm[0m [2X> SingularPolynomialNormalForm( [0X[3Xpoly[, I][0X[2X ) _______________________[0Xoperation [6XReturns:[0X Polynomial Returns the normal form of the polynomial [3Xpoly[0m after reduction by the ideal [3XI[0m. 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 [2XTermOrdering[0m ([14Xsingular: TermOrdering[0m)), or the ideal to use can be set first be calling [2XSingularSetNormalFormIdeal[0m ([14X10.3-1[0m), which is more efficient for repeated use of this function (the latter function also sets the base ring and term ordering). [1X10.3-3 SingularGroebnerBasis[0m [2X> SingularGroebnerBasis( [0X[3XI[0X[2X ) ______________________________________[0Xattribute [6XReturns:[0X List Returns a list of relations which form a Gröbner basis for the ideal [3XI[0m given the [2XTermOrdering[0m ([14Xsingular: TermOrdering[0m) associated with the ring containing [3XI[0m. This function is the same as the [5Xsingular[0m function [2XGroebnerBasis[0m ([14Xsingular: GroebnerBasis[0m), but fixes a bug in that package when using unusual term ordering. [1X10.3-4 SingularReducedGroebnerBasis[0m [2X> SingularReducedGroebnerBasis( [0X[3XI[0X[2X ) _______________________________[0Xattribute [6XReturns:[0X List Returns a list of relations which form a reduced Gröbner basis for the ideal [3XI[0m given the [2XTermOrdering[0m ([14Xsingular: TermOrdering[0m) associated with the ring containing [3XI[0m. This function is the equivalent of the [5Xsingular[0m function [2XGroebnerBasis[0m ([14Xsingular: GroebnerBasis[0m) (and uses that function), but ensures that a reduced basis is returned. [1X10.4 Groups[0X Small groups in [5XGAP[0m can be indexed by their small groups library number [14X'Reference: Small Groups'[0m. An alternative indexing scheme, the Hall-Senior number, is used by Jon Carlson to publish his cohomology ring calculations at [7Xhttp://www.math.uga.edu/~lvalero/cohointro.html[0m. To allow comparison with these results, we provide a function that converts from the [5XGAP[0m small groups library numbers to Hall-Senior number for the groups of order 8, 16, 32 and 64. [1X10.4-1 HallSeniorNumber[0X [2X> HallSeniorNumber( [0X[3Xorder, i[0X[2X ) ____________________________________[0Xattribute [2X> HallSeniorNumber( [0X[3XG[0X[2X ) ___________________________________________[0Xattribute [6XReturns:[0X Integer Returns the Hall-Senior number for a small group (of order 8, 16, 32 or 64). The group can be specified an [3Xorder[0m, [3Xi[0m pair from the [5XGAP[0m [14X'Reference: Small Groups'[0m library, or as a group [3XG[0m, in which case [2XIdSmallGroup[0m ([14XReference: IdSmallGroup[0m) is used to identify the group. [4X--------------------------- Example ----------------------------[0X [4Xgap> HallSeniorNumber(32, 5);[0X [4X20[0X [4Xgap> HallSeniorNumber(SmallGroup(64, 1));[0X [4X11[0X [4X------------------------------------------------------------------[0X