Laplacian and vibrational spectra for homogeneous graphs

Fan R. K. Chung^{∗}^{†}  Shlomo Sternberg^{†}

Abstract A homogeneous graph is a graph together with a group which acts transitively on vertices as symmetries of the graph. We consider Laplacians of homogeneous graphs and generalizations of Laplacians whose eigenvalues can be associated with various equilibria of forces in molecules (such as vibrational modes of buckyballs). Methods are given for calculating such eigenvalues by combining concepts and techniques in group representation theory, gauge theory and graph theory.

1 Introduction

Let Γ = (V, E) be a graph, where V denotes the set of vertices and E denotes the set of edges of Γ. The Laplacian, L is an important operator acting on the space, F(V) ,of functions on V. If Γ is the graph of a molecule, M, then the computation of the spectrum of L is a central ingredient in the Hückel theory of molecular bonds. We may think of M as a map which assigns to each vertex of Γ a point in three dimensional space. Then displacements of M from its equilibrium position may be regarded as a map from V to three dimensional space, the map which assigns to each atom the three vector giving its displacement from equilibrium. Thus the space of displacements is F(V, R^{3}). Then the vibration modes are the eigenvalues of a self adjoint operator, F, on F(V, R^{3}).

Suppose that a group G acts transitively on V as symmetries of Γ. (We say that Γ is a homogeneous graph.)Then L commutes with the representation of G on F(V), in other words, it is an intertwining operator for this representation, and so its eigenspaces must be sums of irreducibles. But it is an intertwining operator of a special sort, having to do with the fact that the Laplacian involves nearest neighbors only. This additional fact allows group theory to be of considerable use in determining the actual eigenvalues and not merely their multiplicity. (We should point out that a Cayley graph is a special kind of homogeneous graph in which the vertices are the elements of G and G acts on itself by left multiplication.)

∗Bell Communications Research, Morristown, New Jersey 07960

†Department of Mathematics, Harvard University, Cambridge, Massachussetts 02138

Similarly, suppose that G acts as geometrical symmetries of the molecule M. Then we get a representation of G on F(V, R^{3}), and F is an intertwining operator for this representation, and hence the multiplicities of the eigenvalues of F are determined by the decomposition of F(V, R^{3}) into irreducibles. Once again, if we require that F be local in the sense that the forces involve nearest (or next nearest) neighbors, this extra condition allows group theory to help in the computation of the eigenvalues themselves, and not just their multiplicity.

In the standard literature of graph theory, a graph whose group of automorphisms acts transitively on the vertices is called a vertex transitive graph. We prefer the word homogeneous for two reasons: i) this is the standard terminology in other areas of mathematics, and ii) our emphasis will be on the group, G, which need not be identical to the group of automorphisms of Γ. For example, in later sections where we want to consider vector bundles over graphs, the homomorphism from G to Aut(Γ) might have a non-trivial kernel.

We would like to thank Bertram Kostant for many useful discussions concerning the geometry of the buckyball, especially the relation to Sl(2, 5) and its representation theory, and its possible relation with E_{8} via the Mckay correspondence.

2 Homogeneous Laplacians

Let the finite group G act transitively on the finite set V. If we pick a point v ∈ V and let H = {g ∈ G|gv = v} denote the isotropy group of v, then we may identify V with the coset space G/H. (For the case of a Cayley graph, H = {e} is trivial.)Hence a function on V = G/H may be identified with a function f on G which satisfies

f(gh) = f(g)  (1)

for all h ∈ H. Thus we have identified F(V) = F(G/H) as a subspace of F(G). The group G acts on itself by left multiplication, and this induces the left multiplication representation, l, of G on F(G) defined by

[l(a)f](x) = f(a^{−1}x).

It is clear that F(V) is an invariant subspace for this representation. We also have the right action of G on itself which induces the right multiplication representation, r defined by

[r(a)f](x) = f(xa).

It is clear that these two representations commute, and hence define a representation of G × G on F(G). It is also clear that the most general operator S that commutes with all the l(a) is of the form

S = ∑ c_{a}r(a).  (2)

Now suppose that

c_{hah^{−1}} = c_{a}, ∀h ∈ H.  (3)

Then, if f satisfies (??), so does Sf. Indeed,

(Sf)(xh) = ∑ c_{a}f(xha) = ∑ c_{a}f(xhah^{−1}h) = ∑ c_{a}f(xhah^{−1}) = (Sf)(x)

by (??). So an S satisfying (??) and (??) maps F(V) into itself and intertwines the representation of G on F(V). Conversely, suppose that S is an operator on F(V) which intertwines the representation of G. If we regard F(V) as the subspace of F(G) consisting of functions satisfying (??), then it is clear that the right action of H on this subspace is trivial, so F(V) is invariant under the action of G × H. So (by extending arbitrarily on a complementary subspace and averaging over G × H ) we can extend S to an operator on all of F(G) which still commutes with the action of G × H. Let us continue to denote this extended operator by S. The fact that S commutes with the left action of G implies that it has the form (??), and the fact that S commutes with the right action of H implies that (??) holds. So we have proved

Theorem 1 If we identify F(V) as the subspace of F(G) consisting of functions satisfying (??), then the intertwining operators for the action of G on F(V) are the restrictions to F(V) of operators (??) which satisfy (??).

Now suppose that Γ = (V, E) is a finite graph and that the finite group G acts transitively on V as automorphisms of Γ. This means that if a and b are vertices which are connected by an edge, then so are ga and gb. Let us pick a vertex v to serve as the origin, and so we have the isotropy group H. Let B ⊂ G consist of those elements b such that v is connected to bv by an edge of the graph. (We write v ∼ bv.) Clearly bh ∈ B if b ∈ B and h ∈ H since hv = v. Also hb ∈ B since h carries the edge joining v to bv into an edge, and hv = v, so v ∼ hbv. Thus B is a union of H double cosets, i.e.

B = HBH.  (4)

We do not allow self loops in our graphs, so

B ∩ H = ∅.  (5)

