You are currently browsing the monthly archive for July 2010.

I’ll be taking a break from blogging and other work for a few weeks.

Let {A, B} be two Hermitian {n \times n} matrices. When {A} and {B} commute, we have the identity

\displaystyle  e^{A+B} = e^A e^B.

When {A} and {B} do not commute, the situation is more complicated; we have the Baker-Campbell-Hausdorff formula

\displaystyle  e^{A+B} = e^A e^B e^{-\frac{1}{2}[A,B]} \ldots

where the infinite product here is explicit but very messy. On the other hand, taking determinants we still have the identity

\displaystyle  \hbox{det}(e^{A+B}) = \hbox{det}(e^A e^B).

Recently I learned (from Emmanuel Candes, who in turn learned it from David Gross) that there is another very nice relationship between {e^{A+B}} and {e^A e^B}, namely the Golden-Thompson inequality

\displaystyle  \hbox{tr}(e^{A+B}) \leq \hbox{tr}(e^A e^B). \ \ \ \ \ (1)

The remarkable thing about this inequality is that no commutativity hypotheses whatsoever on the matrices {A, B} are required. Note that the right-hand side can be rearranged using the cyclic property of trace as {\hbox{tr}( e^{B/2} e^A e^{B/2} )}; the expression inside the trace is positive definite so the right-hand side is positive. (On the other hand, there is no reason why expressions such as {\hbox{tr}(e^A e^B e^C)} need to be positive or even real, so the obvious extension of the Golden-Thompson inequality to three or more Hermitian matrices fails.) I am told that this inequality is quite useful in statistical mechanics, although I do not know the details of this.
To get a sense of how delicate the Golden-Thompson inequality is, let us expand both sides to fourth order in {A, B}. The left-hand side expands as

\displaystyle  \hbox{tr} 1 + \hbox{tr} (A+B) + \frac{1}{2} \hbox{tr} (A^2 + AB + BA + B^2) + \frac{1}{6} \hbox{tr} (A+B)^3

\displaystyle  + \frac{1}{24} \hbox{tr} (A+B)^4 + \ldots

while the right-hand side expands as

\displaystyle  \hbox{tr} 1 + \hbox{tr} (A+B) + \frac{1}{2} \hbox{tr} (A^2 + 2AB + B^2)

\displaystyle  + \frac{1}{6} \hbox{tr} (A^3 + 3A^2 B + 3 A B^2+B^3) +

\displaystyle  \frac{1}{24} \hbox{tr} (A^4 + 4 A^3 B + 6 A^2 B^2 + 4 A B^3 +B^4) + \ldots

Using the cyclic property of trace {\hbox{tr}(AB) = \hbox{tr}(BA)}, one can verify that all terms up to third order agree. Turning to the fourth order terms, one sees after expanding out {(A+B)^4} and using the cyclic property of trace as much as possible, we see that the fourth order terms almost agree, but the left-hand side contains a term {\frac{1}{12} \hbox{tr}(ABAB)} whose counterpart on the right-hand side is {\frac{1}{12} \hbox{tr}(ABBA)}. The difference between the two can be factorised (again using the cyclic property of trace) as {-\frac{1}{24} \hbox{tr} [A,B]^2}. Since {[A,B] := AB-BA} is skew-Hermitian, {-[A,B]^2} is positive definite, and so we have proven the Golden-Thompson inequality to fourth order. (One could also have used the Cauchy-Schwarz inequality for the Frobenius norm to establish this; see below.)
Intuitively, the Golden-Thompson inequality is asserting that interactions between a pair {A, B} of non-commuting Hermitian matrices are strongest when cross-interactions are kept to a minimum, so that all the {A} factors lie on one side of a product and all the {B} factors lie on the other. Indeed, this theme will be running through the proof of this inequality, to which we now turn.

Read the rest of this entry »

