Walks on graphs and tensor products

March 7, 2010 by Qiaochu Yuan

Recently I asked a question on MO about some computations I’d done with Catalan numbers awhile ago on this blog, and Scott Morrison gave a beautiful answer explaining them in terms of quantum groups. Now, I don’t exactly know how quantum groups work, but along the way he described a useful connection between walks on graphs and tensor products of representations which at least partially explains one of the results I’d been wondering about and also unites several other related computations that have been on my mind recently.

Let $G$ be a compact group and let $\text{Rep}(G)$ denote the category of finite-dimensional unitary representations of $G$ . As in the finite case, due to the existence of Haar measure, $\text{Rep}(G)$ is semisimple (i.e. every unitary representation decomposes uniquely into a sum of irreducible representations), and via the diagonal action it comes equipped with a tensor product with the property that the character of the tensor product is the product of the characters of the factors.

Question: Fix a representation $V \in \text{Rep}(G)$ . What is the multiplicity of the trivial representation in $V^{\otimes n}$ ?

Answer 1

Let $\chi_V(g)$ be the character associated to $V$ . Then, again by the orthogonality relations, the multiplicity of the trivial representation in $V^{\otimes n}$ is

$\displaystyle \int_G \chi_V(g)^n \, d \mu$

where the integral is taken with respect to the normalized Haar measure. When $G$ is finite, the integral becomes a sum, from which it follows that the sequence of multiplicities of the trivial representation satisfies a linear recurrence with characteristic polynomial $\prod_G (x - \chi_V(g))$ .

When $G = SU(2)$ and $V$ is the defining representation on $\mathbb{C}^2$ , this integral becomes

$\displaystyle \int_0^1 (2 \cos \pi x)^n (2 \sin^2 \pi x) \, dx$

which, after a straightforward integral computation, is $0$ if $n$ is odd and the Catalan number $C_k$ if $n = 2k$ is even. When I first heard of this identity, I tried to explain it using a finite approximation, e.g. replacing the sum with an integral, and I obtained an expression that precisely counted the number of walks on a path graph from one end to itself, as described in my previous post on the subject. When the length of the path is long enough, the number of these walks approximate the Catalan numbers. Scott Morrison explained this in terms of the behavior of the quantum version of $SU(2)$ at roots of unity, which really makes me want to learn more representation theory! But even without the fancy stuff I can still explain this identity “combinatorially.”

Answer 2

Construct a directed graph $\Gamma(V)$ as follows: its vertices are the irreducible representations of $G$ , and the number of arrows from $A$ to $B$ is the multiplicity of $B$ in $A \otimes V$ . (Compare the construction of Young’s lattice from representations of the symmetric groups.) Then the multiplicity of the trivial representation in $V^{\otimes n}$ is, essentially by definition, the number of walks on $\Gamma(V)$ of length $n$ from the trivial representation to itself! The number of walks between the other vertices also has a clear interpretation. If in addition $V \simeq V^{*}$ , then $A \otimes V \simeq A \otimes V^{*} = \textbf{Hom}(V, A)$ (the internal hom), so a form of Frobenius reciprocity then implies that $\Gamma(V)$ is an undirected graph.

When $G$ is finite, $\Gamma(V)$ has finitely many vertices and its adjacency matrix has coefficients

$\displaystyle \frac{1}{|G|} \sum_{g \in G} \chi_A(g) \chi_V(g) \overline{\chi_B}(g)$ .

This implies that the adjacency matrix of $\Gamma(V)$ is diagonalized by the character table of $G$ and that its eigenvalues are, naturally enough, precisely the values $\chi_V(g)$ . (This suggests an interesting perspective: although a finite graph has as many eigenvalues as vertices, in the construction of $\Gamma(V)$ the eigenvalues are naturally associated to conjugacy classes of elements of $G$ , not to representations, so one shouldn’t think of this identification as canonical. The eigenvalues should instead be thought of as “dual” to the vertices.)

Now again let $G = SU(2), V = \mathbb{C}^2$ with the defining representation. Since $G$ is no longer finite, we shouldn’t expect $\Gamma(V)$ to be, either, but it is still simple to describe. The irreducible representations of $G$ are precisely the symmetric powers $\text{Sym}^n(V)$ of $V$ . In concrete terms, one can dualize and think of the action of $SU(2)$ on $\mathbb{C}^2$ as an action on the dual space of linear polynomials in two variables $x, y$ . If $g \in G$ is written in the form

$\left[ \begin{array}{cc} \alpha & - \bar{\beta} \\ \beta & \bar{\alpha} \end{array} \right], |\alpha|^2 + |\beta|^2 = 1$

then the dual action is given by

$\left[ \begin{array}{cc} \alpha & - \bar{\beta} \\ \beta & \bar{\alpha} \end{array} \right]^{-1} \left[ \begin{array}{c} x \\ y \end{array} \right] = \left[ \begin{array}{cc} \bar{\alpha} x + \bar{\beta} y \\ - \beta x + \alpha \end{array} \right]$ .

