John Baez

November 20, 2009

Groupoidification

For a more formal introduction to the subject, try these:

• John Baez, Alex Hoffnung and Christopher Walker, Higher-dimensional algebra VII: groupoidification.
  (Also in Postscript and LaTeX, and on the arXiv.)
• Alex Hoffnung, The Hecke bicategory.

• John Baez, Groupoidification.
• Christopher Walker, Groupoidified linear algebra.
• Christopher Walker, A categorification of Hall algebras.
• Alex Hoffnung, Categorified Hecke algebras.

• Geometric representation theory seminar, Fall 2007 and Winter 2008.

• Quantization and categorification seminar: Fall 2003, Winter 2004 and Spring 2004.

• John Baez and James Dolan, From finite sets to Feynman diagrams, in Mathematics Unlimited - 2001 and Beyond, vol. 1, edited by Björn Engquist and Wilfried Schmid, Springer, Berlin, 2001, pp. 29-50.

• Jeffrey Morton, Categorified algebra and quantum mechanics, Theory and Applications of Categories 16 (2006), 785-854.

• John Baez, Alexander Hoffnung and Christopher Walker, Groupoidification made easy.
  (Also in Postscript and LaTeX, and on the arXiv.)

The Tale of Groupoidification – Episode 1

 0  0

 1  1 

 1 0 0 0
 1 1 0 0
 1 0 1 0
 1 1 0 1

                     S
                    / \
                   /   \
                 F/     \G
                 /       \
                v         v 
               X           Y

                     S
                    / \
                   /   \
                 F/     \G
                 /       \
                v         v 
               X           Y

12) John Baez and James Dolan, From finite sets to Feynman diagrams, in Mathematics Unlimited - 2001 and Beyond, vol. 1, eds. Bjorn Engquist and Wilfried Schmid, Springer, Berlin, 2001, pp. 29-50. Also available as math.QA/0004133.

And, this can equal any nonnegative rational number! This lets us generalize what we've done from finite sets to finite groupoids, and get rational numbers into the game.

A span of groupoids is a diagram

                     S
                    / \
                   /   \
                 F/     \G
                 /       \
                v         v 
               X           Y

There's also a way of composing spans of groupoids, which corresponds to multiplying matrices. However, there's a trick involved in getting this to work - I'll have to explain this later. For details, try:

13) Jeffrey Morton, Categorified algebra and quantum mechanics, Theory and Application of Categories 16 (2006), 785-854. Available at http://www.emis.de/journals/TAC/volumes/16/29/16-29abs.html; also available as math.QA/0601458.

14) Simon Byrne, On Groupoids and Stuff, honors thesis, Macquarie University, 2005, available at http://www.maths.mq.edu.au/~street/ByrneHons.pdf and http://math.ucr.edu/home/baez/qg-spring2004/ByrneHons.pdf

Anyway: the idea of "groupoidification" is that in many cases where mathematicians think they're playing around with linear operators between vector spaces, they're actually playing around with spans of groupoids!

This is especially true in math related to simple Lie groups, their Lie algebras, quantum groups and the like. While people usually study these gadgets using linear algebra, there's a lot of combinatorics involved - and where combinatorics and symmetry show up, one invariably finds groupoids.

As the name suggests, groupoidification is akin to categorification. But, it's a bit different. In categorification, we try to boost up mathematical ideas this way:

sets → categories
functions → functors

In groupoidification, we try this:

vector spaces → groupoids
linear operators → spans of groupoids

Actually, it's "decategorification" and "degroupoidification" that are systematic processes. These processes lose information, so there's no systematic way to reverse them. But, as I explained in "week99", it's still fun to try! If we succeed, we discover an extra layer of structure beneath the math we thought we understood... and this usually makes that math clearer and less technical, because we're not seeing it through a blurry, information-losing lens.

Episode 2

                     S
                    / \
                   /   \
                 F/     \G
                 /       \
                v         v 
               X           Y

Last time, I gave an example where a Frenchman x and an Englishwoman y were related if they were both the favorites of some Russian s.

Note: there's more information in the span than the relation it determines. The relation either holds or fails to hold. The span does more: it provides a set of "witnesses". The relation holds if this set of witnesses is nonempty, and fails to hold if it's empty.

At least, that's how mathematicians think. When I got married last month, I discovered the state of California demands two witnesses attend the ceremony and sign the application for a marriage license. Here the relation is "being married", and the witnesses attest to that relation - but for the state, one witness is not enough to prove that the relation holds! They're using a more cautious form of logic.

To get the really interesting math to show up, we need to look at other examples of "witnessed relations" - not involving Russians or marriages, but geometry and symmetry.

For example, suppose we're doing 3-dimensional geometry. There's a relation "the point x and the line y lie on a plane", but it's pretty dull, since it's always true. More interesting is the witnessed relation "the point x and the line y lie on the plane z". The reason is that sometimes there will be just one plane containing a point and a line, but when the point lies on the line, there will be lots.

To think of this "witnessed relation" as a span

                     S
                    / \
                   /   \
                 F/     \G
                 /       \
                v         v 
               X           Y

Can we take S to be the set of planes? No! Then there would be no way to define the functions F and G, because the same plane contains lots of different points and lines. So, we should take S to be the set of triples (x,y,z) where x is a point, y is a line, and z is a plane containing x and y. Then we can take

F(x,y,z) = x

and

G(x,y,z) = y

A "witness" to the fact that x and y lie on a plane is not just a plane containing them, but the entire triple.

(If you're really paying attention, you'll have noticed that we need to play the same trick in the example of witnesses to a marriage.)

Spans like this play a big role in "incidence geometry". There are lots of flavors of incidence geometry, with "projective geometry" being the most famous. But, a common feature is that we always have various kinds of "figures" - like points, lines, planes, and so on. And, we have various kinds of "incidence relations" involving these figures. But to really understand incidence geometry, we need to go beyond relations and use spans of sets.

