This mail contains a fix for a minor problem in GAP/lib 3.4.3.13.
The problem is in 'AbelianInvariants' and causes it to return elementary
divisors instead of abelian invariants, e.g. [6] instead of [2,3].
VERSION
GAP/lib 3.4.3.13
Before applying this fix you *must* already have applied fix08lib and
fix013lib.
PRIORITY
The problem is a minor problem, because the result is ``almost correct''.
Thus the fix has low priority.
HOW TO APPLY
Go to the GAP directory (the directory with the 'lib/' subdirectory),
name this mail 'fix21lib.dif', and issue the command:patch -p0 < fix21lib.difIf 'patch' writes "I can't seem to find a patch in there" try 'patch -v'.
If 'patch -v' gives an error message or reports a version older than 2.1,
get 2.1 from 'ftp://FTP.Math.RWTH-Aachen.DE/pub/gap/utils/patch2_1.zoo'.This fix changes only the library.
Thus you need not recompile the GAP kernel.
DESCRIPTION
'AbelianInvariants' may return elementary divisors instead of abelian
invariants, i.e., a list where each element divides the next instead of
a list of prime powers.
CORRECT BEHAVIOUR
gap> F1 := FreeGroup( 1 );; gap> AbelianInvariants( F1 / [ F1.1^6 ] ); [ 2, 3 ]
COMMENT
The manual entry for 'AbelianInvariants' does not define the order of the
result list. This change makes 'AbelianInvariants' return a sorted list,
especially the 0 (for the infinite subgroups) are at the beginning.
DIFFS
Prereq: 3.42.1.3
--- lib/init.g Thu Dec 21 15:30:18 1995
+++ lib/init.g Thu Sep 12 16:14:30 1996
@@ -2,7 +2,7 @@
##
#A init.g GAP library Martin Schoenert
##
-#A @(#)$Id: 1.html,v 1.2 2004/04/21 15:06:19 felsch Exp $
+#A @(#)$Id: 1.html,v 1.2 2004/04/21 15:06:19 felsch Exp $
##
#Y Copyright 1990-1992, Lehrstuhl D fuer Mathematik, RWTH Aachen, Germany
##
@@ -12,7 +12,10 @@
## edit it.
##
#H $Log: 1.html,v $
#H Revision 1.2 2004/04/21 15:06:19 felsch
#H Corrected links in the Forum Archive pages. VF
#H
#H Revision 1.1.1.1 2004/04/20 13:39:30 felsch
#H The final GAP-Forum archive until 2003.
#H
#H Revision 1.4 2003/06/12 19:20:34 gap
#H Further update. AH
#H
#H Revision 1.3 1997/08/15 11:19:38 gap
#H New forum setup. AH
#H
#H Revision 1.2 1997/04/24 15:33:16 gap
#H These files were replaced by the versions in WWW. The content is basically the
#H same but the formatting has been much more friendly towards the HTML-Converter.
#H AH
#H
#H Revision 1.1 1996/10/30 13:07:07 gap
#H added forum archive and translation files.
#H
-#H Revision 3.42.1.3 1995/12/20 18:05:28 mschoene
+#H Revision 3.42.1.4 1996/09/12 14:14:14 mschoene
+#H added 'AbelianInvariantsOfList'
+#H
+#H Revision 3.42.1.3 1995/12/20 18:05:28 mschoene
#H changed for third update
#H
#H Revision 3.42.1.2 1995/05/18 07:55:06 mschoene
@@ -733,13 +736,15 @@
AUTO( ReadLib( "matrix" ),
IsMatrix, MatricesOps, Matrices, DimensionsMat, IdentityMat, NullMat,
RandomMat, RandomInvertableMat, RandomUnimodularMat, TransposedMat,
- PermutationMat, InvariantForm, OrderMatLimit, OrderMat, TraceMat, RankMat,
- DeterminantMat, TriangulizeMat, BaseMat, SemiEchelonMat,
+ PermutationMat, InvariantForm, OrderMatLimit, OrderMat, DiagonalOfMat,
+ TraceMat, RankMat, DeterminantMat, TriangulizeMat, BaseMat, SemiEchelonMat,
InducedActionSpaceMats, SumIntersectionMat, BaseFixedSpace, NullspaceMat,
- NullspaceModQ, SimultaneousEigenvalues, BaseNullspace, DiagonalizeMat,
- ElementaryDivisorsMat, SolutionMat, FieldMatricesOps, FieldMatrices,
- MinimalPolynomial, CharacteristicPolynomial, FiniteFieldMatricesOps,
- FiniteFieldMatrices );
+ NullspaceModQ, SimultaneousEigenvalues, BaseNullspace, BestQuoInt,
+ DiagonalizeIntMatNormDriven, DiagonalizeIntMat, DiagonalizeMat,
+ DiagonalFormMat, SmithNormalizeMat, SmithNormalFormMat,
+ ElementaryDivisorsMat, ElementaryDivisorsOfList, AbelianInvariantsOfList,
+ SolutionMat, FieldMatricesOps, FieldMatrices, MinimalPolynomial,
+ CharacteristicPolynomial, FiniteFieldMatricesOps, FiniteFieldMatrices );
AUTO( ReadLib( "module" ), IsModule, IsFactorModule, ModuleOps, Module, NaturalModule, IsNaturalModule, --- lib/matrix.g Thu Sep 12 16:17:04 1996 +++ lib/matrix.g Thu Sep 12 16:01:13 1996 @@ -2,14 +2,17 @@ ## #A matrix.g GAP library Martin Schoenert ## -#A @(#)$Id: 1.html,v 1.2 2004/04/21 15:06:19 felsch Exp $ +#A @(#)$Id: 1.html,v 1.2 2004/04/21 15:06:19 felsch Exp $ ## #Y Copyright 1990-1992, Lehrstuhl D fuer Mathematik, RWTH Aachen, Germany ## ## This file contains those functions that mainly deal with matrices. ## #H $Log: 1.html,v $ #H Revision 1.2 2004/04/21 15:06:19 felsch #H Corrected links in the Forum Archive pages. VF #H #H Revision 1.1.1.1 2004/04/20 13:39:30 felsch #H The final GAP-Forum archive until 2003. #H #H Revision 1.4 2003/06/12 19:20:34 gap #H Further update. AH #H #H Revision 1.3 1997/08/15 11:19:38 gap #H New forum setup. AH #H #H Revision 1.2 1997/04/24 15:33:16 gap #H These files were replaced by the versions in WWW. The content is basically the #H same but the formatting has been much more friendly towards the HTML-Converter. #H AH #H #H Revision 1.1 1996/10/30 13:07:07 gap #H added forum archive and translation files. #H -#H Revision 3.33.1.2 1996/05/06 12:20:27 mschoene +#H Revision 3.33.1.3 1996/09/12 13:52:04 mschoene +#H fixed handling of abelian invariants +#H +#H Revision 3.33.1.2 1996/05/06 12:20:27 mschoene #H changed 'DiagonalizeMat' to use norms to select the pivot #H #H Revision 3.33.1.1 1994/08/24 15:22:00 sam @@ -712,6 +715,30 @@ ############################################################################# ## +#F DiagonalOfMat(<mat>) . . . . . . . . . . . . . . . . diagonal of matrix +## +## 'DiagonalOfMat' returns the diagonal of the matrix <mat>. The diagonal +## has the same length as the rows of <mat>, it is padded with zeroes if +## <mat> has fewer rows than columns. +## +DiagonalOfMat := function ( mat ) + local diag, i; + diag := []; + i := 1; + while i <= Length(mat) and i <= Length(mat[1]) do + diag[i] := mat[i][i]; + i := i + 1; + od; + while 1 <= Length(mat) and i <= Length(mat[1]) do + diag[i] := mat[1][1] - mat[1][1]; + i := i + 1; + od; + return diag; +end; + + +############################################################################# +## #F TraceMat( <mat> ) . . . . . . . . . . . . . . . . . . . trace of a matrix ## TraceMat := function ( mat ) @@ -1695,41 +1722,107 @@ ############################################################################# ## -#F DiagonalizeMat(<mat>) . . . . . . . . . . . . . . . diagonalize a matrix +#F DiagonalizeMat(<mat>) . . . . . . . . . . convert matrix to diagonal form +## +## 'DiagonalizeMat' converts the matrix <mat> to diagonal form via +## elementary row and column operations. Note that the diagonal form is +## generally not unique (see "SmithNormalizeMat"). ## -#N 1996/05/06 mschoene should be extended for other rings +#N 1996/05/06 M.Schoenert should be extended for other rings ## DiagonalizeMat := DiagonalizeIntMat; ############################################################################# ## -#F ElementaryDivisorsMat(<mat>) . . . . . . elementary divisors of a matrix +#F DiagonalFormMat(<mat>) . . . . . . . . . . . equivalent diagonal matrix ## -## 'ElementaryDivisors' returns a list of the elementary divisors, i.e., the -## unique <d> with '<d>[<i>]' divides '<d>[<i>+1]' and <mat> is equivalent -## to a diagonal matrix with the elements '<d>[<i>]' on the diagonal. +## 'DiagonalFormMat' returns a diagonal matrix <diag> that is equivalent to +## the matrix <mat>. Note that the diagonal form is generally not unique +## (see "SmithNormalFormMat"). ## -ElementaryDivisorsMat := function ( mat ) - local divs, gcd, zero, m, n, i, k; +DiagonalFormMat := function ( mat ) + local copy; + copy := List( mat, ShallowCopy ); + DiagonalizeMat( copy ); + return copy; +end; - # make a copy to avoid changing the original argument - mat := Copy( mat ); - m := Length(mat); n := Length(mat[1]); - # diagonalize the matrix +############################################################################# +## +#F SmithNormalizeMat(<mat>) . . . . . . convert matrix to Smith normal form +## +## 'SmithNormalizeMat' converts the matrix <mat> to Smith normal form via +## elementary row and column operations. The Smith normal form is the +## unique diagonal matrix where each diagonal entry divides the next one. +## +SmithNormalizeMat := function ( mat ) + local zero, gcd, i, k, l; DiagonalizeMat( mat ); + l := Length(mat); + if 0 < l and Length(mat[1]) < l then l := Length(mat[1]); fi; + if 0 < l then zero := mat[1][1] - mat[1][1]; fi; + for i in [1..l-1] do + for k in [i+1..l] do + if mat[i][i] = zero and mat[k][k] <> zero then + mat[i][i] := mat[k][k]; + mat[k][k] := zero; + elif mat[i][i] <> zero + and EuclideanRemainder( mat[k][k], mat[i][i] ) <> zero then + gcd := Gcd( mat[i][i], mat[k][k] ); + mat[k][k] := mat[k][k] / gcd * mat[i][i]; + mat[i][i] := gcd; + fi; + od; + mat[i][i] := StandardAssociate( mat[i][i] ); + od; +end; + - # get the diagonal elements - divs := []; - for i in [1..Minimum(m,n)] do - divs[i] := mat[i][i]; - od; - if divs <> [] then zero := divs[1] - divs[1]; fi; - - # transform the divisors so that every divisor divides the next - for i in [1..Length(divs)-1] do - for k in [i+1..Length(divs)] do +############################################################################# +## +#F SmithNormalFormMat(<mat>) . . . . . . equivalent Smith normal form matrix +## +## 'SmithNormalFormMat' returns the Smith norm form matrix <new> that is +## equivalent to the matrix <mat>. The Smith norm form is the unique +## diagonal matrix where each diagonal entry divides the next one. +## +SmithNormalFormMat := function ( mat ) + local copy; + copy := List( mat, ShallowCopy ); + SmithNormalizeMat( copy ); + return copy; +end; + + +############################################################################# +## +#F ElementaryDivisorsMat(<mat>) . . . . . . elementary divisors of a matrix +## +## 'ElementaryDivisors' returns a list of the elementary divisors of the +## matrix <mat>. The elementary divisors are the unique <divs> with +## '<divs>[<i>]' divides '<divs>[<i>+1]' and <mat> is equivalent to a +## diagonal matrix with the elements '<divs>[<i>]' on the diagonal. <divs> +## has the same length as the rows of <mat>, it is padded with zeroes if +## <mat> has fewer rows than columns. +## +ElementaryDivisorsMat := function ( mat ) + return DiagonalOfMat( SmithNormalFormMat( mat ) ); +end; + + +############################################################################# +## +#F ElementaryDivisorsOfList(<list>) . . . . . elementary divisors of a list +## +ElementaryDivisorsOfList := function ( list ) + local divs, zero, gcd, i, k, l; + divs := ShallowCopy( list ); + l := Length(divs); + if 0 < l then zero := divs[1] - divs[1]; fi; + for i in [1..l-1] do + for k in [i+1..l] do if divs[i] = zero and divs[k] <> zero then divs[i] := divs[k]; divs[k] := zero; @@ -1742,8 +1835,28 @@ od; divs[i] := StandardAssociate( divs[i] ); od; - return divs; +end; + + +############################################################################# +## +#F AbelianInvariantsOfList(<list>) . . . . . . abelian invariants of a list +## +AbelianInvariantsOfList := function ( list ) + local invs, elm; + invs := []; + for elm in list do + if elm = 0 then + Add( invs, 0 ); + elif 1 < elm then + Append( invs, List( Collected(Factors( elm)), x->x[1]^x[2] ) ); + elif elm < -1 then + Append( invs, List( Collected(Factors(-elm)), x->x[1]^x[2] ) ); + fi; + od; + Sort( invs ); + return invs; end; --- lib/fpgrp.g Thu Sep 12 16:17:09 1996 +++ lib/fpgrp.g Thu Sep 12 16:03:57 1996 @@ -2,14 +2,17 @@ ## #A fpgrp.g GAP library Martin Schoenert ## -#H @(#)$Id: 1.html,v 1.2 2004/04/21 15:06:19 felsch Exp $ +#H @(#)$Id: 1.html,v 1.2 2004/04/21 15:06:19 felsch Exp $ ## #Y Copyright 1990-1992, Lehrstuhl D fuer Mathematik, RWTH Aachen, Germany ## ## This file contains the functions dealing with finitely presented groups. ## #H $Log: 1.html,v $ #H Revision 1.2 2004/04/21 15:06:19 felsch #H Corrected links in the Forum Archive pages. VF #H #H Revision 1.1.1.1 2004/04/20 13:39:30 felsch #H The final GAP-Forum archive until 2003. #H #H Revision 1.4 2003/06/12 19:20:34 gap #H Further update. AH #H #H Revision 1.3 1997/08/15 11:19:38 gap #H New forum setup. AH #H #H Revision 1.2 1997/04/24 15:33:16 gap #H These files were replaced by the versions in WWW. The content is basically the #H same but the formatting has been much more friendly towards the HTML-Converter. #H AH #H #H Revision 1.1 1996/10/30 13:07:07 gap #H added forum archive and translation files. #H -#H Revision 3.23.1.11 1996/06/11 14:48:40 mschoene +#H Revision 3.23.1.12 1996/09/12 13:52:04 mschoene +#H fixed handling of abelian invariants +#H +#H Revision 3.23.1.11 1996/06/11 14:48:40 mschoene #H fixed '.preimage' to '.preImage' #H #H Revision 3.23.1.10 1995/11/25 22:42:44 mschoene @@ -1659,17 +1662,12 @@ #F fin. pres. group ## FpGroupOps.AbelianInvariants := function ( G ) - - local abl, # abelian invariants of <G>, result - mat, # relation matrix of <G> + local mat, # relation matrix of <G> row, # one row of <mat> rel, # one relation of <G> g, # one letter of <rel> p, # position of <g> or its inverse in '<G>.generators' - i, # loop variable - divs, # elementary divisors - gcd, # extended gcd - m, n, k; + i; # loop variable # If G is a subgroup of a finitely presented group, find a # presentation for G first. @@ -1705,36 +1703,8 @@ # diagonalize the matrix DiagonalizeMat( mat ); - # get the diagonal elements - m := Length(mat); - n := Length(mat[1]); - divs := []; - for i in [1..Minimum(m,n)] do - divs[i] := mat[i][i]; - od; - for i in [Minimum(m,n)+1..n] do - divs[i] := 0; - od; - - # transform the divisors so that every divisor divides the next - for i in [1..Length(divs)-1] do - for k in [i+1..Length(divs)] do - if divs[i] <> 0 and divs[k] mod divs[i] <> 0 then - gcd := GcdInt( divs[i], divs[k] ); - divs[k] := divs[k] / gcd * divs[i]; - divs[i] := gcd; - fi; - od; - od; - - # and return the ablian invariants - abl := []; - for i in divs do - if i <> 1 then - Add( abl, i ); - fi; - od; - return abl; + # return the abelian invariants + return AbelianInvariantsOfList( DiagonalOfMat( mat ) ); end; --- lib/fpsgpres.g Thu Dec 21 15:30:12 1995 +++ lib/fpsgpres.g Thu Sep 12 16:06:01 1996 @@ -2,7 +2,7 @@ ## #A fpsgpres.g GAP library Volkmar Felsch ## -#H @(#)$Id: 1.html,v 1.2 2004/04/21 15:06:19 felsch Exp $ +#H @(#)$Id: 1.html,v 1.2 2004/04/21 15:06:19 felsch Exp $ ## #Y Copyright 1990-1992, Lehrstuhl D fuer Mathematik, RWTH Aachen, Germany ## @@ -10,7 +10,10 @@ ## finitely presented groups. ## #H $Log: 1.html,v $ #H Revision 1.2 2004/04/21 15:06:19 felsch #H Corrected links in the Forum Archive pages. VF #H #H Revision 1.1.1.1 2004/04/20 13:39:30 felsch #H The final GAP-Forum archive until 2003. #H #H Revision 1.4 2003/06/12 19:20:34 gap #H Further update. AH #H #H Revision 1.3 1997/08/15 11:19:38 gap #H New forum setup. AH #H #H Revision 1.2 1997/04/24 15:33:16 gap #H These files were replaced by the versions in WWW. The content is basically the #H same but the formatting has been much more friendly towards the HTML-Converter. #H AH #H #H Revision 1.1 1996/10/30 13:07:07 gap #H added forum archive and translation files. #H -#H Revision 3.9.1.2 1995/11/25 15:51:34 mschoene +#H Revision 3.9.1.3 1996/09/12 13:52:04 mschoene +#H fixed handling of abelian invariants +#H +#H Revision 3.9.1.2 1995/11/25 15:51:34 mschoene #H cleaned up the handling of involutory generators #H #H Revision 3.9.1.1 1994/08/22 09:46:33 vfelsch @@ -1606,28 +1609,9 @@ ## presented group G. ## AbelianInvariantsSubgroupFpGroupMtc := function ( G, H ) - - local invar, i, j, leng, m; - - m := RelatorMatrixAbelianizedSubgroupMtc( G, H ); - if m = [ ] then - invar := [ ]; - else - invar := ElementaryDivisorsMat( m ); - fi; - - # remove trivial entries (i.e. ones) from invar. - leng := Length( invar ); - i := 0; - for j in [ 1 .. leng ] do - if invar[j] <> 1 then - i := i + 1; - invar[i] := invar[j]; - fi; - od; - if i < leng then invar := Sublist( invar, [ 1 .. i ] ); fi; - - return invar; + return AbelianInvariantsOfList( + ElementaryDivisorsMat( + RelatorMatrixAbelianizedSubgroupMtc( G, H ) ) ); end; @@ -1696,28 +1680,9 @@ ## by its coset table. ## AbelianInvariantsSubgroupFpGroupRrs := function ( G, H ) - - local invar, i, j, leng, m; - - m := RelatorMatrixAbelianizedSubgroupRrs( G, H ); - if m = [ ] then - invar := [ ]; - else - invar := ElementaryDivisorsMat( m ); - fi; - - # remove trivial entries (i.e. ones) from invar. - leng := Length( invar ); - i := 0; - for j in [ 1 .. leng ] do - if invar[j] <> 1 then - i := i + 1; - invar[i] := invar[j]; - fi; - od; - if i < leng then invar := Sublist( invar, [ 1 .. i ] ); fi; - - return invar; + return AbelianInvariantsOfList( + ElementaryDivisorsMat( + RelatorMatrixAbelianizedSubgroupRrs( G, H ) ) ); end; AbelianInvariantsSubgroupFpGroup := AbelianInvariantsSubgroupFpGroupRrs; @@ -1807,28 +1772,9 @@ ## of a subgroup H of a finitely presented group G. ## AbelianInvariantsNormalClosureFpGroupRrs := function ( G, H ) - - local invar, i, j, leng, m; - - m := RelatorMatrixAbelianizedNormalClosureRrs( G, H ); - if m = [ ] then - invar := [ ]; - else - invar := ElementaryDivisorsMat( m ); - fi; - - # remove trivial entries (i.e. ones) from invar. - leng := Length( invar ); - i := 0; - for j in [ 1 .. leng ] do - if invar[j] <> 1 then - i := i + 1; - invar[i] := invar[j]; - fi; - od; - if i < leng then invar := Sublist( invar, [ 1 .. i ] ); fi; - - return invar; + return AbelianInvariantsOfList( + ElementaryDivisorsMat( + RelatorMatrixAbelianizedNormalClosureRrs( G, H ) ) ); end; AbelianInvariantsNormalClosureFpGroup := --- lib/chartabl.g Thu Dec 21 15:29:58 1995 +++ lib/chartabl.g Thu Sep 12 16:07:30 1996 @@ -3,14 +3,17 @@ #A chartabl.g GAP library Thomas Breuer #A & Goetz Pfeiffer ## -#A @(#)$Id: 1.html,v 1.2 2004/04/21 15:06:19 felsch Exp $ +#A @(#)$Id: 1.html,v 1.2 2004/04/21 15:06:19 felsch Exp $ ## #Y Copyright 1993-1995, Lehrstuhl D fuer Mathematik, RWTH Aachen, Germany ## ## This file contains functions and operations for character tables in GAP. ## #H $Log: 1.html,v $ #H Revision 1.2 2004/04/21 15:06:19 felsch #H Corrected links in the Forum Archive pages. VF #H #H Revision 1.1.1.1 2004/04/20 13:39:30 felsch #H The final GAP-Forum archive until 2003. #H #H Revision 1.4 2003/06/12 19:20:34 gap #H Further update. AH #H #H Revision 1.3 1997/08/15 11:19:38 gap #H New forum setup. AH #H #H Revision 1.2 1997/04/24 15:33:16 gap #H These files were replaced by the versions in WWW. The content is basically the #H same but the formatting has been much more friendly towards the HTML-Converter. #H AH #H #H Revision 1.1 1996/10/30 13:07:07 gap #H added forum archive and translation files. #H -#H Revision 3.4 1994/06/10 04:45:27 sam +#H Revision 3.4.1.1 1996/09/12 13:52:04 mschoene +#H fixed handling of abelian invariants +#H +#H Revision 3.4 1994/06/10 04:45:27 sam #H improved 'PrintCharTable' #H #H Revision 3.3 1994/05/25 10:38:43 sam @@ -596,7 +599,7 @@
od;
- return Set( inv ); + return AbelianInvariantsOfList( inv );
end;
END OF fix21lib.dif ________________________________________________________