Tuesday, May 31, 2016

Homology modulo 2

Last week, I was chirping on Twitter about “homology modulo 2”: how closely it matches my geometric intuition of what homology should measure, despite my never having thought seriously about it before, and how its computational simplicity makes it seem like an ideal way to introduce homology to undergraduates, even those who haven’t studied linear algebra. For a very complete graduate-level introduction to homology (and cohomology) modulo 2, check out Jean-Claude Hausmann’s book. I will instead try to demonstrate how this topic can be introduced at nearly any level, with an appropriate amount of care. For the sake of brevity, I will assume familiarity with linear algebra in this post; however, the necessarily elements (image, kernel, rank, row reduction) can easily be learned in the context of homology, particularly when working modulo 2.

Note: This post got long enough in the writing that I didn’t make any pictures to go with it, so you should draw your own! The idea is to discover how algebra can be used to extract geometric/topological information in a way that is really striking when you see it happen.

The space

For simplicity of exposition, I will only consider spaces \(X\) that are created from finitely many convex polytopes (often simplices or hypercubes) by making some identifications (“gluings”) between their faces. The faces are not necessarily joined in pairs, however; more than two faces of the same dimension may be identified, or some faces might not be joined at all. A more careful definition is possible, but to provide one would get away from the fairly non-technical introduction I’m aiming for. Just assume no funny stuff happens, OK? The polytopes that make up \(X\) are called the cells of \(X\); the collection of cells includes all the faces of all the polytopes we started with (some of which, as noted above, have been identified with each other in pairs or larger groupings). Each cell, being a polytope, has a dimension, and if we wish to specify the dimension of a cell as \(k\), we call it a \(k\)-cell.

For example, \(X\) could just be a single convex polytope. Or it could be a convex polytope with the interior removed (keeping in mind that the boundary of a convex polytope is a union of convex polytopes of one dimension lower). The outside of a cube, for instance, is made up of six 2-cells (the faces), twelve 1-cells (the edges), and eight 0-cells (the vertices). A torus, when made from a rectangle by identifying opposite sides, is also such a space, with one 2-cell (the interior of the rectangle), two 1-cells (the result of identifying the edges in pairs), and one 0-cell (because all corners of the square are identified to the same point).

The data

The homology of \(X\) measures the difference between objects in \(X\) that have no boundary (these are called cycles) and objects that are the boundaries of other objects (called, quite sensibly, boundaries). A \(k\)-dimensional cycle that is not a boundary is supposed to “enclose” a \(k\)-dimensional “hole” in \(X\). The formal definitions are intended to quantify what is meant by “boundary;” the intuitive notion of “hole” floats along, generally defying proper definition (and often even intuition).

By “object” in the previous paragraph, we mean something made up from the cells of \(X\). We restrict ourselves to putting together cells of the same dimension, producing objects called chains. That is, a \(k\)-chain is just a collection of \(k\)-cells in \(X\). We can add together \(k\)-chains, but—and this is the beautifully simple part—we add modulo 2. If a particular cell appears twice, then this pair of appearances cancel each other out. The idea is that, since we’re trying to study “holes” in our space \(X\), if one cell appears twice, the pair of copies can be joined up along their common boundary and safely removed. Formally, a \(k\)-chain is a linear combination of \(k\)-cells, with coefficients in the field with two elements, if you find such a formal description helpful.

We now proceed to the key combinatorial data of our space \(X\) and see how it can be used to extract topological information. Because \(X\) is made up of finitely many cells, for each \(k = 1, \dots, n\), we can construct a boundary matrix \(\partial_k\). (Normally \(\partial_k\) would be defined as a linear map between certain vector spaces; we are fully exploiting the equivalence between linear maps and matrices.) The columns of \(\partial_k\) are labelled by the \(k\)-cells of \(X\), and the rows are labelled by the \((k-1)\)-cells. In each column, we put a 1 in each position where the corresponding \((k-1)\)-cell lies in the boundary of the given \(k\)-cell, and a 0 otherwise. Exception. Sometimes the faces of a single \(k\)-cell may be joined to each other, meaning the resulting \((k-1)\)-cell appears with multiplicity on the boundary of that \(k\)-cell. This multiplicity, modulo 2, is taken into account in the boundary matrix. See the boundary matrices of the torus, near the end, for examples of this phenomenon.