In most undergraduate courses, groups are first introduced as a primarily algebraic concept – a set equipped with a number of algebraic operations (group multiplication, multiplicative inverse, and multiplicative identity) and obeying a number of rules of algebra (most notably the associative law). It is only somewhat later that one learns that groups are not solely an algebraic object, but can also be equipped with the structure of a manifold (giving rise to Lie groups) or a topological space (giving rise to topological groups). (See also this post for a number of other ways to think about groups.)

Another important way to enrich the structure of a group {G} is to give it some geometry. A fundamental way to provide such a geometric structure is to specify a list of generators {S} of the group {G}. Let us call such a pair {(G,S)} a generated group; in many important cases the set of generators {S} is finite, leading to a finitely generated group. A generated group {(G,S)} gives rise to the word metric {d: G \times G \rightarrow {\bf N}} on {G}, defined to be the maximal metric for which {d(x,sx) \leq 1} for all {x \in G} and {s \in S} (or more explicitly, {d(x,y)} is the least {m} for which {y = s_1^{\epsilon_1} \ldots s_m^{\epsilon_m} x} for some {s_1,\ldots,s_m \in S} and {\epsilon_1,\ldots,\epsilon_m \in \{-1,+1\}}). This metric then generates the balls {B_S(R) := \{ x \in G: d(x,\hbox{id}) \leq R \}}. In the finitely generated case, the {B_S(R)} are finite sets, and the rate at which the cardinality of these sets grow in {R} is an important topic in the field of geometric group theory. The idea of studying a finitely generated group via the geometry of its metric goes back at least to the work of Dehn.

One way to visualise the geometry of a generated group is to look at the (labeled) Cayley colour graph of the generated group {(G,S)}. This is a directed coloured graph, with edges coloured by the elements of {S}, and vertices labeled by elements of {G}, with a directed edge of colour {s} from {x} to {sx} for each {x \in G} and {s \in S}. The word metric then corresponds to the graph metric of the Cayley graph.

For instance, the Cayley graph of the cyclic group {{\bf Z}/6{\bf Z}} with a single generator {S = \{1\}} (which we draw in green) is given as

while the Cayley graph of the same group but with the generators {S = \{2,3\}} (which we draw in blue and red respectively) is given as

We can thus see that the same group can have somewhat different geometry if one changes the set of generators. For instance, in a large cyclic group {{\bf Z}/N{\bf Z}}, with a single generator {S = \{1\}} the Cayley graph “looks one-dimensional”, and balls {B_S(R)} grow linearly in {R} until they saturate the entire group, whereas with two generators {S = \{s_1,s_2\}} chosen at random, the Cayley graph “looks two-dimensional”, and the balls {B_S(R)} typically grow quadratically until they saturate the entire group.

Cayley graphs have three distinguishing properties:

  • (Regularity) For each colour {s \in S}, every vertex {x} has a single {s}-edge leading out of {x}, and a single {s}-edge leading into {x}.
  • (Connectedness) The graph is connected.
  • (Homogeneity) For every pair of vertices {x, y}, there is a unique coloured graph isomorphism that maps {x} to {y}.

It is easy to verify that a directed coloured graph is a Cayley graph (up to relabeling) if and only if it obeys the above three properties. Indeed, given a graph {(V,E)} with the above properties, one sets {G} to equal the (coloured) automorphism group of the graph {(V,E)}; arbitrarily designating one of the vertices of {V} to be the identity element {\hbox{id}}, we can then identify all the other vertices in {V} with a group element. One then identifies each colour {s \in S} with the vertex that one reaches from {\hbox{id}} by an {s}-coloured edge. Conversely, every Cayley graph of a generated group {(G,S)} is clearly regular, is connected because {S} generates {G}, and has isomorphisms given by right multiplication {x \mapsto xg} for all {g\in G}. (The regularity and connectedness properties already ensure the uniqueness component of the homogeneity property.)

From the above equivalence, we see that we do not really need the vertex labels on the Cayley graph in order to describe a generated group, and so we will now drop these labels and work solely with unlabeled Cayley graphs, in which the vertex set is not already identified with the group. As we saw above, one just needs to designate a marked vertex of the graph as the “identity” or “origin” in order to turn an unlabeled Cayley graph into a labeled Cayley graph; but from homogeneity we see that all vertices of an unlabeled Cayley graph “look the same” and there is no canonical preference for choosing one vertex as the identity over another. I prefer here to keep the graphs unlabeled to emphasise the homogeneous nature of the graph.

