1)abbrev package REP1 RepresentationPackage1 2++ Authors: Holger Gollan, Johannes Grabmeier, Thorsten Werther 3++ Date Created: 12 September 1987 4++ Basic Operations: antisymmetricTensors, symmetricTensors, 5++ tensorProduct, permutationRepresentation 6++ Related Constructors: RepresentationPackage1, Permutation 7++ Also See: IrrRepSymNatPackage 8++ AMS Classifications: 9++ Keywords: representation, symmetrization, tensor product 10++ References: 11++ G. James, A. Kerber: The Representation Theory of the Symmetric 12++ Group. Encycl. of Math. and its Appl. Vol 16., Cambr. Univ Press 1981; 13++ J. Grabmeier, A. Kerber: The Evaluation of Irreducible 14++ Polynomial Representations of the General Linear Groups 15++ and of the Unitary Groups over Fields of Characteristic 0, 16++ Acta Appl. Math. 8 (1987), 271-291; 17++ H. Gollan, J. Grabmeier: Algorithms in Representation Theory and 18++ their Realization in the Computer Algebra System Scratchpad, 19++ Bayreuther Mathematische Schriften, Heft 33, 1990, 1-23 20++ Description: 21++ RepresentationPackage1 provides functions for representation theory 22++ for finite groups and algebras. 23++ The package creates permutation representations and uses tensor products 24++ and its symmetric and antisymmetric components to create new 25++ representations of larger degree from given ones. 26++ Note: instead of having parameters from \spadtype{Permutation} 27++ this package allows list notation of permutations as well: 28++ e.g. \spad{[1, 4, 3, 2]} denotes permutes 2 and 4 and fixes 1 and 3. 29 30RepresentationPackage1(R) : public == private where 31 32 R : Ring 33 OF ==> OutputForm 34 NNI ==> NonNegativeInteger 35 PI ==> PositiveInteger 36 I ==> Integer 37 L ==> List 38 M ==> Matrix 39 P ==> Polynomial 40 SM ==> SquareMatrix 41 V ==> Vector 42 ICF ==> IntegerCombinatoricFunctions Integer 43 SGCF ==> SymmetricGroupCombinatoricFunctions 44 PERM ==> Permutation 45 46 public ==> with 47 48 if R has CommutativeRing then 49 antisymmetricTensors : (M R, PI) -> M R 50 ++ antisymmetricTensors(a, n) applies to the square matrix 51 ++ {\em a} the irreducible, polynomial representation of the 52 ++ general linear group {\em GLm}, where m is the number of 53 ++ rows of {\em a}, which corresponds to the partition 54 ++ {\em (1, 1, ..., 1, 0, 0, ..., 0)} of n. 55 ++ Error: if n is greater than m. 56 ++ Note: this corresponds to the symmetrization of the representation 57 ++ with the sign representation of the symmetric group {\em Sn}. 58 ++ The carrier spaces of the representation are the antisymmetric 59 ++ tensors of the n-fold tensor product. 60 antisymmetricTensors : (L M R, PI) -> L M R 61 ++ antisymmetricTensors(la, n) applies to each 62 ++ m-by-m square matrix in 63 ++ the list {\em la} the irreducible, polynomial representation 64 ++ of the general linear group {\em GLm} 65 ++ which corresponds 66 ++ to the partition {\em (1, 1, ..., 1, 0, 0, ..., 0)} of n. 67 ++ Error: if n is greater than m. 68 ++ Note: this corresponds to the symmetrization of the representation 69 ++ with the sign representation of the symmetric group {\em Sn}. 70 ++ The carrier spaces of the representation are the antisymmetric 71 ++ tensors of the n-fold tensor product. 72 createGenericMatrix : NNI -> M P R 73 ++ createGenericMatrix(m) creates a square matrix of dimension k 74 ++ whose entry at the i-th row and j-th column is the 75 ++ indeterminate {\em x[i, j]} (double subscripted). 76 symmetricTensors : (M R, PI) -> M R 77 ++ symmetricTensors(a, n) applies to the m-by-m 78 ++ square matrix {\em a} the 79 ++ irreducible, polynomial representation of the general linear 80 ++ group {\em GLm} 81 ++ which corresponds to the partition {\em (n, 0, ..., 0)} of n. 82 ++ Error: if {\em a} is not a square matrix. 83 ++ Note: this corresponds to the symmetrization of the representation 84 ++ with the trivial representation of the symmetric group {\em Sn}. 85 ++ The carrier spaces of the representation are the symmetric 86 ++ tensors of the n-fold tensor product. 87 symmetricTensors : (L M R, PI) -> L M R 88 ++ symmetricTensors(la, n) applies to each m-by-m square matrix in the 89 ++ list {\em la} the irreducible, polynomial representation 90 ++ of the general linear group {\em GLm} 91 ++ which corresponds 92 ++ to the partition {\em (n, 0, ..., 0)} of n. 93 ++ Error: if the matrices in {\em la} are not square matrices. 94 ++ Note: this corresponds to the symmetrization of the representation 95 ++ with the trivial representation of the symmetric group {\em Sn}. 96 ++ The carrier spaces of the representation are the symmetric 97 ++ tensors of the n-fold tensor product. 98 tensorProduct : (M R, M R) -> M R 99 ++ tensorProduct(a, b) calculates the Kronecker product 100 ++ of the matrices {\em a} and b. 101 ++ Note: if each matrix corresponds to a group representation 102 ++ (repr. of generators) of one group, then these matrices 103 ++ correspond to the tensor product of the two representations. 104 tensorProduct : (L M R, L M R) -> L M R 105 ++ tensorProduct([a1, ..., ak], [b1, ..., bk]) calculates the list of 106 ++ Kronecker products of the matrices {\em ai} and {\em bi} 107 ++ for {1 <= i <= k}. 108 ++ Note: If each list of matrices corresponds to a group representation 109 ++ (repr. of generators) of one group, then these matrices 110 ++ correspond to the tensor product of the two representations. 111 tensorProduct : M R -> M R 112 ++ tensorProduct(a) calculates the Kronecker product 113 ++ of the matrix {\em a} with itself. 114 tensorProduct : L M R -> L M R 115 ++ tensorProduct([a1, ...ak]) calculates the list of 116 ++ Kronecker products of each matrix {\em ai} with itself 117 ++ for {1 <= i <= k}. 118 ++ Note: If the list of matrices corresponds to a group representation 119 ++ (repr. of generators) of one group, then these matrices correspond 120 ++ to the tensor product of the representation with itself. 121 permutationRepresentation : (PERM I, I) -> M I 122 ++ permutationRepresentation(pi, n) returns the matrix 123 ++ {\em (deltai, pi(i))} (Kronecker delta) for a permutation 124 ++ {\em pi} of {\em {1, 2, ..., n}}. 125 permutationRepresentation : L I -> M I 126 ++ permutationRepresentation(pi, n) returns the matrix 127 ++ {\em (deltai, pi(i))} (Kronecker delta) if the permutation 128 ++ {\em pi} is in list notation and permutes {\em {1, 2, ..., n}}. 129 permutationRepresentation : (L PERM I, I) -> L M I 130 ++ permutationRepresentation([pi1, ..., pik], n) returns the list 131 ++ of matrices {\em [(deltai, pi1(i)), ..., (deltai, pik(i))]} 132 ++ (Kronecker delta) for the permutations {\em pi1, ..., pik} 133 ++ of {\em {1, 2, ..., n}}. 134 permutationRepresentation : L L I -> L M I 135 ++ permutationRepresentation([pi1, ..., pik], n) returns the list 136 ++ of matrices {\em [(deltai, pi1(i)), ..., (deltai, pik(i))]} 137 ++ if the permutations {\em pi1}, ..., {\em pik} are in 138 ++ list notation and are permuting {\em {1, 2, ..., n}}. 139 140 private ==> add 141 142 -- import of domains and packages 143 144 import from OutputForm 145 146 -- declaration of local functions: 147 148 149 calcCoef : (L I, M I) -> I 150 -- calcCoef(beta, C) calculates the term 151 -- |S(beta) gamma S(alpha)| / |S(beta)| 152 153 154 invContent : L I -> V I 155 -- invContent(alpha) calculates the weak monoton function f with 156 -- f : m -> n with invContent alpha. f is stored in the returned 157 -- vector 158 159 160 -- definition of local functions 161 162 163 calcCoef(beta, C) == 164 prod : I := 1 165 for i in 1..maxIndex beta repeat 166 prod := prod * multinomial(beta(i), entries row(C, i))$ICF 167 prod 168 169 170 invContent(alpha) == 171 n : NNI := (+/alpha)::NNI 172 f : V I := new(n, 0) 173 i : NNI := 1 174 j : I := - 1 175 for og in alpha repeat 176 j := j + 1 177 for k in 1..og repeat 178 f(i) := j 179 i := i + 1 180 f 181 182 183 -- exported functions: 184 185 186 187 if R has CommutativeRing then 188 189 antisymmetricTensors(a : M R, k : PI) == 190 nr := nrows a 191 nc := ncols a 192 k = 1 => a 193 k > min(nr, nc) => 194 error("second parameter for antisymmetricTensors is too large") 195 mr := binomial(nr, k)$ICF 196 mc := binomial(nc, k)$ICF 197 ilr : L L I := [subSet(nr, k, i)$SGCF for i in 0..mr - 1] 198 ilc : L L I := [subSet(nc, k, i)$SGCF for i in 0..mc - 1] 199 b : M R := zero(mr::NNI, mc::NNI) 200 for i in 1..mr for lr in ilr repeat 201 for j in 1..mc for lt in ilc repeat 202 c : M R := zero(k, k) 203 for r in 1..k for rr in lr repeat 204 for t in 1..k for tt in lt repeat 205 setelt!(c, r, t, elt(a, 1 + rr, 1 + tt)) 206 setelt!(b, i, j, determinant c) 207 b 208 209 210 antisymmetricTensors(la : L M R, k : PI) == 211 [antisymmetricTensors(ma, k) for ma in la] 212 213 214 215 symmetricTensors(a : M R, n : PI) == 216 217 mr := nrows a 218 mc := ncols a 219 n = 1 => a 220 221 dimr := (binomial(mr + n - 1, n)$ICF)::NNI 222 dimc := (binomial(mc + n - 1, n)$ICF)::NNI 223 c : M R := new(dimr, dimc, 0) 224 f : V I := new(n, 0) 225 g : V I := new(n, 0) 226 nullMatrix : M I := new(1, 1, 0) 227 colemanMatrix : M I 228 229 for i in 1..dimr repeat 230 -- unrankImproperPartitions1 starts counting from 0 231 alpha := unrankImproperPartitions1(n, mr, i - 1)$SGCF 232 f := invContent(alpha) 233 for j in 1..dimc repeat 234 -- unrankImproperPartitions1 starts counting from 0 235 beta := unrankImproperPartitions1(n, mc, j - 1)$SGCF 236 g := invContent(beta) 237 colemanMatrix := nextColeman(alpha, beta, nullMatrix)$SGCF 238 while colemanMatrix ~= nullMatrix repeat 239 gamma := inverseColeman(alpha, beta, colemanMatrix)$SGCF 240 help : R := calcCoef(beta, colemanMatrix)::R 241 for k in 1..n repeat 242 help := help*a((1 + f(k))::NNI, 243 (1 + g(gamma(k)))::NNI) 244 c(i, j) := c(i, j) + help 245 colemanMatrix := nextColeman(alpha, beta, 246 colemanMatrix)$SGCF 247 c 248 249 250 symmetricTensors(la : L M R, k : PI) == 251 [symmetricTensors (ma, k) for ma in la] 252 253 254 tensorProduct(a : M R, b : M R) == kroneckerProduct(a, b)$M(R) 255 256 tensorProduct (la : L M R, lb : L M R) == 257 [tensorProduct(la.i, lb.i) for i in 1..maxIndex la] 258 259 260 tensorProduct(a : M R) == tensorProduct(a, a) 261 262 tensorProduct(la : L M R) == 263 tensorProduct(la :: L M R, la :: L M R) 264 265 permutationRepresentation (p : PERM I, n : I) == 266 -- permutations are assumed to permute {1, 2, ..., n} 267 a : M I := zero(n :: NNI, n :: NNI) 268 for i in 1..n repeat 269 a(eval(p, i)$(PERM I), i) := 1 270 a 271 272 273 permutationRepresentation (p : L I) == 274 -- permutations are assumed to permute {1, 2, ..., n} 275 n : I := #p 276 a : M I := zero(n::NNI, n::NNI) 277 for i in 1..n repeat 278 a(p.i, i) := 1 279 a 280 281 282 permutationRepresentation(listperm : L PERM I, n : I) == 283 -- permutations are assumed to permute {1, 2, ..., n} 284 [permutationRepresentation(perm, n) for perm in listperm] 285 286 permutationRepresentation (listperm : L L I) == 287 -- permutations are assumed to permute {1, 2, ..., n} 288 [permutationRepresentation perm for perm in listperm] 289 290 createGenericMatrix(m) == 291 res : M P R := new(m, m, 0$(P R)) 292 for i in 1..m repeat 293 for j in 1..m repeat 294 iof : OF := coerce(i)$Integer 295 jof : OF := coerce(j)$Integer 296 le : L OF := cons(iof, list jof) 297 sy : Symbol := subscript('x, le)$Symbol 298 res(i, j) := (sy :: P R) 299 res 300 301--Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd. 302--All rights reserved. 303-- 304--Redistribution and use in source and binary forms, with or without 305--modification, are permitted provided that the following conditions are 306--met: 307-- 308-- - Redistributions of source code must retain the above copyright 309-- notice, this list of conditions and the following disclaimer. 310-- 311-- - Redistributions in binary form must reproduce the above copyright 312-- notice, this list of conditions and the following disclaimer in 313-- the documentation and/or other materials provided with the 314-- distribution. 315-- 316-- - Neither the name of The Numerical ALgorithms Group Ltd. nor the 317-- names of its contributors may be used to endorse or promote products 318-- derived from this software without specific prior written permission. 319-- 320--THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS 321--IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 322--TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A 323--PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER 324--OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 325--EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 326--PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 327--PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 328--LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 329--NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 330--SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 331