Actually, we need to go beyond spans of sets and use spans of groupoids! The reason is that incidence geometries usually have interesting symmetries, and a groupoid is like a "set with symmetries". For example, consider lines in 3-dimensional space. These form a set, but there are also symmetries of 3-dimensional space mapping one line to another. To take these into account we need a richer structure: a groupoid!

Here's the formal definition: a groupoid consists of a set of "objects", and for any objects x and y, a set of "morphisms"

f: x → y

which we think of as symmetries taking x to y. We can compose a morphism f: x → y and a morphism g: y → z to get a morphism fg: x → z. We think of fg as the result of doing first f and then g. So, we demand the associative law

(fg)h = f(gh)

whenever either side is well-defined. We also demand that every object x has an identity morphism

1_x: x → x

We think of this as the symmetry that doesn't do anything to x. So, given any morphism f: x → y, we demand that

f 1_y = f = 1_x f

So far this is the definition of a "category". What makes it a "groupoid" is that every morphism f: x → y has an "inverse"

f ^-1: y → x

with the property that

f f ^-1 = 1_x

and

f ^-1 f = 1_y

In other words, we can "undo" any symmetry.

So, in our spans from incidence geometry:

                     S
                    / \
                   /   \
                 F/     \G
                 /       \
                v         v 
               X           Y

What's a functor? Given groupoids A and B, clearly a functor

F: A → B

should send any object x in A to an object F(x) in B. But also, it should send any morphism in A:

f: x → y

to a morphism in B:

F(f): F(x) → F(y)

And, it should preserve all the structure that a groupoid has, namely composition:

F(fg) = F(f) F(g)

and identities:

F(1_x) = 1_F(x)

It then automatically preserves inverses too:

F(f ^-1) = F(f) ^-1

Given this, what's the meaning of a span of groupoids? You could say it's a "invariant" witnessed relation - that is, a relation with witnesses that's preserved by the symmetries at hand. These are the very essence of incidence geometry. For example, if we have a point and a line lying on a plane, we can rotate the whole picture and get a new point and a new line lying on a new plane. Indeed, a "symmetry" in incidence geometry is precisely something that preserves all such "incidence relations".

For those of you not comfy with groupoids, let's see how this actually works. Suppose we have a span of groupoids:

                     S
                    / \
                   /   \
                 F/     \G
                 /       \
                v         v 
               X           Y

F(s) = x and G(s) = y

Also suppose we have a symmetry sending s to some other object of S:

f: s → s'

This gives morphisms

F(f): F(s) → F(s')

in X and

G(f): G(s) → G(s')

in Y. And if we define

F(s') = x' and G(s') = y'

we see that s' is a witness to the fact that x' and y' are related.

Let me summarize the Tale so far:

• Spans of groupoids describe "invariant witnessed relations".
• Invariant witnessed relations are the essence of incidence geometry.
• There's a way to turn spans of groupoids into matrices of numbers, so that multiplying matrices corresponds to some nice way of "composing" spans of groupoids (which I haven't really explained yet).

From all this, you should begin to vaguely see that starting from any sort of incidence geometry, we should be able to get a bunch of matrices. Facts about incidence geometry will give facts about linear algebra!

"Groupoidification" is an attempt to reverse-engineer this process. We will discover that lots of famous facts about linear algebra are secretly facts about incidence geometry!

To prepare for what's to come, the maniacally diligent reader might like to review "week178", "week180", "week181", "week186" and "week187", where I explained how any Dynkin diagram gives rise to a flavor of incidence geometry. For example, the simplest-looking Dynkin diagrams, the A_n series, like this for n = 3:

                           o------o------o
                        points  lines  planes      

(There will also be other ways to get spans of groupoids, that don't quite fit into what's customarily called "incidence geometry", but still fit very nicely into our Tale. For example, Dynkin diagrams become "quivers" when we give each edge a direction, and the "groupoid of representations of a quiver" gives rise to linear-algebraic structures related to a quantum group. In fact, I already mentioned this in item E of "week230". Eventually this will let us groupoidify the whole theory of quantum groups! But, I don't want to rush into that, since it makes more sense when put in the right context.)

Episode 3

The problem goes back a long ways. In 1871, while at Göttingen, Klein worked on non-Euclidean geometry, and showed that hyperbolic geometry was consistent if and only if Euclidean geometry was. In the process, he must have thought hard about the role of symmetry groups in geometry. When he was appointed professor at Erlangen in 1872, he wrote a lecture outlining his "Erlanger Programm" for reducing geometry to group theory.

But, he didn't actually give this lecture as his inaugural speech! He spoke about something else.

So, nobody ever heard him announce the Erlangen program. And, until recently, the lecture he wrote was a bit hard to find. Luckily, now you can get it online:

1) Felix Klein, Vergleichende Betrachtungen ueber neuere geometrische Forschungen, Verlag von Andreas Deichert, Erlangen, 1872. Also available at the University of Michigan Historical Mathematics Collection, http://www.hti.umich.edu/cgi/t/text/text-idx?c=umhistmath;idno=ABN7632

Even better, Johan Ernst Mebius has recently prepared an HTML version, with links to the above version:

2) Johan Ernst Mebius, Felix Klein's Erlanger Programm, http://www.xs4all.nl/~jemebius/ErlangerProgramm.htm

But what if you have the misfortune of only reading English, not German? Until now the only translation was quite hard to obtain:

3) Felix Klein, A comparative review of recent researches in geometry, trans. M. W. Haskell, Bull. New York Math. Soc. 2, (1892-1893), 215-249.

In case you're wondering, the "New York Mathematical Society" no longer exists! It was founded in 1888, but in 1894 it went national and became the American Mathematical Society.

Luckily, after Thomas Love pointed out the existence of this old translation, Chris Hillman was able to get ahold of it and scan it in! Then Robin Houston created a PDF file of the whole thing, and Lukas-Fabian Moser created a DjVu file. Then Nitin C. Rughoonauth took the marvelous step of putting it into LaTeX! So now, you can read Klein's paper in English here:

4) The Erlangen program, http://math.ucr.edu/home/baez/erlangen/

