axiom-source 20170501-3 / usr / share / axiom-20170501 / src / algebra / IRSN.spad

)abbrev package IRSN IrrRepSymNatPackage
++ Authors: Johannes Grabmeier, Thorsten Werther
++ Date Created: 04 August 1988
++ Date Last Updated: 24 May 1991
++ 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 {1,2,...,n} in Young's natural form and their dimensions.
++ These representations can be labelled by number partitions of n,
++ a weakly decreasing sequence of integers summing up to n, for
++ example, [3,3,3,1] labels an irreducible representation for n equals 10.
++ Note that 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() : SIG == CODE where

  NNI   ==> NonNegativeInteger
  I     ==> Integer
  L     ==> List
  M     ==> Matrix
  V     ==> Vector
  B     ==> Boolean
  SGCF  ==> SymmetricGroupCombinatoricFunctions
  ICF   ==> IntegerCombinatoricFunctions Integer
  PP    ==> PartitionsAndPermutations
  PERM  ==> Permutation

  SIG ==> with

    dimensionOfIrreducibleRepresentation  : L I -> NNI
      ++ dimensionOfIrreducibleRepresentation(lambda) is the dimension
      ++ of the ordinary irreducible representation of the symmetric group
      ++ corresponding to lambda.
      ++ Note that the Robinson-Thrall hook formula is implemented.

    irreducibleRepresentation : (L I, PERM I) -> M I
      ++ irreducibleRepresentation(lambda,pi) is the irreducible representation
      ++ corresponding to partition lambda in Young's natural form of the
      ++ permutation pi in the symmetric group, whose elements permute
      ++ {1,2,...,n}.

    irreducibleRepresentation : L I -> L M I
      ++ irreducibleRepresentation(lambda) is the list of the two
      ++ irreducible representations corresponding to the partition lambda
      ++ in Young's natural form for the following two generators
      ++ of the symmetric group, whose elements permute
      ++ {1,2,...,n}, namely (1 2) (2-cycle) and
      ++ (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 lambda
      ++ in Young's natural form for the list of permutations
      ++ given by listOfPerm.

  CODE ==> 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]