Now b^{−1}(v, bv) = (b^{−1}v, v) and b^{−1} carries edges into edges, so v ∼ bv implies v ∼ b^{−1}v and

b ∈ B ⇒ b^{−1} ∈ B.  (6)

Conversely, suppose we start with a group G, a subgroup H and a subset B ⊂ G satisfying (??),(??) and (??). Then define V = G/H and the edge set E by aH ∼ cH if and only if c = ab for some b ∈ B. The conditions guarantee that this definition is consistent and make (V, E) into a G homogeneous graph.

Although G acts transitively on the vertices it need not act transitively on the edges, and so the pairs consisting of a vertex and an edge emanating from that vertex will fall into a finite number of types which are orbits for the action of G. Let us assign a weight q = q_{e} to each type. Then the Laplacian, L is defined by

Lf(u) = \frac{1}{Q} ∑ q_{e}[f(u) − f(u_{e})], Q = ∑ q_{e}  (7)

where, for each vertex u, the sum extends over all edges,e, emanating from u and where u_{e} is the other end point of the edge e. Since L intertwines the action of G it must have the form stated in the theorem, and it is clear how to find this form: Picking a vertex v to serve as origin determines the subgroup H. For each edge e emanating from v there will an H coset, C_{e}, of elements a ∈ G all of which satisfy

av = v_{e}.

Then, in (??) simply divide the weight q_{e} equally among all elements of C_{e} so that

L = Id − \frac{1}{Q} ∑ \frac{q_{e}}{|C_{e}|} ∑_{a∈C_{e}} r(a).  (8)

(Of course, |C_{e}| = |H| for all e.) If h ∈ H and a ∈ C_{e}, then since h is an automorphism of Γ,he = d where d is some other edge emanating from v; and q_{d} = q_{e} since the weights are invariant under the action of G. Hence the coefficients of r(a) in (??) are constant on H double cosets, and hence, in particular, satisfy (??). To check that (??) does indeed define the Laplacian, observe that for any function f, the above operator when applied to f and evaluated at v gives the same result as the Laplacian. Hence, by invariance, it must give the same result at all vertices. The Peter-Weyl theorem asserts that

F(G) = ⨁ W ⊗ W^{∗},  (9)

where the sum ranges over representatives, W of each of the (finitely many) inequivalent irreducible representations of G. We have identified F(V) as a G× H invariant subspace of F(G) and so, in terms of (??), we get the decomposition

F(V) = ⨁ W ⊗ W^{∗H},  (10)

where W^{∗H} denotes the H invariant elements of W^{∗}. The dimension of W^{∗H} can be determined by the Frobenius reciprocity theorem which guarantees that dimW^{∗H} = dim W^{H} = number of times that the trivial representation of H occurs in W. So referring to (??) we see that in terms of the decomposition (??) we need only compute the eigenvalues of

Id − \frac{1}{Q} ∑ \frac{q_{e}}{|C_{e}|} ∑_{a∈C_{e}} a  (11)

on W^{H} for each W, and each eigenvalue will be multiplied in multiplicity by dimW.

To apply (??), we need to know the σ(a) for all irreducible representations, σ and all a in each of the C_{e}. In practice, we can sometimes make a more clever choice than (??), and so get away with fewer a ’s. (See example 2, below.) The point is that (??) only requires that we weight the elements of each orbit under conjugation by H equally, not the elements of H double cosets. So suppose that we can choose subsets D_{e} ⊂ C_{e} such that ⋃ D_{e} is a union of H conjugacy orbits. Then we can replace C_{e} by D_{e} in (??) and hence in (??). So we need only compute the eigenvalues of

Id − \frac{1}{Q} ∑ \frac{q_{e}}{|D_{e}|} ∑_{a∈D_{e}} a  (12)

on W^{H} for each W, and each eigenvalue will be multiplied in multiplicity by dimW.

Examples.

1.Cycles and circulant graphs. Here Γ = G = Z/Z_{n} and there is a specified subset B ⊂ G where the set B satisfies b ∈ B ⇔ b^{−1} ∈ B. So Γ is a Cayley graph. Since G is commutative, all its irreducibles are one dimensional. So there are no algebraic equations to solve. If we weight all the elements of B with equal weight, formula (??) gives the eigenvalues λ_{k} as

λ_{k} = 1 − \frac{1}{|B|} ∑_{b∈B} e^{2πi \frac{kb}{n}} .  (13)

But sometimes we can get the eigenvalues without algebraic computation even if G is not abelian as is shown by

2. The cube. We let Γ be the graph constituted by the vertices and edges of the cube, and let G be the group of rotational symmetries of the cube, G ∼ S_{4}. Then H will be a cyclic subgroup of order 3, say

H = {e, (234), (243)}.

Since G acts transitively on the edges, all the w_{e} are equal, so we may take them equal to one. A vertex is moved to its nearest neighbor be a rotation of degree four, i.e. by a four-cycle. Now the right coset of a cycle of order four consists of two cycles of order four and a transposition. For example, (1234)(234) = (1243) but (1234)(243) = (12) . So we may take D_{e} to consist of the (two) cycles of order four in C_{e}. (They correspond to rotations of order four in each of the faces abutting e.) So ⋃ D_{e} consists of all six four-cycles, which is a single conjugacy class for S_{4} and so a union of conjugacy classes for H. In this case |D_{e}| = 2 and Q = 3 so (??) becomes

L = I − \frac{1}{6} ∑(abcd),  (14)

the sum extending over all six four cycles. Frobenius reciprocity shows that dimW^{H} = 1 for W either of the two one dimensional or two three dimensional representations, while dimW^{H} = 0 for the two dimensional representation. Since all the non-zero W^{H} are one dimensional, there are no algebraic equations to solve. To evaluate the sum in (??), observe that since a four cycle is an odd permutation, the value of the sum in the two three dimensional representations will differ by a sign, and similarly for the one dimensional representations. For the trivial representation each (abcd) gives 1, and hence (??) becomes 0 as expected. The sign representation gives the value 2, reflecting the fact that the cube is a bipartite graph. In the three dimensional representation yielding the realization of S_{4} as symmetries of the cube, the matrix of a fourfold rotation about the z-axis is M or M^{−1} where