English-speakers can read more about the Erlangen program here:

5) Felix Klein, Elementary Mathematics from an Advanced Standpoint: Geometry, part 3: Systematic discussion of geometry and its foundations, Dover, New York, 1939.

Luckily Dover keeps its books in print!

For more on the Erlangen program, try these:

6) Garrett Birkhoff and M. K. Bennett, Felix Klein and his "Erlanger Programm", in History and Philosophy of Modern Mathematics, eds. W. Aspray and P. Kitcher, Minnesota Stud. Philos. Sci. XI, University of Minnesota Press, Minneapolis, 1988, pp. 145-176.

7) Hans A. Kastrup, The contributions of Emmy Noether, Felix Klein and Sophus Lie to the modern concept of symmetries in physical systems, in Symmetries in Physics (1600-1980), ed. M. G. Doncel, World Scientific, Singapore, 1987, pp. 113-163.

8) I. M. Yaglom, Felix Klein and Sophus Lie: Evolution of the Idea of Symmetry in the Nineteenth Century, trans. S. Sossinsky, Birkhauser, Boston, 1988.

For more about Klein, try "week213" and this little biography:

9) MacTutor History of Mathematics Archive, Felix Klein, http://www-history.mcs.st-andrews.ac.uk/Biographies/Klein.html

But what does the Erlangen program actually amount to, in the language of modern mathematics? This will take a while to explain, so the best thing is to dive right in.

In the last episode of the Tale of Groupoidification I tried to explain two slogans:

They're a bit vague; they're mainly designed to give you enough intuition to follow the next phase of the Tale, which is all about how:

But before the next phase, I need to say a bit about how groupoids and spans of groupoids fit into Klein's Erlangen program.

Groupoids are a modern way to think about symmetries. A more traditional approach would use a group acting as symmetries of some set. And the most traditional approach of all, going back to Galois and Klein, uses a group acting transitively on a set.

So, let me explain the traditional approach, and then relate it to the modern one.

I hope you know what it means for a group G to "act" on a set X. It means that for any element x of X and any guy g in G, we get a new element gx in X. We demand that

1x = x

and

g(hx) = (gh)x.

More precisely, this is a "left action" of G on X, since we write the group elements to the left of x. We can also define right actions, and someday we may need those too.

We say an action of a group G on a set X is "transitive" if given any two elements of X, there's some guy in G mapping the first element to the second. In this case, we have an isomorphism of sets

X = G/H

for some subgroup H of G.

For example, suppose we're studying a kind of geometry where the symmetry group is G. Then X could be the set of figures of some sort: points, or lines, or something fancier. If G acts transitively on X, then all figures of this sort "look alike": you can get from any one to any other using a symmetry. This is often the case in geometry... but not always.

Suppose G acts transitively on X. Pick any figure x of type X and let H be its "stabilizer": the subgroup consisting of all guys in G that map x to itself. Then we get a one-to-one and onto map

f: X → G/H

sending each figure gx in X to the equivalence class [g] in G/H.

If you haven't seen this fact before, you should definitely prove it - it's one of the big ways people use symmetry!

Here's one kind of thing people do with this fact. The 3d rotation group G = SO(3) acts on the sphere X = S², and the stabilizer of the north pole is the 2d rotation group H = SO(2), so the sphere is isomorphic to G/H = SO(3)/SO(2). The same sort of result holds in any dimension, and we can use it to derive facts about spheres from facts about rotation groups, and vice versa.

A grander use of this fact is to set up a correspondence between sets on which G acts transitively and subgroups of G. This is one of the principles lurking behind Galois theory.

Galois applied this principle to number theory - see "week201" for details. But, it really has nothing particular to do with number theory! In his Erlangen program, Klein applied it to geometry.

Klein's goal was to systematize a bunch of different kinds of non-Euclidean geometry. Each kind of geometry he was interested in had a different group of symmetries. For example:

