The McKay correspondence I

April 27, 2010 by Qiaochu Yuan

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 beautiful connection between the finite subgroups of $\text{SU}(2)$ , the Platonic solids, and the ADE Dynkin diagrams. This connection has been written about in several other places on the internet, for example here, but I don’t know that any of those places have actually gone through the proof of the big theorem below, which I’d like to (as much for myself as for anyone else who is reading this).

Let $G$ be a finite subgroup of $\text{SL}_2(\mathbb{C})$ . Since any inner product on $\mathbb{C}^2$ can be averaged to a $G$ -invariant inner product, every finite subgroup of $\text{SL}_2(\mathbb{C})$ is conjugate to a finite subgroup of $\text{SU}(2)$ , so we’ll suppose this without loss of generality. The two-dimensional representation $V$ of $G$ coming from this description is therefore faithful and self-dual. Consider the representation graph $\Gamma(V)$ , whose vertices are the irreducible representations of $G$ and where the number of edges between $V_i$ and $V_j$ is the multiplicity of $V_j$ in $V_i \otimes V$ . We will see that $\Gamma(V)$ is a connected undirected loopless graph whose spectral radius $\lambda(\Gamma(V))$ is $2$ . Today our goal is to prove the following.

Theorem: The connected undirected loopless graphs of spectral radius $2$ are precisely the affine Dynkin diagrams $\tilde{A}_n, \tilde{D}_n, \tilde{E}_6, \tilde{E}_7, \tilde{E}_8$ .

We’ll describe these graphs later; for now, just keep in mind that they are graphs with a number of vertices which is one greater than their subscript. In a later post we’ll see how these give us a classification of the Platonic solids, and we’ll also discuss other connections.

Some lemmas

In order to make use of the theorem, we need a few lemmas establishing the properties I claimed the representation graphs described above have. Let $G$ be any finite group and let $\Gamma(V)$ be the representation graph associated to a representation $V$ of $G$ .

Lemma 0: The spectral radius of $\Gamma(V)$ is $d = \dim V$ .

Proof. In fact, we know that the eigenvalues are precisely the numbers $\chi_V(g)$ , which are sums of $d$ roots of unity, and their absolute values are maximized when $g$ is a scalar multiple of the identity.

Lemma 1: If $V$ is self-dual, then $\Gamma(V)$ is undirected.

Proof. The number of edges from $V_i$ to $V_j$ is equal by definition to $\dim \text{Hom}(V_j, V_i \otimes V)$ . By Frobenius reciprocity, this is equal to $\dim \text{Hom}(V_i, V_j \otimes V^{*}) = \dim \text{Hom}(V_i, V_j \otimes V)$ , so $\Gamma(V)$ can be viewed as an undirected graph (one can also establish this with characters).

Lemma 2: If $V$ is faithful, then $\Gamma(V)$ is strongly connected.

Proof. If $V$ is one-dimensional, then $G$ is a cyclic group and the result is clear. Otherwise, $d = \dim V > 1$ . Now, $V$ is faithful if and only if every non-identity element of $g$ acts by a non-identity transformation. The only $g$ such that $|\chi_V(g)| = d$ are the ones which have all eigenvalues the same, hence are a scalar multiple of the identity, and these are precisely the elements of the center $Z(G)$ . Now, for two irreducible representations $A, B$ the number of paths in $\Gamma(V)$ from $A$ to $B$ is

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

and for large $n$ the terms with $|\chi_V(g)| = d$ dominate, so to show the desired result for $G$ it suffices to show the desired result for $Z(G)$ , i.e. we can reduce to the case that $G$ is abelian. But then $G$ is a product of cyclic groups and the result follows by the result for a single cyclic group.

Lemma 3: If the center of $G$ acts nontrivially in each irreducible summand of $V$ , then $\Gamma(V)$ is loopless.

Proof. It suffices to reduce to the case that $V$ is irreducible. We want to show that $\dim \text{Hom}(A, A \otimes V) = 0$ for all irreducible representations $A$ . Equivalently, we want to show that $\dim \text{Hom}(V, A \otimes A^{*}) = 0$ for all irreducible representations $A$ . But the central character of $V$ is nontrivial and the central character of $A \otimes A^{*}$ is trivial (any element of the center acts by multiplication by some scalar of absolute value $1$ in $A$ and by the conjugate in $A^{*}$ ), so this can’t occur. See also question #22540 on MO; I was stuck on this one for awhile!

Lemma 4: The center of any nontrivial finite subgroup of $\text{SU}(2)$ is nontrivial.

Proof. Let $V$ be the corresponding two-dimensional representation of a finite subgroup $G$ . If $V$ is irreducible, then $\dim V = 2$ divides $|G|$ , so $G$ has an element of order $2$ . But an element of order $2$ in $\text{SU}(2)$ must have eigenvalues $-1, -1$ in order to have determinant $1$ , and it must therefore be $-I$ , which is central. If $V$ is reducible, then it is the sum of two one-dimensional representations, and $G$ is abelian.

The above lemmas together imply that if $G$ is a finite subgroup of $\text{SU}(2)$ , then the corresponding representation graph $\Gamma(V)$ is connected, undirected, and loopless.

Some more lemmas

Now we’ll need a few graph-theoretic lemmas.

Lemma 5: Let $G$ be a connected undirected graph. For each vertex $v \in G$ , let $a_{n,v}$ denote the number of closed walks on $G$ of length $n$ which begin and end at $v$ . Then $\displaystyle \lim_{n \to \infty} \frac{a_{n,v}}{\lambda(G)^n}$ is a nonzero constant.

Proof. First of all, we know by standard linear algebra that $a_{n, v}$ is a weighted sum of powers of eigenvalues of the adjacency matrix $\mathbf{A}$ of $G$ , and we know by the spectral theorem that the weights are constants (e.g. not polynomials, as would happen if there were nontrivial Jordan blocks). In fact, we know by the Perron-Frobenius theorem that $\lambda(G)$ has multiplicity $1$ . So all we are trying to verify is that the coefficient of $\lambda(G)^n$ is nonzero.

Let $k$ denote the total number of vertices of $G$ . Then there exists a path from any vertex to any other vertex and back of length most $2(k-1)$ . Hence among the paths from $v$ to itself of length $n$ there are paths which first travel to $w$ along a path of length $r \le 2(k-1)$ , then travel back to $w$ , then travel back to $v$ . It follows that

$a_{n,v} \ge a_{n-r,w}$

for any $v, w \in G$ , and since $\frac{a_{n,v}}{a_{n-r,v}}$ approaches a constant for large $n$ , it follows that $a_{n, v}, a_{n, w}$ are always within a constant multiple of each other for any $v, w \in G$ as $n$ tends to infinity. On the other hand,

$\displaystyle \sum_{v \in G} a_{n, v} = \sum_{\lambda} \lambda^n$

where the right hand side runs over all eigenvalues of $\mathbf{A}$ . The result follows.

Lemma 6: Let $G$ be a connected graph and let $H$ be a proper connected subgraph of $G$ . Then $\lambda(H) < \lambda(G)$ .

Proof. It suffices to do this in the case where $G$ has exactly one more edge than $H$ . Let $v \in H$ be a vertex incident to the extra edge, let $a_{n, v}$ be the number of closed walks in $H$ from $v$ to itself of length $n$ , and let $b_{n, v}$ be the number of closed walks in $G$ from $v$ to itself of length $n$ . By Lemma 5, it suffices to show that $\frac{b_{n,v}}{a_{n,v}}$ can be arbitrarily large for large $n$ .

Take $n$ much larger than some fixed constant $C$ . Among the paths from $v$ to itself in $G$ of length $2n$ there are paths which travel from $v$ to itself in $H$ for $n-k-1$ steps, traverse the extra edge in $G$ and back again, and then travel from $v$ to itself in $H$ for the remaining $n+k-1$ steps, for every $k \in [-C, C]$ . It follows that

$\displaystyle b_{2n, v} \ge \sum_{k = -C}^{C} a_{n-k-1, v} a_{n+k-1, v}$ .

Taking $C$ to be sufficiently large, the result follows.

Proof of Theorem 1

First we describe the Dynkin diagrams $\tilde{A}_n, \tilde{D}_n$ . $\tilde{A}_n$ is the cycle graph on $n + 1$ vertices; we know it as the representation graph of the cyclic group $C_{n+1}$ relative to the representation on $\mathbb{C}^2$ by rotation matrices (which are contained in $\text{SU}(2)$ ), so we already know it has spectral radius $2$ (and the corresponding eigenvector is very easy to write down). The graphs $\tilde{A}_3, \tilde{A}_4, \tilde{A}_5$ are depicted below along with the eigenvectors corresponding to the eigenvalue $2$ .

$\tilde{D}_n$ is the path graph on $n - 1$ vertices with two extra edges, one right before the last vertex at each end; in particular, $\tilde{D}_4$ is a star graph. It’s not hard to write down the eigenvector corresponding to the eigenvalue $2$ , and it’s also not hard to see that $2$ is the spectral radius: a walk on $\tilde{D}_n$ has two choices at each step unless you happen to be at one of the vertices of degree three, in which case there are four choices for the next two steps. The graphs $\tilde{D}_4, \tilde{D}_5, \tilde{D}_6$ are depicted below along with the eigenvectors corresponding to the eigenvalue $2$ .

Now let $G$ be a connected undirected loopless graph with spectral radius $2$ which is not any of the above graphs. By Lemma 6, it cannot contain any of the above graphs as a subgraph. It follows that $G$ is acyclic (in particular it has no multiple edges) and has at most one vertex of degree three or more. In fact, it must have exactly one such vertex, and this vertex must have degree exactly three. So $G$ is specified by an unordered triple $\{ a, b, c \}$ describing the number of vertices in each of three “legs” extending from the vertex of degree three. There are three such graphs $\tilde{E}_6, \tilde{E}_7, \tilde{E}_8$ for which it is easy to write down an eigenvector with eigenvalue $2$ : they are depicted below.

You can prove that these graphs have spectral radius exactly $2$ computationally, but we’ll defer that to the next post, where we’ll construct groups with these representation graphs. Assuming that’s true for now, some straightforward casework shows that any three-legged graph is either a subgraph or a supergraph of one of the above, or is a subgraph of some $\tilde{D}_n$ . None of these graphs can have spectral radius $2$ by Lemma 6, which concludes the proof.

In the next post, we’ll use Theorem 1 to write down the finite subgroups of $\text{SU}(2)$ and discuss their relationship to the Platonic solids.

Posted in math.CO, math.GR, math.RT | Tagged Dynkin diagrams, MathOverflow, walks on graphs | 5 Comments

5 Responses

on October 19, 2012 at 8:47 pm | Reply Jimmy

Very interestingly! I wonder why in the definition of the graph, you only consider the graph of V, the 2 dimensional representation?
Would this combinatorial idea say something about the littlewood – Richardson coefficients? Or kronecker coefficients?

Thanks!
Jimmy
- on October 19, 2012 at 9:01 pm | Reply Qiaochu Yuan
  
  The graphs attached to $2$ -dimensional representations have special properties. You can do the same thing for higher-dimensional representations, but the corresponding graphs are much less constrained.
on July 8, 2010 at 12:53 am | Reply A. Leverkuhn

Hi, Very nice exposition on the topic — thanks! What happens
if you take a self-dual irreducible representation V and consider all self-avoiding paths between two irreducible representations A and B in
the Mckay quiver $\Gamma(V)$ ? Is there a representation-theoretic
meaning to this more restrictive class of paths ?

best, A. Leverkuhn
unexpected colour schemes
on June 26, 2010 at 11:05 pm | Reply Coxeter groups « Annoying Precision

[…] The McKay correspondence I […]
on May 2, 2010 at 6:40 am | Reply j054000

I am j054000 of mathlinks.I am really inspired by you and I would be sitting for the Regional Mathematics Olympiad in India.So,can you please recommend a few really good and tough books on functional equations and theory of equations(olympiad book)?And please suggest some elementary books on the the theory of equations, combinatorics and number theory.
Thank you.

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