It is instructive to revisit the basic concepts of group theory using the language of (unlabeled) Cayley graphs, and to see how geometric many of these concepts are. In order to facilitate the drawing of pictures, I work here only with small finite groups (or Cayley graphs), but the discussion certainly is applicable to large or infinite groups (or Cayley graphs) also.

For instance, in this setting, the concept of abelianness is analogous to that of a flat (zero-curvature) geometry: given any two colours {s_1, s_2}, a directed path with colours {s_1, s_2, s_1^{-1}, s_2^{-1}} (adopting the obvious convention that the reversal of an {s}-coloured directed edge is considered an {s^{-1}}-coloured directed edge) returns to where it started. (Note that a generated group {(G,S)} is abelian if and only if the generators in {S} pairwise commute with each other.) Thus, for instance, the two depictions of {{\bf Z}/6{\bf Z}} above are abelian, whereas the group {S_3}, which is also the dihedral group of the triangle and thus admits the Cayley graph

is not abelian.

A subgroup {(G',S')} of a generated group {(G,S)} can be easily described in Cayley graph language if the generators {S'} of {G'} happen to be a subset of the generators {S} of {G}. In that case, if one begins with the Cayley graph of {(G,S)} and erases all colours except for those colours in {S'}, then the graph foliates into connected components, each of which is isomorphic to the Cayley graph of {(G',S')}. For instance, in the above Cayley graph depiction of {S_3}, erasing the blue colour leads to three copies of the red Cayley graph (which has {{\bf Z}/2{\bf Z}} as its structure group), while erasing the red colour leads to two copies of the blue Cayley graph (which as {A_3 \equiv {\bf Z}/3{\bf Z}} as its structure group). If {S'} is not contained in {S}, then one has to first “change basis” and add or remove some coloured edges to the original Cayley graph before one can obtain this formulation (thus for instance {S_3} contains two more subgroups of order two that are not immediately apparent with this choice of generators). Nevertheless the geometric intuition that subgroups are analogous to foliations is still quite a good one.

We saw that a subgroup {(G',S')} of a generated group {(G,S)} with {S' \subset S} foliates the larger Cayley graph into {S'}-connected components, each of which is a copy of the smaller Cayley graph. The remaining colours in {S} then join those {S'}-components to each other. In some cases, each colour {s \in S\backslash S'} will connect a {S'}-component to exactly one other {S'}-component; this is the case for instance when one splits {S_3} into two blue components. In other cases, a colour {s} can connect a {S'}-component to multiple {S'}-components; this is the case for instance when one splits {S_3} into three red components. The former case occurs precisely when the subgroup {G'} is normal. (Note that a subgroup {G'} of a generated group {(G,S)} is normal if and only if left-multiplication by a generator of {S} maps right-cosets of {G'} to right-cosets of {G'}.) We can then quotient out the {(G',S')} Cayley graph from {(G,S)}, leading to a quotient Cayley graph {(G/G', S \backslash S')} whose vertices are the {S'}-connected components of {(G,S)}, and the edges are projected from {(G,S)} in the obvious manner. We can then view the original graph {(G,S)} as a bundle of {(G',S')}-graphs over a base {(G/G',S\backslash S')}-graph (or equivalently, an extension of the base graph {(G/G',S\backslash S')} by the fibre graph {(G',S')}); for instance {S_3} can be viewed as a bundle of the blue graph {A_3} over the red graph {{\bf Z}/2{\bf Z}}, but not conversely. We thus see that the geometric analogue of the concept of a normal subgroup is that of a bundle. The generators in {S \backslash S'} can be viewed as describing a connection on that bundle.

