|
#############################################################################
##
## This file is part of GAP, a system for computational discrete algebra.
## This file's authors include Thomas Breuer.
##
## Copyright of GAP belongs to its developers, whose names are too numerous
## to list here. Please refer to the COPYRIGHT file for details.
##
## SPDX-License-Identifier: GPL-2.0-or-later
##
## This file contains the methods for magmas given by their multiplication
## tables.
##
#############################################################################
##
#R IsMagmaByMultiplicationTableObj( <obj> )
##
## At position 1 of the element $m_i$, the number $i$ is stored.
##
DeclareRepresentation( "IsMagmaByMultiplicationTableObj",
IsPositionalObjectRep and IsMultiplicativeElementWithInverse,
[ 1 ] );
#T change to IsPositionalObjectOneSlotRep!
#############################################################################
##
#M PrintObj( <obj> )
##
InstallMethod( PrintObj,
"for element of magma by mult. table",
[ IsMagmaByMultiplicationTableObj ],
function( obj )
Print( "m", obj![1] );
end );
#############################################################################
##
#M \=( <x>, <y> )
#M \<( <x>, <y> )
#M \*( <x>, <y> )
#M \^( <x>, <n> )
##
InstallMethod( \=,
"for two elements of magma by mult. table",
IsIdenticalObj,
[ IsMagmaByMultiplicationTableObj,
IsMagmaByMultiplicationTableObj ],
function( x, y ) return x![1] = y![1]; end );
InstallMethod( \<,
"for two elements of magma by mult. table",
IsIdenticalObj,
[ IsMagmaByMultiplicationTableObj,
IsMagmaByMultiplicationTableObj ],
function( x, y ) return x![1] < y![1]; end );
InstallMethod( \*,
"for two elements of magma by mult. table",
IsIdenticalObj,
[ IsMagmaByMultiplicationTableObj,
IsMagmaByMultiplicationTableObj ],
function( x, y )
local F;
F:= FamilyObj( x );
return F!.set[ MultiplicationTable( F )[ x![1] ][ y![1] ] ];
end );
#############################################################################
##
#M OneOp( <elm> )
##
InstallMethod( OneOp,
"for an element in a magma by mult. table",
[ IsMagmaByMultiplicationTableObj ],
function( elm )
local F, n, A, onepos, one;
F:= FamilyObj( elm );
n:= F!.n;
# Check that the mult. table admits a left and right identity element.
A:= MultiplicationTable( F );
onepos:= Position( A, [ 1 .. n ] );
if onepos = fail or A{ [ 1 .. n ] }[ onepos ] <> [ 1 .. n ] then
one:= fail;
else
one:= F!.set[ onepos ];
fi;
SetOne( F, one );
return one;
end );
#############################################################################
##
#M IsGeneratorsOfMagmaWithInverses( <elms> )
##
## Under the assumption that the multiplication for <elms> is associative
## (cf. the discussion for issue 4480),
## a collection of magma by multiplication table elements will always be
## acceptable as generators, provided each one individually has an inverse.
##
InstallMethod( IsGeneratorsOfMagmaWithInverses,
"for a collection of magma by mult table elements",
[IsCollection],
function(c)
if ForAll(c, x-> IsMagmaByMultiplicationTableObj(x) and Inverse(x) <> fail) then
return true;
fi;
TryNextMethod();
end);
#############################################################################
##
#M InverseOp( <elm> )
##
InstallMethod( InverseOp,
"for an element in a magma by mult. table",
[ IsMagmaByMultiplicationTableObj ],
function( elm )
local F, i, one, onepos, inv, j, n, A, invpos;
F:= FamilyObj( elm );
i:= elm![1];
if IsBound( F!.inverse[i] ) then
return F!.inverse[i];
fi;
# Check that `A' admits a left and right identity element.
# (This is uniquely determined.)
one:= One( elm );
if one = fail then
return fail;
fi;
onepos:= one![1];
# Check that `elm' has a left and right inverse.
# (If the multiplication is associative, this is uniquely determined.)
inv:= fail;
j:= 0;
n:= F!.n;
A:= MultiplicationTable( F );
while j <= n do
invpos:= Position( A[i], onepos, j );
if invpos <> fail and A[ invpos ][i] = onepos then
inv:= F!.set[ invpos ];
break;
fi;
j:= invpos;
od;
F!.inverse[i]:= inv;
return inv;
end );
#############################################################################
##
#F MagmaElement( <M>, <i> ) . . . . . . . . . . <i>-th element of magma <M>
##
InstallGlobalFunction( MagmaElement, function( M, i )
M:= AsSSortedList( M );
if Length( M ) < i then
return fail;
else
return M[i];
fi;
end );
#############################################################################
##
#F MagmaByMultiplicationTableCreator( <A>, <domconst> )
##
InstallGlobalFunction( MagmaByMultiplicationTableCreator,
function( arg )
local n, # dimension of `A'
range, # the range `[ 1 .. n ]'
filts;
if IsBound(arg[3]) then
filts:=IsMagmaByMultiplicationTableObj and arg[3];
else
filts:=IsMagmaByMultiplicationTableObj;
fi;
# Check that `arg[1]' is a valid multiplication table.
if IsMatrix( arg[1] ) then
n:= Length( arg[1] );
range:= [ 1 .. n ];
if Length( arg[1][1] ) = n
and ForAll( arg[1], row -> ForAll( row, x -> x in range ) ) then
return MagmaByMultiplicationTableCreatorNC(arg[1], arg[2], filts);
fi;
fi;
Error( "<arg[1]> must be a square matrix with entries in `[ 1 .. n ]'" );
end );
#
InstallGlobalFunction( MagmaByMultiplicationTableCreatorNC,
function( A, domconst, filts )
local n, F, elms, M;
n:=Length(A);
# Construct the family of objects.
F:= NewFamily( "MagmaByMultTableObj", filts );
F!.n:=n;
SetMultiplicationTable( F, A );
elms:= Immutable( List( [1..n],
i -> Objectify( NewType( F, filts), [ i ] ) ) );
SetIsSSortedList( elms, true );
F!.set:= elms;
F!.inverse:= [];
# Construct the magma.
M:= domconst( CollectionsFamily( F ), elms );
SetSize( M, n );
SetAsSSortedList( M, elms );
SetMultiplicationTable( M, MultiplicationTable( F ) );
# Return the result.
return M;
end );
#############################################################################
##
#F MagmaByMultiplicationTable( <A> )
##
InstallGlobalFunction( MagmaByMultiplicationTable, function( A )
return MagmaByMultiplicationTableCreator( A, MagmaByGenerators );
end );
#############################################################################
##
#F MagmaWithOneByMultiplicationTable( <A> )
##
InstallGlobalFunction( MagmaWithOneByMultiplicationTable, function( A )
local n, # dimension of `A'
onepos, # position of the identity in `A'
M; # the magma, result
M:= MagmaByMultiplicationTableCreator( A, MagmaWithOneByGenerators );
# Check that `A' admits a left and right identity element.
n:= Length( A );
onepos:= Position( A, [ 1 .. n ] );
if onepos = fail or A{ [ 1 .. n ] }[ onepos ] <> [ 1 .. n ] then
return fail;
fi;
# Store the identity in the family.
SetOne( ElementsFamily( FamilyObj( M ) ), AsSSortedList( M )[ onepos ] );
SetGeneratorsOfMagma( M, AsSSortedList( M ) );
# Return the result.
return M;
end );
#############################################################################
##
#F MagmaWithInversesByMultiplicationTable( <A> )
##
InstallGlobalFunction( MagmaWithInversesByMultiplicationTable, function( A )
local F, # the family of objects
n, # dimension of `A'
onepos, # position of the identity in `A'
inv, # list of positions of inverses
i, # loop over the elements
invpos, # position of one inverse
elms, # sorted list of elements
M; # the magma, result
M:= MagmaByMultiplicationTableCreator( A,
MagmaWithInversesByGenerators );
# Check that `A' admits a left and right identity element.
n:= Length( A );
onepos:= Position( A, [ 1 .. n ] );
if onepos = fail or A{ [ 1 .. n ] }[ onepos ] <> [ 1 .. n ] then
return fail;
fi;
# Check that `A' admits inverses.
inv:= [];
for i in [ 1 .. n ] do
invpos:= Position( A[i], onepos );
if invpos = fail or A[ invpos ][i] <> onepos then
return fail;
fi;
inv[i]:= invpos;
od;
# Store identity and inverses in the family.
F:= ElementsFamily( FamilyObj( M ) );
elms:= AsSSortedList( M );
SetOne( F, elms[ onepos ] );
F!.inverse:= Immutable( elms{ inv } );
SetGeneratorsOfMagma( M, elms );
# Return the result.
return M;
end );
#############################################################################
##
#F SemigroupByMultiplicationTable( <A> )
##
InstallGlobalFunction( SemigroupByMultiplicationTable,
function( A )
local n, range, i, j, k;
# Check that `A' is a valid multiplication table.
if IsMatrix( A ) then
n := Length( A );
range := [ 1 .. n ];
if Length( A[1] ) = n
and ForAll( A, row -> ForAll( row, x -> x in range ) ) then
# check associativity
for i in range do
for j in range do
for k in range do
if A[A[i][j]][k]<>A[i][A[j][k]] then
return fail;
fi;
od;
od;
od;
return MagmaByMultiplicationTableCreatorNC(A, MagmaByGenerators,
IsAssociativeElement and IsMagmaByMultiplicationTableObj);
fi;
fi;
Error( "<A> must be a square matrix with entries in `[ 1 .. n ]'" );
end );
#############################################################################
##
#F MonoidByMultiplicationTable( <A> )
##
InstallGlobalFunction( MonoidByMultiplicationTable,
function( A )
local n, range, onepos, M, i, j, k;
if IsMatrix( A ) then
n := Length( A );
range := [ 1 .. n ];
if Length( A[1] ) = n
and ForAll( A, row -> ForAll( row, x -> x in range ) ) then
# Check that `A' admits a left and right identity element.
onepos:= Position( A, [ 1 .. n ] );
if onepos = fail or A{ [ 1 .. n ] }[ onepos ] <> [ 1 .. n ] then
return fail;
fi;
# check associativity
for i in range do
for j in range do
for k in range do
if A[A[i][j]][k]<>A[i][A[j][k]] then
return fail;
fi;
od;
od;
od;
M:=MagmaByMultiplicationTableCreatorNC(A, MagmaWithOneByGenerators,
IsAssociativeElement and IsMagmaByMultiplicationTableObj);
# Store the identity in the family.
SetOne( ElementsFamily( FamilyObj( M ) ), AsSSortedList( M )[ onepos ] );
SetGeneratorsOfMagma( M, AsSSortedList( M ) );
# Return the result.
return M;
fi;
fi;
Error( "<A> must be a square matrix with entries in `[ 1 .. n ]'" );
end );
#############################################################################
##
#F GroupByMultiplicationTable( <A> )
##
InstallGlobalFunction( GroupByMultiplicationTable, function( A )
A:= MagmaWithInversesByMultiplicationTable( A );
if A = fail or not IsAssociative( A ) then
return fail;
fi;
return A;
end );
#############################################################################
##
#M MultiplicationTable( <elmlist> )
##
InstallMethod( MultiplicationTable,
"for a list of elements",
[ IsHomogeneousList ],
elmlist -> List( elmlist, x -> List( elmlist,
y -> Position( elmlist, x * y ) ) ) );
#############################################################################
##
#M MultiplicationTable( <M> )
##
InstallMethod( MultiplicationTable,
"for a magma",
[ IsMagma ],
M -> MultiplicationTable( AsSSortedList( M ) ) );
[ Dauer der Verarbeitung: 0.4 Sekunden
(vorverarbeitet)
]
|
