path: root/src/algebra/irsn.spad.pamphlet

\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
  macro PI == PositiveInteger

  public ==> with

    dimensionOfIrreducibleRepresentation  : L PI -> 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 PI, 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 PI -> 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 PI, 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 PI  := nil$L(PI)
    flambda   : NNI := 0           -- dimension of the irreducible repr.
    younglist : L M I := nil$(L M I)     -- list of all standard tableaus
    lprime    : L PI  := nil$L(PI)      -- 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 PI -> 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.

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

    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 lambda ~= oldlambda then
        oldlambda := lambda
        lprime    := conjugate(lambda)$PP
        rows      := first(lprime)$L(PI)
        columns   := first(lambda)$L(PI)
        n         := +/lambda
        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(pi.k,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  : NNI := 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


    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 := 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 PI,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 PI,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}