• n-dimensional spherical geometry has the rotation group SO(n+1) as symmetries. (Or, if you want to include reflections, the bigger group O(n+1).)
• n-dimensional Euclidean geometry has the Euclidean group ISO(n) as symmetries. (This group is built from rotations in SO(n) together with translations in Rⁿ.)
• n-dimensional hyperbolic geometry has the group SO(n,1) as symmetries. (This group also shows up in special relativity under the name of the "Lorentz group": it acts on the "mass hyperboloid", and that's how hyperbolic geometry shows up in special relativity.)
• n-dimensional projective geometry has the group SL(n+1) as symmetries. (This group consists of (n+1)×(n+1) matrices with determinant 1. Scalar multiples of the identity act trivially on projective space, so it's actually better to use the "projective general linear group" PGL(n+1), consisting of invertible matrices mod scalars. But, this has the same Lie algebra as SL(n+1), so people are often a bit slack about which group they use.)

The details here don't matter much yet; the point is that there are lots of interesting kinds of geometry, with interesting symmetry groups!

Klein realized that in any kind of geometry like this, a "type of figure" corresponds to a set on which G acts transitively. Here a "figure" could be a point, a line, a plane, or something much fancier. Regardless of the details, the set of all figures of the same type can be written as G/H, and G acts transitively on this set.

The really cool part is that we can use Klein's idea to define a geometry for any group G. To do this, we just say that every subgroup H of G gives rise to a type of figure. So, we work out all the subgroups of G. Then, we work out all the incidence relations - relations like "a point lies on a line". To do this, we take two sets of figures, say

X = G/H

and

Y = G/K

and find all the invariant relations between them: that is, subsets of X × Y preserved by all the symmetries. I'll say more about how to do this next time - we can use something called "double cosets". In nice cases, like when G is a simple Lie group and H and K are so-called "parabolic" subgroups, these let us express all the invariant relations in terms of finitely many "atomic" ones! So, we can really carry out Klein's program of thoroughly understanding geometry starting from groups - at least in nice cases.

In short, group actions - especially transitive ones - are a traditional and very powerful way of using symmetry to tackle lots of problems.

So, to bridge the gap between the traditional and the new, I should explain how group actions give groupoids. I'll show you that:

It's not very hard to get a groupoid from a group action. Say we have a group G acting on a set X. Then the objects of our groupoid are just elements of X, and a morphism

g: x → y

is just a group element g with

gx = y.

Composing morphisms works the obvious way - it's basically just multiplication in the group G.

Some people call this groupoid an "action groupoid". I often call it the "weak quotient" X//G, since it's like the ordinary quotient X/G, but instead of declaring that x and y are equal when we have a group element g sending x to y, we instead declare they're isomorphic via a specified isomorphism g: x → y.

But for now, let's call X//G the "action groupoid".

So, group actions give action groupoids. But, these groupoids come with extra stuff!

First of all, the action groupoid X//G always comes equipped with a functor

                     X//G 
                      |
                      |p
                      |
                      v
                      G

Second of all, this functor p is always "faithful": given two morphisms from x to y, if p maps them to the same morphism, then they were equal.

And that's all! Any groupoid with a faithful functor to G is equivalent to the action groupoid X//G for some action of G on some set X. This takes a bit of proving... let's not do it now.

So: in my slogan

the "certain extra stuff" was precisely a faithful functor to G.

What if we have a transitive group action? Then something nice happens.

First of all, saying that G acts transitively on X is the same as saying there's a morphism between any two objects of X//G. In other words, all objects of X//G are isomorphic. Or in other words, there's just one isomorphism class of objects.

Just as a groupoid with one object is a group, a groupoid with one isomorphism class of objects is equivalent to a group. Here I'm using the usual notion of "equivalence" of categories, as explained back in "week76".

So, G acts transitively on X precisely when X//G is equivalent to a group!

And what group? Well, what could it possibly be? It's just the stabilizer of some element of X! So, in the case of a transitive group action, our functor

                     X//G 
                      |
                      |p
                      |
                      v
                      G

                      H
                      |
                      |i
                      |
                      v
                      G

So, we see how Klein's old idea of geometrical figures as subgroups of G is being generalized. We can start with any groupoid Y of "figures" and "symmetries between figures", and play with that. It becomes an action groupoid if we equip it with a faithful functor to some group G:

                      Y
                      |
                      |
                      |
                      v
                      G

                      H
                      |
                      |
                      |
                      v
                      G

So, when we blend our ideas on spans of groupoids with Klein's ideas, we'll want to use spans of groupoids "over G" - that is, commutative diamonds of groupoids and functors, like this:

                     S
                    / \
                   /   \
                  /     \
                 /       \
                v         v
               X           Y
                \         /
                 \       /
                  \     /
                   \   /
                    v v
                     G

I'll say one last thing before quitting. It's a bit more technical, but I feel an urge to see it in print.

People often talk about "the" stabilizer group of a transitive action of some group G on some set X. This is a bit dangerous, since every element of X has its own stabilizer, and they're not necessarily all equal!

However, they're all conjugate: if the stabilizer of x is H, then the stabilizer of gx is gHg^-1.

So, when I say above that

                     X//G 
                      |
                      |p
                      |
                      v
                      G

                      H
                      |
                      |i
                      |
                      v
                      G

                      H
                      |
                      |i'
                      |
                      v
                      G

Of course, I'll try to write later issues in a way that doesn't force you to have understood all these nuances!

Episode 4

              -----FRIEND---->


                    YOU

                 \             /
      ------------x-----------x-----------
                   \         /
                    \       /
                     \     /
                      \   /
                       \ /
                        x
                       / \
                      /   \
                     /     \

I gave a more formal introduction to projective geometry in "week106" and "week145", and "week178". If you read these, you'll know that points in the projective plane correspond to lines through the origin in a 3d space. And, you'll know a bit about the group of symmetries in projective geometry: it's the group G = PGL(3), consisting of 3×3 invertible matrices, modulo scalars.

(I actually said SL(3), but I was being sloppy - this is another group with the same Lie algebra.)

For some great examples of double cosets, let F be the space of "flags". A "flag" is a very general concept, but in projective plane geometry a flag is just a point x on a line y:

      -----------------x----------------
                                y

                 \             /
      ------------x-----------x'----------
                   \         /         y
                    \       /
                     \     /
                      \   /
                       \ /
                        x"
                       / \
                      /   \
                   y'/     \y"

For example, the flag (x',y') has the following relation to (x,y):

"The point of (x',y') lies on the line of (x,y), and no more."

There's a lot more to say about this, and we'll need to delve into it much deeper soon... but not yet. For now, I just want to mention that all this stuff generalizes from G = PGL(3) to any other simple Lie group! And, the picture above is an example of a general concept, called an "apartment". Apartments are a great way to visualize atomic invariant relations between flags.

This "apartment" business is part of a wonderful theory due to Jacques Tits, called the theory of "buildings". The space of all flags is a building; a building has lots of apartments in it. Buildings have a reputation for being scary, because in his final polished treatment, Tits started with a few rather unintuitive axioms and derived everything from these. But, they're actually lots of fun if you draw enough pictures!

Next, let me explain why people call atomic invariant relations "double cosets".

First of all, what's a relation between two sets X and Y? We can think of it as a subset S of X × Y: we say a pair (x,y) is in S if the relation holds.

Next, suppose some group G acts on both X and Y. What's an "invariant" relation? It's a subset S of X × Y such that whenever (x,y) is in S, so is (gx,gy). In other words, the relation is preserved by the symmetries.

Now let's take these simple ideas and make them sound more complicated, to prove we're mathematicians. Some of you may want to take a little nap right around now - I'm just trying to make contact with the usual way experts talk about this stuff.

First, let's use an equivalent but more technical way to think of an invariant relation: it's a subset of the quotient space G\(X × Y).

Note: often I'd call this quotient space (X × Y)/G. But now I'm writing it with the G on the left side, since we had a left action of G on X and Y, hence on X × Y - and in a minute we're gonna need all the sides we can get!

Second, recall from the previous episode that if G acts transitively on both X and Y, we have isomorphisms

X ≅ G/H

and

Y ≅ G/K

for certain subgroups H and K of G. Note: here we're really modding out by the right action of H or K on G.

Combining these facts, we see that when G acts transitively on both X and Y, an invariant relation is just a subset of

G\(X × Y) ≅ G\(G/H x G/K)

Finally, if you lock yourself in a cellar and think about this for a few minutes (or months), you'll realize that this weird-looking set is isomorphic to

H\G/K

This notation may freak you out at first - I know it scared me! The point is that we can take G, mod out by the right action of K to get G/K, and then mod out by the left action of H on G/K, obtaining

H\(G/K).

Or we can take G, mod out by the left action of H to get H\G, and then mod out by the right action of K on H\G, obtaining

(H\G)/K.

And, these two things are isomorphic! So, we relax and write

H\G/K

A point in here is called a "double coset": it's an equivalence class consisting of all guys in G of the form

hgk

for some fixed g, where h ranges over H and k ranges over K.

Since subsets of H\G/K are invariant relations, we can think of a point in H\G/K as an "atomic" invariant relation. Every invariant relation is the union - the logical "or" - of a bunch of these.

So, just as any hunk of ordinary matter can be broken down into atoms, every invariant statement you can make about an entity of type X and an entity of type Y can broken down into "atomic" invariant relations - also known as double cosets!

So, double cosets are cool. But, it's good to fit them into the "spans of groupoids" perspective. When we do this, we'll see:

This relies on the simpler slogan I mentioned last time:

Let's see how it goes. Suppose we have two sets on which G acts transitively, say X and Y. Pick a figure x of type X, and a figure y of type Y. Let H be the stabilizer of x, and let K be the stabilizer of y. Then we get isomorphisms

X ≅ G/H

and

Y ≅ G/K

The subgroup H ∩ K stabilizes both x and y, and

Z = G/(H ∩ K)

is another set on which G acts transitively. How can we think of this set? It's the set of all pairs of figures, one of type X and one of type Y, which are obtained by taking the pair (x,y) and applying an element of G. So, it's a subset of X × Y that's invariant under the action of G. In other words, it's an invariant relation between X and Y!

Furthermore, it's the smallest invariant subset of X × Y that contains the pair (x,y). So, it's an atomic invariant relation - or in other words, a double coset!

Now, let's see how to get a span of groupoids out of this. We have a commutative diamond of group inclusions:

                      H∩K
                      / \
                     /   \
                    /     \
                   v       v
                  H         K
                   \       /
                    \     /
                     \   /
                      v v
                       G

                     G/(H∩K)
                      / \
                     /   \
                    /     \
                   v       v
                 G/H      G/K
                   \       /
                    \     /
                     \   /
                      v v
                      G/G

                       Z
                      / \
                     /   \
                    /     \
                   v       v
                  X         Y
                   \       /
                    \     /
                     \   /
                      v v
                       *

                      Z//G
                      / \
                     /   \
                    /     \
                   v       v
                 X//G     Y//G
                   \       /
                    \     /
                     \   /
                      v v
                     *//G

                      Z//G
                      / \
                     /   \
                    /     \
                   v       v
                 X//G     Y//G
                   \       /
                    \     /
                     \   /
                      v v
                       G

                      Z//G
                      / \
                     /   \
                    /     \
                   v       v
                 X//G     Y//G

But, this span of groupoids is a span "over G", meaning it's part of a commutative diamond with G at the bottom:

                      Z//G
                      / \
                     /   \
                    /     \
                   v       v
                 X//G     Y//G
                   \       /
                    \     /
                     \   /
                      v v
                       G

                      H∩K
                      / \
                     /   \
                    /     \
                   v       v
                  H         K
                   \       /
                    \     /
                     \   /
                      v v
                       G

To tersely summarize what we've learned, let's use the fact that a groupoid is equivalent to a group precisely when it's "connected": that is, all its objects are isomorphic. Furthermore, a functor between connected groupoids is equivalent to an inclusion of groups precisely when it's "faithful": one-to-one on each homset. So, when I said that:

what I really meant was:

                       C
                      / \
                     /   \
                    /     \
                   v       v
                  A         B
                   \       /
                    \     /
                     \   /
                      v v
                       G

This sounds complicated, but it's mainly because we're trying to toss in extra conditions to make our concepts match the old-fashioned "double coset" notion. Here's a simpler, more general fact:

where a "G-set" is a set on which G acts. This is the natural partner of the slogan I explained in the last episode, though not in this language:

Things get even simpler if we drop the "faithfulness" assumption, and simply work with groupoids over G, and spans of these. This takes us out of the traditional realm of group actions on sets, and into the 21st century! And that's where we want to go.

Indeed, for the last couple episodes I've just been trying to lay out the historical context for the Tale of Groupoidification, so experts can see how the stuff to come relates to stuff that's already known. In some ways things will get simpler when I stop doing this and march ahead. But, I'll often be tempted to talk about group actions on sets, and double cosets, and other traditional gadgets... so I feel obliged to set the stage.

Episode 5

There is a lot more we could say about this. But, our most urgent goal is to see how spans of groupoids act like twice categorified matrices - matrices whose entries are not just numbers, and not just sets, but groupoids! This will expose the secret combinatorial underpinnings of a lot of fancy linear algebra. Once we've categorified linear algebra this way, we'll be in a great position to tackle fashionable topics like categorified quantum groups, invariants of higher-dimensional knots, and the like.

But, we should restrain ourselves from charging ahead too fast! Everything will hang together better if we lay the groundwork properly. For this, it pays to re-examine the history of mathematics a bit. If we're trying to understand linear algebra using groupoids, it pays to ask: how did people connect linear algebra and group theory in the first place?

This book is very helpful:

9) Charles W. Curtis, Pioneers of Representation Theory: Frobenius, Burnside, Schur and Brauer, History of Mathematics vol. 15, AMS, Providence, Rhode Island, 1999.

Back in 1897, a mathematician named William Burnside wrote the first book in English on finite groups. It was called Theory of Groups of Finite Order.

In the preface, Burnside explained why he studied finite groups by letting them act as permutations of sets, but not as linear transformations of vector spaces:

Cayley's dictum that "a group is defined by means of the laws of combination of its symbols" would imply that, in dealing with the theory of groups, no more concrete mode of representation should be used than is absolutely necessary. It may then be asked why, in a book that professes to leave all applications to one side, a considerable space is devoted to substitution groups [permutation groups], but other particular modes of representation, such as groups of linear transformations, are not even referred to. My answer to this question is that while, in the present state of our knowledge, many results in the pure theory are arrived at most readily by dealing with properties of substitution groups, it would be difficult to find a result that could most directly be obtained by the consideration of groups of linear transformations.

In short, he didn't see the point of representing groups on vector spaces - at least as a tool in the "pure" theory of finite groups, as opposed to their applications.

However, within months after this book was published, he discovered the work of Georg Frobenius, who used linear algebra very effectively to study groups!

So, Burnside started using linear algebra in his own work on finite groups, and by the time he wrote the second edition of his book in 1911, he'd changed his tune completely:

Very considerable advances in the theory of groups of finite order have been made since the appearance of the first edition of this book. In particular the theory of groups of linear substitutions has been the subject of numerous and important investigations by several writers; and the reason given in the original preface for omitting any account of it no longer holds good. In fact it is now more true to say that for further advances in the abstract theory one must look largely to the representation of a group as a group of linear transformations.

I don't really know the full answer to this question. But, it quickly leads us into the fascinating theory of "Hecke operators", which will play a big role in the Tale of Groupoidification. So, let's pursue it a bit.

Suppose we have two guys, William and Georg, who are studying a finite group G.

William says, "I'm studying how G acts on sets."

Georg replies, "I'm studying how it acts on complex vector spaces, as linear transformations. Mere sets are feeble entities. I can do anything you can do - but I have the tools of linear algebra to help me!"

William says, "But, you're paying a moral price. You're getting the complex numbers - a complicated infinite thing - involved in what should be a completely finitary and combinatorial subject: the study of a finite group. Is this really necessary?"

Georg replies, "I don't know, but it's sure nice. For example, suppose I have G acting on vector space V. Then I can always break down V into a direct sum of subspaces preserved by G, which can't themselves be broken down any further. In technical terms: every representation of G is a direct sum of irreducible representations. And, this decomposition is unique! It's very nice: it's a lot like how every natural integer has a unique prime factorization."

William says, "Yes, it's always fun when we can break things down into 'atoms' that can't be further decomposed. It's very satisfying to our reductionist instincts. But, I can do even better than you!"

Georg raises an eyebrow. "Oh?"

"Yeah," William says. "Suppose I have our group G acting on a set S. Then I can always break down S into a disjoint union of subsets preserved by G, which can't themselves be broken down any further. In technical terms: every action of G is a disjoint union of transitive actions. And, this decomposition is unique!"

Embarrassed, Georg replies, "Oh, right - we heard that back in Episode 3". I wasn't paying enough attention. But how is what you're doing better than what I'm doing? It sounds just the same."

William hesitates. "Well, first of all, a rather minor point, which I can't resist mentioning ... when you said your decomposition of representations into irreducibles was unique, you were exaggerating a little. It's just unique up to isomorphism, and not a canonical isomorphism either.

For example, if you have an irreducible representation of G on V, there are lots of different ways to slice the direct sum V + V into two copies of the representation V. It's a sort of floppy business. On the other hand, when I have a transitive action of G on S, there's exactly one way to chop the disjoint union S + S into two copies of the G-set S. I just look at the two orbits."

Georg says, "Hmm. This is actually a rather delicate point. There's not really a canonical isomorphism in your case either, since S may be isomorphic to itself in lots of ways, even as a G-set. There's something in what you say, but it's a bit hard to make precise, and it's certainly not enough to worry me."

"Okay, but here's my more serious point. Given that I can break apart any set on which G acts into 'atoms', my job is to classify those atoms: the transitive G-sets. And there's a very nice classification! Any subgroup H of G gives a transitive G-set, namely G/H, and all transitive G-sets look like this. More precisely: isomorphism classes of transitive G-sets correspond to conjugacy classes of subgroups of G.

Even better, this has a nice meaning in terms of Klein geometry. Any type of figure in Klein geometry gives a transitive G-set, with H being the stabilizer of a chosen figure of that type.

You, on the other hand, need to classify irreducible representations of G. And this is not so conceptual. What do these irreducible representations mean in terms of the group G?"

Georg replies, "Well, there's one irreducible representation for each conjugacy class in G..."

At this, William pounces. "You mean the number of isomorphism classes of irreducible representations of G equals the number of conjugacy classes in G! But as you know full well, there's no god-given correspondence. You can't just take a conjugacy class in G and cook up an irreducible representation, or irrep. So, you've just made my point. You've shown how mysterious these irreps actually are!"

Georg replies, "Actually in some cases there is a nice way to read off irreps from conjugacy classes. For example, you can do it for the symmetric groups S_n. But, I admit you can't in general... or at least, I don't know how."

William laughs, "So, I win!"

"Not at all!" replies Georg. "First, there are lots of theorems about groups that I can prove using representations, which you can't prove using actions on sets. For example, nobody knows how to prove that every group with an odd number of elements is solvable without using the tools of linear algebra."

William nods. "I admit that linear algebra is very practical. But just give us time! I proved back in 1904 that every group of size p^aq^b is solvable if p and q are prime. To do it, I broke down and used linear algebra. But then, in 1972, Helmut Bender found a proof that avoids linear algebra."

Georg said, "Okay, struggle on then. So far, without using linear algebra, nobody can even prove my famous theorem on 'Frobenius groups'. The details don't matter here: the point is, this is a result on group actions, which seems to need linear algebra for its proof.

But if practicality won't sway you, maybe this conceptual argument will. My atoms are more fine-grained than yours!"

"What do you mean?" asks William.

"You can decompose any action of G into 'atoms', namely transitive G-sets. Similarly, I can decompose any representation of G into one of my 'atoms', namely irreps. But, there's an obvious way to turn G-sets into representations of G, and if we do this to one of your atoms, we don't get one of my atoms! We can usually break it down further! So, my atoms are smaller than yours."

"How does this work, exactly?"

"It's easy," says Georg, getting a bit cocky. "Say you have a group G acting on a set S. Then I can form the vector space C[S] whose elements are formal linear combinations of elements of S. In other words, it's the vector space having S as basis. If we're feeling sloppy we can think of guys in C[S] as functions on S that vanish except at finitely many points. It's better to think of them as measures on S. But anyway: since G acts on S, it acts linearly on C[S]!

So, any G-set gives a representation of G. But, even when G acts transitively on S, its representation on C[S] is hardly ever irreducible."

William glowers. "Oh yeah?"

"Yeah. Suppose for example that S is finite. Then the constant functions on S form a 1-dimensional subspace of C[S] that's invariant under the action of G. So, at the very least, we can break C[S] into two pieces."

"Well," replies William defensively, "That's pretty obvious. But it's also not such a big deal. So you can break up any my transitive G-sets into two of your irreps, one being the 'trivial' irrep. So what???"

"It wouldn't be a big deal if that's all that ever happened," says Georg. "In fact, we can break C[S] into precisely two irreps whenever the action of G on S is 'doubly transitive' - meaning we can send any pair of distinct elements of S to any other using some element of G. But, there lots of transitive actions aren't doubly transitive! And usually, one your atoms breaks down into a bunch of my atoms. In fact I'd like to show you how this works, in detail, for the symmetric groups."

"Maybe next time," says William. "But, I see your point. Your atoms are more atomic than my atoms."

Georg seems to have won the argument. But, William wouldn't have conceded the point quite so fast, if he'd thought about invariant relations!

The point is this. Suppose we have two G-sets, say X and Y. Any G-set map from X to Y gives an intertwining operator from C[X] to C[Y]. But, even after taking linear combinations, there are typically plenty of intertwining operators that don't arise this way. It's these extra intertwining operators that let us chop representations into smaller atoms.

But where do these extra intertwining operators come from? They come from invariant relations between X and Y!

And, what are these extra intertwining operators called? In some famous special cases, like in study of modular forms, they're called "Hecke operators". In some other famous special cases, like in the study of symmetric groups, they form algebras called "Hecke algebras".

A lot of people don't even know that Hecke operators and Hecke algebras are two faces of the same idea: getting intertwining operators from invariant relations. But, we'll see this is true, once we look at some examples.

I think I'll save those for future episodes. But if you've followed the Tale so far, you can probably stand a few extra hints of where we're going. Recall from Episode 4 that invariant relations between G-sets are just spans of groupoids equipped with some extra stuff. So, invariant relations between G-sets are just a warmup for the more general, and simpler, theory of spans of groupoids. I said back in Episode 2 that spans of groupoids give linear operators. What I'm trying to say now is that these linear operators are a massive generalization - but also a simplification - of what people call "Hecke operators".

Finally, for students trying to learn a little basic category theory, I'd like to cast the argument between William and Georg into the language of categories, just to help you practice your vocabulary.

A G-set is the same as a functor

A: G → Set

where we think of G as a 1-object category. There's a category of G-sets, namely

hom(G,Set)

This has functors A: G → Set as objects, and natural transformations between these as morphisms. Usually the objects are called "G-sets", and the morphisms are called "maps of G-sets".

We can also play this whole game with the category of vector spaces replacing the category of sets. A representation of G is the same as a functor

A: G → Vect

As before, there's a category of such things, namely

hom(G,Vect)

This has functors A: G → Vect as objects, and natural transformations between these as morphisms. Now the objects are called "representations of G" and the morphisms are called "intertwining operators".

We could let any groupoid take the place of the group G. We could also let any other category take the place of Set or Vect.

Part of what William and Georg were debating was: how similar are hom(G,Set) and hom(G,Vect)? How are they related?

First of all, there's a functor

F: Set → Vect

sending each set S to the vector space C[S] with that set as basis. So, given an action of G on a set:

A: G → Set

we can compose it with F and get a representation of G:

FA: G → Vect

This kind of representation is called a "permutation representation". And, this trick gives a functor from G-sets to representations of G:

hom(G,Set) → hom(G,Vect) 
        A |-> FA

hom(G,Set) → hom(G,Vect)

is not "essentially surjective".

Moreover, not every intertwining operator between permutation representations comes from a map between their underlying G-sets! In other words, the functor

hom(G,Set) → hom(G,Vect)

is not "full".

But, given two different maps from one G-set to another, they give different intertwining operators. So, at least our functor is "faithful".

Maps of G-sets are a special case of invariant relations. So, to get a category that more closely resembles hom(G,Vect), while remaining purely combinatorial, we can replace hom(G,Set) by the category with G-sets as objects and invariant binary relations as morphisms. This is the basic idea of "Hecke operators".

Or, even better, we can try a weak 2-category, with

• groupoids over G as objects

• spans of groupoids over G as morphisms

• maps between spans of groupoids over G as 2-morphisms

This is where groupoidification comes into its own.

Episode 6

                     S
                    / \
                   /   \
                 P/     \Q
                 /       \
                v         v 
               X           Y

                     S
                    / \
                   /   \
                 P/     \Q
                 /       \
                v         v 
               X           Y

It's a great example of a mathematical cover-up - one we're gonna bust wide open.

Episode 7

                       S
                      / \
                     /   \
                    /     \
                   v       v
                  X         Y

                       S         T
                      / \       / \
                    f/   \g   h/   \i
                    /     \   /     \
                   v       v V       v
                  X         Y         Z

                            TS
                           / \
                         j/   \k
                         /     \
                        v       v
                       S         T
                      / \       / \
                    f/   \g   h/   \i
                    /     \   /     \
                   v       v v       v
                  X         Y         Z

                            TS
                           /  \
                          /    \
                         /      \
                     fj /        \ ik
                       /          \
                      /            \
                     /              \
                    /                \
                   v                  v
                  X                    Z

                       S
                      / \
                     /   \
                    /     \
                   v       v
                  X         Y

                      1
                      |
                      |p
                      |
                      v
                      X

                      V
                      |
                      |p
                      |
                      v
                      X

            ------------------
     V     |    o             |
           |    o  o          |
     |     |    o  o  o     o |   
     |p    | o  o  o  o     o |
     |      ------------------
     v
            ------------------
     X     | o  o  o  o  o  o |
            ------------------

     [V] = (1, 4, 3, 2, 0, 2)

                      V
                      |
                      |p
                      |
                      v
                      X

(Exercise: check that the cardinality of the groupoid of finite sets is e = 2.718281828... If you get stuck, read "week147".)

Also: define the morphisms in the essential preimage. Figure out and prove the universal property of the essential preimage. Hint: the essential preimage is a special case of a weak pullback!)

