one weird kernel trick

I recently stumbled upon a programming interview question and the first solution that sprang to mind used a sprinkling of algebraic topology. I thought this might be a fun little pedagogical way to introduce the idea of homology, so here goes!¹ I’ll assume familiarity with matrices, the basics of linear algebra, and a bit of python.

Say we’re given a 2-dimensional matrix where each cell consists of either a forward slash, a backward slash, or a space. We’ll write a program to compute the number of regions in the resulting space, treating the matrix edges as boundaries. Given, for example, the 3-by-6 matrix,

1\    /
2 \  /
3  \/

our program will output 3.

brainstorming

It’s always good to start out with a handful of examples to think about. Let’s draw them out as strings, which we will then convert to 2-dimensional numpy arrays.

 1# we'll need numpy for working with our matrices
 2import numpy as np
 3# and some tools for solving linear systems of equations
 4from scipy import linalg
 5
 6examples = [
 7    ' ',
 8    '/',
 9    (
10    '\    /\n'
11    ' \  / \n'
12    '  \/  '
13    ),
14    (
15    '\/\n'
16    '/\\'
17    ),
18     (
19    '\/  \/\n'
20    ' \/\/ \n'
21    '  \/  '
22    )
23]
24
25# hopefully I counted these correctly
26answers = [1, 2, 3, 4, 6]
27
28# convert our string drawings to 2d numpy arrays
29# recall that list converts a string to a list of characters
30def string_to_np(s):
31    return np.array(list(map(list, s.split('\n'))))

It might also help to draw in the edges of our matrix to help us visualize the regions a little better.

 1# add in the boundaries along the edges of the matrix
 2def viz_boundaries(matrix):
 3    vertical = np.full((matrix.shape[0], 1), '|')
 4    left_and_right = np.hstack((vertical, matrix, vertical))
 5    horizontal = np.full((1, matrix.shape[1] + 2), '-')
 6    boundarized = np.vstack((horizontal, left_and_right, horizontal))
 7    s = ''
 8    for i in range(matrix.shape[0] + 2):
 9        for j in range(matrix.shape[1] + 2):
10            s += boundarized[i][j]
11        s += '\n'
12    return s
13
14# visualize our examples
15for i, example in enumerate(examples):
16    print(f'Example {i}:')
17    print(viz_boundaries(string_to_np(example)))

 1Example 0:
 2---
 3| |
 4---
 5
 6Example 1:
 7---
 8|/|
 9---
10
11Example 2:
12--------
13|\    /|
14| \  / |
15|  \/  |
16--------
17
18Example 3:
19----
20|\/|
21|/\|
22----
23
24Example 4:
25--------
26|\/  \/|
27| \/\/ |
28|  \/  |
29--------

What makes a region a region? Well, let’s see. Clearly it has to be two-dimensional. That’s an obvious statement, and one that we probably don’t really think explicitly about. Less trivially, our regions all have 1-dimensional boundaries: each is enclosed by a trail of line segments that forms a loop. Aha, so we just need to figure out how to get all the loops in our space!

Well, hold up a minute, sure every region gives us a boundary loop, but not every loop corresponds to one of our regions. Take Example 1 from before: the loop around the edge of the matrix corresponds to the union of two triangular regions that we’d like to count. Even worse, we could take pathological loops that go around a region 17 times! That corresponds to the same region as the loop that just goes around once does… I guess?

formalizing our intuition

Let’s think a bit more carefully about that first issue we’re running into, still in the context of Example 1. It’ll help to number the corners — the vertices — of our loops.

1'''
20 1
3---
4|/|
5---
62 3
7'''

If we choose to start from the top-left corner, we can write the loop that goes around the edge of the matrix as the list of line segments [01,13,32,20]. The regions we’re really after, however, are bounded by [01,12,20] and [21,13,32]. Since the quadrilateral region \(Q\) is a union, a sum of sorts, of the two triangular regions \(T_1\) and \(T_2\), we should be able to somehow write the boundary \(\partial Q\) of the quadrilateral as a sum of the boundaries \(\partial T_1\) and \(\partial T_2\) of the triangles.

Here’s the secret sauce: let’s try to take the idea of sums more literally. Okay, so \(Q = T_1 + T_2\) and

\begin{equation*} \partial Q = e_{01} + e_{13} + e_{32} + e_{20}, \end{equation*}

