Robert's Mistakes

Chomology for kids, part 2: computing homology groups

Dec 29, 2019

Before we get to the fun, let me thank everybody who gave feedback, of which there has been a lot. And important criticism from people who know much better than me. My short list of homotopy groups of the sphere was completely borked ([twitter], [twitter]). Thanks Yuhang Chen, and Rogier Brussee!

and the homotopy groups of the 2-torus commute, so they are the same as as the homology groups ([twitter]). Thanks Ward Beullens!

and my claim that homology and torsion classify manifolds lead much deeper ([twitter]) than I had expected. Also: I was quite wrong. I seem to have conflated Whitehead's theorem with Hurewicz' theorem, and imagined something too nice to be true. Special thanks to John C. Baez, Daniel Litt, and Rogier Brussee for their help!

I will look into these things and see if I can put them in shape for the next installment. Some links:

Join the discussion on twitter, maybe here: [twitter]. Questions welcome!

Computing the homology of a graph

The following example is from a 2-part video lecture by Norman Wildberger, "An introduction to homology". He does all computations slowly and in full detail. My notes follow his account rather closely, but all errors are mine. ([youtube], [youtube])

Cycles and boundaries

We will be obsessing over cycles and boundaries, because they produce closed surfaces. Let's first introduce a hierarchy of labels for vertices S0S_0, edges S1S_1, surfaces S2S_2, and so on. Maybe like this:

S0={x,y,z}S1={a,b,c,d}S2={A,B} S_0 = \{x,y,z\} \\ S_1 = \{a,b,c,d\} \\ S_2 = \{A,B\}

Any formal linear combination of symbols from one of these sets is called a chain. Here's an example chain made of edges:

a+2b7dC1 a+2b-7d \in C_1

'Formal' means that we won't actually fill in numbers for the symbols, as these summands aren't variable names standing for numbers, but symbols to label geometric objects! But they will behave very much like sums of variables, there's a zero element, and we have commutativity:

bb=0a+b=b+a b-b = 0 \\ a+b = b+a

Next, we package all the information on how all those simplices fit together as a family of functions, called boundary operators n:CnCn1\partial_n: C_n \rightarrow C_{n-1}. For any collection of edges it should be able to produce a formal linear combination of vertices, for any face chain an edge chain, and for any n-simplex chain an (n-1)-simplex chain.

There's some wiggle room left. As we will see later, we want some things to sum up to zero, and for that we need minus signs! Remember the meaning of all this, we want to grab the simplex by its boundary, so a triangle AA should be mapped to the sum of its edges a+b+ca+b+c. Tracing out the edges of a triangle puts them in order, tracing them backwards should give almost the same expression, but with minus signs.

To do that, we need to decide which sign each element gets, and then we're good to go! You can think of these signs as orientations, like putting arrowheads on the edges, picking front and back for every face, and so on. We will be summing over everything in the end, so it doesn't matter which way we put the orientations, and we also don't need to match up, say, faces' and edges' orientations, which may impossible anyhow.

Puzzle: Find a triangulation for a physical surface where all the edge's orientations match with all the face's orientations. Find one where that's impossible.

An example:

1(a)=yx2(A)=a+b+d2(B)=cd... \begin{aligned} \partial_1(a) & = y-x \\ \partial_2(A) & = a+b+d \\ \partial_2(B) & = c-d \end{aligned} \\ ...

Get the pattern? Edges are always like 'head minus tail', and I've labeled the blue and red cycles A and B. Now, if we substitute the edges into, say, the sum 2(A)\partial_2(A) it all adds up to zero! That's a general pattern: the boundary of a boundary is zero. That's because it is a cycle! And this is what will allow us to search for cycles using linear algebra: by solving systems of linear equations!

Computing HiH_i

Definition: A chain tt in CiC_i is a cycle when its boundary (t)\partial(t) is zero.

In general, an edge chain is a linear combination or weighted sum of edge names. Using greek letters for the weights which are actually numbers it looks like this :

(αa+βb+γc+δd) \partial(\alpha a + \beta b + \gamma c + \delta d) \\

One cool thing about i\partial_i is that it is a linear operator! It means, we can rewrite the above to:

α(a)+β(b)+γ(c)+δ(c) \alpha \partial(a) + \beta \partial(b) + \gamma \partial(c) + \delta \partial(c)

And now we can expand the (.)\partial(.)'s, rearrange for clarity, and set to zero:

α(yx)+β(zy)+γ(xz)+δ(xz)=x(α+γ+δ)+y(αβ)+z(βγδ)=0 \alpha (y-x) + \beta (z-y) + \gamma (x-z) + \delta (x-z) \\ = x(-\alpha+\gamma+\delta) + y(\alpha-\beta) + z(\beta-\gamma-\delta) = 0

We have no reason to assume that the latin labels for vertices could collude to become zero, so this can only be true if all summands become zero, which we can write like so:

α+γ+δ=0αβ=0βγδ=0 -\alpha+\gamma+\delta = 0 \\ \alpha-\beta = 0 \\ \beta-\gamma-\delta = 0

Now there's our system of linear equations, and it's underspecified! So the solution will be a subspace (called null space)!

α=r+sβ=r+sγ=rδ=s \alpha = r+s \\ \beta = r+s \\ \gamma = r \\ \delta = s

It is two dimensional, and has a basis:

(αβγδ)=r(1110)+s(1101) \begin{pmatrix} \alpha \\ \beta \\ \gamma \\ \delta \end{pmatrix} = r \begin{pmatrix} 1 \\ 1 \\ 1 \\ 0 \end{pmatrix} + s \begin{pmatrix} 1 \\ 1 \\ 0 \\ 1 \end{pmatrix}

And rr and ss are integer parameters. That's the reason why we say that the first homology group is the two-dimensional group Z+Z\Z+\Z.

Is Z+Z\Z + \Z the same as Z×Z\Z \times \Z?

You may wonder why the cycles as a group are often denoted as Z+ZZ+Z while the homology group is stated H1(M)=Z2H_1(M) = Z^2. This is confusing, why aren't these groups written as cartesian product, like Z×Z=Z2Z \times Z = Z^2?

Well, that ++ sign means direct sum, and in the context of abelian groups it's the same as the direct product. And the direct product turns out to be a cartesian product. (Thanks to Carles Sáez on [twitter])

Cycles over boundaries

So far I have only told you how to compute the singular homology of a graph. To fix that, let's look at what happens when we fill in a face AA bounded by one of our cycles cdc-d. Because the new face plugs a hole, we should expect that we get fewer cycles. After all, the boundary of our face could be homotopically shrunk to a point.

So we need to remove all boundaries of faces! At the moment, there's just one, it's named AA and its boundary is 2(A)=cd\partial_2(A) = c-d. Now all places on this boundary should be mapped on top of each other, glued together to a single point. So we simply need to redo our computation with an extra equation saying c=dc = d! Let's see this en jargon:

Forcing a set of things to be equal is called taking a quotient. Further, a kernel keri\textbf{ker}\, \partial_i is the name for those elements that i\partial_i maps to zero. So it's an instructive way to speak about cycles. And the image imi\textbf{im}\, \partial_i is a name for the the set of elements that appear as the boundary of some element in CnC_n.

ker1/im2 \textbf{ker}\, \partial_1 / \textbf{im}\, \partial_2

Take a surface, apply \partial once and get its boundary, apply it twice and get zero. The following neat way to say just this is called a short exact sequence:

0C22C11C00 0 \rightarrow C_2 \xrightarrow{\partial_2} C_1 \xrightarrow{\partial_1} C_0 \rightarrow 0

Anyways, for our example it all means that the first homology becomes:

Z+Z/Z=Z \Z + \Z / \Z = \Z

Computing HiH_i with spanning trees

As I also learned from Wildberger's lecture, there's a much simpler way to compute the homology of a graph using spanning trees. It goes like this:

Put any spanning tree on a graph. Then there will be as many cycles as there are edges not covered by the spanning tree. Because any spanning tree has v1v-1 edges, if a graph GG has ee edges, then there is a basis made of ev+1e-v+1 cycles.

If that's all that can happen, why not use numbers to signify the dimensions of the null spaces or homology groups, for a much simpler description? That's what Betti numbers are about, and it's where we'll start next time!