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 ________________________________________________________