Continuing yesterday’s story about relative positions, let be a finite group and let and be finite -sets. Yesterday we showed that -orbits on can be thought of as “atomic relative positions” of “-figures” and “-figures” in some geometry with symmetry group , and further that if and are transitive -sets then these can be identified with double cosets .

Representation theory provides another interpretation of -orbits on as follows. First, if is any permutation representation, then the -fixed points have a natural basis given by summing over -orbits. (This is a mild categorification of Burnside’s lemma.) Next, consider the representations . Because is self-dual, we have

and hence has a natural basis given by summing over -orbits of the action on .

**Definition:** The -morphism associated to a -orbit of via the above isomorphisms is the **Hecke operator** associated to the -orbit (relative position, double coset).

Below the fold we’ll write down some details about how this works and see how we can use the idea that -morphisms between permutations have a basis given by Hecke operators to work out, quickly and cleanly, how some permutation representations decompose into irreducibles. At the end we’ll state another puzzle.

**Some details**

Let’s be more explicit about the isomorphism

.

If (where ), then the self-duality of associates to it the linear map (where denotes the internal hom), where is the linear map which takes value on and on any . The former is -invariant iff the latter is a -morphism.

So, consider a -orbit (atomic relative position) . Write for the corresponding -invariant relation (hence if and otherwise). Then the corresponding morphism takes the form

and is extended by linearity from here.

Hecke operators don’t compose quite like the corresponding -invariant relations compose: instead, we can think about a relation as describing a matrix of nonnegative integers, each of which happens to be or , and composition of Hecke operators corresponds to multiplication of these matrices.

In the special case that , we get a natural basis for the algebra coming from -orbits on . Said another way, we get a natural algebra structure on the free vector space . An algebra arising in this way is called a **Hecke algebra**. This construction is interesting because does not itself have an algebra (e.g. monoid) structure in any obvious sense.

**Some applications**

If is the irreducible composition of a permutation representation , then we have

.

This has a number of useful corollaries.

**Corollary:** Let be transitive. Then

;

in words, the number of double cosets in (atomic relative positions of -figures and -figures) is equal to the sum of squares of the multiplicities in the irreducible decomposition of .

**Corollary:** decomposes into a direct sum of the trivial representation (corresponding to the map sending every to ) and an irreducible representation iff there are exactly atomic relative positions iff the action of on is doubly transitive.

**Corollary:** is multiplicity free (each ) iff the Hecke algebra is commutative.

*Example.* Let act on in the usual way. The corresponding permutation representation is the direct sum of the trivial representation and an irreducible representation because the action of on is doubly transitive: recall that this means precisely that there are two orbits of acting on , namely the diagonal and its complement.

In fact we can say more than this. The nontrivial Hecke operator sends an element to the sum of all . The square of this operator satisfies

since, after applying twice, we either end up at some (which can happen in ways, one for each ) or back at (which can happen in ways, one for each ). Hence its only possible eigenvalues are and . The eigenspace is the irreducible representation of dimension , and the eigenspace is the trivial representation.

*Example.* Let act on , by which we mean the set of -element subsets of , in the obvious way. This action is transitive with stabilizer . The corresponding permutation representation is the exterior power of the standard permutation representation. Since , we will restrict our attention to the case that .

The possible Hecke operators correspond to -orbits of the action on (pairs of an -element subset and a -element subset of ). Such an orbit is completely determined by the cardinality of the intersection of these subsets, which (when ) can range from to . In other words, the relative position of two subsets of is the size of their intersection. Hence

.

In particular,

.

But more is true: is commutative. To see this it suffices to show that the Hecke operators commute. Let denote the Hecke operator which sends an -element subset to the sum over all -element subsets sharing exactly elements with the original subset; that is, writing for an -element subset, we have

.

The key observation is that the relation is symmetric in and . It follows that is self-adjoint with respect to the natural inner product on . But because the product of Hecke operators is a sum, with integer coefficients, of Hecke operators, any such product is also self-adjoint. (Note that this is certainly not true for general self-adjoint operators!) Hence

and all the Hecke operators commute. It follows that is multiplicity-free, and so must decompose as a direct sum of nonisomorphic irreducible representations. This is worth summarizing.

**Corollary (the Gelfand trick):** If every -orbit (atomic relative position) in is symmetric, then the Hecke algebra is commutative, and hence is multiplicity free.

This leads to the notion of a Gelfand pair.

But we can say even more than this. There is a Hecke operator sending an -element subset to the sum over all -element subsets containing , and if then this Hecke operator is injective. Since has irreducible components and has irreducible components, the quotient is an irreducible representation of dimension

.

*Example.* The q-analogue of the above discussion involves taking and to be the -set of subspaces of of dimension . Analogous to the relative position of two subsets being the size of the intersection, the relative position of two subspaces is the dimension of their intersection, and for an -dimensional and -dimensional subspace, , this can range from to as above. The rest of the above discussion also carries through with minimal modification, and we produce irreducible representations of of dimension

where is the q-binomial coefficient counting -dimensional subspaces of .

**A puzzle**

To a categorically minded person it’s very tempting to describe the relationship between relative positions and Hecke operators as a functor of some sort. The source of this functor should have objects finite -sets and morphisms relative positions, in some sense, and the target of this functor should be -representations.

**Puzzle:** How can this be made precise cleanly?

John Baez has written about the answer here and here (and probably elsewhere), but this should still be fun to think about if you happen not to have read the answer already.

## Leave a Reply