Initial population.

1 files changed, 365 insertions, 0 deletions

diff --git a/src/algebra/irsn.spad.pamphlet b/src/algebra/irsn.spad.pamphlet
new file mode 100644
index 00000000..369e7fc8
--- /dev/null
+++ b/src/algebra/irsn.spad.pamphlet
@@ -0,0 +1,365 @@
+\documentclass{article}
+\usepackage{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}