GAP 3 Share Package "arep"

AREP: Abstract REPresentations

Share package since August 1998, communicated by Herbert Pahlings, Aachen.
This package has not yet been transferred to or replaced in GAP 4. You can use it only in GAP 3.

Authors

Sebastian Egner and Markus Püschel.

Implementation

Language: GAP 3 (includes a C program which speeds up some computations)
Operating system: Any
Current version: 1.0 (available from here)

Description

The package AREP was developed to create data structures and functions for the efficient calculation with group representations with special attention to permutation and monomial representations. The idea is to calculate with representations up to equality not only up to equivalence as it is usually done in representation theory. Furthermore we wanted to be able to create highly structured representations in GAP 3 as you do it on a piece of paper by writing e.g.

  R = (R1 innerTensorProduct R2) induction G, 

where R1, R2 are representations and G is a group. The representation R constructed this way should be kept this way; it should not be evaluated until you ask for it. In this sense we have implemented an infrastructure for representations. The more advanced part is given by functions which allow to transform a given representation. These functions are mostly decompositions in a certain sense. E.g. it is well known that every transitive monomial representation of a group G is equivalent to an induction of a onedimensional representation of a subgroup H <= G. But how do you choose the subgroup, the transversal and the conjugation to obtain equality? This problem is solved by the function TransitiveToInductionMonRep (in lib/arepfcts.g) which transforms a given transitive monomial rep R into the form

  R = (L induction_By_T G)^D, 

where L is a onedimensional rep of a subgroup. A more sophisticated function for constructively decomposing a given representation is the function DecompositionMonRep (in lib/arepfcts.g) which decomposes a monomial rep R into a conjugated direct sum of irreducibles of the form

R = (R1 directSum R2 ... Rk)^A

where Ri, i = 1..k are irreducible and the (inverted) decomposition matrix A is explicitly given, even in a highly structured form!

A striking application of constructive representation theory is the decomposition of matrices with symmetry. This technique allows to explain and generate a lot of classical fast signal transforms. The original idea is due to Minkwitz and was further developed by the authors.

Abstractly, a symmetry of a given matrix M is given by a pair (R1, R2) of representations of the same group G, such that

  R1(g) * M = M * R2(g) for all g in G. 

If R1 and R2 both are permutation representations we call the symmetry Perm-Perm-Symmetry. Mon-Mon-Symmetry is defined analogous. Functions to determine the symmetry of a given matrix can be found in lib/symmetry.g. If a matrix possesses symmetry of the types above, it can be decomposed into a product of sparse matrices (see [2], [3]). Functions implementing this idea can be found in algogen.g allowing to generate wellknown fast signal transforms such as Cooley-Tukey-FFT, Rader-FFT, Fast Cosine Transforms, and others in an automatic way. In order for you to get a better impression of what AREP can do and can not do we have prepared some examples for you (see: Documentation and Examples). These examples are ordered according to the library files. Every GAP 3 file in the library lib/ contains a short documentation including the specification of all important functions. This documentation can be accessed by extracting all lines beginning with: #F. For example, on a UNIX system

  cd lib/
  grep #F complex.g
  

tells you about the functions in 'complex.g'. We recommend to extract these documentations before you proceed with the examples below.

Manual

An AREP manual is available as dvi, or pdf, or postscript file.

Contact addresses

Sebastian Egner
Philips Research Labs
Prof. Holstlaan 4
Eindhoven, 5656 AA
Netherlands
email: sebastian.egner@philips.com

Markus Püschel
Research Faculty, Electrical and Computer Engineering
Carnegie Mellon University
Pittsburgh,
USA
email: pueschel@ece.cmu.edu

Steve Linton
School of Computer Science
University of St. Andrews
The North Haugh
St. Andrews, Fife, KY16 9SS
UK
email: sal@dcs.st-and.ac.uk