Computer package for representation theory of the symmetric group - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T13:40:54Z http://mathoverflow.net/feeds/question/96705 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/96705/computer-package-for-representation-theory-of-the-symmetric-group Computer package for representation theory of the symmetric group Melanie Matchett Wood 2012-05-11T20:29:27Z 2012-05-17T01:32:38Z <p>Is there a computer algebra package in which I can compute the following for representations of a specific symmetric group (e.g. $S_7$):</p> <p>(1) $V \otimes W$</p> <p>(2) $S_\lambda V$, where $S_\lambda$ is a Schur functor, or even just $\wedge^s V$,</p> <p>where $V$ and $W$ are input as sums of irreducible representations, i.e. by partitions with coefficients, and output in the same format? </p> http://mathoverflow.net/questions/96705/computer-package-for-representation-theory-of-the-symmetric-group/96707#96707 Answer by Wouter Meeussen for Computer package for representation theory of the symmetric group Wouter Meeussen 2012-05-11T20:56:01Z 2012-05-11T20:56:01Z <p>If you have access to Mathematica, then the functions in <a href="http://users.telenet.be/Wouter.Meeussen/ToolBox.nb" rel="nofollow">http://users.telenet.be/Wouter.Meeussen/ToolBox.nb</a> might be of use.</p> http://mathoverflow.net/questions/96705/computer-package-for-representation-theory-of-the-symmetric-group/96708#96708 Answer by Alexander Woo for Computer package for representation theory of the symmetric group Alexander Woo 2012-05-11T21:04:11Z 2012-05-11T21:04:11Z <p>The combinatorics package in Sage should do these things, at least if you are just interested in the decompositions into irreducibles and not actual matrices.</p> http://mathoverflow.net/questions/96705/computer-package-for-representation-theory-of-the-symmetric-group/96709#96709 Answer by Alexander Woo for Computer package for representation theory of the symmetric group Alexander Woo 2012-05-11T21:05:11Z 2012-05-11T21:05:11Z <p>Another answer: John Stembridge's Maple code for dealing with Weyl groups may also have something along these lines.</p> http://mathoverflow.net/questions/96705/computer-package-for-representation-theory-of-the-symmetric-group/96710#96710 Answer by Mark Wildon for Computer package for representation theory of the symmetric group Mark Wildon 2012-05-11T21:06:32Z 2012-05-12T01:02:55Z <p>Magma can be used to do (1) by taking products of characters, and (2) using the function 'Symmetrization', provided $|\lambda| \le 6$. In either case the output will be a character $\chi$ of a symmetric group. You can then write a short function that calculates all the inner products of $\chi$ with irreducible characters to get the answer in the form you want. The function 'SymmetricCharacter' returns the irreducible character labelled by a given partition.</p> <p><b>Edit:</b> Gap also has most of the required functions built-in. To generate the irreducible characters of $S_7$ use 'Irr(SymmetricGroup(7))'. You can then add and multiply characters to get the character of the tensor product of two representations of $S_7$. Then 'Symmetrizations(Irr(SymmetricGroup(7)),s)' computes $S_\lambda \chi$ for all irreducible characters of $S_7$ and all partitions $\lambda$ of $s$. This took almost no time to run, even for $s=10$, a case Magma fails on.</p> <p>I'm not sure if Gap provides any way to determine the partition labelling an irreducible character of $S_n$. Before 'SymmetricCharacter' was introduced in Magma, I used some code of my own to identify the labelling partition, by first looking at the degree (using the hook-formula), and then resolving any ambiguities using classical formulae for the values of symmetric group characters on cycles of short length. Please send me an email if you'd like more details. </p> http://mathoverflow.net/questions/96705/computer-package-for-representation-theory-of-the-symmetric-group/96713#96713 Answer by Natalie for Computer package for representation theory of the symmetric group Natalie 2012-05-11T21:20:32Z 2012-05-11T21:20:32Z <p>You could try GAP. This is far from being elegant, just if you are very desperate ;-)</p> <p>gap> g := SymmetricGroup(7);;</p> <p>gap> regmod := RegularModule(g,GF(19));;</p> <p>//This not elegant: I chose GF(11) to make the group ring semisimple (as if working over a field of characteristic 0. This is necessary here, as GAP uses the MeatAxe which needs finite fields). Moreover it would be better to get the simple constituents from another source than the regular module as the regular module soon gets too large in dimension. Maybe one could consider an action of $g$ on cosets of a subgroup where your simples of interest occur as composition factors. Ask for more details if you are interested. For $g=S_7$ this is too large to handle. So I take the natural PermutationModule, which has two constituents, a module of dimension 1 and a module of dimension 6.//</p> <p>gap> permod := PermutationGModule(g,GF(11));; </p> <p>gap> comps := MTX.CompositionFactors(permod);</p> <p>[ rec( field := GF(11), isMTXModule := true, dimension := 1, generators := [ [ [ Z(11)^0 ] ], [ [ Z(11)^0 ] ] ], smashMeataxe := rec( algebraElement := [ [ [ 1, 2 ], [ 3, 1 ] ], [ Z(11)^0, Z(11)^0, Z(11)^9, Z(11) ] ], algebraElementMatrix := [ [ Z(11)^5 ] ], characteristicPolynomial := x_1+Z(11)^0, charpolFactors := x_1+Z(11)^0, nullspaceVector := [ Z(11)^0 ], ndimFlag := 1 ), IsIrreducible := true ), rec( field := GF(11), isMTXModule := true, dimension := 6, generators := [ &lt; immutable compressed matrix 6x6 over GF(11) >, &lt; immutable compressed matrix 6x6 over GF(11) > ], smashMeataxe := rec( algebraElement := [ [ [ 2, 1 ], [ 2, 3 ] ], [ Z(11)^6, Z(11)^9, Z(11)^8, Z(11) ] ], algebraElementMatrix := &lt; immutable compressed matrix 6x6 over GF( 11) >, characteristicPolynomial := x_1^6+Z(11)^6*x_1^5+Z(11)^7*x_1^3+Z(11)^3*x_1^2+Z(11)^4*x_1+Z(11)^8, charpolFactors := x_1-Z(11)^0, nullspaceVector := [ Z(11), Z(11)^8, Z(11)^5, Z(11)^3, Z(11)^7, Z(11)^0 ], ndimFlag := 1 ), IsIrreducible := true ) ]</p> <p>gap> c1 := comps[1];;</p> <p>gap> c2 := comps[2];;</p> <p>gap> TensorProductGModule(c1,c2);</p> <p>rec( field := GF(19), isMTXModule := true, dimension := 6, generators := [ &lt; immutable compressed matrix 6x6 over GF(19) >, &lt; immutable compressed matrix 6x6 over GF(19) > ] ) gap> </p> <p>From this point on you can do whatever MTX in GAP allows you to do with modules. See also <a href="http://www.gap-system.org/Manuals/doc/htm/ref/CHAP067.htm#SSEC002.2" rel="nofollow">http://www.gap-system.org/Manuals/doc/htm/ref/CHAP067.htm#SSEC002.2</a> for more information on GAP.</p> http://mathoverflow.net/questions/96705/computer-package-for-representation-theory-of-the-symmetric-group/97161#97161 Answer by Ira Gessel for Computer package for representation theory of the symmetric group Ira Gessel 2012-05-16T22:10:14Z 2012-05-16T22:10:14Z <p>If I understand correctly, you can do the computation with symmetric functions using the operation of inner plethysm, which bears the same relationship to the internal, or Kronecker, product on symmetric functions that ordinary plethysm bears to ordinary multiplication of symmetric functions (and also makes the ring of symmetric functions with the internal product into a $\lambda$-ring). Inner plethysm is not as well known as it should be (I don't think it's mentioned in Macdonald's book), but the formulas for computing it aren't complicated:</p> <p>Using, for simplicity, the notation $f[g]$ for this operation, it's determined by the following:</p> <p>(1) for fixed $g$, the map $f\mapsto f[g]$ is a homorphism.</p> <p>(2) For a partition $\lambda$ of $n$ and an integer $k$, let $\lambda^k$ denote the cycle type of the $k$th power of a permutation with cycle type $\lambda$. Then $$p_k\left[\sum_{\lambda\vdash n}a_{\lambda}\frac{p_{\lambda}}{z_\lambda}\right] =\sum_{\lambda\vdash n}a_{\lambda^k}\frac{p_{\lambda}}{z_\lambda}$$ I don't think that inner plethysm is implemented in John Stembridge's SF package, but it will easily express Schur functions in terms of power sum symmetric functions and vice-versa, and computing inner plethysms with power sum symmetric functions isn't hard; if you know Maple, essentially all you need to do is write a function to compute $\lambda^k$. Then to compute the characteristic of $S_\lambda V$, all you need to do is compute the inner plethysm $s_\lambda[\text{ch } V]$.</p> http://mathoverflow.net/questions/96705/computer-package-for-representation-theory-of-the-symmetric-group/97176#97176 Answer by John Wiltshire-Gordon for Computer package for representation theory of the symmetric group John Wiltshire-Gordon 2012-05-17T01:32:38Z 2012-05-17T01:32:38Z <p>Here is the GAP code I use to do these computations:</p> <pre><code>SchurFunctorOfCharacter:=function(char,p) local n,t,c; if p=[] then return TrivialCharacter(UnderlyingCharacterTable(char)); fi; n:=Sum(p); t:=CharacterTable("Symmetric",n); c:=List(CharacterParameters(t),u-&gt;u[2]); return Symmetrizations([char],n)[Position(c,p)]; end;; CharacterFromPartition:=function(table,p) local c; c:=List(CharacterParameters(table),u-&gt;u[2]); return Irr(table)[Position(c,p)]; end;; DecomposeCharacter:=char-&gt;List(Irr(UnderlyingCharacterTable(char)),x-&gt;ScalarProduct(x,char));; t:=CharacterTable("Symmetric",7);; chi:=CharacterFromPartition(t,[3,3,1]);; DecomposeCharacter(SchurFunctorOfCharacter(chi,[1,1,1])); </code></pre> <p>This code computes the character table of $S_7$, finds the character corresponding to the partition $3+3+1$, and applies the Schur functor corresponding to the partition $1+1+1$ (otherwise known as $\wedge^3$). Here is the result:</p> <pre><code>[ 0, 1, 2, 4, 6, 9, 7, 4, 7, 9, 4, 2, 4, 1, 1 ] </code></pre> <p>These are the multiplicities of the irreducible constituents of our character. The ordering on partitions is lexicographic. For example, to determine the meaning of the $6$, just take the fifth partition of $7$:</p> <pre><code>Partitions(7)[5]; </code></pre> <p>The output shows that the coefficient $6$ appears before the L-shaped partition $3+1+1+1+1$:</p> <pre><code>[3,1,1,1,1] </code></pre>