A concrete example: the tetrahedron

The boundary matrix, like most computational objects, is best understood through examples. Let’s start with the empty tetrahedron. Label the vertices \(v_1\), \(v_2\), \(v_3\), \(v_4\), and let \(f_i\) be the triangular face opposite \(v_i\). Let \(e_{ij}\) be the edge joining \(v_i\) to \(v_j\), with \(i < j\). Then we have two boundary matrices,

\( \partial_1 = \begin{bmatrix} 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 \end{bmatrix} \)      and      \(\partial_2 = \begin{bmatrix} 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 \end{bmatrix}\).
In \(\partial_1\), the columns are labelled by the edges and the rows are labelled by the vertices. In \(\partial_2\), the rows are labelled by the edges and the columns are labelled by the faces. In both matrices, the edges are listed in the order \(e_{12}\), \(e_{13}\), \(e_{14}\), \(e_{23}\), \(e_{24}\), \(e_{34}\). Notice that each column of \(\partial_1\) has two 1s, because each edge has two endpoints, and each column of \(\partial_2\) has three 1s, because each face is bounded by three edges.

Once we have these matrices, we can use them to find boundaries of more general chains. For instance, when joined together, the edges \(e_{12}\) and \(e_{23}\) form a path from \(v_1\) to \(v_3\), so we expect the boundary to be these two points. Indeed, adding together (modulo 2!) the corresponding entries from the first and fourth columns of \(\partial_1\), we see that the 1s in the second entry cancel (which corresponds to the edges being joined at \(v_2\)), and we are left with 1s in the first and third entries. We can write this relation as \(\partial_1(e_{12}+e_{23}) = v_1 + v_3\). Similarly, if we add together the first three columns of \(\partial_2\), which correspond to \(f_1\), \(f_2\), and \(f_3\), the result is a vector with 1s in the first, second, and fourth entries, which correspond to \(e_{12}\), \(e_{13}\), and \(e_{23}\), producing the equation \(\partial_2(f_1 + f_2 + f_3) = e_{12} + e_{13} + e_{23}\). This demonstrates that the union of three of the faces has the same boundary as the fourth face. The sum of all four columns of \(\partial_2\) has all 0s for its entries, showing that the four faces of the tetrahedron, taken together, have no boundary.

How to extract information from the boundary matrix

Having illustrated some computations with boundary matrices in the above example, let’s codify some definitions. A collection of \(k\)-cells is called a \(k\)-cycle (or closed) if the sum of the corresponding columns of \(\partial_k\) is the zero vector. (This is a formal way of saying “has no boundary.”) A collection of \(k\)-cells is called a \(k\)-boundary (or exact) if it can be obtained as a sum of columns of \(\partial_{k+1}\). In linear algebra terms, a \(k\)-cycle is an element of the kernel of \(\partial_k\), and a \(k\)-boundary is an element of the image of \(\partial_{k+1}\). Again, the benefit of working modulo 2 is that these conditions can be easily checked. The set of \(k\)-boundaries is denoted \(B_k\), and the set of \(k\)-cycles is denoted \(Z_k\) (the notation \(C_k\) generally being reserved for \(k\)-chains).