Okay. Now in principle you know how any groupoid over X, say

                      V
                      |
                      |
                      |
                      v
                      X

So, let's finally figure out how a span of groupoids

                       S
                      / \
                     /   \
                    /     \
                   v       v
                  X         Y

[S]: [X] → [Y]

It's enough to know what this operator does to vectors coming from groupoids over X:

                       V
                       |
                       |
                       |
                       v
                       X

                       V
                      / \
                     /   \
                    /     \
                   v       v
                  1         X

So here's what we do. To apply the operator [S] coming from the span

                       S
                      / \
                     /   \
                    /     \
                   v       v
                  X         Y

                       V
                      / \
                     /   \
                    /     \
                   v       v
                  1         X

                       SV
                      /  \
                     /    \
                    /      \
                   v        v
                  1          Y

[S] [V] = [SV]

Slick, eh? Of course you need to check that [S] is well-defined.

Given that, it's trivial to prove that [-] gets along with composition of spans:

[TS] = [T] [S]

At least, it's trivial once you know that composition of spans is associative up to equivalence, and equivalent spans give the same operator! But your friendly neighborhood category theorist can check such facts in a jiffy, so let's just take them for granted. Then the proof goes like this. We have:

[TS] [V] = [(TS)V]       by definition 
         = [T(SV)]       by those facts I just mentioned
         = [T] [SV]      by definition 
         = [T] [S] [V]   by definition 

