The Mathematica Package PERMS

B. Fiedler
Eichelbaumstr. 13, D-04249 Leipzig
email: bfiedler@fiemath.de

March, 1999

1  General characteristics of PERMS

The program package PERMS, version 2.1 (15.1.1999)1 is a Mathematica-package. It is a collection of tools for investigations of permutation groups and for doing calculations in the representation theory of symmetric groups. These tools can be used together with the full power of the Mathematica-system. PERMS  runs under Mathematica 2.x [2] and 3.x [3]. It works without Mathematica frontends. Thus it can used without difficulties under all operating systems and on all machines for which Mathematica is available.

The present version makes available 187 tools which are collected in a context Perms`. In the next section we present a selection of 137 of these tools. All tools in Perms` are fitted out with help texts which can used by means of the help system of Mathematica. These texts are stored in the file usage.m (80197 Byte). Of course, a user can also work with all (internal) tools which are not contained in the context Perms` since all sources are accessible.

The following statistics characterize the files of PERMS:

files number name byte
source code 29 354279
data 3
ftdata.m 331766
chartab.m (small) 40221
chartab.m (full) 2324983

The file ftdata.m contains the precomputed data for the discrete Fourier transform. Character tables are stored in the files chartab.m. The user can choose between a small version of chartab.m which contains the character tables of S2 , ¼, S10 and a long version of chartab.m comprises the character tables of S2 , ¼, S17. We have observed the following costs for the load process of PERMS  under the conditions (1) in Section ..

memory
time for loading after loading
with small chartab.m 33.66 s 1921708 byte 1721012 byte
with full chartab.m 236.44 s 13549484 byte 7915796 byte

The long version of chartab.m has only to be loaded if values of characters of symmetric groups Sr with r > 10 are needed.

We do not store the original files chartab.m on the hard disk but compressed files which will be uncompressed during the load process. Under MS-Dos we use pkzip/pkunzip to this end. Only the use of such a compression utility has to be modified if a transfer of PERMS  to an other operating system is intended.

We have made many efforts to get a high working speed of PERMS. Since Mathematica uses an extensive set of rules to evaluate a given expression, it can happen that Mathematica makes unnecessary attempts to change an expression by means of rules which can be neglected or have no effect in the given situation. The reduction of the number of such superfluous attempts of evaluation is an important factor to increase the speed of a program. To achieve such a reduction, we have found out by the Mathematica-tool TraceDialog which single steps every PERMS-tool carries out during a run. Then we have modified the implementations of the PERMS-tools to eliminate unnecessary evaluation steps.

We have kept to a great extent the principle to omit any tests of the correctness of the input for the PERMS-tools. Thus a user has to make sure himself whether the input fulfils all conditions required by a tool. However, this principle also involves the advantage that the use of a PERMS-tool in a program package which calls very often this tool have more favourable costs in calculation time.

PERMS  uses own data types or types of expressions identified by the following heads:

head expression
GLoop loop in a Cayley graph
GWord word defined by a path of a Cayley graph
HoldList list of elements
Parti partition of a natural number
Perm permutation
Tableau Young frame or Young tableau
TabRow row of a Young tableau
Type type of a natural number

To all these heads the attribute HoldAll is assigned. This attribute causes that no subexpression of an expression with one of the above heads is automatically evaluated by Mathematica. An evaluation of such subexpressions is carried out only then if it is required by an instruction of PERMS. This helps to avoid unnecessary evaluations.

The use of the above own data types had a further favourable effect. PERMS turned out to be insensitive to modifications in Mathematica 3.x which are not compatible with the standard of Mathematica 2.x (see [3]). Mathematica can evaluate these data types only by means of rules from PERMS. We have not discovered up to now a rule of PERMS  which does not work correct under Mathematica 3.x. Our program does not use any Mathematica-tool from the list in [3]. An investigation (by means of TraceDialog) whether unnecessary evaluations again arise under Mathematica 3.x has not yet been carried out for all tools of PERMS.

2  A list of tools of PERMS

(i) Tools for the investigation of permutation groups

GeneratedGroup
determines all elements of the group G = áP ñ generated by a given set P Í Sr of permutations.
SymmetricGroup
determines the set of all elements of a symmetric group Sr of a given natural number r Î N.
Subgroup:
Let G be a permutation group and P be a property characterizing a subgroup H = { g Î G   |  P(g) = true }. Subgroup determines the set H and a set of generators of H.
Centralizer
determines the centralizer C (S) of a subset S Í G within a given permutation group G.
Normalizer
determines the normalizer N (S) of a subset S Í G within a given permutation group G.

Cayley graph and defining relations of a permutation group [1]

CayleyGraph
generates the Cayley graph G (G,S) of a small permutation group G with a given set S of generators.
PermPos
determines the position of a permutation p within a given set S Í Sr of permutations.
Perm2Node
determines the node in G(G,S) which represents a given permutation p Î G.
Node2Perm
determines the permutation p Î G which is represented by a given node of a Cayley graph G (G,S) of G.
EdgeValue:
If an edge (p1 , p2) of a Cayley graph G (G,S) is given, then the tool EdgeValue yields that generator s Î S which satisfies p2 = s °p1.
SpanningTree
determines a spanning tree T of a given Cayley graph G (G,S).
BackTraceST
determines the sequence of nodes which leads from the root id  to a given node p within a given spanning tree T of a Cayley graph G (G,S).
DepthST
yields the number of nodes within a longest path in a given spanning tree T from the root id  to a leaf of T.
TreeWord
yields the sequence of generators (word) which is given by the values of EdgeValue on the edges of a path from id  to a given node p within a given spanning tree T.
LoopCG:
Let T be a given spanning tree and (p1 , p2) be an edge of a given Cayley graph G (G,S). Then LoopCG yields the word w2-1 °s °w1 where wi : =  TreeWord[pi,T] and s : =  EdgeValue[p1 , p2].
SetOfDefiningRelations
determines a set of defining relations for given generators S of a permutation group G from a Cayley grapg G (G,S) and a spanning tree T of G (G,S) by colouring the Cayley graph (see [1]).

Cyclic extension method (see [1])

ZGenerators:
Let G be a permutation group. ZGenerators determines a generating element si for every cyclic subgroup Ci Í G of prime power order pini and forms the set Z of all these si.
TestElements
calculates the element sipi for every si Î Z. The tool NextLayer needs the sipi as test elements.
FirstLayer
determines layer 1 of the subgroup lattice of G. Layer 1 consists of all cyclic subgroups of G with prime order.
FirstGroups:
Let k be a given layer number. FirstGroups determines all cyclic subgroups ási ñ, si Î Z, which lie in the k-th layer. (Such a group has an order pini with ni = k.)
NextLayer:
If a permutation group G, the set Z and the (k-1)-th layer of the set of solvable subgroups of G are given, then NextLayer determines the k-th layer of solvalble subgroups of G.
LayerEmbedding:
Toll which is useful in the search of all subgroups of a full Sr. Assume that all layers of the subgroup lattice of Sr-1 are given. LayerEmbedding applies ClassesOfEmbeddedGroups to the k-th layer of Sr-1 and generates a subset of the k-th layer of Sr in this way.
CommutatorgroupLattice
calculates the commutator group G¢ of a given permutation group G and afterwards the lattice of all subgroups H with G¢ Í H Í G.
OneOrbit:
Let S be a given set of generators of a group G Í Sr and l Î {1 , ¼, r} be a given natural number. OneOrbit calculate the orbit lG : = { p(l)   |  p Î G } of l and a Schreier vector and a backward pointer list of lG relative to S.
AllOrbits:
Let S be a given set of generators of a group G Í Sr. AllOrbits determines all orbits of G, a Schreier vector and a backward pointer list relative to S.
SchreierTrace:
Let v be a given Schreier vector found by AllOrbits and l Î {1,¼,r} be a given point. SchreierTrace determines a permutation p Î G which fulfils l = p(l0) where l0 Î lG is the representative of lG defined by v.
CyclicGroup
determines the cyclic group áp ñ which is generated by a given permutation p.
CommutatorGroup
calculates the commutator group G¢ of a given permutation group G.
Stabilizer
yields the stabilizer GI : = { p Î G   |  " i Î I:  p(i) = i } of a given permutation group G Í Sr and a given point set I Í { 1 , ¼, r }.
ConjClass
calculates the conjugacy class of a given permutation p within a permutation group G which is defined by a given set S of generators.
AllConjClasses
determines all conjugacy classes of a given permutation group G with a given set S of generators of G.
SnConjClasses
determines all conjugacy classes of a given symmetric group Sr.
CardConjClass
calculates the cardinality of a conjucacy class of a Sr which is characterized by a type or a partition of r.
ConjClassPosNumbers
transforms every conjugacy class C Ì Sr into a a set { PermNumber[p]  |  p Î C } of position numbers (see description of PermNumber in (ii)).
AllConjugateGroups
determines all conjugate subgroups of a given subgroup H of a given permutation group G.
ClassesOfConjGroups:
Let { H1 , H2 , ¼} be a given list of subgroups of a given permutation group G. The tool determines all such classes of conjugate subgroups of G which contains at least one of the groups Hi.
ClassesOfEmbeddedGroups:
Let { H1 , H2 , ¼} be a set of subgroups of a Sr-1. The tool produces the natural embeddings Hi ® H¢i Í Sr of all Hi into Sr and applies ClassesOfConjGroups to the set { H¢1 , H¢2 , ¼}. (See Embedding.)
ClasslistToGrouplist
transforms a list of classes of conjugate groups into a simple list of the groups of these classes (a use of the Mathematica-tool Flatten).
Embedding
maps permutations p Î Sm onto permutations q Î Sn, m < n, according to the rule
q(i)
: =
ì
í
î
p(i - D) + D
if    D+ 1 £ i £ D+ m
i
else
where D is an integer with 0 £ D £ n - m which can be chosen by the user. If expr is an expression which contains permutations p Î Sn, then Embedding replaces all these permutations by their images in Sn. The tool Embedding is used in ClassesOfEmbeddedGroups with D = 0.
DirectProduct:
If G1 , G2 Í Sr are subgroups which fulfil the conditions of an internal direct product, then DirectProduct generates the set of the elements of G1 ×G2.
LeftCosets
If a permutation group G and a subgroup H Í G are given, then LeftCosets generates all left cosets of G relative to H.
LeftCosetReps
determines a set of representatives of the left cosets of a given permutation group G relative to a given subgroup H Í G.
RightCosets
If a permutation group G and a subgroup H Í G are given, then RightCosets generates all right cosets of G relative to H.
RightCosetReps
determines a set of representatives of the right cosets of a given permutation group G relative to a given subgroup H Í G.
Ord[p]
calculates the order of a given permutation p.
MaxOrder
determines max{ Ord[p]  |  p Î Sr } for a given symmetric group Sr.
FirstAppearance
yields the smallest number r Î N for which a given number k Î N occurs as order of an element p of the symmetric group Sr.
AllOrders
gives a list of all orders which occur among the elements of a given symmetric group Sr.
ModuloOrder:
If N Í G is a normal subgroup of a permutation group G and p Î G is an element from G, then ModuloOrder yields the order of the element p °N of the factor group G/N.
OrderSets
arranges the elements of a given permutation group G in subsets whose elements have the same order.
MaxOrderElements
yields the list of the elements with maximal order from a given permutation group G.
SmallGroupGenerators
determines a set of generators S for a given small permutation group G in the following way: If a subset S¢ of generators of G is already found, then the first element of the list G\áS¢ñ is choosen as further generator of G and added to S¢.
SmallGroupOrdGenerators
is a modification of SmallGroupGenerators: The tool chooses an element of maximal order from G\áS¢ñ as further generator of G.

(ii) Group ring tools

PermProd
calculates the product a1 ·a2 of two given group ring elements a1 , a2 Î C [Sr]. Especially, PermProd is used to determine the product p1 °p2 of two permutations p1 , p2 Î Sr in PERMS.
PermPower
calculates powers pk, k Î N, of a given permutation p.
InvPerm
calculates the inverse element p-1 of a given permutation p.
IdPerm
yields the identity element id  Î Sr of a given symmetric group Sr.
Commutator
calculates the commutator p °q °p-1 °q-1 of two given permutations p , q Î Sr.
PermNumber
determines the position (described by a natural number) of a given permutation p within the lexicographically ordered list of the elements of the symmetric group Sr which contains p.
Star[a]
calculates the element a* = åp Î Sr a(p) p-1 from a given group ring element a = åp Î Sr a(p) p Î C [Sr].
NumVal
replaces all coefficients of a given group ring element a Î C [Sr] by numerical approximate values of these coefficients. The user can choose the digit precision to which the tool calculates the aproximate values.
FirstPermutation
searches a given expression expr for permutations. If a permutation p is found within expr, then the search is stopped and p is returned.
FactorOfPerm
returns the coefficient a(p) which stand by a given permutation p within a given group ring element a = åp Î Sr a(p) p Î C [Sr].
AllFactors
returns the list of all coefficients a(p) of a given group ring element a = åp Î Sr a(p) p Î C [Sr].
ToMapping:
If a = åp Î Sr a(p) p Î C [Sr] is a given group ring element, then ToMapping produces a list2 A = { a1 , a2 , ¼, ar! } where ai = a(p) if i =  PermNumber[p]. This list A describes a mapping i ® ai.
Split:
If a group ring element a = åp Î Sr a(p) p Î C [Sr] is given, then Split produces the list of all permutations p within a and the list of all coefficients a(p) of a. The arrangements of the elements of these lists correspond to each other.
PermCollect
Let a Î C [Sr] be a given group ring element. PermCollect collects together terms of a that involve the same permutation p.
Support
yields the support { p Î Sr   |  a(p) ¹ 0 } of a given group ring element a Î C [Sr]. The result is an unsorted list of permutations which several times contains such permutations that repeatedly occur in a.
OrdSupport
yields the support of a given group ring element a. The result is an ordered list of permutations which contains no multiple elements.
Projection
determines the projection projM a = åp Î M a(p) p of a given group ring element a = åp Î Sr a(p) p onto a given set M Í Sr of permutations.
IsotropyGroup
determines the isotropy group Ca : = { p Î Sr   |  $ m(p) Î C :   p·a = m(p) a } of a given group ring element a Î C [Sr].
IsoHom:
Let a Î C [Sr] be a group ring element and p Î Ca be an element of the isotropy group of a. Then IsoHom yields that complex number m(p) Î C which fulfils p ·a = m(p) a.
KerIsoHom
determines the kernel kerm = { p Î Ca   |  m(p) = 1 } of the above Homomorphism m: Ca ® C belonging to the isotropy group of a given group ring element a Î C [Sr].
Char1Dat4IsoHom:
The above homomorphism m: Ca ® C is a 1-dimensinal character of Ca. The tool calculates the data {ker,reps,mus} from m where ker is the kernel of m, reps is a set of representatives of the cosets of Ca relative to ker and mus is a list of the values of m on the elements of reps. A structur {ker,reps,mus} is expected by PERMS for data of a 1-dimensional character.

(iii) Partitions, types, tableaux

AllPartitions
generates all partitions l |- r of a given natural number r Î N.
LongPartition
transforms the short form of a given partition l |- r into the long form of l.
ShortPartition
transforms the long form of a given partition l |- r into the short form of l.
MakePartition
determines the partition l |- r which belongs to a given Young tableau or Young frame.
Part2Type
transforms a given partition l |- r of a natural number r into a type r |-| r of r.
Type2Part
transforms a given type r |-| r of a natural number r into a partition l |- r of r.
AllTypes
determines all types r |-| r of a given natural number r Î N.
Perm2Part
calculates the cycle partition of a given permutation p.
PartMult
calculates the partition k l = (k l1 , k l2 , ¼), k Î N, from a given partition l = (l1 , l2 , ¼).
AllDecompositions
determines all decompositions q  | =  r of a given natural number r Î N.
MakeFrame
generates the Young frame [l] of a given partition l |- r. All boxes of [l] are filled with 0.
StandardTableaux
determines the set STl of all standard tableaux of a given partition l |- r.
FilledFrame
generates the lexicographically smallest standard tableau t Î STl of a given partition l |- r.
TransposeTableau
produces the transposed tableau of a given Young tableau.
DefTableau
tool which allows a convenient input of a Young tableau by hand.
YoungFactor
determines from a given partition l |- r that factor c Î Q which transforms every Young symmetrizer yt, t Î Tl, of l into an idempotent c yt.
PartDim
determines the dimension dimC [Sr]·yt of every left ideal C [Sr]·yt generated by a Young symmetrizer yt, t Î Tl, of a given partition l |- r by means of the hook length formula from l.
FrameDim
produces the same result as PartDim using a Young frame [l] or a Young tableau t Î Tl as input.
CombLemmaQ:
Let t1 , t2 Î Tl be two given Young tableaux of a partition l |- r. CombLemmaQ yields True if no column of t1 contains two numbers which lie in t2 in the same row. Otherwise, CombLemmaQ yields False. (Compare with the Combinatorial Lemma ..)
PTCompose
calculates the composition p °t of a given permutation p Î Sr and a given Young tableau t Î Tl, l |- r.
TransPerm:
Let t1 , t2 Î Tl be two given Young tableaux of a partition l |- r. TransPerm determines that permutation p Î Sr which fulfils t1 = p °t2.
DecomposedTransPerm
yields s =  TransPerm[t1 , t2] and the decomposition s = p °q of s with p Î Ht2, q Î Vt2.
AllTransPerms:
Let { t1 , t2 , ¼} be a given list of Young tableaux ti Î Tl of a partition l |- r. AllTransPerms calculates the list { s1 , s2 , ¼} of that permutations si Î Sr which fulfil ti = si °t1 for all i.

(iv) Special idempotents and generating elements

HorizontalPerms
generates the group Ht of all horizontal permutations of a given Young tableau t.
VerticalPerms
generates the group Vt of all vertical permutations of a given Young tableau t.
HorizontalSum
calculates the sum åp Î Ht p of all horizontal permutations of a given Young tableau t.
VerticalSum
calculates the alternating sum åq Î Vt c(q) q of all vertical permutations of a given Young tableau t. Here c(q) denotes the signature of q.
YoungSymmetrizer
determines the Young symmetrizer yt of a given Young tableau t.
CentralGenerator
determines the symmetrizer cl of an irreducible character cl of a symmetric group Sr (see Proposition .). The tool needs as input the list of all conjugacy classes of Sr and the partition l |- r that characterizes the character cl.
Char1Idempotent:
Let c be a 1-dimensional character of a permutation group G Í Sr. The tool yields the idempotent which is proportional to the symmetrizer of c.

Group ring elements3 connected with Solomon's algebra (see Section .)

LieXi[q]
calculates the element Xq of a given decomposition q  | =  r of a natural number r Î N.
LieOmegaProd
generates the element wq of a given decomposition q  | =  r.
LieOmega
calculates the element wq = Xq ·wq for a given decomposition q  | =  r.
NuFactor
calculates the number [1/ q?] from a given decomposition q  | =  r. The multiplication with [1/ q?] transforms wq into an idempotent nq = [1/ q?] wq.
LieNu[r]
calculates the idempotent nr = 1/r wr of a given natural number r Î N.
Char1LieZeta:
Let r Î N be a given natural number. The tool calculates the data of the 1-dimensional character f: (1  2 ¼r )k ® rk, r: = exp([(2pi)/ r]), of the cyclic group C = á(1  2 ¼r ) ñ (see Section .).
LieZeta
calculates the idempotent zr of a given natural number r Î N (see Section .).
TestIdempotent:
Let y Î C [Sr] be a Young symmetrizer and a Î C [Sr] be a group ring element with y ·a ¹ 0. The tool determines a generating idempotent of the minimal left ideal C [Sr] ·y ·a searching for a permutation p Î Sr with y ·a ·p ·y ¹ 0 (see Section .).

Tools, concerning tensor investigations

GenerateVTuples:
Let l , n Î N be given natural numbers and { i1 , ¼, is } be a finite sequence of narural numbers from { 1 , ¼, n }. The tool generates all sequences { m1 , m1 , m2 , m2 , ¼, ml , ml , i1 , ¼, is }, mk Î { 1 , ¼, n }, which represent tuples
b    =   (nm1 , nm1 , ¼, nml , nml , ni1 , ¼,nis )    Î   Bb0
of (basis) vectors from a vector space V where b0 = (ni1 , ¼, nis ) is a given subtuple.
MinimalGrouping:
Let { i1 , ¼, ir } be a sequence of natural numbers that represents a vector tuple b = ( ni1 , ¼, nir ) Î Br of basis vectors of a finite-dimensional vector space V. The tool determines that number sequence { j1 , ¼, jr } which corresponds to the smallest grouping ( nj1 , ¼, njr ) = ál; wi ñ of b. Furthermore, the tools calculates the grouping partition l = b  | and a permutation p which fulfils b = p ál; wi ñ.
GroupingData
Let Bb0 be a set of vector tuples represented by finite number sequences (see GenerateVTuples). The tool determines the sets Lb0 and Mb0 , l and returns
ì
í
î
ì
í
î
l, { (ál; wi ñ,aál; wi ñ)   |  ál; wi ñ Î Mb0 , l } ü
ý
þ
   ê
ê
  l Î Lb0 ü
ý
þ
(see Theorem in ). The minimal groupings ál; wi ñ are represented by finite number sequences, too. The mapping p required for the calculation of aál; wi ñ is given by the procedure MinimalGrouping.

(v) Characters, Littlewood-Richardson rule, plethysms

MurNak
Let l |- r be a partition characterizing an irreducible character cl of a symmetric group Sr and m |- r be a partition characterizing a conjugacy class of Sr. MurNak[l, m] calculates the value of cl on the class of m using the Murnaghan-Nakayama formula. If 2 £ r £  $CharTabLimit, then MurNak reads the values of characters from precomputed character tables.
CharTab[r]
is a variable which contains the character table of Sr.
TICharTab[r]
is a variable which contains the transposed inverse matrix of the matrix of the charactertable of Sr.
PartTab[r]
contains the list of all partitions l |- r of the natural number r Î N. This list is used to number the rows and columns of the matices CharTab[r] and TICharTab[r].
$CharTabLimit
is a system variable which contains the maximum of all natural numbers r ³ 1 for which data CharTab[r], TICharTab[r] and PartTab[r] exist in PERMS. Its present value is $CharTabLimit  = 17.
NextCharTab
is a tool which allows the user to calculate the data CharTab[r+1], TICharTab[r+1] and PartTab[r+1] with r =  $CharTabLimit and to add them to the system of precomputed data of PERMS.
Char1Data:
Let G be a permutation group and N Í G be a normal subgroup such that the factor group G/N is cyclic. Further let p Î G be a representative of a generator p °N of G/N. Then Char1Data[G , N , p] calculates the data {ker,reps,mus} (see Char1Dat4IsoHom) which describe the 1-dimensional character m: G ® C that fulfils m(p) = exp([(2pi)/ k]), k = |G/N|, and kerm = N.
Char1Value
Let dat = {ker,reps,mus} be the given data of a 1-dimensional character m of a permutation group G and p Î G be an element of G. Then Char1Value[p,dat] yields the value m(p).
Char1Multiplicity
Let dat = {ker,reps,mus} be the data of a 1-dimensional character m of a permutation group G Í Sr and l |- r be a partition which characterizes an irreducible character cl of Sr. Then Char1Multiplicity[l,dat] calculates the multiplicity ácl|G , mñG.
AllChar1Multiplicities
calculates all multiplicities ácl|G , mñG for a given 1-dimensional character m: G ® C and all irreducible characters cl of a given symmetric group Sr with G Í Sr.
InvChar1
replaces the values m1 , m2 , ¼ in the set mus  = { m1 , m2 , ¼} of the data {ker,reps,mus} of a 1-dimensional character m by [1/( m1)] , [1/( m2)] , ¼. Thus the character [1/( m)] = [`(m)] is obtained.
RLRule
calculates the Littlewood-Richardson product [l1][l2]¼[lk] of a given sequence of partitions li  |- ri. The first argument of the tool is allowed to be a linear combination åm |- r1 cm [m], cm Î N.
Plethysm
calculates the plethysm [m]Ä[n] of two irreducible representations [m] , [n] of symmetric groups Sm , Sn, respectively, using the formula of F. Sänger (see () and () in Chapter ).
IdPotCM
Let l = C [Sr]·e be a left ideal generated by a given idempotent e Î C [Sr] and C be the set of conjugacy classes of Sr. The tool calculates the values c(l) of the character c of the representation wSr|l and the multiplicities ml of the decomposition of l into minimal left ideals. For more details see Section ..
LongIdPotCM
is a modification of IdPotCM which works more efficiently than IdPotCM if e is a long idempotent. (See Section ..)

