Feeds:
Posts

## Hecke operators are also relative positions

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

Representation theory provides another interpretation of $G$-orbits on $X \times Y$ as follows. First, if $\mathbb{C}[X]$ is any permutation representation, then the $G$-fixed points $\mathbb{C}[X]^G$ have a natural basis given by summing over $G$-orbits. (This is a mild categorification of Burnside’s lemma.) Next, consider the representations $\mathbb{C}[X], \mathbb{C}[Y]$. Because $\mathbb{C}[X]$ is self-dual, we have

$\displaystyle \text{Hom}_G(\mathbb{C}[X], \mathbb{C}[Y]) \cong (\mathbb{C}[X] \otimes \mathbb{C}[Y])^G \cong \mathbb{C}[X \times Y]^G$

and hence $\text{Hom}_G(\mathbb{C}[X], \mathbb{C}[Y])$ has a natural basis given by summing over $G$-orbits of the action on $X \times Y$.

Definition: The $G$-morphism $\mathbb{C}[X] \to \mathbb{C}[Y]$ associated to a $G$-orbit of $X \times Y$ via the above isomorphisms is the Hecke operator associated to the $G$-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 $G$-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

$\displaystyle \text{Hom}_G(\mathbb{C}[X], \mathbb{C}[Y]) \cong (\mathbb{C}[X] \otimes \mathbb{C}[Y])^G$.

If $\sum c_{ij} x_i \otimes y_j \in \mathbb{C}[X] \otimes \mathbb{C}[Y]$ (where $x_i \in X, y_j \in Y$), then the self-duality of $\mathbb{C}[X]$ associates to it the linear map $\sum c_{ij} x_i^{\ast} \otimes y_j \in [\mathbb{C}[X], \mathbb{C}[Y]]$ (where $[-, -]$ denotes the internal hom), where $x_i^{\ast}$ is the linear map which takes value $1$ on $x_i$ and $0$ on any $x \neq x_i \in X$. The former is $G$-invariant iff the latter is a $G$-morphism.

So, consider a $G$-orbit (atomic relative position) $O \subseteq X \times Y$. Write $xRy$ for the corresponding $G$-invariant relation (hence $xRy = 1$ if $(x, y) \in O$ and $xRy = 0$ otherwise). Then the corresponding morphism $\mathbb{C}[X] \to \mathbb{C}[Y]$ takes the form

$\displaystyle \mathbb{C}[X] \ni x \mapsto \sum_{x R y} y \in \mathbb{C}[Y]$

and is extended by linearity from here.

Hecke operators don’t compose quite like the corresponding $G$-invariant relations compose: instead, we can think about a relation $R \subseteq X \times Y$ as describing a $|X| \times |Y|$ matrix of nonnegative integers, each of which happens to be $0$ or $1$, and composition of Hecke operators corresponds to multiplication of these matrices.

In the special case that $X = Y \cong G/H$, we get a natural basis for the algebra $\text{End}_G(\mathbb{C}[X])$ coming from $G$-orbits on $X \times X$. Said another way, we get a natural algebra structure on the free vector space $\mathbb{C}[H \backslash G/H]$. An algebra arising in this way is called a Hecke algebra. This construction is interesting because $H \backslash G/H$ does not itself have an algebra (e.g. monoid) structure in any obvious sense.

Some applications

If $\mathbb{C}[X] \cong \bigoplus_i n_i V_i$ is the irreducible composition of a permutation representation $\mathbb{C}[X]$, then we have

$\displaystyle \text{End}_G(\mathbb{C}[X]) \cong \prod_i M_{n_i}(\mathbb{C})$.

This has a number of useful corollaries.

Corollary: Let $X \cong G/H$ be transitive. Then

$\displaystyle \dim \text{End}_G(\mathbb{C}[X]) = \dim \mathbb{C}[H \backslash G/H] = \sum_i n_i^2$;

in words, the number of double cosets in $H \backslash G/H$ (atomic relative positions of $X$-figures and $X$-figures) is equal to the sum of squares of the multiplicities in the irreducible decomposition of $\mathbb{C}[X]$.

Corollary: $\mathbb{C}[X]$ decomposes into a direct sum of the trivial representation (corresponding to the map $\mathbb{C}[X] \to \mathbb{C}$ sending every $x \in X$ to $1$) and an irreducible representation iff there are exactly $2$ atomic relative positions iff the action of $G$ on $X$ is doubly transitive.

Corollary: $\mathbb{C}[X]$ is multiplicity free (each $n_i = 1$) iff the Hecke algebra $\mathbb{C}[H \backslash G/H]$ is commutative.