where \(e_{ij}\) represents the edge running from the \(i\)th vertex to the \(j\)th vertex (it’s kinda awkward to just write something like \(01 + 13\)). If we cross our fingers and ask that this \(\partial\) operator, which seems to send 2-dimensional regions to 1-dimensional boundaries, distributes over sums, then

\begin{equation*} \partial Q = \partial (T_1 + T_2) = \partial T_1 + \partial T_2. \end{equation*}

We have an expression for the left (the four terms above) and on the right we have

\begin{equation*} e_{01} + e_{12} + e_{20} + e_{21} + e_{13} + e_{32}. \end{equation*}

Canceling out the common terms, we arrive at

\begin{equation*} e_{12} + e_{21} = 0. \end{equation*}

Okay, so this is just expressing that travelling along the edge \(e_{12}\) should be the same as travelling backwards along \(e_{21}\).

Since we’re now working implicitly with a directed graph, let’s go ahead and rewrite our paths from earlier, but this time respecting the ordering on the numbering of the vertices:

\begin{align*} \partial Q &= e_{01} + e_{13} - e_{23} + e_{20}, \\ \partial T_1 &= e_{01} + e_{12} - e_{20}, \\ \partial T_2 &= -e_{12} + e_{13} - e_{23}. \end{align*}

This gives us a way to express our intuition that \(Q\) is formed by putting \(T_1\) and \(T_2\) together. One interesting thing to note is that \(\partial (17 T_1) = 17 \partial T_1\), so the pathological boundary looping around 17 times that we mentioned above is, in these terms, the boundary of the sum of 17 copies of \(T_1\). That’s kinda gnarly, but this doesn’t help solve our initial problem. We can write down a bunch of loops in the notation of above, but how do we get rid of those coming from composite regions like \(Q\)? For that, we’re going to have be a little less wishy-washy handwavy about these symbols that we’re pushing around.

introducing vector spaces

How do we start working more formally with these regions and their boundaries? For that we’re going to need a bit of linear algebra. The operations we’ve been carrying out above are pretty simple: addition (\(e_{01} + e_{12}\)) and scalar multiplication (\(-1 \cdot e_{12}\)). These should remind you of vectors in a vector space, I hope! As a quick review: let’s think about the vector space \(\R^2\). This is a vector space (over the real numbers) generated by two basis vectors. That is to say, any two linearly independent vectors will span the whole space. I’m personally fond of \(e_1 = (1, 0)^T\) and \(e_2 = (0, 1)^T\), but you could just as well work with \(\{7e_1, e_1 + \pi e_2\}\) if you enjoy suffering. Hence why we say that \(\R^2\) is 2-dimensional.² Let’s suppose, now, that we could get our hands on a vector space of all loops in \(X\). Those pesky loops that correspond to composite regions are sums of the ‘irreducible’ loops that we’re after. All we really care about are the linearly independent loops. In other words, the problem is just asking us to compute the dimension of this vector space of loops! That’s the key insight.

Let’s make this precise. If we write out the space in Example 1 as \(X\) and the set of edges as \(X_1\), we can consider the real vector space \(\R^{|X_1|}\) of dimension \(|X_1|\) — that is, a vector space with as many directions as there are edges in \(X_1\). So, since there are 5 elements of \(X_1\), we’re working with \(\R^5\), and we may as well choose a basis

\begin{align*} e_{01} &= (1, 0, 0, 0, 0)^T \\ e_{02} &= (0, 1, 0, 0, 0)^T \\ e_{12} &= (0, 0, 1, 0, 0)^T \\ e_{13} &= (0, 0, 0, 1, 0)^T \\ e_{23} &= (0, 0, 0, 0, 1)^T \end{align*}

The way in which we’ve chosen these doesn’t really matter, but these basis vectors are easy on the eyes. An arbitrary vector in \(\R^5\) is going to be as sum of these basis edges, which we can think of as a possibly-disconnected path in \(X\). How do we figure out whether a vector is a loop or not? Because we need a nice connected path, so if \(v = e_{01} + \cdots\), there’d better be a \(e_{1j}\) (for some \(j\)) hiding somewhere in there too (or a \(e_{j0}\)). To be a loop is harder because we also need that the edges end up where they started.