(vi) Discrete Fourier transform

FourierTransform
calculates the natural projection Dl(a) of the discrete Fourier transform D(a) defined by Young's natural representation of Sr where a Î C [Sr] is a given group ring element and l |- r is a given partition characterizing a minimal two-sided ideal al of C [Sr] (see Theorem .).
InvFourierTransform
Let l |- r be a partition and A Î Cnl×nl be a matrix with nl =  PartDim[l]. Then InvFourierTransform calculates (D|al)-1(A) by means of Fourier Inversion Formula () in Chap. where D is the discrete Fourier transform defined by Young's natural representation of Sr and al is the minimal two-sided ideal of C [Sr] characterized by l. If, further, a subset M Ì Sr of permutations is given, then InvFourierTransform calculates the projection projM (D|al)-1(A).
MakeFourierData
calculates the data sets Dt for all standard tableaux t Î STl of a given partition l |- r. These sets Dt are used by PERMS as precomputed data for the discrete Fourier transform. A user can extend the present system of such precomputed data by means of this tool.
FTData[r]
contains all precomputed data Dt for the Sr generated by means of MakeFourierData.
$FourierLimit
is a system variable that contains the greatest number r Î N for which precomputed data Dt exist and discrete Fourier transforms can be carried out by PERMS. Its present value is $FourierLimit  = 8.
MakeInvFourierData
calculates the set data  = { Dl(p-1)   |  p Î M } where M Í Sr is a given set of permutations and l |- r is a given partition. This set data can be used by DataInvFourierTransform to determine projM (D|al)-1(A).
DataInvFourierTransform
calculates projM (D|al)-1(A) for a given matrix A and a given permutation set M using a data set data which is generatet by means of MakeInvFourierData from M. The use of the pair MakeInvFourierData and DataInvFourierTransform works quicker than InvFourierTransform if projM (D|al)-1(A) has to be calculated for many matrices A since InvFourierTransform repeatedly determines the elements of data for every matrix A.