$\text{Sym}^n(V)$ can then be described as the representation of $SU(2)$ on the space of polynomials of degree $n$ in two variables given by extending the above action multiplicatively. That these representations give the complete list of irreducible representations of $SU(2)$ is classic; you can prove it using character theory, as is done in Singer’s Linearity, Symmetry, and Prediction in the Hydrogen Atom (which I highly recommend and will blog about when I have time), or you can do it by passing to the Lie algebra; see, for example, Fulton and Harris.

Now, to describe the structure of $\Gamma(V)$ , I claim that

$\displaystyle \text{Sym}^n(V) \otimes V \simeq \text{Sym}^{n+1}(V) \oplus \text{Sym}^{n-1}(V)$ .

This will then establish that $\Gamma(V)$ is the infinite path graph $A_{\infty}$ with vertices $\{ \text{Sym}^n(V) | n \ge 0 \}$ and undirected edges $0 \leftrightarrow 1 \leftrightarrow 2 \leftrightarrow ...$ . The number of walks on $A_{\infty}$ from the finite end (the trivial representation) to itself is now, practically by definition, either zero for walks of odd length or $C_k$ for walks of length $2k$ . This is a totally combinatorial explanation of the observation that the moments of the trace of a random element of $SU(2)$ gives Catalan numbers.

It remains to prove the desired isomorphism. A cheap but revealing way to do this, using the fact that the character of a representation of $G$ uniquely determines it, is to verify that the characters of the LHS and RHS are the same. By the spectral theorem, it’s not hard to see that the character of $\text{Sym}^n(V)$ evaluated at an element $g \in G$ is equal to $\frac{\sin (n+1) \theta}{\sin \theta}$ where $\theta$ is the argument of one of the eigenvalues of $g$ (which have absolute value $1$ and are conjugate, so it doesn’t matter which one is chosen). When $n = 1$ , this gives $2 \cos \theta$ , so the characters of the larger representations are the Chebyshev polynomials of the second kind in the character of $V$ . (The orthogonality relations for $SU(2)$ then tell us that the Chebyshev polynomials are orthogonal with respect to some measure obtained from the Haar measure on $SU(2)$ ; this is one way to prove that the list of representations above is complete, by appealing to the completeness of the Chebyshev polynomials (equivalently, the Fourier sine basis) as an orthonormal basis in the appropriate Hilbert space.)

In any case, to prove the desired result it now suffices to prove that

$\displaystyle 2 \sin (n+1) \theta \cos \theta = \sin (n+2) \theta + \sin n \theta$ .

But this is just a special case of the product-to-sum identities.

Of course, in the spirit of categorification, proving an isomorphism is always better than proving an identity. Now, $\text{Sym}^n(V)$ describes an action of $SU(2)$ on monomials $x^n, x^{n-1} y, ... y^n$ of degree $n$ as described above, and $V$ describes an action of $SU(2)$ on monomials $z, w$ as described above. It follows that $\text{Sym}^n(V) \otimes V$ describes an action of $SU(2)$ on all products of these monomials. To give the desired isomorphism it is enough to observe that $xw - yz$ is fixed by $SU(2)$ , hence the polynomials

$(xw - yz)x^{n-1}, (xw - yz) x^{n-2} y, ..., (xw - y z) y^{n-1}$

span an invariant subspace isomorphic to $\text{Sym}^{n-1}(V)$ , while the polynomials

$x^n z, x^n w + x^{n-1} yz, ..., xy^{n-1} w + y^n z, y^n w$

span an invariant subspace isomorphic to $\text{Sym}^{n+1}(V)$ .

More examples

I am very curious about what other graphs $\Gamma(V)$ one can get for other choices of $G$ and $V$ , since interesting graphs correspond to interesting sequences of numbers of closed walks. Consider, for example, the representation of the finite cyclic group $G = \mathbb{Z}/m\mathbb{Z}$ on $V = \mathbb{C}^2$ by rotation matrices. The irreducible representations of $G$ are all one-dimensional, and they are all tensor powers of the representation $W$ on $\mathbb{C}$ which sends $k$ to $\zeta_m^k$ . Since $V \simeq W \oplus W^{*}$ , it follows that $\Gamma(V)$ is precisely the undirected cycle graph with $m$ vertices, which makes sense since the trace of $k$ acting on $V^{\otimes n}$ is $(2 \cos \frac{2\pi k}{m})^n$ . It follows that the multiplicity of the irreducible representation in $V^{\otimes n}$ is the number of closed walks of length $n$ from the trivial representation to itself, which by symmetry is $\frac{1}{m}$ times the total number of closed walks, or

$\displaystyle \frac{1}{m} \sum_{k=0}^{m-1} \left( 2 \cos \frac{2 \pi k}{m} \right)^n$ .

When $m > n$ , it’s not hard to see from the combinatorial definition that this number is equal to zero if $n$ is odd and $\displaystyle {2k \choose k}$ if $n = 2k$ is even.