Let’s think geometrically again. Remember our friend \(\partial\), who took 2-dimensional regions to 1-dimensional loops. If we shift our dimensions down by one, we can think about the boundary of a path. The boundary of a line segment is its two endpoints: \(\partial e_{01} = e_1 - e_0\). Two things to notice here. The first is that we’re implicitly introducing another vector space: a vector space \(\R^{|X_0|}\) with basis the vertices (here \(X_0\) is the set of vertices of \(X\)). The second is that funky minus sign. Intuitively, this sign captures the fact that \(e_{01}\) has a direction. We’re moving from the vertex \(e_0\) to the vertex \(e_1\). Actually we already saw this when we computed, for example, \(\partial T_1 = e_{01} + e_{12} - e_{20}\). Great, so this \(\partial\) operator can take regions to paths (loops, in fact), and paths to points. Okay, so back to loops. Let’s see what happens when we take the boundary of the loop around \(T_1\):

\begin{align*} \partial (\partial T_1) &= \partial(e_{01} + e_{12} - e_{20}) \\ &= e_1 - e_0 + e_2 - e_1 - (e_2 - e_0) \\ &= 0. \end{align*}

It’s zero! In fact, loops are precisely the paths that have no boundary. This is intuitive geometrically: there’s no fixed start or endpoint of a loop because it just sorta goes around in a circle.

We now have a linear algebraic criterion for determining whether a path in \(X\) is a loop: check whether it’s in the kernel of \(\partial\)! To be a bit more precise, we’ve constructed a linear transformation between two vector spaces:

\begin{align*} \partial : \R^{|X_1|} &\to \R^{|X_0|} \\ e_{ij} &\mapsto e_j - e_i \end{align*}

and the loops in \(X\) are precisely the vectors in \(\R^{|X_1|}\) that are sent to zero in \(\R^{|X_0|}\). This allows us to concretely compute the space of loops — we just need to compute the kernel of \(\partial\).

computing the kernel: an example

Let’s focus on \(X\) being our Example 1 as usual. In this case we have 5 edges and 4 vertices, so the boundary operator is a linear map \(\partial: \R^5 \to \R^4\) determined by its action \(\partial e_{ij} = e_j - e_i\) on the basis vectors. Remember how we wrote the \(e_{ij}\) as the standard basis vectors of \(\R^5\) earlier? Let’s do that for our space of vertices as well:

\begin{align*} e_0 &= (1, 0, 0, 0)^T \\ e_1 &= (0, 1, 0, 0)^T \\ e_2 &= (0, 0, 1, 0)^T \\ e_3 &= (0, 0, 0, 1)^T. \end{align*}

We can now write out what \(\partial\) looks like as a matrix! We know, for instance, that,

\begin{equation*} \partial e_{01} = \partial \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} = e_1 - e_0 = \begin{pmatrix} -1 \\ 1 \\ 0 \\ 0 \end{pmatrix} \end{equation*}

and so we can assemble the matrix:

\begin{equation*} \partial = \begin{pmatrix} -1 & -1 & 0 & 0 & 0 \\ 1 & 0 & -1 & -1 & 0 \\ 0 & 1 & 1 & 0 & -1 \\ 0 & 0 & 0 & 1 & 1 \end{pmatrix} \end{equation*}

To find the kernel of \(\partial\), we want to solve the equation \(\partial v = 0\). If we write \(v = (x_1, x_2, x_3, x_4, x_5)^T\), a bit of algebra (or row reduction, if you like) shows that the solutions are written

\begin{align*} \begin{pmatrix} x_3 - x_5 \\ x_5 - x_3 \\ x_3 \\ -x_5 \\ x_5 \end{pmatrix} \end{align*}

for \(x_3, x_5 \in\R\) free. We see immediately that the kernel is 2-dimensional, which is awesome, because that’s the answer we’re after! Visually we have two independent, irreducible loops \(\partial T_1\) and \(\partial T_2\). Congratulations! You’ve computed your first so-called ‘homology group’!³

Rewriting in terms of our ordered basis for \(\R^5\), we find that the kernel of \(\partial\) is spanned by

\begin{equation*} e_{01} - e_{02} + e_{12} \text{ and } e_{02} + e_{23} - e_{13} - e_{01}, \end{equation*}