A fundamental property is that \(\partial_k \partial_{k+1} = 0\), which has the satisfying geometric interpretation that “every \(k\)-boundary is a \(k\)-cycle,” or \(B_k \subseteq Z_k\). This property can be checked directly in the above example of the tetrahedron. In general, it applies because, in a \(k\)-dimensional polytope, each \((k-2)\)-dimensional face appears in two \((k-1)\)-dimensional faces (provided \(k \ge 2\); if \(k=1\), then there are no \((k-2)\)-dimensional faces, so \(\partial_0 = 0\), and the property \(\partial_0 \partial_1 = 0\) holds trivially). From the perspective of homology, this means boundaries aren’t “interesting” cycles. They’re the boundaries of something, after all, so they certainly don’t enclose a “hole.”

What we really want to measure, then, is how many cycles are not boundaries. To determine this, we first need to find out how many cycles and how many boundaries there are. Except we can add cycles together to get new cycles (in linear algebra terms, the kernel of a matrix is a subspace of the domain), and we can add boundaries to get new boundaries (the image of a matrix is also a subspace), so what we really want is to know how many independent cycles there are: that is, we want the dimension or rank of the set of cycles and the set of boundaries. I’ll use rank here, even though we’re working with vector spaces, because that terminology transfers to the case of integral homology.

The rank of the \(k\)-boundaries is the rank of \(\partial_{k+1}\), because by definition this describes the maximal number of independent boundaries of \((k+1)\)-chains. On the other hand, the rank of the \(k\)-cycles is the nullity of \(\partial_k\), because this measures the maximal number of independent \(k\)-chains with no boundary. From linear algebra, we know that the rank of a matrix can be determined by row reducing to echelon form and counting the number of rows (equivalently, columns) that have leading ones.

Homology gets its name from the notion of homologous cycles (“homologous” meaning, etymologically, “having the same position or structure”). Two \(k\)-cycles are homologous if their difference is a \(k\)-boundary. Modulo 2, the difference of two objects is the same as their sum, so this just means that two cycles are homologous if, when we put them together, they form the boundary of an object of one higher dimension. Boundaries are “homologically trivial” because, by definition, they are homologous to the chain consisting of no cells, \(0\). The \(k\)th homology of \(X\) is the quotient (group, vector space, module, etc.) of the cycles and the boundaries: \[ H_k = Z_k/B_k. \] The associated numeric invariant is the \(k\)th Betti number \(\beta_k\) of \(X\), which is the rank of the \(k\)th homology. It can thus be computed as the difference between the rank of the \(k\)-cycles and that of the \(k\)-boundaries: \[ \beta_k = \mathrm{rank}\,Z_k - \mathrm{rank}\,B_k. \] This is the number that “counts” the “\(k\)-dimensional holes” in our space \(X\). Note that this is an ordinary natural number, not an integer modulo 2. However, when working modulo 2, the Betti numbers entirely determine the homology, up to isomorphism. (In ordinary, integral homology, this is not the case: homology may have “torsion” elements, while the Betti numbers only count the “free” part of homology. The integral homology determines the mod 2 homology, but the reverse is not true, so homology modulo 2 is undoubtably “weaker,” and there are certainly times one would want the full theory. However, I hope this post is illustrating the benefits of using homology modulo 2 as a shortcut for introducing the key concepts.)

Examples of homology

Let’s return to the example of the tetrahedron. Using \(\sim\) for row equivalence, we have