M = ( \begin{matrix}0 & −1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{matrix} ) .

So M_{x} + M_{x}^{−1} + M_{y} + M_{y}^{−1} + M_{z} + M_{z}^{−1} = 2I . Hence the eigenvalues of the Laplacian for the cube are 0, \frac{2}{3}, \frac{4}{3}, and 2, with the fractional values occurring with multiplicity 3. The condition that all the non-zero W^{H} be one dimensional, is the condition that the pair G, H be a Gelfand pair. A detailed discussion of this condition with a view to the application described above can be found in [?] together with an extensive bibliography. The Gelfand pair condition is a condition on the group G and the subgroup H, that is, it involves the action of G on the set V of vertices, but does not involve the edges. In other words, the Gelfand pair condition does not involve the graph structure.

But the structure of the graph was involved in our choice of the D_{e} above to consist of the four cycles. More generally, whenever we can choose the D_{e} such that ⋃ D_{e} is an entire G conjugacy class, (and all the q_{e} = 1) the operator (??) must be a scalar in each representation by Schur’s lemma. Then no algebraic equation need be solved, and if we take the trace of (??) in the representation on W, we get

λ_{W} = 1 − \frac{| ⋃ D_{e}|χ(a)}{Q|D_{e}|dimW}  (15)

where λ_{W} is the eigenvalue corresponding to the irreducible representation on W, and its multiplicity is dimW × dimW^{H}.

3.The Petersen graph. This can be thought of a follows: Let V be the set of all two element subsets of the five element set,{1, 2, 3, 4, 5} so V contains 5 × 4/2 = 10 vertices in all. Connect any two element set with all two element sets lying in its complement. So {1, 2} is connected to {3, 4}, {3, 5} and {4, 5}. The group S_{5} clearly acts as automorphisms of this graph, and the subgroup fixing a point is H = S_{2} × S_{3}. The space F(V) decomposes into 1 ⊕ 4 ⊕ 5 and so we have a Gelfand pair. The space 1 ⊕ 4 can be thought of as all functions on {1, 2, 3, 4, 5} with the 1 consisting of the constants and the 4 consisting of functions whose “integral” i.e. sum vanishes. The subspace of 1 ⊕ 4 fixed by H consists of functions which are constant on {1, 2} and on {3, 4, 5}. So a basis of 4^{H} is the function which takes the values \frac{1}{2} on 1 and 2, and −\frac{1}{3} on 3, 4,and 5. Hence the adjacency matrix on 4^{H} is the scalar −2. Since 3 − 2 × 4 = −5, the eigenvalue on 5 must be 1 as the total trace of the adjacency matrix, A is zero. Hence the eigenvalues of A are 3, −2 with multiplicity 4 and 1 with multiplicity 5.

All of the above examples are Geland pairs, since any distance transitive group action gives a Gelfand pair by virtue of Gelfand’s lemma. All this (and the above examples) is well known, cf. [?] or [?], for example. In fact, the whole idea of this section, to use group theory to compute the eigenvalues really goes back to Frobenius, [?]. It might be useful to the reader to record here some additional results for distance transitive graphs even though they are in the standard literature, [?]: When a group, G, acts on a set, V, the number of irreducible components in the decomposition of F(V) under the induced action of G equals the number of G orbits on V × V. (See, for example [?].) In the case of a distance regular graph, G acts transitively on each subset of V × V of the form {u, v)| distance from u to v = k}. Here k ranges from 0 to d where d is the diameter of the graph. Hence F(V) decomposes into d + 1 irreducibles, so the adjacency matrix, A, or the Laplacian L = I − A has at most d + 1 distinct eigenvalues. On the other hand, for any graph, Γ, we can consider the “adjacency algebra” A = A(Γ) which is defined as the algebra consisting of all polynomials in the adjacency matrix, A. If Γ has diameter, d, then for every i ≤ d there will be a non- zero entry in A^{i} which is zero for all smaller powers. So the powers A^{i} are all linearly independent for i ≤ d and, in particular, dim A ≥ d + 1. Since the adjacency matrix, A , is symmetric, it is diagonizable, and hence A has no nilpotents and so dim A equals the number of distinct eigenvalues of A. So for any graph, A has at least d+1 distinct eigenvalues. We see that for a distance transitive graph, A has exactly d+1 distinct eigenvalues, each λ occurring with a multiplicity m(λ) = dimM_{λ} where M_{λ} is one of the components of the decomposition of F(V) .

4. The buckyball. Here there are sixty vertices, on which the icosahedral group (including reflections) acts transitively. In fact it is a Cayley graph for the alternating group, A_{5}, as illustrated in Figure 1. There are two types of edges, those which lie on the boundary of a pentagon, and those which do not. So there is a one parameter family of (normalized) Laplacians depending on the relative weight we attach to the two types of bonds. The group H = Z_{2}, where the non-identity element consists of reflection through a plane containing a nonpentagonal edge. The irreducibles are direct products of irreducibles of Z_{2} and those of A_{5}, and the ones with W^{H} ≠ 0 are the ones which are trivial on the Z_{2} component. On these, W^{H} = W. The irreducible representations of the alternating groups were found by Frobenius, see[?]. For the case of A_{5} they are are of dimension 1,3,3,4 and 5, cf. [?] or [?] for a modern reference for A_{5}. So finding the eigenvalues involves solving equations of these orders. We will present the details elsewhere [?].

In the Hückel theory, the stability of a molecule is determined by what is essentially the following rule, cf. [?] for a very coherent exposition: One calculates the eigenvalues of the adjacency matrix of the graph whose vertices are the carbon atoms and whose edges are the bonds, and arranges the eigenvalues in nonincreasing order. Suppose for simplicity that the number, n, of atoms is even. The one compares the sum of the top n/2 eigenvalues with n/2 . If the sum is larger than n/2 the molecule is stable. Thus for benzene, which is a cycle graph with n = 6, the top three eigenvalues are 2,1,1 as we have seen. So the sum is 4 which is greater than 3. For the buckyball, the sum of the top thirty eigenvalues comes to 46.15, cf. [?]. This is to be compared with 30. So the ratio of stability of the buckyball (according to this model) is even greater than benzene.

