1)abbrev package IRSN IrrRepSymNatPackage
2++ Authors: Johannes Grabmeier, Thorsten Werther
3++ Date Created: 04 August 1988
4++ Basic Operations: dimensionOfIrreducibleRepresentation
5++   irreducibleRepresentation
6++ Related Constructors: RepresentationTheoryPackage1
7++   RepresentationTheoryPackage2
8++ Also See: SymmetricGroupCombinatoricFunctions
9++ AMS Classifications:
10++ Keywords:
11++ References:
12++   G. James, A. Kerber: The Representation Theory of the Symmetric
13++    Group. Encycl. of Math. and its Appl. Vol 16., Cambr. Univ Press 1981;
14++   J. Grabmeier, A. Kerber: The Evaluation of Irreducible
15++    Polynomial Representations of the General Linear Groups
16++    and of the Unitary Groups over Fields of Characteristic 0,
17++    Acta Appl. Math. 8 (1987), 271-291;
18++   H. Gollan, J. Grabmeier: Algorithms in Representation Theory and
19++    their Realization in the Computer Algebra System Scratchpad,
20++    Bayreuther Mathematische Schriften, Heft 33, 1990, 1-23
21++ Description:
22++   IrrRepSymNatPackage contains functions for computing
23++   the ordinary irreducible representations of symmetric groups on
24++   n letters {\em {1, 2, ..., n}} in Young's natural form and their dimensions.
25++   These representations can be labelled by number partitions of n,
26++   i.e. a weakly decreasing sequence of integers summing up to n, e.g.
27++   {\em [3, 3, 3, 1]} labels an irreducible representation for n equals 10.
28++   Note: whenever a \spadtype{List Integer} appears in a signature,
29++   a partition required.
30--   NOT TRUE in current system, but should:
31--   also could be an element of \spadtype{Partition}
32
33IrrRepSymNatPackage() : public == private where
34  NNI   ==> NonNegativeInteger
35  I     ==> Integer
36  L     ==> List
37  M     ==> Matrix
38  V     ==> Vector
39  B     ==> Boolean
40  SGCF  ==> SymmetricGroupCombinatoricFunctions
41  ICF   ==> IntegerCombinatoricFunctions Integer
42  PP    ==> PartitionsAndPermutations
43  PERM  ==> Permutation
44
45  public ==> with
46
47    dimensionOfIrreducibleRepresentation  : L I -> NNI
48      ++ dimensionOfIrreducibleRepresentation(lambda) is the dimension
49      ++ of the ordinary irreducible representation of the symmetric group
50      ++ corresponding to {\em lambda}.
51      ++ Note: the Robinson-Thrall hook formula is implemented.
52    irreducibleRepresentation : (L I, PERM I) -> M I
53      ++ irreducibleRepresentation(lambda, pi) is the irreducible representation
54      ++ corresponding to partition {\em lambda} in Young's natural form of the
55      ++ permutation {\em pi} in the symmetric group, whose elements permute
56      ++ {\em {1, 2, ..., n}}.
57    irreducibleRepresentation : L I -> L M I
58      ++ irreducibleRepresentation(lambda) is the list of the two
59      ++ irreducible representations corresponding to the partition {\em lambda}
60      ++ in Young's natural form for the following two generators
61      ++ of the symmetric group, whose elements permute
62      ++ {\em {1, 2, ..., n}}, namely {\em (1 2)} (2-cycle) and
63      ++ {\em (1 2 ... n)} (n-cycle).
64    irreducibleRepresentation : (L I, L PERM I)  -> L M I
65      ++ irreducibleRepresentation(lambda, listOfPerm) is the list of the
66      ++ irreducible representations corresponding to {\em lambda}
67      ++ in Young's natural form for the list of permutations
68      ++ given by {\em listOfPerm}.
69
70  private ==> add
71
72    -- local variables
73    oldlambda : L I  := []
74    flambda   : NNI := 0           -- dimension of the irreducible repr.
75    younglist : L M I := []     -- list of all standard tableaus
76    lprime    : L I  := []     -- conjugated partition of lambda
77    n         : NNI := 0           -- concerning symmetric group S_n
78    rows      : NNI := 0           -- # of rows of standard tableau
79    columns   : NNI := 0           -- # of columns of standard tableau
80    aId       : M I  := new(1, 1, 0)
81
82    -- declaration of local functions
83
84    aIdInverse : () -> Void
85      -- computes aId, the inverse of the matrix
86      -- (signum(k, l, id))_1 <= k, l <= flambda, where id
87      -- denotes the identity permutation
88
89    alreadyComputed? : L I -> Void
90      -- test if the last calling of an exported function concerns
91      -- the same partition lambda as the previous call
92
93    listPermutation : PERM I -> L I   -- should be in Permutation
94      -- converts a permutation pi into the list
95      -- [pi(1), pi(2), .., pi(n)]
96
97    signum : (NNI, NNI, L I) -> I
98      -- if there exists a vertical permutation v of the tableau
99      -- tl := pi o younglist(l) (l-th standard tableau)
100      -- and a horizontal permutation h of the tableau
101      -- tk := younglist(k) (k-th standard tableau)  such that
102      --                v o tl = h o tk,
103      -- then
104      --            signum(k, l, pi) = sign(v),
105      -- otherwise
106      --            signum(k, l, pi) = 0.
107
108    sumPartition : L I -> NNI
109      -- checks if lambda is a proper partition and results in
110      -- the sum of the entries
111
112    testPermutation : L I -> NNI
113      -- testPermutation(pi) checks if pi is an element of S_n,
114      -- the set of permutations of the set {1, 2, ..., n}.
115      -- If not, an error message will occur, if yes it replies n.
116
117
118    -- definition of local functions
119
120
121    aIdInverse() ==
122
123      aId := new(flambda, flambda, 0)
124      for k in 1..flambda repeat
125        aId(k, k) := 1
126      if n < 5 then return aId
127
128      idperm      : L I  := []
129      for k in n..1 by -1 repeat
130        idperm := cons(k, idperm)
131      for k in 1..(flambda-1) repeat
132        for l in (k+1)..flambda repeat
133          aId(k::NNI, l::NNI) := signum(k::NNI, l::NNI, idperm)
134
135      -- invert the upper triangular matrix aId
136      for j in flambda..2 by -1 repeat
137        for i in (j-1)..1 by -1 repeat
138          aId(i::NNI, j::NNI) := -aId(i::NNI, j::NNI)
139        for k in (j+1)..flambda repeat
140          for i in (j-1)..1 by -1 repeat
141            aId(i::NNI, k::NNI) := aId(i::NNI, k::NNI) +
142                aId(i::NNI, j::NNI) * aId(j::NNI, k::NNI)
143
144
145    alreadyComputed?(lambda) ==
146      if not(lambda = oldlambda) then
147        oldlambda := lambda
148        lprime    := conjugate(lambda)$PP
149        rows      := (first(lprime)$(L I))::NNI
150        columns   := (first(lambda)$(L I))::NNI
151        n         := (+/lambda)::NNI
152        younglist := listYoungTableaus(lambda)$SGCF
153        flambda   := #younglist
154        aIdInverse()        -- side effect : creates actual aId
155
156    listPermutation(pi) ==
157      li : L I := []
158      for k in n..1 by -1 repeat
159        li := cons(eval(pi, k)$(PERM I), li)
160      li
161
162    signum(numberOfRowTableau, numberOfColumnTableau, pi) ==
163
164      rowtab : M I  := copy younglist numberOfRowTableau
165      columntab : M I  := copy younglist numberOfColumnTableau
166      swap : I
167      sign : I   := 1
168      end  : B   := false
169      endk : B
170      ctrl : B
171
172      -- k-loop for all rows of tableau rowtab
173      k    : NNI := 1
174      while (k <= rows) and (not end) repeat
175        -- l-loop along the k-th row of rowtab
176        l : NNI := 1
177        while (l <= oldlambda(k)) and (not end) repeat
178          z : NNI := l
179          endk := false
180          -- z-loop for k-th row of rowtab beginning at column l.
181          -- test whether the entry rowtab(k, z) occurs in the l-th column
182          -- beginning at row k of pi o columntab
183          while (z <= oldlambda(k)) and (not endk) repeat
184            s : NNI := k
185            ctrl := true
186            while ctrl repeat
187              if (s <= lprime(l))
188                then
189                  if (1+rowtab(k, z) = pi(1+columntab(s, l)))
190                  -- if entries in the tableaus were from 1, .., n, then
191                  -- it should be ..columntab(s, l)... .
192                    then ctrl := false
193                    else s := s + 1
194                else ctrl := false
195            -- end of ctrl-loop
196            endk := (s <= lprime(l)) -- same entry found ?
197            if not endk
198              then       -- try next entry
199                z := z + 1
200              else
201                if k < s
202                  then     -- verticalpermutation
203                    sign := -sign
204                    swap := columntab(s, l)
205                    columntab(s, l) := columntab(k, l)
206                    columntab(k, l) := swap
207                if l < z
208                  then     -- horizontalpermutation
209                    swap := rowtab(k, z)
210                    rowtab(k, z) := rowtab(k, l)
211                    rowtab(k, l) := swap
212              -- end of else
213          -- end of z-loop
214          if (z > oldlambda(k))  -- no corresponding entry found
215            then
216              sign := 0
217              end := true
218          l := l + 1
219        -- end of l-loop
220        k := k + 1
221      -- end of k-loop
222
223      sign
224
225
226    sumPartition(lambda) ==
227      ok   : B := true
228      prev : I := first lambda
229      sum  : I := 0
230      for x in lambda repeat
231        sum := sum + x
232        ok := ok and (prev >= x)
233        prev := x
234      if not ok then
235        error("No proper partition ")
236      sum::NNI
237
238
239    testPermutation(pi : L I) : NNI ==
240      ok : B := true
241      n  : I := 0
242      for i in pi repeat
243        if i > n then n  := i     -- find the largest entry n in pi
244        if i < 1 then ok := false -- check whether there are entries < 1
245      -- now n should be the number of permuted objects
246      if (not (n=#pi)) or (not ok) then
247        error("No permutation of 1,2,..,n")
248      -- now we know that pi has n Elements ranging from 1 to n
249      test : Vector(B) := new((n)::NNI, false)
250      for i in pi repeat
251        test(i) := true   -- this means that i occurs in pi
252      if member?(false,test) then error("No permutation")  -- pi not surjective
253      n::NNI
254
255
256    -- definitions of exported functions
257
258
259    dimensionOfIrreducibleRepresentation(lambda) ==
260      nn : I :=  sumPartition(lambda)::I --also checks whether lambda
261      dd : I := 1                        --is a partition
262      lambdaprime : L I := conjugate(lambda)$PP
263      -- run through all rows of the Youngtableau corr. to lambda
264      for i in 1..lambdaprime.1 repeat
265        -- run through all nodes in row i of the Youngtableau
266        for j in 1..lambda.i repeat
267            -- the hooklength of node (i, j) of the Youngtableau
268            -- is the new factor, remember counting starts with 1
269            dd := dd * (lambda.i + lambdaprime.j - i - j + 1)
270      (factorial(nn)$ICF quo dd)::NNI
271
272
273    irreducibleRepresentation(lambda : (L I), pi : (PERM I)) ==
274      nn : NNI := sumPartition(lambda)
275      alreadyComputed?(lambda)
276      piList : L I := listPermutation pi
277      if not (nn = testPermutation(piList)) then
278        error("Partition and permutation are not consistent")
279      aPi : M I := new(flambda, flambda, 0)
280      for k in 1..flambda repeat
281        for l in 1..flambda repeat
282          aPi(k, l) := signum(k, l, piList)
283      aId * aPi
284
285
286    irreducibleRepresentation(lambda) ==
287      listperm : L PERM I := []
288      li : L I  := []
289      sumPartition(lambda)
290      alreadyComputed?(lambda)
291      listperm :=
292        n = 1 =>  cons(1$(PERM I), listperm)
293        n = 2 =>  cons(cycle([1, 2])$(PERM I), listperm)
294        -- the n-cycle (1, 2, .., n) and the 2-cycle (1, 2) generate S_n
295        for k in n..1 by -1 repeat
296          li := cons(k, li)  -- becomes n-cycle (1, 2, .., n)
297        listperm := cons(cycle(li)$(PERM I), listperm)
298        -- 2-cycle (1, 2)
299        cons(cycle([1, 2])$(PERM I), listperm)
300      irreducibleRepresentation(lambda, listperm)
301
302
303    irreducibleRepresentation(lambda : (L I), listperm : (L PERM I)) ==
304      sumPartition(lambda)
305      alreadyComputed?(lambda)
306      [irreducibleRepresentation(lambda, pi) for pi in listperm]
307
308--Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd.
309--All rights reserved.
310--
311--Redistribution and use in source and binary forms, with or without
312--modification, are permitted provided that the following conditions are
313--met:
314--
315--    - Redistributions of source code must retain the above copyright
316--      notice, this list of conditions and the following disclaimer.
317--
318--    - Redistributions in binary form must reproduce the above copyright
319--      notice, this list of conditions and the following disclaimer in
320--      the documentation and/or other materials provided with the
321--      distribution.
322--
323--    - Neither the name of The Numerical ALgorithms Group Ltd. nor the
324--      names of its contributors may be used to endorse or promote products
325--      derived from this software without specific prior written permission.
326--
327--THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
328--IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
329--TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
330--PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
331--OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
332--EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
333--PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
334--PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
335--LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
336--NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
337--SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
338