Matrix groups from GAP

[Rob Beezer]

I'm working (along with a summer research student) to expand the collection of small groups (and their representations) in Sage.  A question about matrix groups, as built by GAP for Sage.

For small, not-very-sophisticated groups, such as a Dihedral group, is it preferable to concoct generators in Sage and use the generic MatrixGroup() constructor or use a GAP routine to build the group?

A simple example:

GAP:  Wrap - "CyclicGroup( IsMatrixGroup, GF(2), 12 )"
  will build a matrix group of order 12 with matrices of size 12, over a few different types of fields.  This is about as much freedom as GAP allows.

Python:  Mythical - CyclicMatrixGroup(n, R, dimension=None)
  to build a cyclic group of order n over R, but where "dimension" could default to n, or be sum of invariants, or sum of prime powers, or 1 over the cyclotomic field.  Then an appropriate matrix could be created and sent to the MatrixGroup() (ideally as part of a class providing a sensible repr, etc.)

The second approach allows for a lot more flexibility in providing representations of different dimensions.

My question: is much lost by building the generators and computing the GAP group from those, versus using the built-in GAP named constructions?  Again, I'm just interested right now about simpler matrix groups, not the classical groups like GL(), PSL(), etc.

Thanks,
Rob

[Dima Pasechnik]

On Thursday, 19 July 2012 08:13:04 UTC+8, Rob Beezer wrote:

I'm working (along with a summer research student) to expand the collection of small groups (and their representations) in Sage.  A question about matrix groups, as built by GAP for Sage.

For small, not-very-sophisticated groups, such as a Dihedral group, is it preferable to concoct generators in Sage and use the generic MatrixGroup() constructor or use a GAP routine to build the group?

A simple example:

GAP:  Wrap - "CyclicGroup( IsMatrixGroup, GF(2), 12 )"
  will build a matrix group of order 12 with matrices of size 12, over a few different types of fields.  This is about as much freedom as GAP allows.

Python:  Mythical - CyclicMatrixGroup(n, R, dimension=None)
  to build a cyclic group of order n over R, but where "dimension" could default to n, or be sum of invariants, or sum of prime powers, or 1 over the cyclotomic field.  Then an appropriate matrix could be created and sent to the MatrixGroup() (ideally as part of a class providing a sensible repr, etc.)

The second approach allows for a lot more flexibility in providing representations of different dimensions.

It looks like a hack. IMHO representations and groups themselves should not be mixed in one glass.

Moreover, your approach does not go far enough, as representations of Z_n might be quite exotic thing, as soon as n is divisible by 

the characteristic of the field R, or when R isn't a field any more...

(and even in characteristic 0, when your field does not contain the splitting field of the group, things are rather nontrivial, IMHO)

Dima

[Julien Puydt]

Le 19/07/2012 08:22, Dima Pasechnik a �crit :

> It looks like a hack. IMHO representations and groups themselves should
> not be mixed in one glass.

I agree on both points :
(1) mixing things in the same glass sometimes gives unwanted results ;
(2) putting both representations and groups in the same class doesn't
sound like a good idea.

Snark on #sagemath

PS: my favorite typo is when I want to have a look at a file and type
"mess filename" instead of "less filename"... it looks so like a
declaration of intention!

[Javier López Peña]

I understand that from some point of view mixing groups and 

their representations is a bad idea, but many groups are naturally

defined as transformation groups and using a matrix presentation 

is just as natural as describing them by permutations, or even more so. 

Not to mention the huge size some of the "constructions by 

permutations" have. 

For groups with a canonical matrix form I'd vote for the mythical 

python construction.  Surely everybody agrees PSL(2,16) 

has a "natural" presentation by 2x2 matrices over GF(16), and

there is no reason we shouldn't be able to use it.

But for groups where the matrix presentation is not canonical 

(eg the cyclic or dihedral groups) my vote is to construct them 

from the generators. 

Cheers,

J

On Thursday, July 19, 2012 7:29:57 AM UTC+1, Snark wrote:

Le 19/07/2012 08:22, Dima Pasechnik a �crit :

[Dima Pasechnik]

On Thursday, 19 July 2012 15:37:32 UTC+8, Javier López Peña wrote:

I understand that from some point of view mixing groups and 

their representations is a bad idea, but many groups are naturally