Note, though, that the structure group of this connection is not simply {G'}, unless {G'} is a central subgroup; instead, it is the larger group {G' \rtimes \hbox{Aut}(G')}, the semi-direct product of {G'} with its automorphism group. This is because a non-central subgroup {G'} can be “twisted around” by operations such as conjugation {g' \mapsto sg's^{-1}} by a generator {s \in S}. So central subgroups are analogous to the geometric notion of a principal bundle. For instance, here is the Heisenberg group

\displaystyle  \begin{pmatrix} 1 & {\bf F}_2 & {\bf F}_2 \\ 0 & 1 & {\bf F}_2 \\ 0 & 0 & 1 \end{pmatrix}

over the field {{\bf F}_2} of two elements, which one can view as a central extension of {{\bf F}_2^2} (the blue and green edges, after quotienting) by {{\bf F}_2} (the red edges):

Note how close this group is to being abelian; more generally, one can think of nilpotent groups as being a slight perturbation of abelian groups.

In the case of {S_3} (viewed as a bundle of the blue graph {A_3} over the red graph {{\bf Z}/2{\bf Z}}), the base graph {{\bf Z}/2{\bf Z}} is in fact embedded (three times) into the large graph {S_3}. More generally, the base graph {(G/G', S \backslash S')} can be lifted back into the extension {(G,S)} if and only if the short exact sequence {0 \rightarrow G' \rightarrow G \rightarrow G/G' \rightarrow 0} splits, in which case {G} becomes a semidirect product {G \equiv G' \rtimes H} of {G'} and a lifted copy {H} of {G/G'}. Not all bundles can be split in this fashion. For instance, consider the group {{\bf Z}/9{\bf Z}}, with the blue generator {1} and the red generator {3}:

This is a {{\bf Z}/3{\bf Z}}-bundle over {{\bf Z}/3{\bf Z}} that does not split; the blue Cayley graph of {{\bf Z}/3{\bf Z}} is not visible in the {{\bf Z}/9{\bf Z}} graph directly, but only after one quotients out the red fibre subgraph. The notion of a splitting in group theory is analogous to the geometric notion of a global gauge. The existence of such a splitting or gauge, and the relationship between two such splittings or gauges, are controlled by the group cohomology of the sequence {0 \rightarrow G' \rightarrow G \rightarrow G/G' \rightarrow 0}.

Even when one has a splitting, the bundle need not be completely trivial, because the bundle is not principal, and the connection can still twist the fibres around. For instance, {S_3} when viewed as a bundle over {{\bf Z}/2{\bf Z}} with fibres {A_3} splits, but observe that if one uses the red generator of this splitting to move from one copy of the blue {A_3} graph to the other, that the orientation of the graph changes. The bundle is trivialisable if and only if {G'} is a direct summand of {G}, i.e. {G} splits as a direct product {G = G' \times H} of a lifted copy {H} of {G/G'}. Thus we see that the geometric analogue of a direct summand is that of a trivialisable bundle (and that trivial bundles are then the analogue of direct products). Note that there can be more than one way to trivialise a bundle. For instance, with the Klein four-group {{\bf Z}/2{\bf Z} \times {\bf Z}/2{\bf Z}},

the red fibre {{\bf Z}/2{\bf Z}} is a direct summand, but one can use either the blue lift of {{\bf Z}/2{\bf Z}} or the green lift of {{\bf Z}/2{\bf Z}} as the complementary factor.

I’ve just opened the Mini-polymath2 project over at the polymath blog.  I decided to use Q5 from the 2010 IMO in the end, rather than Q6, as it seems to be a little bit more challenging and interesting.

This post will serve as the discussion thread of the project, intended to focus all the non-research aspects of the project such as organisational matters or commentary on the progress of the project.     (Is it possible for one blog thread to “live-blog” another?) The third component of the project is the wiki page, which is intended to summarise the progress made so far on the problem.

As with mini-polymath1, I myself will be serving primarily as a moderator, and hope other participants will take the lead in the research and in keeping the wiki up-to-date.   (Ideally, once we get all the kinks in the format ironed out, it should be possible for anyone with a blog and an interested pool of participants to start their own mini-polymath project, without being overly dependent on one key contributor.)