\( \partial_1 \sim \begin{bmatrix} 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix} \)      and      \(\partial_2 \sim \begin{bmatrix} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}\).
The rank of both matrices is \(3\). The nullity of the first matrix is \(6 - 3 = 3\), and the nullity of the second matrix is \(4 - 3 = 1\). Thus we have \[ \mathrm{rank}\,Z_1 = 3, \qquad \mathrm{rank}\,B_1 = 3, \qquad \mathrm{rank}\,Z_2 = 1, \qquad \mathrm{rank}\,B_2 = 0, \qquad \] the last quantity following from the fact that there are no 3-cells in the empty tetrahedron. We also know that \[ \mathrm{rank}\,Z_0 = 4, \qquad \mathrm{rank}\,B_0 = 3, \qquad \] with the first of this pair of equations coming from the fact that a point has no boundary. The Betti numbers of tetrahedron are \[ \beta_0 = 4 - 3 = 1, \qquad \beta_1 = 3 - 3 = 0, \qquad \beta_2 = 1 - 0 = 1. \] Here is a geometric interpretation of these numbers, in reverse order.
  • The equation \(\beta_2 = 1\) means that there is one independent 2-cycle which is not a boundary. The reduced form of \(\partial_2\) shows that this cycle is \(f_1 + f_2 + f_3 + f_4\), i.e., the sum of all the faces of the tetrahedron. Thus, when we take all the faces together, the result is a closed cycle, and no other combination of faces has an empty boundary. Roughly speaking, the entire tetrahedron encloses a “hole.”
  • The equation \(\beta_1 = 0\) can be read as “every 1-cycle is a 1-boundary.” A stronger form of this statement is that the tetrahedron is simply connected—every loop can be contracted to a point, or every closed loop on the tetrahedron is the boundary of something 2-dimensional. Roughly speaking, there are no holes on the surface of the tetrahedron.
  • The “holes” measured by the 0th homology are of a somewhat different type. Generally speaking, the Betti number \(\beta_0\) measures the number of connected components. Because any point has no boundary on its own (hence is a 0-cycle), two vertices are are boundary if and only if they can be joined by a path of edges. Thus the equation \(\beta_0 = 1\) simply means that the tetrahedron is connected.

Now let’s turn to the example of the torus, formed from a rectangle by identifying opposite sides. This space has one 2-cell \(f\) (the interior of the torus), two 1-cells \(e_1\) and \(e_2\) (the edges of the rectangle, after being identified in pairs), and one 0-cell \(v\) (all four vertices of the rectangle become a single point on the torus). Each edge \(e_i\) appears twice on the boundary of \(f\), and the vertex \(v\) appears at both ends of each edge, so the boundary matrices are \[ \partial_1 = \begin{bmatrix} 0 & 0 \end{bmatrix}, \qquad\qquad \partial_2 = \begin{bmatrix} 0 \\ 0 \end{bmatrix}. \] Thus every \(k\)-chain has an empty boundary for \(k = 0, 1, 2\), and the rank of the \(k\)-cycles equals the number of \(k\)-cells. The interpretations of \(\beta_0 = 1\) and \(\beta_2 = 1\) are the same as in the case of the tetrahedron. In this case, the equation \(\beta_1 = 2\) tells us there are two different, independent 1-cycles, which can be represented by a latitude circle and a longitude circle on the torus.

Footnote on topological spaces

A few words justifying the restriction to polytopal complexes: When I was in Hatcher’s algebraic topology class, he chose to introduce cellular homology first so that we could get to computations quickly; later he introduced singular homology mainly to prove that the homology groups only depend on the underlying topological space. It thus seems entirely reasonable to me, for purposes of introduction, to work directly with CW complexes. The appendix to Hatcher’s book is a standard reference for learning about CW complexes, but in practice a CW complex usually means a topological space that is assembled from convex polytopes, attached along their faces.

Another introductory source on homology for undergraduates

I recently came across Peter Giblin’s book Graphs, Surfaces and Homology, which provides a very thorough introduction to its eponymous topics with only the prerequisite of linear algebra. However, like most treatments of homology, it first deals with integral homology, then comes around to homology modulo 2 late in the book, in Chapter 8, specifically to deal with non-orientable (or at least unoriented) surfaces and simplicial complexes. Gibson describes the theory of homology modulo 2 as “satisfactory” but “weaker than the theory with integral coefficients,” which is absolutely true.

However, if one’s goal is either to learn about homology quickly or to study new spaces (rather than, say, to prove the classification of surfaces), then I think homology modulo 2 is perfectly sufficient, particularly since the contemporary field of persistent homology, applied to study data sets in large dimensions, often works with homology modulo 2. (See this survey, or the remark on page 7 of this overview, for instance.)

No comments: