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
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.
|