coming from setting \(x_3 = 1, x_5 = 0\), and \(x_3 = 0, x_5 = 1\), respectively. If we trace the vertices around Example 1, we can see that the first is exactly \(\partial T_1\), and the second is \(-\partial Q\). Why these two instead of \(\partial T_1\) and \(\partial T_2\), the loops that we like to visualize? No fundamental reason really — it’s an artifact of the bases we chose and the way we solved the system of equations. We can always choose any \(k\) linearly independent vectors to span a \(k\)-dimensional space. The coordinate-invariant object is the 2-dimensional subspace \(\ker\partial \subset \R^5\), which doesn’t care how we choose to map it out. Indeed, we can always write \(\partial T_2\) in terms of \(\partial T_1\) and \(-\partial Q\):

\begin{equation*} \partial T_1 - \partial Q = e_{12} - e_{13} + e_{23}. \end{equation*}

Just to make sure we didn’t make any algebra mistakes, let’s ask scipy to compute the dimension of the kernel for us.

1# the matrix constructed for the boundary operator in Example 1
2example_d = np.array([[-1, -1, 0, 0, 0],
3                      [1, 0, -1, -1, 0],
4                      [0, 1, 1, 0, -1],
5                      [0, 0, 0, 1, 1]])
6# scipy can compute vectors spanning the kernel of a matrix
7ker = linalg.null_space(example_d)
8print(ker.round(4))
9print(f'The kernel is {ker.shape[1]}-dimensional')

1[[-0.5    -0.3536]
2 [ 0.5     0.3536]
3 [ 0.     -0.7071]
4 [-0.5     0.3536]
5 [ 0.5    -0.3536]]
6The kernel is 2-dimensional

You’ll notice that the first column that scipy spits out is just \(-\partial Q / 2\), but the second basis vector is who-knows-what. Definitely not the basis I’d have chosen. Regardless, it’s clear that the kernel is 2-dimensional. Sweet.

the general solution

To summarize, this little exercise in linear algebra shows us how to solve our interview problem by computing the nullity of a certain matrix associated to our shape. What we’re doing when we do this is computing the number of linearly independent loops in the shape. The loops are the vectors in \(\R^{|X_1|}\) sent to \(0\in\R^{|x_0|}\) by \(\partial\), so the the dimension of the kernel of \(\partial\) is what we’re after. That’s it!

What we’ve done above is a baby’s first computation in algebraic topology, the aptly named field of mathematics that uses algebraic techniques to attack problems involving topology. We treated the given shape as what’s called a simplicial complex (a one-dimensional simplicial complex, to be precise), and computed its first homology group (this was our real vector space \(\text{ker }\partial\) of dimension 2). The adjective ‘first’ indicates the dimension of the objects we were studying — loops! I’ll talk a bit more about homology below, but first we had better get to coding up our solution.

We start by associating to our string a one-dimensional simplicial complex. To create the matrix \(\partial\) above, all we needed was to number the vertices and the edges, and then keep track of how things were connected. If our original given matrix (whose entries held the slashes or spaces) was \(m\times n\) , we’ll need an \((m+1) \times (n+1)\) matrix to index the vertices. As a sanity check, recall our Example 1 above had \(m=1, n=1\) and we needed 4 vertices \(e_0,\ldots, e_3\). We’ll keep a list called complex whose \(i\)th entry will contain the \(j>i\) for which we have \(e_{ij}\in X_1\). So, in our example,

1'''
2complex = [[1, 2], # e_{01} and e_{02}
3           [2, 3], # e_{12} and e_{13}
4           [3],    # e_{23}
5           []]     # no edges starting at e_3
6'''

To create complex, we just loop through the vertices from top left to bottom right. If we’re at a boundary vertex, we’ll make sure to connect it to the appropriate boundary vertices, but otherwise, if we’re at a vertex on the interior, we’ll take a look below and add vertices according to the slashes we find.

 1def simplicial_complex(s):
 2    # get the numpy matrix
 3    matrix = string_to_np(s)
 4    mp1 = matrix.shape[0] + 1
 5    np1 = matrix.shape[1] + 1
 6    complex = []
 7    # loop through the vertices v at (i, j)
 8    for i in range(mp1):
 9        for j in range(np1):
