aboutsummaryrefslogtreecommitdiff
path: root/src/algebra/irsn.spad.pamphlet
blob: 4cde0675b55bae2fffef263ad718b18bc8dfbbe7 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
\documentclass{article}
\usepackage{open-axiom}
\begin{document}
\title{\$SPAD/src/algebra irsn.spad}
\author{Johannes Grabmeier, Thorsten Werther}
\maketitle
\begin{abstract}
\end{abstract}
\eject
\tableofcontents
\eject
\section{package IRSN IrrRepSymNatPackage}
<<package IRSN IrrRepSymNatPackage>>=
)abbrev package IRSN IrrRepSymNatPackage
++ Authors: Johannes Grabmeier, Thorsten Werther
++ Date Created: 04 August 1988
++ Date Last Updated: 24 May 1991
++ Basic Operations: dimensionOfIrreducibleRepresentation
++   irreducibleRepresentation
++ Related Constructors: RepresentationTheoryPackage1
++   RepresentationTheoryPackage2
++ Also See: SymmetricGroupCombinatoricFunctions
++ AMS Classifications:
++ Keywords:
++ References:
++   G. James, A. Kerber: The Representation Theory of the Symmetric
++    Group. Encycl. of Math. and its Appl. Vol 16., Cambr. Univ Press 1981;
++   J. Grabmeier, A. Kerber: The Evaluation of Irreducible
++    Polynomial Representations of the General Linear Groups
++    and of the Unitary Groups over Fields of Characteristic 0,
++    Acta Appl. Math. 8 (1987), 271-291;
++   H. Gollan, J. Grabmeier: Algorithms in Representation Theory and
++    their Realization in the Computer Algebra System Scratchpad,
++    Bayreuther Mathematische Schriften, Heft 33, 1990, 1-23
++ Description:
++   IrrRepSymNatPackage contains functions for computing
++   the ordinary irreducible representations of symmetric groups on
++   n letters {\em {1,2,...,n}} in Young's natural form and their dimensions.
++   These representations can be labelled by number partitions of n,
++   i.e. a weakly decreasing sequence of integers summing up to n, e.g.
++   {\em [3,3,3,1]} labels an irreducible representation for n equals 10.
++   Note: whenever a \spadtype{List Integer} appears in a signature,
++   a partition required.
--   NOT TRUE in current system, but should:
--   also could be an element of \spadtype(Partition)

IrrRepSymNatPackage(): public == private where
  NNI   ==> NonNegativeInteger
  I     ==> Integer
  L     ==> List
  M     ==> Matrix
  V     ==> Vector
  B     ==> Boolean
  SGCF  ==> SymmetricGroupCombinatoricFunctions
  ICF   ==> IntegerCombinatoricFunctions Integer
  PP    ==> PartitionsAndPermutations
  PERM  ==> Permutation

  public ==> with

    dimensionOfIrreducibleRepresentation  : L I -> NNI
      ++ dimensionOfIrreducibleRepresentation(lambda) is the dimension
      ++ of the ordinary irreducible representation of the symmetric group
      ++ corresponding to {\em lambda}.
      ++ Note: the Robinson-Thrall hook formula is implemented.
    irreducibleRepresentation : (L I, PERM I) -> M I
      ++ irreducibleRepresentation(lambda,pi) is the irreducible representation
      ++ corresponding to partition {\em lambda} in Young's natural form of the
      ++ permutation {\em pi} in the symmetric group, whose elements permute
      ++ {\em {1,2,...,n}}.
    irreducibleRepresentation : L I -> L M I
      ++ irreducibleRepresentation(lambda) is the list of the two
      ++ irreducible representations corresponding to the partition {\em lambda}
      ++ in Young's natural form for the following two generators
      ++ of the symmetric group, whose elements permute
      ++ {\em {1,2,...,n}}, namely {\em (1 2)} (2-cycle) and
      ++ {\em (1 2 ... n)} (n-cycle).
    irreducibleRepresentation : (L I, L PERM I)  -> L M I
      ++ irreducibleRepresentation(lambda,listOfPerm) is the list of the
      ++ irreducible representations corresponding to {\em lambda}
      ++ in Young's natural form for the list of permutations
      ++ given by {\em listOfPerm}.

  private ==> add

    -- local variables
    oldlambda : L I  := nil$(L I)
    flambda   : NNI := 0           -- dimension of the irreducible repr.
    younglist : L M I := nil$(L M I)     -- list of all standard tableaus
    lprime    : L I  := nil$(L I)      -- conjugated partition of lambda
    n         : NNI := 0           -- concerning symmetric group S_n
    rows      : NNI := 0           -- # of rows of standard tableau
    columns   : NNI := 0           -- # of columns of standard tableau
    aId       : M I  := new(1,1,0)

    -- declaration of local functions

    aIdInverse : () -> Void
      -- computes aId, the inverse of the matrix
      -- (signum(k,l,id))_1 <= k,l <= flambda, where id
      -- denotes the identity permutation

    alreadyComputed? : L I -> Void
      -- test if the last calling of an exported function concerns
      -- the same partition lambda as the previous call

    listPermutation : PERM I -> L I   -- should be in Permutation
      -- converts a permutation pi into the list
      -- [pi(1),pi(2),..,pi(n)]

    signum : (NNI, NNI, L I) -> I
      -- if there exists a vertical permutation v of the tableau
      -- tl := pi o younglist(l) (l-th standard tableau)
      -- and a horizontal permutation h of the tableau
      -- tk := younglist(k) (k-th standard tableau)  such that
      --                v o tl = h o tk,
      -- then
      --            signum(k,l,pi) = sign(v),
      -- otherwise
      --            signum(k,l,pi) = 0.

    sumPartition : L I -> NNI
      -- checks if lambda is a proper partition and results in
      -- the sum of the entries

    testPermutation : L I -> NNI
      -- testPermutation(pi) checks if pi is an element of S_n,
      -- the set of permutations of the set {1,2,...,n}.
      -- If not, an error message will occur, if yes it replies n.


    -- definition of local functions


    aIdInverse() ==

      aId := new(flambda,flambda,0)
      for k in 1..flambda repeat
        aId(k,k) := 1
      if n < 5 then return aId

      idperm      : L I  := nil$(L I)
      for k in n..1 by -1 repeat
        idperm := cons(k,idperm)
      for k in 1..(flambda-1) repeat
        for l in (k+1)..flambda repeat
          aId(k::NNI,l::NNI) := signum(k::NNI,l::NNI,idperm)

      -- invert the upper triangular matrix aId
      for j in flambda..2 by -1 repeat
        for i in (j-1)..1 by -1 repeat
          aId(i::NNI,j:NNI) := -aId(i::NNI,j::NNI)
        for k in (j+1)..flambda repeat
          for i in (j-1)..1 by -1 repeat
            aId(i::NNI,k:NNI) := aId(i::NNI,k::NNI) +
                aId(i::NNI,j:NNI) * aId(j::NNI,k::NNI)


    alreadyComputed?(lambda) ==
      if not(lambda = oldlambda) then
        oldlambda := lambda
        lprime    := conjugate(lambda)$PP
        rows      := (first(lprime)$(L I))::NNI
        columns   := (first(lambda)$(L I))::NNI
        n         := (+/lambda)::NNI
        younglist := listYoungTableaus(lambda)$SGCF
        flambda   := #younglist
        aIdInverse()        -- side effect: creates actual aId

    listPermutation(pi) ==
      li : L I := nil$(L I)
      for k in n..1 by -1 repeat
        li := cons(eval(pi,k)$(PERM I),li)
      li

    signum(numberOfRowTableau, numberOfColumnTableau,pi) ==

      rowtab : M I  := copy younglist numberOfRowTableau
      columntab : M I  := copy younglist numberOfColumnTableau
      swap : I
      sign : I   := 1
      end  : B   := false
      endk : B
      ctrl : B

      -- k-loop for all rows of tableau rowtab
      k    : NNI := 1
      while (k <= rows) and (not end) repeat
        -- l-loop along the k-th row of rowtab
        l : NNI := 1
        while (l <= oldlambda(k)) and (not end) repeat
          z : NNI := l
          endk := false
          -- z-loop for k-th row of rowtab beginning at column l.
          -- test wether the entry rowtab(k,z) occurs in the l-th column
          -- beginning at row k of pi o columntab
          while (z <= oldlambda(k)) and (not endk) repeat
            s : NNI := k
            ctrl := true
            while ctrl repeat
              if (s <= lprime(l))
                then
                  if (1+rowtab(k,z) = pi(1+columntab(s,l)))
                  -- if entries in the tableaus were from 1,..,n, then
                  -- it should be ..columntab(s,l)... .
                    then ctrl := false
                    else s := s + 1
                else ctrl := false
            -- end of ctrl-loop
            endk := (s <= lprime(l)) -- same entry found ?
            if not endk
              then       -- try next entry
                z := z + 1
              else
                if k < s
                  then     -- verticalpermutation
                    sign := -sign
                    swap := columntab(s,l)
                    columntab(s,l) := columntab(k,l)
                    columntab(k,l) := swap
                if l < z
                  then     -- horizontalpermutation
                    swap := rowtab(k,z)
                    rowtab(k,z) := rowtab(k,l)
                    rowtab(k,l) := swap
              -- end of else
          -- end of z-loop
          if (z > oldlambda(k))  -- no coresponding entry found
            then
              sign := 0
              end := true
          l := l + 1
        -- end of l-loop
        k := k + 1
      -- end of k-loop

      sign


    sumPartition(lambda) ==
      ok   : B := true
      prev : I := first lambda
      sum  : I := 0
      for x in lambda repeat
        sum := sum + x
        ok := ok and (prev >= x)
        prev := x
      if not ok then
        error("No proper partition ")
      sum::NNI


    testPermutation(pi : L I) : NNI ==
      ok : B := true
      n  : I := 0
      for i in pi repeat
        if i > n then n  := i     -- find the largest entry n in pi
        if i < 1 then ok := false -- check whether there are entries < 1
      -- now n should be the number of permuted objects
      if (not (n=#pi)) or (not ok) then
        error("No permutation of 1,2,..,n")
      -- now we know that pi has n Elements ranging from 1 to n
      test : Vector(B) := new((n)::NNI,false)
      for i in pi repeat
        test(i) := true   -- this means that i occurs in pi
      if member?(false,test) then error("No permutation")  -- pi not surjective
      n::NNI


    -- definitions of exported functions


    dimensionOfIrreducibleRepresentation(lambda) ==
      nn : I :=  sumPartition(lambda)::I --also checks whether lambda
      dd : I := 1                        --is a partition
      lambdaprime : L I := conjugate(lambda)$PP
      -- run through all rows of the Youngtableau corr. to lambda
      for i in 1..lambdaprime.1 repeat
        -- run through all nodes in row i of the Youngtableau
        for j in 1..lambda.i repeat
            -- the hooklength of node (i,j) of the Youngtableau
            -- is the new factor, remember counting starts with 1
            dd := dd * (lambda.i + lambdaprime.j - i - j + 1)
      (factorial(nn)$ICF quo dd)::NNI


    irreducibleRepresentation(lambda:(L I),pi:(PERM I)) ==
      nn : NNI := sumPartition(lambda)
      alreadyComputed?(lambda)
      piList : L I := listPermutation pi
      if not (nn = testPermutation(piList)) then
        error("Partition and permutation are not consistent")
      aPi : M I := new(flambda,flambda,0)
      for k in 1..flambda repeat
        for l in 1..flambda repeat
          aPi(k,l) := signum(k,l,piList)
      aId * aPi


    irreducibleRepresentation(lambda) ==
      listperm : L PERM I := nil$(L PERM I)
      li       : L I  := nil$(L I)
      sumPartition(lambda)
      alreadyComputed?(lambda)
      listperm :=
        n = 1 =>  cons(1$(PERM I),listperm)
        n = 2 =>  cons(cycle([1,2])$(PERM I),listperm)
        -- the n-cycle (1,2,..,n) and the 2-cycle (1,2) generate S_n
        for k in n..1 by -1 repeat
          li := cons(k,li)  -- becomes n-cycle (1,2,..,n)
        listperm := cons(cycle(li)$(PERM I),listperm)
        -- 2-cycle (1,2)
        cons(cycle([1,2])$(PERM I),listperm)
      irreducibleRepresentation(lambda,listperm)


    irreducibleRepresentation(lambda:(L I),listperm:(L PERM I)) ==
      sumPartition(lambda)
      alreadyComputed?(lambda)
      [irreducibleRepresentation(lambda, pi) for pi in listperm]

@
\section{License}
<<license>>=
--Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd.
--All rights reserved.
--
--Redistribution and use in source and binary forms, with or without
--modification, are permitted provided that the following conditions are
--met:
--
--    - Redistributions of source code must retain the above copyright
--      notice, this list of conditions and the following disclaimer.
--
--    - Redistributions in binary form must reproduce the above copyright
--      notice, this list of conditions and the following disclaimer in
--      the documentation and/or other materials provided with the
--      distribution.
--
--    - Neither the name of The Numerical ALgorithms Group Ltd. nor the
--      names of its contributors may be used to endorse or promote products
--      derived from this software without specific prior written permission.
--
--THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
--IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
--TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
--PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
--OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
--EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
--PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
--PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
--LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
--NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
--SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
@
<<*>>=
<<license>>

<<package IRSN IrrRepSymNatPackage>>
@
\eject
\begin{thebibliography}{99}
\bibitem{1} nothing
\end{thebibliography}
\end{document}