Example. Let $S_n$ act on $[n] = \{ 1, 2, \dots n \}$ in the usual way. The corresponding permutation representation $\mathbb{C}^n$ is the direct sum of the trivial representation and an irreducible representation because the action of $S_n$ on $[n]$ is doubly transitive: recall that this means precisely that there are two orbits of $S_n$ acting on $[n] \times [n]$, namely the diagonal and its complement.

In fact we can say more than this. The nontrivial Hecke operator $T : \mathbb{C}^n \to \mathbb{C}^n$ sends an element $x \in [n]$ to the sum of all $x' \neq x \in [n]$. The square of this operator satisfies

$\displaystyle T^2 = (n-2) T + (n-1)$

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

Example. Let $S_n$ act on $X_i = {[n] \choose i}$, by which we mean the set of $i$-element subsets of $[n]$, in the obvious way. This action is transitive with stabilizer $S_i \times S_{n-i}$. The corresponding permutation representation $\mathbb{C}[X_i]$ is the $i^{th}$ exterior power $\Lambda^i(\mathbb{C}^n)$ of the standard permutation representation. Since $X_i \cong X_{n-i}$, we will restrict our attention to the case that $i \le \frac{n}{2}$.

The possible Hecke operators $\mathbb{C}[X_i] \to \mathbb{C}[X_j]$ correspond to $S_n$-orbits of the action on $X_i \times X_j$ (pairs of an $i$-element subset and a $j$-element subset of $[n]$). Such an orbit is completely determined by the cardinality of the intersection of these subsets, which (when $i, j \le \frac{n}{2}$) can range from $0$ to $\text{min}(i, j)$. In other words, the relative position of two subsets of $[n]$ is the size of their intersection. Hence

$\displaystyle \dim \text{Hom}_G(\mathbb{C}[X_i], \mathbb{C}[X_j]) = \text{min}(i, j) + 1$.

In particular,

$\displaystyle \dim \text{End}_G(\mathbb{C}[X_i]) = i + 1$.

But more is true: $\text{End}_G(\mathbb{C}[X_i])$ is commutative. To see this it suffices to show that the Hecke operators $\mathbb{C}[X_i] \to \mathbb{C}[X_i]$ commute. Let $T_j$ denote the Hecke operator which sends an $i$-element subset to the sum over all $i$-element subsets sharing exactly $j$ elements with the original subset; that is, writing $S$ for an $i$-element subset, we have

$\displaystyle T_j(S) = \sum_{|S' \cap S| = j} S'$.

The key observation is that the relation $|S' \cap S| = j$ is symmetric in $S'$ and $S$. It follows that $T_j$ is self-adjoint with respect to the natural inner product on $\mathbb{C}[X_i]$. 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

$\displaystyle T_k T_j = (T_k T_j)^{\dagger} = T_j^{\dagger} T_k^{\dagger} = T_j T_k$

and all the Hecke operators commute. It follows that $\mathbb{C}[X_i]$ is multiplicity-free, and so must decompose as a direct sum of $i + 1$ nonisomorphic irreducible representations. This is worth summarizing.

Corollary (the Gelfand trick): If every $G$-orbit (atomic relative position) in $X \times X$ is symmetric, then the Hecke algebra $\text{End}_G(\mathbb{C}[X]) \cong \mathbb{C}[H \backslash G/H]$ is commutative, and hence $\mathbb{C}[X]$ 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 $T_i : \mathbb{C}[X_i] \to \mathbb{C}[X_{i+1}]$ sending an $i$-element subset $S$ to the sum over all $i+1$-element subsets $S'$ containing $S$, and if $i \le \frac{n-1}{2}$ then this Hecke operator is injective. Since $\mathbb{C}[X_i]$ has $i$ irreducible components and $\mathbb{C}[X_{i+1}]$ has $i+1$ irreducible components, the quotient $\mathbb{C}[X_{i+1}]/\mathbb{C}[X_i]$ is an irreducible representation of dimension

$\displaystyle {n \choose i+1} - {n \choose i}, i \le \frac{n-1}{2}$.

Example. The q-analogue of the above discussion involves taking $G = GL_n(\mathbb{F}_q)$ and $X_i$ to be the $G$-set of subspaces of $\mathbb{F}_q^n$ of dimension $i$. 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 $i$-dimensional and $j$-dimensional subspace, $i, j \le \frac{n}{2}$, this can range from $0$ to $\text{min}(i, j)$ as above. The rest of the above discussion also carries through with minimal modification, and we produce irreducible representations of $GL_n(\mathbb{F}_q)$ of dimension

$\displaystyle {n \choose i+1}_q - {n \choose i}_q, i \le \frac{n-1}{2}$

where ${n \choose i}_q$ is the q-binomial coefficient counting $i$-dimensional subspaces of $\mathbb{F}_q^n$.

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 $G$-sets and morphisms relative positions, in some sense, and the target of this functor should be $G$-representations.

Puzzle: How can this be made precise cleanly?