Packaging all the cyclic groups together, consider the representation of the circle group $G = \mathbb{T} \simeq SO(2)$ on $V = \mathbb{C}^2$ by rotation matrices. Again, the irreducible representations of $SO(2)$ are one-dimensional, but this time they are tensor powers of a single representation $W$ or its dual $W^{*}$ . The representation $W$ sends $e^{i \theta}$ to multiplication by $e^{i \theta}$ , and its dual sends $e^{i \theta}$ to multiplication by $e^{-i \theta}$ . (In other words, the dual group to $\mathbb{T}$ – the group of characters under tensor product – is $\mathbb{Z}$ .) Since $V \simeq W \oplus W^{*}$ , it follows that $\Gamma(V)$ is precisely the undirected infinite cycle graph $\mathbb{Z}$ . The multiplicity of the trivial representation in $V^{\otimes n}$ is the number of closed walks from the trivial representation to itself of length $n$ , which is now

$\displaystyle \int_0^1 (2 \cos 2 \pi x)^n \, dx$

and which, by the combinatorial interpretation, is always equal to zero if $n$ is odd and equal to ${2k \choose k}$ if $n = 2k$ is even. (This is straightforward to prove by manipulating the above integral, but the point here is not to prove the identity but to categorify it in some sense.)

Generally, it follows from the general theory of Pontryagin duality that the dual of a compact abelian group $G$ is a discrete group $G^{\vee}$ which can be identified with the finite-dimensional irreducible unitary representations of $G$ (all of which are one-dimensional) under tensor product. If $G^{\vee}$ is finitely generated, then letting $V$ be the direct sum of a set of generators, it follows that $\Gamma(V)$ is the Cayley graph of $G^{\vee}$ with respect to the generators that make up $V$ . This subsumes both of the examples above. ( $G^{\vee}$ is not always finitely generated; if $G$ is the profinite integers $\hat{\mathbb{Z}} \simeq \prod_p \mathbb{Z}_p$ , then I believe that $G^{\vee} \simeq \mathbb{Q}/\mathbb{Z}$ .)

What happens for nonabelian groups? I haven’t yet tried many examples, but here’s a family. When $G = S_m$ and $V = \mathbb{C}^m$ with the permutation representation then we know that $\chi_V(g) = \text{Fix}(g)$ , the number of fixed points of $g$ . It follows that the multiplicity of the trivial representation in $V^{\otimes n}$ is

$\displaystyle \frac{1}{m!} \sum_{g \in S_m} \text{Fix}(g)^n$ .

There is a fairly direct way to interpret this sum: by Burnside’s lemma, it is equal to the number of orbits of the action of $S_m$ on $n$ -tuples of elements of a set of size $m$ . Convince yourself that this is, more or less by definition, the number of ways to partition a set of size $n$ into at most $m$ nonempty blocks, which gives

$\displaystyle \frac{1}{m!} \sum_{g \in S_m} \text{Fix}(g)^n = S(n, 1) + S(n, 2) + ... + S(n, m)$

where $S(n, k)$ is the Stirling numbers of the second kind. When $n \le m$ , this is equal to the Bell number $B_n$ . This identity came up in another recent MO question, and it highlights an interesting relationship between the rencontres numbers and the Stirling numbers, especially if one writes the above identity in generating function form.

On the other hand, the above numbers count walks on $\Gamma(V)$ , which has vertices the Young diagrams of size $m$ and a somewhat complicated set of edges. $V$ is the direct sum of the trivial representation, which corresponds to the diagram $(m)$ (if I’ve got my conventions straight), and an irreducible representation of size $m-1$ , which corresponds to the diagram $(m-1, 1)$ . The presence of the trivial representation means that $\Gamma(V)$ has self-loops at each vertex, but unfortunately I don’t know how to describe the edges coming from the rest of the representation. This kind of stuff should be well-known to people who work with the symmetric groups; it would be interesting to give a description of the edges of $\Gamma(V)$ and then to provide a combinatorial proof that walks from the trivial representation to itself describe set partitions. Anyone want to give it a try?

I’m also very curious about what happens when $G$ is a compact (connected) Lie group. $\Gamma(V)$ should be related to the weight lattice of $G$ , but I don’t know enough representation theory to say anything more than that with certainty.

Posted in math.CO, math.RT | Tagged Catalan numbers, Fourier transforms, walks on graphs | 2 Comments

2 Responses

on June 26, 2011 at 11:09 am | Reply The representation theory of SU(2) « Annoying Precision

[…] continuous) irreducible representations of (which you’ll recall we assumed way back in this previous post). As a first step, it turns out that the finite-dimensional representation theory of compact groups […]
on April 27, 2010 at 9:20 pm | Reply The McKay correspondence I « Annoying Precision

[…] April 27, 2010 Today we’re going to relate the representation graphs introduced in this blog post to something I blogged about in the very first and second posts in this blog! The result will be a […]

Comments RSS

	ZW on The double commutant theo…
	auto on More about the Schrödinger equ…
	Jaromir Kuben on Meditation on the Sylow theore…
	Qiaochu Yuan on Meditation on the Sylow theore…
	Qiaochu Yuan on Some remarks on the infinitude…

Annoying Precision

"A good stock of examples, as large as possible, is indispensable for a thorough understanding of any concept, and when I want to learn something new, I make it my first job to build one." – Paul Halmos