rep1.spad

)abbrev package REP1 RepresentationPackage1
++ Authors: Holger Gollan, Johannes Grabmeier, Thorsten Werther
++ Date Created: 12 September 1987
++ Basic Operations: antisymmetricTensors, symmetricTensors,
++   tensorProduct, permutationRepresentation
++ Related Constructors: RepresentationPackage1, Permutation
++ Also See: IrrRepSymNatPackage
++ AMS Classifications:
++ Keywords: representation, symmetrization, tensor product
++ 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:
++   RepresentationPackage1 provides functions for representation theory
++   for finite groups and algebras.
++   The package creates permutation representations and uses tensor products
++   and its symmetric and antisymmetric components to create new
++   representations of larger degree from given ones.
++   Note: instead of having parameters from \spadtype{Permutation}
++   this package allows list notation of permutations as well:
++   e.g. \spad{[1, 4, 3, 2]} denotes permutes 2 and 4 and fixes 1 and 3.

RepresentationPackage1(R) : public == private where

   R   : Ring
   OF    ==> OutputForm
   NNI   ==> NonNegativeInteger
   PI    ==> PositiveInteger
   I     ==> Integer
   L     ==> List
   M     ==> Matrix
   P     ==> Polynomial
   SM    ==> SquareMatrix
   V     ==> Vector
   ICF   ==> IntegerCombinatoricFunctions Integer
   SGCF  ==> SymmetricGroupCombinatoricFunctions
   PERM  ==> Permutation

   public ==> with

     if R has CommutativeRing then
       antisymmetricTensors : (M R, PI) ->  M R
         ++ antisymmetricTensors(a, n) applies to the square matrix
         ++ {\em a} the irreducible, polynomial representation of the
         ++ general linear group {\em GLm}, where m is the number of
         ++ rows of {\em a}, which corresponds to the partition
         ++ {\em (1, 1, ..., 1, 0, 0, ..., 0)} of n.
         ++ Error: if n is greater than m.
         ++ Note: this corresponds to the symmetrization of the representation
         ++ with the sign representation of the symmetric group {\em Sn}.
         ++ The carrier spaces of the representation are the antisymmetric
         ++ tensors of the n-fold tensor product.
       antisymmetricTensors : (L M R, PI) -> L M R
         ++ antisymmetricTensors(la, n) applies to each
         ++ m-by-m square matrix in
         ++ the list {\em la} the irreducible, polynomial representation
         ++ of the general linear group {\em GLm}
         ++ which corresponds
         ++ to the partition {\em (1, 1, ..., 1, 0, 0, ..., 0)} of n.
         ++ Error: if n is greater than m.
         ++ Note: this corresponds to the symmetrization of the representation
         ++ with the sign representation of the symmetric group {\em Sn}.
         ++ The carrier spaces of the representation are the antisymmetric
         ++ tensors of the n-fold tensor product.
     createGenericMatrix : NNI -> M P R
       ++ createGenericMatrix(m) creates a square matrix of dimension k
       ++ whose entry at the i-th row and j-th column is the
       ++ indeterminate {\em x[i, j]} (double subscripted).
     symmetricTensors : (M R, PI) -> M R
       ++ symmetricTensors(a, n) applies to the m-by-m
       ++ square matrix {\em a} the
       ++ irreducible, polynomial representation of the general linear
       ++ group {\em GLm}
       ++ which corresponds to the partition {\em (n, 0, ..., 0)} of n.
       ++ Error: if {\em a} is not a square matrix.
       ++ Note: this corresponds to the symmetrization of the representation
       ++ with the trivial representation of the symmetric group {\em Sn}.
       ++ The carrier spaces of the representation are the symmetric
       ++ tensors of the n-fold tensor product.
     symmetricTensors : (L M R, PI)  ->  L M R
       ++ symmetricTensors(la, n) applies to each m-by-m square matrix in the
       ++ list {\em la} the irreducible, polynomial representation
       ++ of the general linear group {\em GLm}
       ++ which corresponds
       ++ to the partition {\em (n, 0, ..., 0)} of n.
       ++ Error: if the matrices in {\em la} are not square matrices.
       ++ Note: this corresponds to the symmetrization of the representation
       ++ with the trivial representation of the symmetric group {\em Sn}.
       ++ The carrier spaces of the representation are the symmetric
       ++ tensors of the n-fold tensor product.
     tensorProduct : (M R, M R) -> M R
       ++ tensorProduct(a, b) calculates the Kronecker product
       ++ of the matrices {\em a} and b.
       ++ Note: if each matrix corresponds to a group representation
       ++ (repr. of  generators) of one group, then these matrices
       ++ correspond to the tensor product of the two representations.
     tensorProduct : (L M R, L M R) -> L M R
       ++ tensorProduct([a1, ..., ak], [b1, ..., bk]) calculates the list of
       ++ Kronecker products of the matrices {\em ai} and {\em bi}
       ++ for {1 <= i <= k}.
       ++ Note: If each list of matrices corresponds to a group representation
       ++ (repr. of generators) of one group, then these matrices
       ++ correspond to the tensor product of the two representations.
     tensorProduct : M R -> M R
       ++ tensorProduct(a) calculates the Kronecker product
       ++ of the matrix {\em a} with itself.
     tensorProduct : L M R -> L M R
       ++ tensorProduct([a1, ...ak]) calculates the list of
       ++ Kronecker products of each matrix {\em ai} with itself
       ++ for {1 <= i <= k}.
       ++ Note: If the list of matrices corresponds to a group representation
       ++ (repr. of generators) of one group, then these matrices correspond
       ++ to the tensor product of the representation with itself.
     permutationRepresentation : (PERM I, I) -> M I
       ++ permutationRepresentation(pi, n) returns the matrix
       ++ {\em (deltai, pi(i))} (Kronecker delta) for a permutation
       ++ {\em pi} of {\em {1, 2, ..., n}}.
     permutationRepresentation : L I -> M I
       ++ permutationRepresentation(pi, n) returns the matrix
       ++ {\em (deltai, pi(i))} (Kronecker delta) if the permutation
       ++ {\em pi} is in list notation and permutes {\em {1, 2, ..., n}}.
     permutationRepresentation : (L PERM I, I) -> L M I
       ++ permutationRepresentation([pi1, ..., pik], n) returns the list
       ++ of matrices {\em [(deltai, pi1(i)), ..., (deltai, pik(i))]}
       ++ (Kronecker delta) for the permutations {\em pi1, ..., pik}
       ++ of {\em {1, 2, ..., n}}.
     permutationRepresentation : L L I -> L M I
       ++ permutationRepresentation([pi1, ..., pik], n) returns the list
       ++ of matrices {\em [(deltai, pi1(i)), ..., (deltai, pik(i))]}
       ++ if the permutations {\em pi1}, ..., {\em pik} are in
       ++ list notation and are permuting {\em {1, 2, ..., n}}.

   private ==> add

     -- import of domains and packages

     import from OutputForm

     -- declaration of local functions:


     calcCoef : (L I, M I) -> I
       -- calcCoef(beta, C) calculates the term
       -- |S(beta) gamma S(alpha)| / |S(beta)|


     invContent : L I -> V I
       -- invContent(alpha) calculates the weak monoton function f with
       -- f : m -> n with invContent alpha. f is stored in the returned
       -- vector


     -- definition of local functions


     calcCoef(beta, C) ==
       prod : I := 1
       for i in 1..maxIndex beta repeat
         prod := prod * multinomial(beta(i), entries row(C, i))$ICF
       prod


     invContent(alpha) ==
       n : NNI := (+/alpha)::NNI
       f : V I  := new(n, 0)
       i : NNI := 1
       j : I   := - 1
       for og in alpha repeat
         j := j + 1
         for k in 1..og repeat
           f(i) := j
           i := i + 1
       f


     -- exported functions:



     if R has CommutativeRing then

         antisymmetricTensors(a : M R, k : PI) ==
             nr := nrows a
             nc := ncols a
             k = 1 => a
             k > min(nr, nc) =>
               error("second parameter for antisymmetricTensors is too large")
             mr := binomial(nr, k)$ICF
             mc := binomial(nc, k)$ICF
             ilr : L L I := [subSet(nr, k, i)$SGCF for i in 0..mr - 1]
             ilc : L L I := [subSet(nc, k, i)$SGCF for i in 0..mc - 1]
             b : M R   := zero(mr::NNI, mc::NNI)
             for i in 1..mr for lr in ilr repeat
                 for j in 1..mc for lt in ilc repeat
                     c : M R := zero(k, k)
                     for r in 1..k for rr in lr repeat
                         for t in 1..k for tt in lt repeat
                             setelt!(c, r, t, elt(a, 1 + rr, 1 + tt))
                     setelt!(b, i, j, determinant c)
             b


         antisymmetricTensors(la : L M R, k : PI) ==
             [antisymmetricTensors(ma, k) for ma in la]



     symmetricTensors(a : M R, n : PI) ==

         mr := nrows a
         mc := ncols a
         n = 1 => a

         dimr := (binomial(mr + n - 1, n)$ICF)::NNI
         dimc := (binomial(mc + n - 1, n)$ICF)::NNI
         c : M R := new(dimr, dimc, 0)
         f : V I := new(n, 0)
         g : V I := new(n, 0)
         nullMatrix : M I := new(1, 1, 0)
         colemanMatrix : M I

         for i in 1..dimr repeat
             -- unrankImproperPartitions1 starts counting from 0
             alpha := unrankImproperPartitions1(n, mr, i - 1)$SGCF
             f := invContent(alpha)
             for j in 1..dimc repeat
                 -- unrankImproperPartitions1 starts counting from 0
                 beta := unrankImproperPartitions1(n, mc, j - 1)$SGCF
                 g := invContent(beta)
                 colemanMatrix := nextColeman(alpha, beta, nullMatrix)$SGCF
                 while colemanMatrix ~= nullMatrix repeat
                     gamma := inverseColeman(alpha, beta, colemanMatrix)$SGCF
                     help : R := calcCoef(beta, colemanMatrix)::R
                     for k in 1..n repeat
                         help := help*a((1 + f(k))::NNI,
                                        (1 + g(gamma(k)))::NNI)
                     c(i, j) := c(i, j) + help
                     colemanMatrix := nextColeman(alpha, beta,
                                                  colemanMatrix)$SGCF
         c


     symmetricTensors(la : L M R, k : PI) ==
       [symmetricTensors (ma, k) for ma in la]


     tensorProduct(a : M R, b : M R) == kroneckerProduct(a, b)$M(R)

     tensorProduct (la : L M R, lb : L M R) ==
       [tensorProduct(la.i, lb.i) for i in 1..maxIndex la]


     tensorProduct(a : M R) == tensorProduct(a, a)

     tensorProduct(la : L M R) ==
       tensorProduct(la :: L M R, la :: L M R)

     permutationRepresentation (p : PERM I, n : I) ==
       -- permutations are assumed to permute {1, 2, ..., n}
       a : M I := zero(n :: NNI, n :: NNI)
       for i in 1..n repeat
          a(eval(p, i)$(PERM I), i) := 1
       a


     permutationRepresentation (p : L I) ==
       -- permutations are assumed to permute {1, 2, ..., n}
       n : I := #p
       a : M I := zero(n::NNI, n::NNI)
       for i in 1..n repeat
          a(p.i, i) := 1
       a


     permutationRepresentation(listperm : L PERM I, n : I) ==
       -- permutations are assumed to permute {1, 2, ..., n}
       [permutationRepresentation(perm, n) for perm in listperm]

     permutationRepresentation (listperm : L L I) ==
       -- permutations are assumed to permute {1, 2, ..., n}
       [permutationRepresentation perm for perm in listperm]

     createGenericMatrix(m) ==
       res : M P R := new(m, m, 0$(P R))
       for i in 1..m repeat
         for j in 1..m repeat
            iof : OF := coerce(i)$Integer
            jof : OF := coerce(j)$Integer
            le : L OF := cons(iof, list jof)
            sy : Symbol := subscript('x, le)$Symbol
            res(i, j) := (sy :: P R)
       res

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