[TS] = [T] [S]

Voilà!

By the way, if "week47" doesn't satisfy your hunger for information on groupoid cardinality, try this:

19) John Baez and James Dolan, From finite sets to Feynman diagrams, in Mathematics Unlimited - 2001 and Beyond, vol. 1, eds. Bjorn Engquist and Wilfried Schmid, Springer, Berlin, 2001, pp. 29-50. Also available as math.QA/0004133.

For more on turning spans of groupoids into linear operators, and composing spans via weak pullback, try these:

20) Jeffrey Morton, Categorified algebra and quantum mechanics, TAC 16 (2006), 785-854. Available at http://www.emis.de/journals/TAC/volumes/16/29/16-29abs.html; also available as math.QA/0601458.

21) Simon Byrne, On Groupoids and Stuff, honors thesis, Macquarie University, 2005, available at http://www.maths.mq.edu.au/~street/ByrneHons.pdf and http://math.ucr.edu/home/baez/qg-spring2004/ByrneHons.pdf

For a more leisurely exposition, with a big emphasis on applications to combinatorics and the quantum mechanics of the harmonic oscillator, try:

22) John Baez and Derek Wise, Quantization and Categorification, lecture notes available at:
http://math.ucr.edu/home/baez/qg-fall2003/
http://math.ucr.edu/home/baez/qg-winter2004/
http://math.ucr.edu/home/baez/qg-spring2004/