We remark that the eigenvalues of the buckyball can be written in closed form as roots of the following equations (cf. [?]) where the single bonds are weighted by 1 and the double bonds are weighted by t:

(a) (x^{2} + x − t^{2} + t − 1)(x^{3} − tx^{2} − x^{2} − t^{2}x + 2tx − 3x + t^{3} − t^{2} + t + 2) = 0 with multiplicity 5;

(b) (x^{2} + x − t^{2} − 1)(x^{2} + x − (t + 1)^{2}) = 0 with multiplicity 4;

(c) (x^{2} + (2t + 1)x + t^{2} + t − 1)(x^{4} − 3x^{3} + (−2t^{2} + t − 1)x^{2} + (3t^{2} − 4t + 8)x + t^{4} − t^{3} + t^{2} + 4t − 4) = 0 with multiplicity 3;

(d) x − t − 2 = 0 with multiplicity 1.

3 Homogeneous bundles over graphs

A vector bundle, E over the finite set V is simply a rule which assigns a vector space E_{u} to each u ∈ V. A section of the vector bundle is a rule, s, which assigns to each u ∈ V a vector, s(u) in the vector space E_{u}. We will denote the space of all sections of E by sec E. It is a vector space in a natural way. If the group G acts on V, then we say that G acts as automorphisms of the vector bundle E if, for each a ∈ G and u ∈ V we are given a linear isomorphism

a : E_{u} → E_{au}

which gives a group action, i.e.,

a ∘ b = ab : E_{u} → E_{abu}.

If G acts as automorphisms of E, then we get a representation, σ, of G on sec E given by

[σ(a)s](u) = as(a^{−1}u).  (16)

If G acts transitively on V and H is the isotropy of some point v chosen as origin, then the vector bundle E is completely determined by the representation of H on E_{v} given by the restriction of the action of G to H: Given any homogeneous vector bundle we get a representation of H on the fiber E_{v} over v, and conversely, given any representation, ρ of H on a vector space X, we obtain a vector bundle E by setting

E = G ×_{H} X.

The above equation means that we let E consist of all equivalence classes, [(a, x)] of pairs (a, x) a ∈ G, x ∈ X, and where

(ah, x) ∼ (a, ρ(h)x).

Then the fiber E_{u} over u will consist of all equivalence classes of the above form where a is chosen so that u = av. The group G acts by left multiplication:

g[(a, x)] = [(ga, x)].

The representation σ is then nothing other than the representation of g induced from ρ. We can identify this representation as a subrepresentation of F(G, X), the space of all functions from G to X as follows: Consider the subspace of F(G, X) consisting of all functions satisfying

f(xh) = ρ^{−1}(h)f(x).  (17)

We identify such a function f with the section s determined by