defined as transformation groups and using a matrix presentation 

is just as natural as describing them by permutations, or even more so. 

Not to mention the huge size some of the "constructions by 

permutations" have. 

let me nitpick first by saying that in group theory 

"presentation" means "presentation by generators and

relations" whereas you mean a (linear) "representation".

In this way of thinking, the most compact way to represent Z_n is by

generators and relations, i.e. Z_n=<a| a^n=1>.

But of course this requires quite a bit of machinery to be useful.

Z_n can also be naturally represented as a permutation group, with 

<(1,2,...,n)> the most straightforward one.

Already what GAP is doing is essentially constructing the permutation 

matrix from (1,2,...,n).

 

For groups with a canonical matrix form I'd vote for the mythical 

python construction.  Surely everybody agrees PSL(2,16) 

has a "natural" presentation by 2x2 matrices over GF(16), and

there is no reason we shouldn't be able to use it.

These are  typically available in GAP (and this in Sage) already.

GAP has all these GL, SL, SU, Sp, etc. e.g:

sage: gg=SU(5,2)

sage: print gg

Special Unitary Group of degree 5 over Finite Field of size 2

sage: gg.order()

13685760

Dima

[Simon King]

Hi!

On 2012-07-19, Dima Pasechnik <dim...@gmail.com> wrote:
> let me nitpick first by saying that in group theory=20

> "presentation" means "presentation by generators and
> relations" whereas you mean a (linear) "representation".
>
> In this way of thinking, the most compact way to represent Z_n is by

> generators and relations, i.e. Z_n=3D<a| a^n=3D1>.

> But of course this requires quite a bit of machinery to be useful.

> Z_n can also be naturally represented as a permutation group, with=20

><(1,2,...,n)> the most straightforward one.

To me, that sounds like we should use the "parents with multiple
realisations" (recently introduced by Nicolas) as a base class for
groups. In that way, we would have an abstract group, which would then
be able to provide different realisations of itself (as permutation group,
by different faithful linear representations, by a group presentation)
and transitions between different realisations.

Perhaps Nicolas can chime in...

Best regards,
Simon

[Nicolas Borie]

Le 19/07/2012 11:17, Simon King a �crit :

Hi all,

Currently, the most sophiticated example in Sage is probably the
Symmetric Functions. It is an abstract parent with no element class,
with no basis as free module. It is just an abstract Parent gluyng
differant realizations.

*************************************************************
sage: SF = SymmetricFunctions(QQ); SF
Symmetric Functions over Rational Field
sage: SF.category()
Join of Category of hopf algebras over Rational Field and Category of
graded algebras over Rational Field and Category of coalgebras over
Rational Field with realizations
sage: for pres in SF.realizations(): print pres
....:
Symmetric Function Algebra over Rational Field, Power symmetric
functions as basis
Symmetric Function Algebra over Rational Field, Homogeneous symmetric
functions as basis
Symmetric Function Algebra over Rational Field, Elementary symmetric
functions as basis
Symmetric Function Algebra over Rational Field, Schur symmetric
functions as basis
Symmetric Function Algebra over Rational Field, Monomial symmetric
functions as basis
sage: SF.basis()
Traceback (most recent call last):
...
AttributeError: 'SymmetricFunctions_with_category' object has no
attribute 'basis'
sage: SF.schur().basis()
Lazy family (Term map from Partitions to Symmetric Function Algebra over
Rational Field, Schur symmetric functions as basis(i))_{i in Partitions}
*************************************************************

Now, I am not sure but I really think the Realizations framework is
adapted to any kind of parent (Any Group should work fine...)

Here is the structure of the code to declare practical realizations of
an abstract parent.
**************************************************************
class MyAbstractParent(UniqueRepresentation, Parent):
def __init__(self, foo):
Parent.__init__(self, bla, category = (
cat1.WithRealizations(), cat2, cat3, ... ) )

def realization_as_bla(self):
return PracticalRealization1( good_args )

...

class PracticalRealization1(UniqueRepresentation, Parent):
def __init__(self, foo3):
Parent.__init__(self, bla2, category = (
Realizations(MyAbstractParent), cat4, cat5, ... ) )

...

class Element( Good_data_structure_class ):
...
**************************************************************

I don't really know what are the good pointers for the documentation.
One can read :
sage: Realizations??
sage: SymmetricFunctions??

