Four flavors of Schur-Weyl duality

If is a finite-dimensional complex vector space, then the symmetric group naturally acts on the tensor power by permuting the factors. This action of commutes with the action of , so all permutations are morphisms of -representations. This defines a morphism , and a natural question to ask is whether this map is surjective.

Part of Schur-Weyl duality asserts that the answer is yes. The double commutant theorem plays an important role in the proof and also highlights an important corollary, namely that admits a canonical decomposition

where runs over partitions, are some irreducible representations of , and are the Specht modules, which describe all irreducible representations of . This gives a fundamental relationship between the representation theories of the general linear and symmetric groups; in particular, the assignment can be upgraded to a functor called a Schur functor, generalizing the construction of the exterior and symmetric products.

The proof below is more or less from Etingof’s notes on representation theory (Section 4.18). We will prove four versions of Schur-Weyl duality involving , and (in the special case that is a complex inner product space) .

Read Full Post »

Graded representation theory

Let be a group and let

be a graded representation of , i.e. a functor from to the category of graded vector spaces with each piece finite-dimensional. Thus acts on each graded piece individually, each of which is an ordinary finite-dimensional representation. We want to define a character associated to a graded representation, but if a character is to have any hope of uniquely describing a representation it must contain information about the character on every finite-dimensional piece simultaneously. The natural definition here is the graded trace

.

In particular, the graded trace of the identity is the graded dimension or Hilbert series of .

Classically a case of particular interest is when for some fixed representation , since is the symmetric algebra (in particular, commutative ring) of polynomial functions on invariant under . In the nicest cases (for example when is finite), is finitely generated, hence Noetherian, and is a variety which describes the quotient .

In a previous post we discussed instead the case where for some fixed representation , hence is the tensor algebra of functions on . I thought it might be interesting to discuss some generalities about these graded representations, so that’s what we’ll be doing today.

Read Full Post »

The Jacobi-Trudi identities

Today I’d like to introduce a totally explicit combinatorial definition of the Schur functions. Let be a partition. A semistandard Young tableau of shape is a filling of the Young diagram of with positive integers that are weakly increasing along rows and strictly increasing along columns. The weight of a tableau is defined as where is the total number of times appears in the tableau.

Definition 4:

where the sum is taken over all semistandard Young tableaux of shape .

As before we can readily verify that . This definition will allow us to deduce the Jacobi-Trudi identities for the Schur functions, which describe among other things the action of the fundamental involution . Since I’m trying to emphasize how many different ways there are to define the Schur functions, I’ll call these definitions instead of propositions.

Definition 5: .

Definition 6: .

Read Full Post »

The many faces of Schur functions

The last time we talked about symmetric functions, I asked whether the vector space could be turned into an algebra, i.e. equipped with a nice product. It turns out that the induced representation allows us to construct such a product as follows:

Given representations of , their tensor product is a representation of the direct product in a natural way. Now, injects naturally into , which gives a new representation

.

The character of this representation is called the induction product of the characters of , and with this product becomes a graded commutative algebra. (Commutativity and associativity are fairly straightforward to verify.) It now remains to answer the first question: does there exist an algebra homomorphism ? And can we describe the inner product on coming from the inner product on ?

To answer this question we’ll introduce perhaps the most important class of symmetric functions, the Schur functions .

N.B. I’ll be skipping even more proofs than usual today, partly because they require the development of a lot of machinery I haven’t described and partly because I don’t understand them all that well. Again, good references are Sagan or EC2.

Read Full Post »

Set-multiset duality and supervector spaces

Recall that the elementary symmetric functions generate the ring of symmetric functions as a module over any commutative ring . A corollary of this result, although I didn’t state it explicitly, is that the elementary symmetric functions are algebraically independent, hence any ring homomorphism from the symmetric functions is determined freely by the images of .

A particularly interesting choice of endomorphism occurs when we set . This endomorphism sends the generating function for the elementary symmetric polynomials to the generating function , and this is an involution – in other words, it follows that and itself must also be an involution on the ring of symmetric functions. Thus the elementary symmetric functions and complete homogeneous symmetric functions are dual in a very strong sense. This is closely related to the identity

and today I’d like to try to explain one interpretation of what’s going on that I learned from Todd Trimble, which is that “the exterior algebra is the symmetric algebra of a purely odd supervector space.”

Read Full Post »

Newton’s sums, necklace congruences, and zeta functions II

In a previous post I gave essentially the following definition: given a discrete dynamical system, i.e. a space and a function , and under the assumption that has a finite number of fixed points for all , we define the dynamical zeta function to be the formal power series

.

What I didn’t do was motivate this definition, mostly because I hadn’t really worked out the motivation myself. Now that we have an important special case worked out, we can discuss the general case, which will give a purely combinatorial proof of the second half of the Newton-Girard identities.

Read Full Post »

Newton’s sums, necklace congruences, and zeta functions

The goal of this post is to give a purely combinatorial proof of Newton’s sums which would have interrupted the flow of the previous post. Recall that, in the notation of the previous post, Newton’s sums (also known as the first Newton-Girard identity) state that

.

One way to motivate a combinatorial proof is to recast the generating function interpretation appropriately. Given a polynomial with non-negative integer coefficients and , let be the reciprocals of the roots of . Then

.

The left hand side of this identity suggests a particular interpretation in terms of the combinatorial species described by . Today we’ll describe this species when is a polynomial with non-negative integer coefficients and then describe it in the general case, which will handle the extension to the symmetric function case as well.

The method of proof used here is closely related to a post I made previously about the properties of the Frobenius map, and at the end of the post I’ll try to discuss what I think might be going on.

Read Full Post »

Introduction to symmetric functions

The theory of symmetric functions, which generalizes some ideas that came up in the previous discussion of Polya theory, can be motivated by thinking about polynomial functions of the roots of a monic polynomial . Problems on high school competitions often ask for the sum of the squares or the cubes of the roots of a given polynomial, and those not familiar with symmetric functions will often be surprised that these quantities end up being integers even though the roots themselves aren’t integers. The key is that the sums being asked for are always symmetric in the roots, i.e. invariant under an arbitrary permutation. The coefficients of a monic polynomial are the elementary symmetric polynomials of its roots, which we are given are integers. It follows that any symmetric polynomial that can be written using integer coefficients in terms of the elementary symmetric polynomials must in fact be an integer, and as we will see, every symmetric polynomial with integer coefficients has this property.

These ideas lead naturally to the use of symmetric polynomials in Galois theory, but combinatorialists are interested in symmetric functions for a very different reason involving the representation theory of . This post is a brief overview of the basic results of symmetric function theory relevant to combinatorialists. I’m mostly following Sagan, who recommends Macdonald as a more comprehensive reference.

Read Full Post »

GILA V: The Polya enumeration theorem and applications

I ended the last post by asking whether the proof of baby Polya extends to the multi-parameter setting where we want to keep track of how many of each color we use. In fact, it does. First, we should specify what exactly we’re trying to compute. Recall the setup: we have colors (represented by variables ), and we have a set of slots with acted on by a group where each slot will be assigned a color. Define to be the number of orbits of functions under the action of where color is used times. (Since the action of only permutes slots, it doesn’t change the multiset of colors used.) What we want to compute is the generating function

.

Note that setting we recover , which doesn’t contain information about particular color combinations. By the orbit-counting lemma, this is equivalent to computing

where we must now count fixed points in a weighted manner, recording the multiset of colors in each fixed point. How do we go about doing this?

Read Full Post »