Finally, a technical note. Why did I say the degroupoidification process was "something like" a functor? It's because spans of groupoids don't want to be a category!

Already spans of sets don't naturally form a category. They form a weak 2-category! Since pullbacks are only defined up to canonical isomorphism, composition of spans of sets is only associative up to isomomorphism... but luckily, this "associator" isomorphism satisfies the "pentagon identity" and all that jazz, so we get a weak 2-category, or bicategory.

Similarly, spans of groupoids form a weak 3-category. Weak pullbacks are only defined up to canonical equivalence, so composition of spans of groupoids are associative up to equivalence... but luckily this "associator" equivalence satisfies the pentagon identity up to an isomorphism, and this "pentagonator" isomomorphism satisfies a coherence law of its own, governed by the 3d Stasheff polytope.

So, we're fairly high in the ladder of n-categories. But, if we want a mere category, we can take groupoids and equivalence classes of spans. Then, degroupoidification gives a functor

[-]: [finite groupoids, spans] → [vector spaces, linear maps]

That's the fact whose proof I tried to sketch here.

While I'm talking about annoying technicalities, note we need some sort of finiteness assumption on our spans of groupoids to be sure all the necessary sums converge. If we go all-out and restrict to spans where all groupoids involved are finite, we'll be very safe. The cardinality of a finite groupoid is a nonnegative rational number, so we can take our vector spaces to be defined over the rational numbers.

But, it's also fun to consider "tame" groupoids, as defined that paper I wrote with Jim Dolan. These have cardinalities that can be irrational numbers, like e. So, in this case we should use vector spaces over the real numbers - or complex numbers, but that's overkill.

Finding a class of groupoids or other entities whose cardinalities are complex would be very nice, to push the whole groupoidification program further into the complex world. In the above paper by Jeff Morton, he uses sets over U(1), but that's probably not the last word.

Further Episodes

• Geometric representation theory seminar, http://math.ucr.edu/home/baez/qg-fall2007/
• Geometric representation theory seminar, http://math.ucr.edu/home/baez/qg-winter2008/

home