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 , 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 be a finite subgroup of . Since any inner product on can be averaged to a -invariant inner product, every finite subgroup of is conjugate to a finite subgroup of , so we’ll suppose this without loss of generality. The two-dimensional representation of coming from this description is therefore faithful and self-dual. Consider the representation graph , whose vertices are the irreducible representations of and where the number of edges between and is the multiplicity of in . We will see that is a connected undirected loopless graph whose spectral radius is . Today our goal is to prove the following.

**Theorem:** The connected undirected loopless graphs of spectral radius are precisely the affine Dynkin diagrams .

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 be any finite group and let be the representation graph associated to a representation of .

**Lemma 0:** The spectral radius of is .

*Proof.* In fact, we know that the eigenvalues are precisely the numbers , which are sums of roots of unity, and their absolute values are maximized when is a scalar multiple of the identity.

**Lemma 1:** If is self-dual, then is undirected.

*Proof.* The number of edges from to is equal by definition to . By Frobenius reciprocity, this is equal to , so can be viewed as an undirected graph (one can also establish this with characters).

**Lemma 2:** If is faithful, then is strongly connected.

*Proof.* If is one-dimensional, then is a cyclic group and the result is clear. Otherwise, . Now, is faithful if and only if every non-identity element of acts by a non-identity transformation. The only such that 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 . Now, for two irreducible representations the number of paths in from to is

.

and for large the terms with dominate, so to show the desired result for it suffices to show the desired result for , i.e. we can reduce to the case that is abelian. But then is a product of cyclic groups and the result follows by the result for a single cyclic group.

**Lemma 3:** If the center of acts nontrivially in each irreducible summand of , then is loopless.

*Proof.* It suffices to reduce to the case that is irreducible. We want to show that for all irreducible representations . Equivalently, we want to show that for all irreducible representations . But the central character of is nontrivial and the central character of is trivial (any element of the center acts by multiplication by some scalar of absolute value in and by the conjugate in ), 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 is nontrivial.

*Proof.* Let be the corresponding two-dimensional representation of a finite subgroup . If is irreducible, then divides , so has an element of order . But an element of order in must have eigenvalues in order to have determinant , and it must therefore be , which is central. If is reducible, then it is the sum of two one-dimensional representations, and is abelian.

The above lemmas together imply that if is a finite subgroup of , then the corresponding representation graph is connected, undirected, and loopless.

**Some more lemmas**

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

**Lemma 5:** Let be a connected undirected graph. For each vertex , let denote the number of closed walks on of length which begin and end at . Then is a nonzero constant.

*Proof.* First of all, we know by standard linear algebra that is a weighted sum of powers of eigenvalues of the adjacency matrix of , 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 has multiplicity . So all we are trying to verify is that the coefficient of is nonzero.

Let denote the total number of vertices of . Then there exists a path from any vertex to any other vertex and back of length most . Hence among the paths from to itself of length there are paths which first travel to along a path of length , then travel back to , then travel back to . It follows that

for any , and since approaches a constant for large , it follows that are always within a constant multiple of each other for any as tends to infinity. On the other hand,

where the right hand side runs over all eigenvalues of . The result follows.

**Lemma 6:** Let be a connected graph and let be a proper connected subgraph of . Then .

*Proof.* It suffices to do this in the case where has exactly one more edge than . Let be a vertex incident to the extra edge, let be the number of closed walks in from to itself of length , and let be the number of closed walks in from to itself of length . By Lemma 5, it suffices to show that can be arbitrarily large for large .

Take much larger than some fixed constant . Among the paths from to itself in of length there are paths which travel from to itself in for steps, traverse the extra edge in and back again, and then travel from to itself in for the remaining steps, for every . It follows that

.

Taking to be sufficiently large, the result follows.

**Proof of Theorem 1**

First we describe the Dynkin diagrams . is the cycle graph on vertices; we know it as the representation graph of the cyclic group relative to the representation on by rotation matrices (which are contained in ), so we already know it has spectral radius (and the corresponding eigenvector is very easy to write down). The graphs are depicted below along with the eigenvectors corresponding to the eigenvalue .

is the path graph on vertices with two extra edges, one right before the last vertex at each end; in particular, is a star graph. It’s not hard to write down the eigenvector corresponding to the eigenvalue , and it’s also not hard to see that is the spectral radius: a walk on 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 are depicted below along with the eigenvectors corresponding to the eigenvalue .

Now let be a connected undirected loopless graph with spectral radius 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 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 is specified by an unordered triple describing the number of vertices in each of three “legs” extending from the vertex of degree three. There are three such graphs for which it is easy to write down an eigenvector with eigenvalue : they are depicted below.

You can prove that these graphs have spectral radius exactly 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 . None of these graphs can have spectral radius by Lemma 6, which concludes the proof.

In the next post, we’ll use Theorem 1 to write down the finite subgroups of and discuss their relationship to the Platonic solids.

on May 2, 2010 at 6:40 am |j054000I 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.

on June 26, 2010 at 11:05 pm |Coxeter groups « Annoying Precision[…] The McKay correspondence I […]

on July 8, 2010 at 12:53 am |A. LeverkuhnHi, 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 October 19, 2012 at 8:47 pm |JimmyVery 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 |Qiaochu YuanThe graphs attached to -dimensional representations have special properties. You can do the same thing for higher-dimensional representations, but the corresponding graphs are much less constrained.