10            connections = []
11
12            # special logic for vertices on the boundary
13            # if v is in the top row, connect it to the vertex on its right
14            if i == 0 and j != (np1 - 1):
15                connections.append(i * np1 + j + 1)
16            # if v is in the bottom row, connect it to the vertex on its right
17            if i == (mp1 - 1) and j != (np1 - 1):
18                connections.append(i * np1 + j + 1)
19            # if v is in the left column, connect it to the vertex below it
20            if j == 0 and i != (mp1 - 1):
21                connections.append((i + 1) * np1 + j)
22            # if v is in the right column, connect it to the vertex below it
23            if j == (np1 - 1) and i != (mp1 - 1):
24                connections.append((i + 1) * np1 + j)
25
26            # check SW diagonal for /
27            if i != (mp1 - 1) and j != 0 and matrix[i][j - 1] == '/':
28                connections.append((i + 1) * np1 + j - 1)
29            # check SE diagonal for \
30            if i != (mp1 - 1) and j != (np1 - 1) and matrix[i][j] == '\\':
31                connections.append((i + 1) * np1 + j + 1)
32
33            # make sure they're sorted! This is important to faithfully
34            # represent the linear algebra that we're doing
35            connections.sort()
36            complex.append(connections)
37    return complex

Okay, so that’s not too bad (ugh, indexing). Let’s make sure we get what we wanted.

1complex = simplicial_complex(examples[1])
2for i, vertex in enumerate(complex):
3    print(f'{i} | {vertex}')

10 | [1, 2]
21 | [2, 3]
32 | [3]
43 | []

Looks good. Now we’ve gotta construct the matrix \(\partial\). This was actually pretty simple. The number of rows was \(|X_0|\) (the number of vertices) and the number of columns was \(|X_1|\) (the number of edges). For each edge \(e_{ij}\), the map \(\partial\) returns \(e_j - e_i\), so the column corresponding to \(e_{ij}\) should have a \(-1\) in the \(i\)th row and a \(1\) in the \(j\)th row. Zeroes everywhere else. Pretty straightforward. We’ll order our vertices in the obvious way, \(e_0, e_1,\ldots\), and our edges by the starting vertex first and the ending vertex second (i.e. reading left-to-right from the top-to-bottom in the output of our previous code block ).

 1def differential(complex):
 2    num_vertices = len(complex)
 3    num_edges = sum([len(row) for row in complex])
 4    # initialize our matrix with zeros
 5    d = np.zeros((num_vertices, num_edges), dtype = int)
 6    for start_vertex, v in enumerate(complex):
 7        for j, end_vertex in enumerate(v):
 8            # what's the column index of e_{start_vertex, end_vertex}?
 9            # count how many edges came above start_vertex in our ordering,
10            # and then add the index of end_vertex in the list of vertices
11            # that start_vertex is connected to
12            column = sum([len(row) for i, row in enumerate(complex) if i < start_vertex]) + j
13            d[start_vertex][column] = -1
14            d[end_vertex][column] = 1
15
16    return d

If we feed it Example 1…

1differential(simplicial_complex(examples[1]))

1array([[-1, -1,  0,  0,  0],
2       [ 1,  0, -1, -1,  0],
3       [ 0,  1,  1,  0, -1],
4       [ 0,  0,  0,  1,  1]])

That’s exactly the matrix that we had constructed earlier. You might notice that I’ve called the function (by force of habit) differential. That’s just a synonym for ‘boundary’ in the context of homology theories.⁴

All that’s left now is to compute its nullity. That’s easy enough with scipy.

1def regions(s):
2    # return the number of basis vectors in the basis computed by scipy
3    # for the kernel of the boundary matrix d
4    return linalg.null_space(differential(simplicial_complex(s))).shape[1]

If we run it on our examples, we find:

1print('Computed:')
2print(list(map(regions, examples)))
3print('Expected:')
4print(answers)

1Computed:
2[1, 2, 3, 4, 6]
3Expected:
4[1, 2, 3, 4, 6]

And there you have it! That’s our solution to this interview problem!⁵ If you take the time to write code to perform row-reduction and back-substitution, you could even display a basis of loops that generate the kernel of \(\partial\) (in our case earlier it was \(\partial T_1\) and \(-\partial Q\)). Anyway, if you’re interested in learning a bit more about homology, stick around and I’ll say a few words below.

homology

Okay, so now to get a bit more abstract. We’ve been working with one-dimensional simplicial complexes, but in general we can have vertices, edges, surfaces, volumes, etc. So if \(X\) is a simplicial complex, \(X_k\) represents the set of \(k\)-simplices. Given such an \(X\) in general, we can form its simplicial chain complex:⁶