As I am only a level 1 sage contributor with categories, I can't tell
you how to implement morphisms between the differents realizations. But
that's clearly the second step (and the interessting one!!). The
TestSuite is already aware of abstract parent and their different
realizations.

Hope that would help a little.
Best regards,
Nicolas B.

P.S. : Nicolas (Thi�ry) is probably not availlable for a time...

[Javier López Peña]

On Thursday, July 19, 2012 9:52:26 AM UTC+1, Dima Pasechnik wrote:

let me nitpick first by saying that in group theory 

"presentation" means "presentation by generators and

relations" whereas you mean a (linear) "representation".

Fine, maybe I should have use "realization" or "imploementation" instead. 

I didn't want to mix up "representation" in the group theory sense and in 

the "internal representation as a sage object" sense. 

 

In this way of thinking, the most compact way to represent Z_n is by

generators and relations, i.e. Z_n=<a| a^n=1>.

Agreed. There is a patch (#12339) bringing GAP's machinery for finitely 

presented groups to Sage, and I believe this should be the default 

implementation for groups defined by generators and relations unless 

there are severe performance issues, in which case an easy way to opt to

a more efficient implementation should be provided. 

 

Z_n can also be naturally represented as a permutation group, with 

<(1,2,...,n)> the most straightforward one.

Here I don't agree. There is nothing "natural" in the mathematical sense

(functorial, since you wanted to nitpick) in that representation. The closest

thing is to consider the Cayley representation of a (finite) group acting on

itself, but this is terribly inefficient and does not respect group homomorphisms.

Many groups are internally built in GAP/Sage by means of some "minimal" 

permutation representation even if they "naturally" are defined as

(quotients of) matrix groups, try to define PSL(2,7) and look at the 

generators to see what I mean.

I am not aware of an easy way of obtaining a sage version of those groups that

works with matrices; since I am currently performing some heavy 

computations involving simple groups of up to order 100000 I would 

certainly benefit from a faster/more efficient internal implementation than

the default one as groups of permutations. 

 

These are  typically available in GAP (and this in Sage) already.

GAP has all these GL, SL, SU, Sp, etc. e.g:

Full matrix groups are, simple groups of Lie type are internally constructed as 

permutation groups. I would like to have an option to see them as matrix groups.

Cheers

J

 

[Nathann Cohen]

(and if I may interrupt, we also really need to be able to deal with permutation groups on something *different* from 1...n, which is GAP's choice.
And I know that I am the first one to complain about labels instead of integers when it comes to a graph's vertices.
And I know that it is a nightmare to deal with it, everywhere in the code.
Please, don't remind me. I feel guilty already.

But it would be so nice to deal with permutation groups over anything...
I knew it would be a bad idea to interrupt anyway.

Have fuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuunnnnn !!! )

[Keshav Kini]

Wasn't this supposed to be implemented by trac #10335?
http://trac.sagemath.org/sage_trac/ticket/10335

-Keshav

----
Join us in #sagemath on irc.freenode.net !

[Nathann Cohen]

> Wasn't this supposed to be implemented by trac #10335?
> http://trac.sagemath.org/sage_trac/ticket/10335

Ahem :-P

Then it's just that Graph.automorphism_group does not know it. And it is trivial to update it then. Niiiiiiiiiiiiice !! And thanks for the tip !!

If nobody needs it before I will probably write the patch when I am back from traveling, something around mid september. Cool, Cool, Cool ! :-)

Nathann

[Keshav Kini]

Nathann Cohen <nathan...@gmail.com> writes:
>> Wasn't this supposed to be implemented by trac #10335?
>> http://trac.sagemath.org/sage_trac/ticket/10335
>
> Ahem :-P
>
> Then it's just that Graph.automorphism_group does not know it. And it
> is trivial to update it then. Niiiiiiiiiiiiice !! And thanks for the
> tip !!

Sure! I just dimly recalled we had applied such a patch to Sage 4.7 when
using it for an undergraduate class last fall, so I went and looked for
it to find the ticket number.

> If nobody needs it before I will probably write the patch when I am
> back from traveling, something around mid september. Cool, Cool, Cool
> ! :-)

Great! :)

[Rob Beezer]

Thanks everyone for your helpful posts, which came in overnight.

