One of the most important discoveries in the history of science is the structure of the periodic table. This structure is a consequence of how electrons cluster around atomic nuclei and is essentially quantum-mechanical in nature. Most of it (the part not having to do with spin) can be deduced by solving the Schrödinger equation by hand, but it is conceptually cleaner to use the symmetries of the situation and representation theory. Deducing these results using representation theory has the added benefit that it identifies which parts of the situation depend only on symmetry and which parts depend on the particular form of the Hamiltonian. This is nicely explained in Singer’s Linearity, symmetry, and prediction in the hydrogen atom.
For awhile now I’ve been interested in finding a toy model to study the basic structure of the arguments involved, as well as more generally to get a hang for quantum mechanics, while avoiding some of the mathematical difficulties. Today I’d like to describe one such model involving finite graphs, which replaces the infinite-dimensional Hilbert spaces and Lie groups occurring in the analysis of the hydrogen atom with finite-dimensional Hilbert spaces and finite groups. This model will, among other things, allow us to think of representations of finite groups as particles moving around on graphs.
I am going to be vague about the mathematics here because it’s all about to get a lot simpler anyway. I am also not going to justify the physics because I am not particularly knowledgeable in this area.
In quantum mechanics, the states of a quantum system in a configuration space are described by unit vectors in the Hilbert space up to phase, that is, up to multiplication by a complex number of norm . The system does not have a definite state in ; instead, if the state is , the probability that the state of the system lies in a region is the integral of over .
Observables in a quantum system are given by self-adjoint operators , and their values can be predicted as follows: if is sufficiently nice, it has an orthonormal basis of eigenvectors with corresponding real eigenvalues . If our quantum system is in a state , then takes the value with probability , and the state is then projected to the -eigenspace (wave function collapse). In particular, the expected value of is given by . (If has continuous spectrum, as is the case with the position operator, then one must do more work. Discrete spectrum, however, occurs in many applications and is responsible for the discreteness after which quantum mechanics is named, and we will only be dealing with discrete spectrum anyway.)
Time evolution of a quantum system is described by a strongly continuous one-parameter unitary group, that is, a collection of unitary operators such that and such that in the strong operator topology. By Stone’s theorem, there exists a self-adjoint operator such that . (Since can stand for a more general one-parameter group of symmetries of our quantum system, this is a form of Noether’s theorem in quantum mechanics.) An appropriate multiple of is then the observable corresponding to energy; it is called the Hamiltonian , we label its eigenvalues , and the dynamics of our quantum system are then described by the Schrödinger equation
where describes the time evolution of our system (and should perhaps be written ) and is the reduced Planck constant. Note that this is equivalent to having the form
Given the eigenvalues and eigenvectors of , we can write down the family of solutions
to the Schrödinger equation, and since the are an orthonormal basis, these solutions span the space of solutions (in the Hilbert space sense). These are the solutions for which the energy takes the definite value , so they are called the base states relative to . A generic state in is a linear combination of base states, so energy does not take a definite value for such a state. However, time evolution preserves the probability distribution on the set of possible energies of a state, which is a form of conservation of energy. More generally, an observable (a self-adjoint operator) is preserved by time evolution if and only if it commutes with the Hamiltonian .
If the eigenspaces of are all one-dimensional, as one would expect to happen for generic choices of , then knowing the energy of a base state uniquely determines it up to phase. However, in many quantum systems of interest, is far from generic, and the eigenspaces are larger; this means that more than one base state will have the same energy in general, which physicists refer to as degeneration. In the degenerate case, one must use additional observables other than energy to name states.
A general mechanism which produces degeneration is the existence of a sufficiently large group of symmetries of the Hamiltonian, that is, a group of unitary operators on which commute with . The reason is that acts on the eigenspaces of , so if the representation of on is nontrivial then the eigenspaces of must carry nontrivial irreducible subrepresentations (and in particular must degenerate if is non-abelian). This is certainly the case for an important example, the case of a single electron in a hydrogen atom, where and includes the group (but, as it turns out, actually includes the larger group ). Here, the decomposition of the eigenspaces of into irreducible representations of is responsible for the list of possible states of the electron. The idea here is that as long as we are going to attempt to label different parts of each energy eigenspace, we might as well do it in a -invariant way. In any case, the decomposition of into irreducible representations of , which exists independent of the form of the Hamiltonian, strongly constrains the energy eigenspaces of any Hamiltonian with -symmetry.
Solutions to the Schrödinger equation are called wave functions; the historical reason is related to wave-particle duality. Informally, one can think of an eigenvector of the Hamiltonian with eigenvalue as vibrating at angular frequency , a manifestation of the de Broglie relations connecting energy and frequency. This vibration is not noticeable if the state of the system is , since time evolution will only change its phase, but if the state of the system is a superposition of states then they will interfere with one another roughly as if they were waves with the corresponding angular frequencies, as one can readily verify. (It’s not healthy to take this intuition too seriously, though. Quantum mechanics is quantum mechanics, regardless of one’s intuitions about either waves or particles.)
Part of wave-particle duality is a mathematical similarity between the eigenfunctions of Hamiltonians which occur in nature and solutions to the wave equation. A particle in moving under the influence of a potential has quantum Hamiltonian
where is the Laplacian, is the mass of the particle, and denotes the operator corresponding to multiplication by . This is true more generally for a particle in a Riemannian manifold, where is the Laplace-Beltrami operator. Here the first term is the kinetic energy of the particle and the second term is the potential energy. It follows that solutions to the Schrödinger equation in this case involve eigenfunctions of the Laplacian, which are the same functions which correspond to the standing wave solutions of the wave equation.
This suggests that in order to find finite toy models of quantum systems, we should find a finite analogue of the Laplacian. The usual choice is as follows. Our configuration space will be the vertices of an undirected finite graph with no self-loops, but possibly with multiple edges. We denote by and its edge and vertex sets, respectively, and by the Hilbert space of functions with inner product
The state of our particle is then described by a unit vector in . To construct a Hamiltonian we define the Laplacian (or combinatorial Laplacian)
(There is a sign convention to choose here, and I am choosing the one which gives the better analogy to the usual Laplacian.) In other words, if we define by (the degree operator) and by (the adjacency operator), then . (In particular, if is regular then the Laplacian differs from the adjacency matrix by an identity matrix, so talking about the eigenvalues of one is equivalent to talking about the eigenvalues of the other.)
The Laplacian naturally arises in the study of random walks and electrical networks (see, for example, Doyle and Snell). Informally it measures the extent to which the value of at differs from the average of the value at its neighbors, and if we take with its natural graph structure then can be written as a sum of discrete second finite differences which approximates the Laplacian on . For example, the combinatorial Laplacian on is just
Before looking at the Schrödinger equation, it is perhaps a good idea to look at two other natural differential equations one can define using the Laplacian on a finite graph which generalize to to give, in the limit, well-known partial differential equations. First, the heat equation
can be motivated as follows: we want a function describing the evolution of a heat distribution on the vertices over time. Heat should tend to propagate from hot regions to cool regions, so a given vertex should lose heat proportional to how much hotter it is than its neighbors. (There should be a constant in there describing how quickly heat propagates, but it is not particularly important for the discussion that follows.) Since heat is the result of Brownian motion of particles, we expect that heat equation on a finite graph is related to the behavior of random walks on the graph.
What are the possible stable heat distributions on a finite graph? These are precisely the (real-valued) solutions to , or the harmonic functions.
Proposition: A (real-valued) function on a finite graph is harmonic if and only if it is constant on connected components.
Proof. Verify that
hence that implies for every . On the other hand any such function is harmonic. One can also argue by a finite form of the maximum modulus principle: is harmonic if and only if the value of at any vertex is the average of its neighbors, so since there are only finitely many vertices in each connected component, there must be some vertex for which is maximal. Since this maximal value is the average over all its neighbors, the neighbors of must share that value. In physical terms, there cannot be a hottest point on any connected component, since heat would have flowed away from it to some other point.
The argument above establishes more than we asked for: it shows that, not only is the Laplacian self-adjoint (hence has all real eigenvalues), but it is also negative-semidefinite (since its negative represents a positive-semidefinite quadratic form), and the multiplicity of the eigenvalue is the number of connected components of the graph, and the remaining eigenvalues are all negative. The general solution to the heat equation is a linear combination of the solutions
corresponding to each (real) eigenvector of the Laplacian with eigenvalue ; since the nonzero eigenvalues are negative, these solutions have temperature decaying to zero as is physically reasonable. In fact these solutions of the heat equation correspond to modes of “pure decay,” where the temperature decays exponentially in the simplest possible way, and the general solution is a linear combination of these modes. The rate of decay from generic initial conditions is controlled by the eigenvalue closest to zero, and if the graph is connected, this is the eigenvalue second smallest in absolute value , a fundamental invariant called the algebraic connectivity in graph theory. It is related to several other measures of connectivity in graphs and is important in the theory of expander graphs.
Similarly, the wave equation
can be motivated as follows: imagine that our graph describes a system of point masses connected by springs, one for each edge. Hooke’s law then tells us that, if we displace these point masses very slightly, the restoring force that pulls a given vertex back to equilibrium is proportional to the sum of the differences in the displacements between that vertex and its neighbors. The general solution to the wave equation is a linear combination of the solutions
(keeping in mind that the eigenvalues are negative), and it is because of this that the eigenvectors of the Laplacian on anything are called its harmonics. The solutions above are the standing waves, and so we know we can express any solution to the wave equation as a superposition of standing waves.
I think the following would be a very fun project for a graph theory class: for various interesting graphs, plot using mathematical software the solutions to the heat and wave equations from various initial conditions. I would do this myself if I had more time.
The Schrödinger equation (without potential)
Replacing the continuous Laplacian by a discrete Laplacian, and in the absence of a potential, the Schrödinger equation on a finite graph (which we will assume to be connected) reads
The energy eigenvalues of the Hamiltonian are related to the eigenvalues of the Laplacian by ; in particular, they are non-negative, and the vacuum state, which has energy zero, has multiplicity . The corresponding eigenvector, the all-ones vector, corresponds to a state with position smeared out evenly over all of . The general solution is a superposition of the solutions
which are the states in which the energy has a definite value . And for a general state , the probability that a particle moving around will be measured at location is given by .
If the eigenvalues of the Laplacian all have multiplicity , then as mentioned above, the energy constitutes a completely satisfying label for base states. Consider, therefore, what happens when the graph has a nontrivial automorphism group . In that case, each energy eigenspace decomposes into a direct sum of representations of , at least one of which will be nontrivial, so if these irreducible representations have dimension greater than some eigenspace must degenerate. (There is a purely graph-theoretic consequence of this argument: if the eigenvalues of the Laplacian of a graph have multiplicity , then the automorphism group of the graph is abelian.) One of these eigenstates, the vacuum state, always corresponds to a copy of the trivial representation. In general the character of the representation of on is , so the number of copies of the trivial representation is
which is also, by Burnside’s lemma, the number of orbits of the action of on . (The subspace spanned by copies of the trivial representation is precisely the subspace spanned by functions constant on orbits.) In particular, if acts transitively then there are no other copies of the trivial representation. In any case, this suggests that we should restrict our attention to the positive subspace, the orthogonal complement of the all-ones vector (where the Hamiltonian has positive eigenvalues).
Example. Let be the complete graph . Then acts, not only transitively, but double transitively, on . This implies (this is a nice exercise) that the positive subspace is an irreducible representation of , which means that it must correspond to a single energy eigenspace of dimension . By computing the trace of the Laplacian, or otherwise, we see that the corresponding eigenvalue is , hence corresponds to energy . We can further slice up this eigenspace by picking out permutations in , but I don’t see a particularly good reason to do this in this case.
Time evolution starting from the state (where the particle is at some vertex with probability ; we can prepare this state by observing the position of the particle) is as follows. We write
where the first vector is in the zero eigenspace and the second is in the positive subspace, and the Schrödinger equation then gives
Thus at time , the probability that the particle is at its starting vertex is
and the probability that it is at any particular other vertex is
This particle is in a superposition of two base states: the vacuum state where it is uniformly distributed over all other vertices, and a positive-energy state where it is found at its original vertex with high probability and at the other vertices with low probability. The observed behavior is “interference” between these two states. One can think of these results as a very simple manifestation of the uncertainty principle: the particle resists being located entirely at its starting vertex, so it distributes itself a little across all the other vertices. (We will give a slightly better manifestation of the uncertainty principle later.)
The complete graph is somewhat anomalous in how degenerate its positive eigenspace is: the only way the group of automorphisms of a graph can act double transitively on it in general is if it is either the complete graph or the empty graph, so in any other case the positive subspace decomposes into two or more irreducible representations. We can get a grip on how many of these there are as follows. By character theory, if decomposes into a direct sum of copies of the irreducible representation of , then
By Burnside’s lemma, this is just the number of orbits of acting on . There is always one orbit consisting of pairs of identical vertices, and the number of remaining orbits constrains how many representations can occur in the positive subspace. In particular, since , it follows that the number of orbits of on pairs of distinct vertices is an upper bound on the number of representations the positive subspace decomposes into (hence on the number of distinct positive eigenvalues the Laplacian can have). One can think of the number of orbits as “the number of ways two distinct vertices can stand in relation to each other up to automorphism,” and for structured graphs that makes it relatively easy to count directly.
Example. Consider the Kneser graph of -element subsets of , where two subsets are joined by an edge if they are disjoint. The graph has automorphism group acting in the obvious way, two distinct vertices can only be related to each other in two ways up to the action of : they can be connected or not connected. It follows that the positive eigenspace decomposes into two irreducible representations of of total dimension . Given an element , consider the vector in the positive subspace equal to on subsets containing and equal to on subsets not containing . The vectors add to zero and acts on them via its standard permutation reprsentation, hence they span a -dimensional irreducible representation corresponding to the positive subspace of the representation of on . The orthogonal complement of this representation is a -dimensional irreducible representation whose character is now easy to write down. I will leave the computation of the corresponding energy eigenvalues as an exercise.
In ordinary quantum mechanics, linear momentum comes from the self-adjoint operators which generate linear translations via Stone’s theorem, and angular momentum comes from the self-adjoint operators which generate rotations. So momentum is generally related to spatial symmetries. In the finite graph model, spatial symmetries – the automorphisms of the graph – are discrete, so Stone’s theorem doesn’t apply. But we can still give a definition of a quantity which behaves something like momentum.
Definition: Let and suppose that a state is an eigenvector for with eigenvalue . Then is the -momentum of .
In other words, it’s what the eigenvalue of a self-adjoint operator generating would be if it existed. The -momentum does not come from a self-adjoint operator and so is not an observable as we have narrowly defined it, but nevertheless it is still a number which behaves like ordinary momentum; one might think of it as the momentum the particle has in the “direction” given by . And it is still possible, for an arbitrary , to write down the probability that the -momentum is one of its several possible values, and to decompose the energy eigenspaces of the Hamiltonian by the eigenspaces of , each one corresponding to a particular value for the -momentum. And since commutes with the Laplacian, -momentum is conserved by time evolution.
Example. Let be the cycle graph , with vertices . Then is the dihedral group . Letting be the rotation , the decomposition of into eigenspaces of is straightforward, since it is the same as the decomposition of the regular representation of : the eigenspace spanned by the eigenvector where is the one where the -momentum has value .
In this particular case the Laplacian can be written in terms of : it is precisely equal to , hence is an eigenvector of the Laplacian with eigenvalue , hence energy . Since it follows that eigenvectors pair up into energy eigenspaces (and in fact, pair up into irreducible representations of ), and we can slice up each pair according to whether the -momentum is directed clockwise or counterclockwise (as measured by whether it is closer to in the clockwise or counterclockwise direction).
This situation is the discrete analogue of the particle in a ring, and indeed note that the eigenvectors are very similar and that if is very small compared to we have , hence
which is very close to the lower energy levels of the spectrum in the continuous case. (One should think of as a conversion factor between the discrete and continuous Laplacians.)
The cycle graph is also not a bad place to demonstrate another form of the uncertainty principle: position and -momentum operators do not commute. Here by a position operator we mean a self-adjoint operator which projects onto the subspace of functions nonzero except at a particular . In particular, as is already clear from our computations above, there is no state in in which both position and -momentum are uniquely determined (a common eigenvector). Furthermore, a state in which position is completely determined is a state with maximum ambiguity in -momentum:
Conversely, a state in which -momentum is completely determined is a state with maximum ambiguity in position. One should think of this in terms of the discrete Fourier transform, since the story parallels perfectly the story of the Fourier transform on which describes the relationship between position and momentum for free particles in .
Representations, duals, and tensor products
There is a philosophy going back at least as far as Wigner that irreducible representations of the symmetry group of a quantum system should be identified with the possible types of particles in that system. This seems pretty reasonable: if is a wave function describing some particle then for should be thought of as the same particle, just moving in a different direction, so it is natural to collect all of these wave functions into the same representation of . Thus an arbitrary wave function is a superposition of different types of particles corresponding to the different irreducible representations of occurring in the decomposition of .
This gives us a physical language for making sense of basic operations on representations. For example, if is an irreducible subrepresentation of , then since the character of is real, it follows that the dual representation is also an irreducible subrepresentation. (Concretely, it is obtained from by taking the complex conjugate of the corresponding wave functions. If has a basis of wave functions with real coordinates, then .) In physical language, one might call the antiparticle of . Note that if has energy eigenvalue , then evolves as
whereas its antiparticle evolves as
The probabilities one computes from this evolution are the same as the probabilities one computes from its complex conjugate
and so one might say that an antiparticle is “the same thing” as the original particle going backwards in time. But in the finite graph model one should be a little more careful about this, since the above object is not, strictly speaking, a solution to the Schrödinger equation when is positive.
Particles and antiparticles are probably best known for colliding. To give this operation some kind of meaning in the finite graph model, we must first discuss the following general construction. If one quantum system is given by a Hilbert space and another is given by a Hilbert space , then to study them together, we work in the Hilbert space tensor product , and we call the corresponding quantum system the composite system. This is the natural thing to do if, for example, and are the Hilbert spaces of states of two particles and you want to study the particles together. (But it is also the natural thing to do if and describe two aspects of the same object, e.g. the and -coordinates of a particle in the plane.) Given any self-adjoint operator on we get a self-adjoint operator on , and similarly for , so one can make all of the same observations on each subsystem as before. In addition, for every symmetry of there is a corresponding symmetry of , and similarly for . If are both equipped with Hamiltonians , then the operators giving the energy of each subsystem are , so the total energy is a new Hamiltonian
(assuming there is no interaction between the subsystems; otherwise we need a third term to describe that interaction.) The time evolution operator given by the Schrödinger equation for is then
since and commute. It follows that if are states in , then the time evolution of the state in is given by the individual evolution of each state in each subsystem. Of course, in general a state in is a superposition of states of the form ; this is the mechanism behind quantum entanglement.
If are finite graph models on graphs , then their tensor product can be identified with , and the composite Hamiltonian is the Hamiltonian of a new finite graph model given by a new graph structure on , the Cartesian product (or box product) of graphs . The box product has Laplacian
so it defines the correct composite Hamiltonian. There is even a Wikipedia article about this construction, in the special case of the usual discrete Laplacian on . (Note that the Cartesian product of copies of is with the obvious graph structure, a nice property not shared by the tensor product of graphs. More generally, it does the obvious thing to Cayley graphs.) Thus one can identify a pair of free particles traveling on and with a single free particle traveling on .
Remark: Philosophically, it seems to me that the distinction between the box product and the tensor product comes from whether one wants to treat the Laplacian as a one-dimensional Lie algebra acting on the graph or whether one wants to treat, say, the adjacency matrix as a monoid acting on the graph.
For every pair of eigenvectors of the Laplacians with eigenvalues , there is an eigenvector of the composite Laplacian with eigenvalue , and this is a complete orthonormal basis of eigenvectors. The energy eigenspaces of decompose into irreducible representations of where is the symmetry group of , and these irreducible representations are exactly what you would expect: tensor products of irreducible representations of the groups . (Note that may have additional symmetries which allow us to group some of these representations together into larger irreducible representations.)
Now suppose that . Then one can think of a pair of free particles on as traveling on the same copy of (although not interacting), and instead of allowing as the symmetry group we should only consider symmetries we can perform on both particles at once, that is, the diagonal copy of inside . Then is the tensor square of the representation of given by , so one can think of a tensor product of two subrepresentations of as describing the behavior of a pair of particles on , one of which is of type and one of which is of type . Since is not usually itself irreducible, this representation breaks up into irreducible components, which correspond to the different types of ways (up to symmetry) that a particle of type and a particle of type can behave together on .
A collision between a particle of type and a particle of type can then be thought of as a morphism of representations of , where is some subrepresentation of . That is, it is a linear and -invariant process for obtaining a new particle. And if , there is a canonical -invariant morphism (where denotes the trivial representation) given by the dual pairing. Physicists call this morphism particle-antiparticle annihilation, since its result is the vacuum state. The dual morphism (whose image corresponds to the identity operator ) is particle-antiparticle creation.
If one wants to think of all these morphisms as taking place in the same Hilbert space, then the natural thing to do is to set up a Hilbert space which is large enough to accompany any finite number of particles. The operation on Hilbert spaces correspond to studying a subsystem or a subsystem (in contrast to the tensor product, where we want to study the first and the second) is the direct sum , so we construct the tensor algebra
Since the tensor products of a faithful representation of a finite group contain all irreducible representations of that group, it follows that we can get all irreducible representations of by considering enough different particles moving around on .
In practice, people don’t work with the full tensor algebra. This is because particles in physics of the same type are actually identical (for example, every pair of electrons is identical, as is every pair of photons, etc.), so switching the identities of two particles is a physical symmetry. The two simplest cases are bosons, where switching the two particles gives exactly the same composite wave function, and fermions, where switching the two particles gives the negative of the original wave function. This means that instead of working in the full tensor square , we work instead in either the symmetric square (for bosons) or the exterior square (for fermions). Similarly, for particles, instead of working in the full tensor power we work in either the symmetric power or the exterior power. So to work with a variable number of particles, instead of working in the tensor algebra, we work in either the symmetric algebra or the exterior algebra; in either case the corresponding construction is called Fock space. Note that the need to work in exterior powers for fermions is responsible for the Pauli exclusion principle. Fermions and bosons are not easy to explain in the context of the finite graph model itself; they are a consequence of the spin-statistics theorem, which is relativistic. In any case, we now have a physical interpretation of the symmetric and exterior powers, and of the symmetric and exterior algebras.
(Regardless of whether one cares about fermions and bosons in the finite graph model, the Hilbert space describing identical particles on still has an -symmetry relative to which it decomposes in terms of irreducible representations of , so one still needs to understand the corresponding Schur functors to understand the ways in which particles can behave up to symmetry.)