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