s(aH) = [(a, f(a)]  (18)

Starting with an f satisfying (??) equation (??) gives a well defined section. Conversely, starting with a section, (??) defines a function f satisfying (??). So we have identified sec E as a subspace of F(G, X). The group G acts on F(G, X) by the left multiplication representation,

[l(a)f](x) = f(a^{−1}x),

the subspace sec E is invariant, and the restriction of the left multiplication representation to sec E is equivalent to the representation σ: If f corresponds to s then l(g)f corresponds to σ(g)s. Indeed, the section corresponding to l(g)f assigns to the point aH the value

[(a, f(g^{−1}a))] = g[(g^{−1}a, f(g^{−1}a))] = gs(g^{−1}a) = [σ(g)s](a).

For details on all of this, cf.[?].

Now the centralizer of the left multiplication representation of G on F(G, X) consists of all operators of the form

S = ∑ R_{a} ⊗ r(a), R_{a} ∈ End(X).  (19)

By this we mean that

(Sf)(x) = ∑ R_{a}f(xa).

Which of these operators preserve the subspace sec E? If

R_{hah^{−1}} = ρ(h)R_{a}ρ(h^{−1}), ∀h ∈ H  (20)

then for f satisfying (??) we have

(Sf)(xh) = ∑ R_{a}f(xha) = ∑ R_{a}f(xhah^{−1}h) = ∑ R_{a}ρ(h)^{−1}f(xhah^{−1}).

Substituting b = hah^{−1} into the above sum and using (??) shows that Sf satisfies (??). To prove the converse, we merely adapt the proof of Theorem 1: Let τ denote the representation of H on F(G, X) defined by

[τ(h)f](x) = ρ(h)f(xh).

Then sec E is the subspace of F(G, X) consisting of elements that are invariant for this action of H. So if we have an operator on sec E which intertwines the action of G, we can extend it to an operator on F(G, X) which intertwines the action of G × H where H acts via τ and G acts via left multiplication. Then intertwining the G action implies that S is of the form (??), and intertwining the action of H implies (??). We have thus generalized Theorem 1 to

Theorem 2 If we identify sec E with the subspace of F(G, X) consisting of functions which satisfy (??), then the intertwining operators for the representation σ are the restrictions to sec E of operators of the form (??) which satisfy (??).

Once again, if V is the vertex set of a homogeneous graph, we may talk of operators localized at one or several edge lengths by insisting that the R_{a} be non-zero only for group elements a which move the origin no more than a given distance. Also, the realization of sec E as a subspace of F(G, X) together with the Peter-Weyl theorem and the Frobenius reciprocity theorem give a method for computing eigenvalues.

4 Bond energies

A very important special kind of vector bundle arises when the representation ρ of H is the restriction of a representation defined on all of G, which we shall also denote by ρ. We now have a different way of looking at the induced representation σ: To each f ∈ F(G, X) satisfying (??) we assign a function g from V to X by

g(aH) = ρ(a)f(a).  (21)

Notice that (??) guarantees that this is well defined. In terms of this picture, the induced representation is given by

[ϕ(a)g](u) = ρ(a)g(a^{−1}u),  (22)

as can easily be checked from the definitions. Conversely, suppose we start with a representation, ρ of G on X. We make V × X into a vector bundle over V by assigning to each point u ∈ V a copy of X and define the action of G on V × X by

a(u, x) = (au, ρ(a)x).

A section of this vector bundle is simply a function from V to X and the induced action on sections is then given by (??). This is the situation in the theory of molecular vibrations: The space X is just three dimensional Euclidean space giving the displacement of an atom from its equilibrium position.

Suppose that the space X has a scalar product which we shall denote by · and which is invariant under the representation ρ. We can generalize the Dirichlet form as follows: suppose that to each edge, e , of the graph we associate a selfadjoint operator, A_{e} , on X; we then define the quadratic form Q on F(V, X) by

Q(g) = \frac{1}{2} ∑[g(u) − g(v)] · A_{e}[g(u) − g(v)].  (23)

The sum is over all edges of Γ. This quadratic form will be invariant under ϕ, i.e., will satisfy

Q(ϕ(a)g) = Q(g), ∀a ∈ G, g ∈ F(V, X)

if and only if

A_{ae} = ρ(a)A_{e}ρ(a)^{−1}  (24)

for all edges, e and all a ∈ G. Of course, under the identification of F(V, X) with sec E ⊂ F(G, X), we can regard Q as a quadratic form on sec E. Now the norm ∥f∥^{2} = ∑ ∥f(a)∥^{2} is G invariant. Hence there is a unique self adjoint operator F such that

⟨f, F f⟩ = |H|^{2}Q(g),

and F is G invariant. Let B = {b} range over the group elements which move the origin, v to one of its nearest neighbors, and let A_{b} denote A_{e_{b}} where e_{b} is the edge joining v to bv. Recall that

b ∈ B ⇔ b^{−1} ∈ B.

Theorem 3 The operator F is given by

F = (∑ A_{b}) ⊗ I − ∑ A_{b}ρ(b) ⊗ r(b).  (25)

In other words,

(F f)(a) = (∑ A_{b})f(a) − ∑ A_{b}ρ(b)f(ab).  (26)

Proof. For each fixed b and a we have

ρ(b)f(ab) · A_{b}ρ(b)f(ab) = f(ab) · ρ(b)^{−1}A_{b}ρ(b)f(ab) = f(ab) · A_{b^{−1}}f(ab),

so summing over b and a gives

⟨f, (∑ A_{b})f⟩ = ⟨(∑ ρ(b) ⊗ r(b))f, (∑ A_{b}ρ(b) ⊗ r(b)f⟩.

Similarly,

f(a) · A_{b}ρ(b)f(ab) = ρ(b)^{−1}A_{b}f(a) · f(ab)
= ρ(b)^{−1}A_{b}ρ(b)ρ(b)^{−1}f(a) · f(ab)
= A_{b^{−1}}ρ(b)^{−1}f(a) · f(ab),

so

2⟨f, F f⟩ = ∑_{b} ∑_{a}[f(a) − ρ(b)f(ab)] · A_{b}[f(a) − ρ(b)f(ab)]

= ∑_{b} ∑_{a} ρ(a)^{−1}[g(a) − g(ab)] · A_{b}ρ(a)^{−1}[g(a) − g(ab)]

= |H|^{2}Q(g)

QED

The case of Theorem 3 when Γ is a Cayley graph and all the A_{e} = I appears in[?] (in slightly different language)see also [?]. But the case with general A_{e} is not without physical interest, as is illustrated by the following.

Examples.

1.Hooke’s law. Let u ∈ R^{3}, w ∈ R^{3}, etc. denote the equilibrium positions of the vertices labeled u, w and so on. Let h : V → R^{3} describe a deviation from equilibrium, so that u + h(u) is the new position of the vertex u. Then Hooke associates to h the potential energy

W_{H}(h) = \frac{1}{2} ∑ k_{u,w}(∥u + h(u) − (w + h(w))∥ − ∥u − w∥)^{2}.

In the above expression, the sum is over all pairs {u, w} of vertices connected by an edge, and k_{u,w} is the spring constant of that edge. If h is small so that we ignore terms quadratic in h, we have

∥u+h(u)−(w+h(w))∥ ≐ [∥u−w∥^{2}+2(u−w)·(h(u)−h(w))]^{\frac{1}{2}} ≐ ∥u−w∥+ω_{u,w}·(h(u)−h(w))

where

ω_{u,w} = \frac{u − w}{∥u − w∥}

is the unit vector from u to w and · denotes the scalar product on R^{3}. So the quadratic approximation to W_{H} is given by

V_{H}(h) = \frac{1}{2} ∑ k_{u,w}[ω_{u,w} · (h(u) − h(w))]^{2}.

So we may take

A_{e} = ω_{u,w} ⊗ ω_{u,w}^{t}

where e is the edge joing u to w.

We can now use the methods of the Section 2 (with a tensor product thrown in) to compute the vibrational spectra of a molecule in terms of irreducible representations.

2.Next nearest neighbors. Hooke’s law involves nearest neighbors, i.e adjacent vertices. In the semi-empirical theory of molecular vibrations one takes into account potential energies other than those associated with bond stretching; for example energies associated to the bending of angles. In this section we show that studying angle energies leads to a Laplacian attached to the associated graph of distance 2. Of course the method generalizes to distance k graphs.

So we now consider an operator associated with the change in angle between adjacent bonds, and so involving next nearest neighbor vertices. We will take as the fundamental variables the square roots of the scalar product of two adjacent edges of our molecule, and consider the potential energy associated to the changes in these variables. Explicitly, for any three vertices u ∼ z ∼ w, u ≠ w (where ∼ denotes adjacency) consider the expression

\{[(z + h(z) − u − h(u)) · (z + h(z) − w − h(w))]^{\frac{1}{2}} − [(z − u) · (z − w)]^{\frac{1}{2}} \}^{2}.

We are assuming that the equilibrium bond angles are all acute, so the expressions in the square root sign are all positive for small h. If h is very small in comparison to all bond lengths we have

[(z + h(z) − u − h(u)) · (z + h(z) − w − h(w))]^{\frac{1}{2}}  ≐
[(z − u) · (z − w) + (z − u) · (h(z) − h(w)) + (z − w) · (h(z) − h(u))]^{\frac{1}{2}}  ≐

[(z − u) · (z − w)]^{\frac{1}{2}} + \frac{(z − u) · (h(z) − h(w)) + (z − w) · (h(z) − h(w))}{2[(z − u) · (z − w)]^{\frac{1}{2}}}.

So the quadratic form on sec E will be given as

∑_{u∼z∼w} c_{uzw}[(z − u) · (h(z) − h(w)) + (z − w) · (h(z) − h(u))]^{2}  (27)

Here the coefficients c_{uzw} are constant on G orbits of triples u ∼ z ∼ w, that is, on pairs of edges meeting at a vertex. We can break (??) into three parts obtained by “collecting coefficients” in (??). So we get three terms :

I + II + III.

Here I is given by collecting the diagonal terms in (??) so

I = ∑_{z} h(z) · X_{z}h(z)  (28)

where the operator X_{z} is given by

∑_{u,w}[c_{uzw}(2z−u−w)⊗(2z−u−w)^{t}+c_{zuw}(u−w)⊗(u−w)^{t}+c_{uwz}(w−u)⊗(w−u)^{t}].

Notice that X_{z} satisfies

ρ(a)X_{z}ρ(a^{−1}) = X_{az}.

Thus in the identification of sec E with a subspace of F(G, R^{3}) given by (??), the self adjoint operator corresponding to I becomes

\frac{1}{|H|}X_{v} ⊗ I

(where v is the vertex chosen as “origin”). The second term in the decomposition is

II = ∑_{u∼z} h(u) · Y_{uz}h(z)  (29)

where

Y_{uz} = − ∑_{w|w∼z}(c_{uzw} + c_{wzu})(z − w) ⊗ (2z − u − w)^{t}

− ∑_{w|w∼u}(c_{wuz} + c_{zuw})(2u − z − w) ⊗ (u − w)^{t}.

This is a nearest neighbor interaction as in the preceeding section, and it is clear from the definition of Y that

ρ(a)Y_{uz}ρ(a)^{−1} = Y_{(au)(az)},

so that under the identification (??) the operator corresponding to the quadratic form II becomes

\frac{1}{|H|} ∑_{b∈B} Y_{v(bv)}ρ(b) ⊗ r(b).

The third term is given by

III = ∑_{u,w|d(u,w)=2} h(u) · W_{u,w}h(w)  (30)

where

W_{u,w} = ∑_{z|u∼z∼w}(c_{uzw} + c_{wzu})(z − w) ⊗ (z − u)^{t}

Once again, we have the identity

ρ(a)W_{u,w}ρ(a)^{−1} = W_{au,aw}.

So we are back in the situation of section 4, but with a different homogeneous graph, the edges of our new graph connect two points which are at distance two in the original graph. In terms of the subset B, let

B^{(2)} = {bb′}_{b,b′∈B}\H.  (31)

In other words, to get B^{(2)} we take all products of pairs of elements of B and throw away those products which belong to H. Then the operator corresponding to III is

∑_{c∈B^{(2)}} W_{v,cv}ρ(c) ⊗ r(c).  (32)

General remarks, illustrated in the case of buckyballs.

We should point out that the methods of this section, whether implemented by hand or by computer, not only determine the vibrational spectrum, but also the specific representation associated to each eigenvalue. This additional information is important in chemical applications. For example, for a vibrational line to be visible as an absorption or emission line in the infrared (as a transition between the ground state and a one phonon state) it is necessary that the associated representation have a non-zero intertwining operator with (the complexification of) the representation of G on the ordinary three dimensional space, R^{3} in which the molecule lies. In the Raman experiment, light of a definite frequency is scattered with a change of frequency. This change, known as the Raman spectrum, is associated to those representations which have non-zero intertwining with the space, S^{2}(R^{3}), of symmetric two tensors. In general, the electronic states of the molecule will tend to distort the modes associated to a given eigenvalue unless the corresponding representation is one dimensional. This is known as the Jahn-Teller effect. For details on all of this cf.[?]. For the case of homogeneous molecules, we can, in advance of all computations, and independent of specific models for the potential energy, determine the number of representations of each type by a simple application of the Frobenius reciprocity formula. Let us illustrate this for the case of the buckyball where we take G to be A_{5} × Z_{2}, as above. The isotropy group of a point consists of {e, h} where h is the product of a rotation through 180^{∘} which takes a vertex, v to −v, and the inversion−I which sends it back to v. So h = diag(−1, 1, 1) Now the space of sections of the vector bundle associated to distortions of the buckyball has dimension 180 = 60 × 3. But the space of overall (infinitesimal) rigid displacements of the molecule as a whole is six dimensional (the Lie algebra of the Euclidean group). So subtracting these six dimensions we get

1 The configuration space of the space of vibrational states is 174 dimensional.

The group G acts on this space. The forces holding the molecule together will be described (in the quadratic approximation to the potential energy whose minimum is the equilibrium configuration) by a force matrix F which must commute with the action of G. So the maximum number of distinct eigenvalues of F is the number of irreducible components (counted with multiplicity) in the decomposition of this 174 dimensional space. Since the Z_{2} acts as scalars (either the trivial or the sign representation) on each such component, to find out how many components there are it is enough to do the computation for A_{5}. Now the 180 dimensional space is the tensor product of the regular representation with a three dimensional representation, and hence is three copies of the regular representation. So we must decompose the regular representation, which contains each irreducible with a multiplicity equal to its dimension. We have mentioned that the irreducibles of A_{5} are given as 1, 3, 3’ , 4 and 5 where 3 is the three dimensional representation given by the action of A_{5} on the icosahedron, and 3’ differs from 3 in that the generator of degree 5 has been replaced by its square. Since 1 + 3 + 3 + 4 + 5 = 16, we see that the 180 decomposes into 48 = 3 × 16 irreducibles. Subtracting off two three dimensional representations

2 we see that the number of distinct vibrational modes is at most 46.

To be visible in the infrared (as a transition from the ground state to a one phonon state) the irreducible must be equivalent to the representation of G on (the complexification of) R^{3}; call it V. Here the Z_{2} component makes a difference! To find out how many such there are we apply Frobenius reciprocity. We are inducing from the three dimensional representation of the isotropy group of a point. So we are inducing from two copies of the trivial representation and one copy of the sign representation since the eigenvalues are -1,1,1 . But this same eigenvalue computation shows that the restriction of the three dimensional representation (with the non-trivial action of Z_{2}) contains two copies of the trivial and one copy of the sign. So induction from the trivial contains two copies and induction from the sign contains one copy of the three dimensional representation. Thus there are five copies of V in the 180. But one copy is the translations. (Remember that the infinitesimal rotations are ∧^{2}(V) on which Z_{2} acts trivially, so this is not equivalent to V under G.) So we are left with four copies of V in the 174. Thus there are four lines visible in the infrared as observed in [?]. To be visible as Raman, the irreducible must transform as one of the components in the decomposition of (the complexification of) S^{2}(R^{3}), the space of symmetric two tensors on R^{3}. Under the rotation group SO(3) this space breaks up into a five and a one dimensional representation. These remain irreducible upon restriction to A_{5}. On the other hand, involution through the origin and rotations through 180^{∘} both act trivially on symmetric two tensors. Now rotation through 180^{∘} has eigenvalues 1,-1,1,-1,1 in the five dimensional representation.(This most easily seen by identifying 5 with the space of symmetric polynomials of degree two in two complex variable.) Since −I acts trivially, this representation (the five on A_{5} ,trivial on Z_{2}) restricts to three copies of the trivial and two copies of the sign representation. Since 2 + 2 × 3 = 8, we get 8 lines from 5, and another two from the trivial representation, ten lines in all in the Raman spectrum some of which were observed in [?, ?]. To summarize, we have

3 The space of classical vibrational states has dimension 174. Any force matrix, F, invariant under the group has (at most) 46 distinct eigenvalues yielding four lines visible in the infrared and ten in the Raman.

The only one dimensional representations of G come from the trivial representation of A_{5} and either the trivial or the sign representation of Z_{2}. So the sign occurs once, and the trivial occurs four times by Frobenius reciprocity. But we use up one sign and two trivials in the space of translations, leaving two trivial representations. So

4 All but two of the vibrational modes exhibit the Jahn-Teller effect.

5 Graph gauge theories

The assumptions made at the beginning Section 4 can be characterized as saying that we have a G invariant trivialization of the vector bundle, E. (In analogy to the differential geometric situation, this is like assuming that there is a G invariant globally flat connection on E.) However, we can get away with a lot less in order to make the method work: Let us define a connection on the vector bundle E to be a family of linear maps

T_{x,e} : E_{y} → E_{x},

one for each edge, e, and vertex x where x is a boundary node of e and y is the other boundary node, subject to the condition that

T_{x,e} ∘ T_{y,e} = id.  (33)

Notice that there is no hypothesis about the composition of the T ’s along edges of a path. In particular, the composition of the t’s around a closed path can be different from the identity, and this is the graph theoretical analog of the holonomy. For a very lucid discussion of this subject, and its relation to lattice gauge theories, Wilson loops and the renormalization group, see the introduction by Rebbi to [?].

In the situation of Section 4, all of the fibers were identified with a fixed vector space, V and in terms of this identification all the T ’s are the identity, so that the holonomy is trivial.

If each of the fibers E_{x} has a scalar product, then we will assume in addition to (??) that the T_{x,e} are isometries for this scalar product. We will make this assumption in what follows.

Let Conn = Conn(E) denote the set of all connections on E. If G acts as automorphisms of E, then G acts on Conn by

(a · T)_{x,e} = aT_{a^{−1}x,a^{−1}e}a^{−1}.  (34)

We can consider a rule, A, which associates to each pair, (x, e), where e is an edge emanating from the vertex, x, a self adjoint operator A_{x,e} on the space E_{x}. The group G then acts on the space of all A’s by

(a · A)_{x,e} = aA_{a^{−1}x,a^{−1}e}a^{−1} = aA_{a^{−1}x,a^{−1}e}a^{∗}.  (35)

Associated to a T and an A we can define the quadratic form Q = Q_{T,A} on sec E by

Q_{T,A}(s) = \frac{1}{2} ∑_{x,e}[s(x) − T_{x,e}s(y)] · A_{x,e}[s(x) − T_{x,e}s(y)],  (36)

where, as usual, y denotes the vertex at the other end of the edge e from x. It then follows immediately from the definition, that

Q_{T,A}(σ(a)s) = Q_{a^{−1}T,a^{−1}A}(s).  (37)

In particular, if T and A are invariant, so that a · T = T and a · A = A for all a ∈ G, the form Q is invariant. Then there will be a unique G invariant operator, F, such that

⟨s, F s⟩ = |h|^{2}Q(s).

As in Theorem 3, we would like to express F as the restriction to sec E of an operator on F(G, X), that is, an operator of the form (??) satisfying (??). In order to do this, recall that every b ∈ B gives rise to an edge e_{b}, joining the “origin”, v to bv. Also, the choice of b determines an identification of E_{bv} with X, where an element of E_{bv} is written as

[(b, η)] η ∈ X.

This then defines the linear transformation t_{b} ∈ Aut(X) by

T_{v,e_{b}}[(b, η)] = [(id, t_{b}η)].  (38)

If h ∈ H then bhv = bv and hence T_{v,e_{bv}} = T_{v,e_{bhv}} so

[(id, t_{bh}η)] = T_{v,e_{bhv}}[(bh, η)] = T_{v,e_{bv}}[(b, ρ(h)η)] = [(id, t_{b}(ρ(h)η)],

so

t_{bh} = t_{b}ρ(h), b ∈ B, h ∈ H.  (39)

On the other hand, the G invariance of T implies that for any k ∈ H we have

[(id, t_{b}η)] = T_{v,e_{b}}[(b, η)]
= k^{−1}T_{v,e_{kb}}k[(b, η)]
= k^{−1}[(id, t_{kb}η)]
= [(k^{−1}, t_{kb}η)]
= [(id, ρ(k)^{−1}t_{kb}η)]

so

t_{kb} = ρ(k)t_{b}, b ∈ B, k ∈ H.  (40)

Suppose that we start with isomorphisms T_{v,e}, one for each of the edges, e, emanating from the origin, v. What are the conditions on the family of isomorphisms which allow us to extend it to a G invariant connection on all of E ? We must demand H invariance, so

T_{v,ekb} = kT_{v,e−b}k^{−1}, ∀k ∈ H, b ∈ B.  (41)

Also, if b ∈ B,we have b^{−1}bv = v with b^{−1}e_{b} = e_{b^{−1}} so (??) implies that

b^{−1}T_{v,e_{b}}b = [T_{v,e_{b^{−1}}} ]^{−1},

or

T_{v,e_{b^{−1}}} = b^{−1}T_{v,e_{b}}^{−1}b.  (42)

If we start with a family of isomorphisms, T_{v,e}, for all edges emanating from v which satisfy (??) and (??), then we can use the transitive action of G to define the connection isomorphism for an edge emanating from any vertex and so get a unique G invariant connection on E. If we wish to define the T via (??) the t_{b} must satisfy(??). Condition (??) gives (??) while a direct check from the definitions shows that (??) is equivalent to

t_{b^{−1}} = t_{b}^{−1}.  (43)

So we have proved

Theorem 4 Any G invariant connection on E defines a family of isomorphisms, t_{b} ∈ Aut(X), b ∈ B which satisfy (??), (??), (??) and (??). Conversely, starting with t_{b}, b ∈ B satisfying these conditions, we get a unique G invariant connection on E.

Now the proof of Theorem 3 goes over with only minor modifications to give:

Theorem 5 Under the identification of sec E as a subspace of F(G, X), the operator F can be represented as the restriction to sec E of the operator

F = (∑_{b∈B} A_{v,be}) ⊗ I − ∑_{b∈B} A_{v,be}t_{b} ⊗ r(b).  (44)

Example. As was emphasized to us by Prof. kostant, the group G = Sl(2, 5) acts on the buckyball graph. Since P Sl(2, 5) ∼ A_{5} is the group of rotational symmetries, the isotropy subgroup of a point is Z_{2}. So there will be exactly two homogeneous line bundles for G corresponding to the two characters of H. The trivial character induces to the space of functions, and we get the usual Laplacian as we have already discussed. If we choose the non-trivial character, we get a line bundle, E, and Frobenius reciprocity says that sec E decomposes under G into a direct sum of the irreducible representations of G which do not descend to A_{5}, each occurring with a multiplicity equal to its dimension.

Choose a vertex,v, of the buckyball to serve as origin. Let w ∈ G be one of the two elements of order four which move v to its double bond (i.e. hexagonal) neighbor. Then w^{−1} = −w so (??) implies that

t_{w} = ±i.

Let b be one of the cyclic generators of order five which moves v to one of its single bond (pentagonal) neighbors. But (??) imposes no condition on t_{b}. The spectrum of the Laplacians on this line bundle is discussed in [?].

References

[1] N.Biggs, Algebraic Graph Theory, Cambridge Univ. Press (1974)

[2] B.Brooks, Combinatorial problems in spectral geometry, in Curvature and Topology of Riemannian Manifolds Springer Lecture Notes in Mathematics.1201 (1988), 14-32

[3] M. Burrow, Representation Theory of Finite Groups Academic Press, New York (1965)

[4] F.R.K.Chung, D.Rockmore, S.Sternberg, preprint.

[5] J. H. Conway, Monsters and Moonshine, The Mathematical Intelligencer 2 (1980)165-171

[6] C.A.Coulson, B. O’Leary, R.B. Mallon,Hückel theory for Organic Chemists Academic Press (1978)

[7] P. Diaconis, Group Representations in Probability and Statistics Institute of Mathematical Statistics, Hayward, CA, (1988)

[8] S. J. Duclos, R. C. Haddon, S. H. Glarum, A. F. Hebard, and K. B. Lyons, Raman studies of alkali-metal doped A_{x}C_{60} films (A = Na, K, Rb, Cs; x = 0, 3, 6), Science 254 (1991) 1625.

[9] G. Frobenius, Uber Gruppencharaktere, Sitzungsber. Pruess. Akad. Wiss. Berlin (1896) 985-1021 and Uber die Primfaktoren der Gruppendeterminante, Sitzungsber. Pruess. Akad. Wiss. Berlin (1896) 1343-1382.

[10] G. Frobenius, Uber die Charaktere der alternierenden Gruppe, Sitzungsberichte Preuss. Akad. Wiss. (1901) 303-315

[11] W. Krätschmer, Lowell D. Lamb, K. Fostiropoulos and Donald R. Huffman, Solid C_{60}: a new form of carbon, Nature, 347 (September 1990) 354-358.

[12] C. Rebbi, Lattice Gauge Theories and Monte Carlo Simulations World Scientific (1983)

[13] S.Sternberg, Group Theory in Physics, Cambridge University Press(1992)

[14] Kai-An Wang, Ping Zhou, Ying Wang, J. M. Holden, Song-lin Ren, G. T. Ni, P. C. Eklund, G. Dresselhaus and M. S. Dresselhaus, Raman scattering in M_{x}C_{60} films (M = K, Rb, Cs; x = 0, 3, 6), Phys. Rev. B (to appear).