In my last post, we talked about homology and Betti numbers. We had a very simple example with a simplicial complex $K$ and we were able to easily compute $H_1(K)$ and $\beta_1(K)$. But that wasn’t really the whole story.

To write an algorithm that can find the Betti numbers of any given (finite) simplicial complex, we actually need to know more about how to read off the geometric information of the input complex and what to do with that information.

(Most of the material in this post can be found in Munkres, Elements of Algebraic Topology $\S 11$.)

Let’s first lay out the basics.

A(n abstract) simplicial complex is a collection $K$ of finite non-empty sets such that if $\sigma$ is an element of $K$, so is every non-empty subset of $\sigma$.

An element $\sigma$ of $K$ is called a simplex of $K$; its dimension is one less than the number of its elements. We may refer to $\sigma$ as a $p$-simplex or denote it as $\sigma^p$ to indicate its dimension $p$.

Each nonempty subset $\tau$ of $\sigma$ is called a face of $\sigma$; we say that $\tau$ is incident to $\sigma$ and denote it $\tau \prec \sigma$.

The dimension $d$ of $K$ is the largest dimension of one of its simplices. A $d$-simplex of $K^d$ is called a facet of $K$.

Given a finite complex $L$, we say that there is a labeling of the vertices of $L$, which means that there is a surjective function $f$ mapping the vertex set of $L$ to a set of labels (usually $\{0,1,2, \dots\}$ or $\{1,2, \dots\}$). Corresponding to this labeling is an abstract complex $K$ whose vertices are the labels and whose simplices consist of all sets of the form $\{f(v-0), f(v_1), \dots, f(v_n)\}$, where $v_0, \dots, v_n$ span a simplex of $L$.

This labeling mumbo-jumbo is essentially formalizing the obvious. We want to refer to specific simplices of $K$ and the convention used is to name it by its vertices.

One important property of a simplicial complex is that for every cell $\sigma$ in $K$, all of the faces of $\sigma$ are also in $K$. This property we will exploit when setting up our problem.

Step 1: Setting up the input

For a given simplicial complex $K^d$ of dimension $d$, we need only the set of $d$-simplices of $K$, the facets of $K$, as the input for our algorithm. With this list we can determine all the simplices of $K$ and their connectivity.

We’re now ready to set up all of our $C_p$’s, the $p$-chain groups of $K$. Actually, what we really have is the just the basis elements of the $C_p$, but that’s all we need. For each $p= 0, \dots, d$, the basis of $C_p$ is the set of $p$-simplices of $K$.

Let $F$ be our facet list of $K^d$. Every element of $F$ contains $(d+1)$ elements. For any $i=0, \dots, d$, the basis of $C_i$ will be the union of all subsets of elements of $F$ of length $i+1$.

So if $K$ is just two triangles, $F = \{ [1 \, 2\, 3],[2\, 3\, 4]\}$, then the basis of $C_1(K)$ is just the set of edges of $K$ or $\{[1\, 2], [1\, 3], [2\, 3], [2\, 4], [3\, 4]\}$, all length 2 subsets of elements of $F$. Even though edge $[2\, 3]$ is in both triangles, we only need to count it once.

Step 2: Setting up the boundary map

The boundary maps $\partial_p$ are the main characters in homology groups. From group theory, we know that all we really need to know about a homomorphism $f: G \to G’$ is how $f$ acts on the basis elements of $G$ in terms of the basis elements of $G’$.

More formally, let’s take a look at this definition:

Definition (matrix of a homomorphism) Let $G$ and $G’$ be free abelian groups with bases $a_1, \dots, a_n$ and $a_1′, \dots, a_m’$, respectively. If $f: G \to G’$ is a homomorphism, then $$f(a_j) = \sum_{i=1}^{m} \lambda_{ij}a_i’$$ for unique integers $\lambda_{ij}$. The matrix $(\lambda_{ij})$ is called the matrix of $f$ relative to the given bases for $G$ and $G’$.

The chain groups $C_p$ are the free abelian groups. And our boundary maps $\partial_p: C_p \to C_{p-1}$ are the homomorphisms between them. To learn more about the boundary maps, we must further analyze the matrix of $\partial_p$.

Step 3: Computing the Smith Normal Form

To understand what the boundary map is doing, let’s first recall a nice theorem from algebra.

Theorem (normal form) Let $G$ and $G’$ be free abelian groups of ranks $n$ and $m$, respectively; let $f: G \to G’$ be a homomorphism. Then there are bases for $G$ and $G’$ such that, relative to these bases, the matrix of $f$ has the form $$B=\left[\begin{array}{c|c}\begin{matrix}b_1 & ~ & 0 \\ ~ & \ddots & ~ \\ 0 & ~&b_q\end{matrix} & 0 \\ \hline 0 & 0\end{array}\right]$$ where $b_i \ge 1$ and $b_1 | b_2| \dots | b_q$.

This matrix is uniquely determined by $f$ and is called the normal form for the matrix of $f$.

To get from some jumbled up matrix $(\lambda_{ij})$ to its normal form, we perform what are called elementary row and column operations. These operations are

1. exchange row $i$ and row $k$
2. multiply row $i$ by $-1$
3. replace row $i$ by (row $i$) + $q$ (row $k$), where $q$ is an integer and $k \ne i$,

plus the 3 respective column operations.

Perhaps you remember seeing the elementary row operations from linear algebra. It’s important to note that here we’re only allowing integer multiplication for operation type 3 (and 6 for the column operations).

Step 4: What it means

Recall what our goal was: to compute the homology groups of some finite simplicial complex $K$. And we know that all homology groups $H_p \cong \mathbb{Z}_{t_1} \times \cdots \times \mathbb{Z}_{t_k} \times \mathbb{Z}^{\beta}$ can be written in terms of their Betti numbers $\beta$ and their torsion coefficients $t_1, \dots t_k$.

Now that we have the normal form for all the boundary maps $\partial_p$ for $p=0, \dots, d$, we can easily read off this information.

Torsion coefficients: The entries of the normal form for the matrix of $\partial_p: C_p \to C_{p-1}$ that are greater than 1 are the torsion coefficients of $K$ in dimension $p-1$.

Betti numbers: Let $B_i$ be the normal form for the matrix of $\partial_i: C_i \to C_{i-1}$. The Betti number of $K$ in dimension $p$ is $$\beta_p = \text{rank} C_p – \text{rank} B_p – \text{rank} B_{p+1}.$$

So we’re done.

Or we should be, but we’re not. If we’re done why, then, are people still working on developing homology algorithms?

We’ll answer that question in another post.