We have the classical groups (GL, SL,...) from GAP as groups of matrices (in a natural way) and we have the projective versions (PGL, PSL,...) from GAP as permutation groups.  Testing indicates you cannot switch it around (projective versions as matrices, plain versions as groups of matrices, from GAP).  Maybe GAP has an efficient conversion between the two implementations, but I'm not seeing it.  We have an interesting, but incomplete, collection of permutation groups.  So it seems that we have implementations tied tightly to the groups themselves right now.  I was suggesting loosening this up some (though that was not the point of my question).

Simon - I was not aware of "parents with multiple realisations", so I will pursue that.  Thanks, Little Nicolas, for the introduction.  It will be helpful as I am still at level 0.5 with categories.  (And I'm glad to see that *somebody* in France is working during the holiday season!)  Finally, Javier, I have not kept up with the group presentations ticket, which will be a great addition, so I'm glad to see that progressing.

Rob

[Rob Beezer]

On Thursday, July 19, 2012 8:47:20 AM UTC-7, Nathann Cohen wrote:

If nobody needs it before I will probably write the patch when I am back from traveling, something around mid september. Cool, Cool, Cool ! :-)

Dear Naaaaaaaaaaaaathan,

It'd sure be great to have automorphism groups of graphs start their symbol sets back at 0!  And perhaps optionally use vertex labels.

sage: G = SymmetricGroup([0, 1, 2]); G
Symmetric group of order 3! as a permutation group
sage: G.domain()
{0, 1, 2}
sage: G = SymmetricGroup(['dog', 'cat', 'fish']); G
Symmetric group of order 3! as a permutation group
sage: G.domain()
{'dog', 'cat', 'fish'}

I have not investigated the following yet.  I thought tuples being hashable was sufficient.

sage: G = SymmetricGroup([(1,0), (0,1)])
...
TypeError: not all arguments converted during string formatting

Rob
 

[Dima Pasechnik]

On Thursday, 19 July 2012 19:33:48 UTC+8, Javier López Peña wrote:

On Thursday, July 19, 2012 9:52:26 AM UTC+1, Dima Pasechnik wrote:

let me nitpick first by saying that in group theory 

"presentation" means "presentation by generators and

relations" whereas you mean a (linear) "representation".

Fine, maybe I should have use "realization" or "imploementation" instead. 

I didn't want to mix up "representation" in the group theory sense and in 

the "internal representation as a sage object" sense. 

 

In this way of thinking, the most compact way to represent Z_n is by

generators and relations, i.e. Z_n=<a| a^n=1>.

Agreed. There is a patch (#12339) bringing GAP's machinery for finitely 

presented groups to Sage, and I believe this should be the default 

implementation for groups defined by generators and relations unless 

there are severe performance issues, in which case an easy way to opt to

a more efficient implementation should be provided. 

when GAP works with these kinds of groups (any soluble group, in fact), 

it treats them as power-commutator presented groups.

This allows for relatively efficient procedures (many algorithmic problems, which are unsolvable 

for general  finitely presented groups, and solvable for power-commutator presented groups)

 

Z_n can also be naturally represented as a permutation group, with 

<(1,2,...,n)> the most straightforward one.

Here I don't agree. There is nothing "natural" in the mathematical sense

(functorial, since you wanted to nitpick) in that representation. The closest

thing is to consider the Cayley representation of a (finite) group acting on

itself, but this is terribly inefficient and does not respect group homomorphisms.

I didn't mean to use "natural" in categorical sense here.

 

Many groups are internally built in GAP/Sage by means of some "minimal" 

permutation representation even if they "naturally" are defined as

(quotients of) matrix groups, try to define PSL(2,7) and look at the 

generators to see what I mean.

sure, you'd get PSL as a permutation group. By you can get SL as a matrix group,

no problem about it.  

I am not aware of an easy way of obtaining a sage version of those groups that

works with matrices; since I am currently performing some heavy 

computations involving simple groups of up to order 100000 I would 

certainly benefit from a faster/more efficient internal implementation than

the default one as groups of permutations. 

just use matrix groups rather than projective groups...

 

 

These are  typically available in GAP (and this in Sage) already.

GAP has all these GL, SL, SU, Sp, etc. e.g:

Full matrix groups are, simple groups of Lie type are internally constructed as 

permutation groups.

Huh? I don't think you are right here.

Dima