\begin{equation*} C_*(X) = \cdots \to C_3(X) \xrightarrow{\partial_3} C_2(X) \xrightarrow{\partial_2} C_1(X) \xrightarrow{\partial_1} C_0(X) \to 0 \end{equation*}

This is a sequence of vector spaces \(C_k(X) = \R^{|X_k|}\), where \(C_k\) has dimension the number of \(k\)-simplices in \(X\), together with a sequence of linear transformations between them. The notation might be a bit intimidating, but it’s really quite concrete. For \(X\) the simplicial complex from Example 1 earlier, the associated simplicial chain complex \(C_*(X)\) is just

\begin{equation*} C_*(X) = 0 \xrightarrow{0} \R^5 \xrightarrow{\partial} \R^4 \xrightarrow{0} 0. \end{equation*}

There’s only two non-trivial vector spaces in the sequence, and therefore only one non-trivial map: the map that takes an edge \(e_{ij}\) to the difference \(e_j - e_i\). But wait, you might protest, what about the regions \(T_1\) and \(T_2\)? Those were 2-dimensional thingies so shouldn’t we have a non-zero vector space of 2-simplices \(C_2(X)\)? Well we only worked with 0- and 1-dimensional simplices in the calculations above: we treated \(X\) like a directed graph instead of an object with surfaces. Think of empty space in those triangles that you could poke your fingers into. As to why we made that choice, I’ll explain in a moment.

Returning to the setting of a general simplicial complex \(X\), the map \(\partial_k: C_k(X) \to C_{k-1}(X)\) sends a \(k\)-simplex (or linear combination of \(k\)-simplices) to its boundary, which will be a sum of \((k-1)\)-simplices. Again, think of a line segment sent to the difference of its endpoints, or a triangle sent to a linear combination of its edges, or a triangular pyramid (tetrahedron) sent to a linear combination of its faces. At any point in the sequence — say we’re looking at \(C_k(X)\) — there’s a linear transformation \(\partial_{k+1}\) coming in to \(C_k(X)\) and a linear transformation leaving \(C_k(X)\). The crucial observation that underlies the theory of homology theory is that \(\partial_k \circ \partial_{k+1} = 0\) for each \(k\). That is, if you were to multiply the matrix for \(\partial_k\) against the matrix for \(\partial_{k+1}\), you’d get the zero matrix. Why is that? Unfortunately, I can’t give the precise proof without writing down all the formulas for \(\partial_k\) in general (and all of its gory alternating signs), but we’ve actually already seen an example. Remember when we were point out that the boundary of a loop is zero?

\begin{align*} \partial (\partial T_1) &= \partial(e_{01} + e_{12} - e_{20}) \\ &= e_1 - e_0 + e_2 - e_1 - (e_2 - e_0) \\ &= 0. \end{align*}

In our notation here, \(\partial_1(\partial_2 T_1)=0\), or rather, \((\partial_1 \circ \partial_2)(T_1)=0\). The loop \(\partial T_1\) is the boundary of the 2-simplex \(T_1\) (which, again, we didn’t actually use in our calculations earlier) and the boundary of a boundary is always zero! You’ll usually see this cornerstone of the theory of chain complexes written as the beautifully simple⁷

\begin{equation*} \partial^2 = 0. \end{equation*}

From a linear algebraic standpoint, what happens when the composition of two maps is zero? It means that the image \(\text{im }\partial_{k+1}\) of the first map is contained in the kernel \(\text{ker }\partial_k\) of the second map. Make sure you parse that out and it makes sense to you. The idea behind homology is really quite simple: the \(k\)th homology group measures how much of \(\text{ker }\partial_k\) is not hit by \(\partial_{k+1}\). More precisely, the \(k\)th simplicial homology vector space of \(X\) is the quotient space

\begin{equation*} H_k(X) = \frac{\text{ker }(\partial_k:C_k(X) \to C_{k-1}(X))}{\text{im }(\partial_{k+1}:C_{k+1}(X) \to C_k(X))}. \end{equation*}

If you’re not too familiar with quotient spaces, you won’t go too wrong in thinking of the \(k\)th homology space as the orthogonal complement of \(\text{im }\partial_{k+1}\) inside \(\text{ker }\partial_k\). If you were to just count dimensions, the dimension of \(H_k(X)\) is the nullity of \(\partial_k\) minus the rank of \(\partial_{k+1}\).

That’s all a bit of a mouthful to parse, so let’s back it up and think about what that means geometrically for a moment. Let’s go back to our handy Example 1. We only have one non-zero differential, but let’s compute the 0th and 1st homologies.

\begin{equation*} 0 \xrightarrow{0} \R^5 \xrightarrow{\partial_1} \R^4 \xrightarrow{0} 0. \end{equation*}

The 0th homology is the quotient of \(\text{ker }\partial_0\) by \(\text{im }\partial_1\). Well \(\partial_0=0\) so its kernel is all of its domain, \(\R^4\). That is to say, \(\partial e_i=0\) for all \(i\), which makes sense — points don’t have boundaries. There are no \((-1)\)-simplices. What’s the image of \(\partial_1\)? Well we have that (I’ll drop the subscript on \(\partial_1\) here)

\begin{align*} \partial e_{01} &= e_1 - e_0 \\ \partial e_{02} &= e_2 - e_0 \\ \partial e_{12} &= e_2 - e_1 \\ \partial e_{13} &= e_3 - e_1 \\ \partial e_{23} &= e_3 - e_2 \end{align*}

so how much of our space \(\R^4\) of vertices can we write as \(\partial\) of something? First, notice that \(\partial e_{12} = \partial e_{02} - \partial e_{01}\) and \(\partial e_{23} = \partial e_{13} - \partial e_{12}\) (do you see where we got these? hint: think \(\partial^2=0\)). The remaining \(\{\partial e_{01}, \partial e_{02}, \partial e_{13}\}\) are clearly linearly independent in \(\R^4\), and so we see that the image of \(\partial_1\) is 3-dimensional. Thus the homology \(H_0(X)\), which is the nullity of \(\partial_0=0\) minus the rank of \(\partial_1\), is \((4-3)\)-dimensional:

\begin{equation*} H_0(X) \cong \R^1. \end{equation*}

What about the 1st homology? Well that will have dimension equal to the nullity of \(\partial_1\) minus the rank of \(\partial_2\). Since \(\partial_2=0\), this is just the dimension of the kernel of \(\partial_1\). But we’ve already computed that — that was the solution to our interview problem! So

\begin{equation*} H_1(X) \cong \R^2. \end{equation*}

In other words, our solution equated the number of regions to dimension of the first homology space of the relevant one-dimensional simplicial complex. The code was (after setting up the vertices and edges carefully) just a matter of computing the kernel of a matrix. Is there a 2nd homology group? No, because it would involve a quotient of the kernel of \(\partial_2\) but \(C_2(X)=0\).

Notice that if we had instead worked with a 2-dimensional simplicial complex, the dimension of the first homology would not be what the problem was asking for. The problem is looking for the nullity of \(\partial_1\), but the dimension of the homology would be smaller by the rank of \(\partial_2\), due to the presence of a non-trivial \(C_2(X)\). Very roughly speaking, the \(k\)th homology counts the number of distinct \(k\)-dimensional loops that can’t be written as the boundary of a \(k-1\)-dimensional simplex. And if we were to throw in the 2-simplices into Example 1, all our loops would be boundaries, hence 0 in homology!

This post is too long already, so let me wrap it up with a few remarks to give some perspective on the broader picture. The study of algebraic gadgets like chain complexes is a part of the field of homological algebra, which at it core studies the consequences of the equation \(\partial^2=0\). What we’ve been doing here falls under the realm of algebraic topology, which uses such algebraic techniques to better understand topological spaces. Simplicial homology, the tool we used to solve the interview problem, is an example of such a technique. There are many different types of homology theories for topological spaces — the simplicial one that we’ve been working with requires the least machinery to get up and running. An important class of theorems determine the conditions under which different homology theories spit out the same dimensions, and under these conditions, it’s often computation convenient to use one particular homology theory over another.

Homology, in the general abstract, provides an invariant of topological spaces. That is to say, if you were to continuously deform a space \(X\) into a space \(Y\), then \(H_k(X) \cong H_k(Y)\) for every \(k\). Hence the joke that topologists cannot distinguish between tori and coffee mugs — they’re the same, as far as homology can tell!