The ADE affair, 5

A root system is a finite set S of vectors in Euclidean space with the properties

  • If ssS, then λ=±1.
  • The set S is mapped to itself by the reflection in the hyperplane perpendicular to each element s of S. (This reflection is given by rs(t) = t−(2s.t/s.s)s.)
  • For any two vectors s,tS, the coefficient 2s.t/s.s occurring in the expression for the reflection is an integer.

A root system is indecomposable if it is not contained in the union of two orthogonal subspaces. It is clear that any root system can be expressed uniquely as the disjoint union of indecomposable root systems; and given indecomposable root systems in pairwise orthogonal subspaces, their union is a root system.

The root systems of types A, D and E that we have been discussing are precisely the indecomposable root systems in which all the roots have the same length. (We may rescale so that the squared length s.s of each root is 2; then the third condition shows that the inner product of linearly independent roots is +1, 0, or −1.)

Now let S be an indecomposable root system. Then clearly the vectors of fixed length in S themselves form a root system, which falls under the ADE classification. Moreover, if S contains roots of two different lengths, then the ratio of their squared lengths is 2 or 3. (For if s and t are roots of different lengths, then 2s.t/s.s and 2s.t/t.t are both integers, and their product is at most 4, by Cauchy’s inequality; the product cannot be 4 ince s and t must be independent in this case.

So the classification follows by seeing how we can fit two root systems together after a re-scaling. (Remember that the two constituents may not be indecomposable.) There are only a few solutions:

  • A root system consisting of a Dn system together with an orthogonal basis whose squared lengths are half those in the first system. This can be represented as all the vectors ±ei and ±ei±ej, where i and j are distinct and run from 1 to n. This is type Bn.
  • A root system consisting of a Dn system together with an orthogonal basis whose squared lengths are twice those in the first system. This can be represented as all the vectors ±2ei and ±ei±ej, where i and j are distinct and run from 1 to n. This is type Cn.
  • Two copies of D4, squared lengths having a factor of 2. This is type F4.
  • Two copies of A2, squared lengths having a factor of 3. This is type G2.

Note that, while Bn and Cn are different, there are some applications where we do not need to distinguish them.

The root systems first arose in the classification of simple Lie algebras (or simple Lie groups) over the complex numbers, where there is one algebra or group for each indecomposable root system. There are many derived classifications, including simple algebraic groups and finite simple groups of Lie type.

However, I will give an application with which I was involved. You may wish to refer back to the first post in this series for the definition of generalized line graphs and their characterization by means of the root systems of type ADE.

The line graph L(X) of a graph X has as vertices the edges of X, two vertices adjacent in the line graph if they share a vertex of X. A theorem of Whitney asserts that two non-isomorphic connected graphs have non-isomorphic line graphs, with a single exception: the line graph of a triangle and of a three-pointed star both consist of a triangle. Whitney also showed that, with the exception of a few small graphs on four vertices, any isomorphism between line graphs L(X) and L(Y) is induced by an isomorphism between X and Y.

Using root systems, there is a simple conceptual proof of this theorem and an extension of it to generalized line graphs. Any generalized line graph (indeed, any connected graph with least eigenvalue −2 or greater) can be realised as a subset of a root system of type ADE with all inner products non-negative. Now there is a natural representation of the vertices of the “root graph” as unit vectors having inner product 0 or 1 with the vertices of the (generalized) line graph. Vertices and edges together are then contained in a root system with roots of two different squared lengths differing by a factor of 2.

If this root system is Bn, then the vertices are uniquely determined as the unit basis vectors. So the theorem holds in all generalized line graphs except for those represented in D4, in which case the vertices and edges could be represented in F4. It is now a fairly simple matter to list the small number of possibilities.

Thus, just as the exceptional root systems E6, E7 and E8 explain graphs with least eigenvalue −2 which are not generalized line graphs, the exceptional root system F4 explains exceptional isomorphisms between generalized line graphs.

If S is a root system, then the reflections in the hyperplanes perpendicular to the elements of S generate a finite group. From this point of view, root systems form a special case of the concept of finite groups generated by reflections in hyperplanes in Euclidean space. Such groups were determined by Coxeter, and are now referred to as finite Coxeter groups. Essentially, Coxeter showed that any such group is determined by the relations asserting that each generating reflection has order 2, and that the product of any two reflections has order m if the angle between the hyperplanes is π/m. Thus, Coxeter determined all finite groups which have presentations of this form.

To return to the ADE classification: in this case the angle between two roots is either π/2 or π/3. So the groups are generated by elements of order 2 whose products have order 2 or 3. In fact, the groups are succinctly described by the ADE diagrams with which we began the series: generators correspond to the nodes of the diagram, and the product of two adjacent generators has order 3, while the product of two non-adjacent generators has order 2.


About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition and tagged , , , , . Bookmark the permalink.

2 Responses to The ADE affair, 5

  1. Ralph says:

    I like your style of exposition.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.