References

[1]
G. Butler. Fundamental Algorithms for Permutation Groups, volume 559 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, Heidelberg, New York, 1991.
 
[2]
Stephen Wolfram. Mathematica. Addison-Wesley, Bonn, München, Paris, Reading, Mass., 2. edition, 1992. In German.
 
[3]
Stephen Wolfram. Das Mathematica-Buch. Addison-Wesley-Longman, Bonn, Reading, Mass., Menlo Park, Cal., New York, Harlow, Don Mills, Sydney, Mexico City, Madrid, Amsterdam, 3. edition, 1997.
 

Footnotes:

1 Some examples in this paper were calculated by means of PERMS, version 2.1 (23.3.1998). The above newer version of PERMS  is identical with this older version up to the five tools GenerateVTuples, MinimalGroupings, GroupingData, MakeInvFourierData, DataInvFourierTransform which are added to PERMS  1999. No other tool of PERMS  calls these five tools. Thus all calculations which do not use one of these five tools have the same course under both versions.

2 The coefficient list generated by AllFactors contains only the non-vanishing coefficients of a.

3 Only a part of the following group ring elements are Lie idempotents or proportional to Lie idempotents. We have used the substring Lie in all names of these tools so that a user can easily find them by means of the help system of Mathematica entering ?Lie*.


File translated from TEX by TTH, version 2.10.
On 17 Jul 1999, 01:17.