How to compute homology

In this article we summarize the procedure for computing the homology of a cell complex, by hand.

Procedure

Step 1: present the cell complex

List the cells of the complex $K$. Try to find the most economical representation - start with the highest dimension. Then merge the cells whenever possible and use cell collapse as well. Indicate the orientations. List the boundaries of the cells.

Step 2: find the chain groups

The $k$-chain group $C_k(K)$ is given as a vector space with basis consisting of the cells of the complex:

$C_k(K) =$ span$\{k$-cells in $K \}$.

Its dimension is then obvious.

Step 3: find the matrices of the boundary operators

The $k$-boundary operator

$${\partial}_k: C_k(K) {\rightarrow} C_{k-1}(K)$$

is a linear operator. As such it is determined by its values on the elements of the basis of the domains space $C_k(K)$, the $k$-cells, as they are expressed as linear combinations of the elements of the basis of the target space $C_{k-1}(K)$, the $(k-1)$-cells. The coefficients of these linear combinations form the columns of the matrix.

Step 4: find the cycle groups

The $k$-cycle group is the kernel of the $k$-boundary operator:

$$Z_k(K) = \ker {\partial}_k.$$

As such it is the solution of the matrix equation:

find all $x{\in}C_k(K)$ such that ${\partial}_k(x) = 0$.

It is a subspace of the chain group $C_k(K)$. One finds it by finding its basis.

Shortcuts:

• if ${\partial}_k$ is $0$, its kernel is the whole domain space:

$$Z_k(K) = C_k(K).$$

• if ${\partial}_k$ is one-to-one, its kernel is $0$:

$$Z_k(K) = 0.$$

Otherwise the problem is reduced to solving the homogeneous system of linear equations that corresponds to the matrix equation.

Step 5: find the boundary groups

The $k$-boundary group is the image of the $(k+1)$-boundary operator:

$$B_k(K) = {\partial}_{k+1}.$$

As such it is spanned by the images of the basis of the $(k+1)$-cycle group, $(k+1)$-cells:

$B_k(K) = {\rm \hspace{3pt} span \hspace{3pt}} \{\partial_{k+1}(s_i): s$ is a $(k+1)$-cell in $K \}.$

It is a subspace of the cycle group $Z_k(K)$. One finds it by finding its basis.

Shortcuts:

• if ${\partial}_{k+1}$ is onto, its image is the whole target space:

$$B_k(K) = C_k(K).$$

• if ${\partial}_k$ is $0$, its image is $0$:

$$B_{k+1}(K) = 0.$$

Otherwise the problem is solved by removing vectors from the spanning set to make it linearly independent. The problem is reduced to solving the homogeneous system of linear equations:

find $a_i$ such that $\displaystyle\sum_ia_i{\partial}_{k+1}(s_i) = 0.$

Step 6: find the homology groups

The homology group is the quotient vector space of cycles over boundaries:

$$H_k(K) = Z_k(K) / B_k(K).$$

It is a vector space of dimension

$$\dim H_k(K) = \dim Z_k(K) - \dim B_k(K),$$

which gives us the Betti numbers of $K$. This vector space is the space of equivalence classes on the cycle group:

for $x,y{\in}Z_k(K), x {\sim} y$ if $x - y{\in}B_k(K)$.

Shortcuts:

$$Z_k(K) = B_k(K) \rightarrow H_k(K) = 0,$$ $$B_k(K) = 0 \rightarrow H_k(K) = Z_k(K).$$

Otherwise, one has to remove the elements of the basis of the cycle group that are equivalent to $0$.

Example

Step 1: present the cell complex

One may choose to triangulate the sphere and then add the string (first image). A more efficient way is to cut the sphere into two hemispheres (second image). Turns out, one can remove one of the edges and merge the hemispheres. One $2$-cells is enough (third image).

Cells and their boundaries: $$\dim 2: {\tau}, {\partial}_2{\tau} = a - a = 0;$$

$$\dim 1: a, c, {\partial}_1a = B - A, {\partial}_1c = B - A;$$

$$\dim 0: A, B, {\partial}_0A = 0, {\partial}_0B = 0.$$

Step 2: find the chain groups

$$C_2(K) = {\rm \hspace{3pt} span \hspace{3pt}}\{\tau \} = {\bf R},$$ $$C_1(K) = {\rm \hspace{3pt} span \hspace{3pt}}\{a, c \} = {\bf R}^2,$$ $$C_0(K) = {\rm \hspace{3pt} span \hspace{3pt}}\{A, B \} = {\bf R}^2.$$

Step 3: find the matrices of the boundary operators

$${\partial}_2: C_2(K) {\rightarrow} C_1(K), {\bf R} {\rightarrow} {\bf R}^2,$$

$${\partial}_2 = [0, 0]^T = \left| \begin{array}{} 0 \\ 0 \end{array} \right| ; $$

$${\partial}_1: C_1(K) {\rightarrow} C_0(K), {\bf R}^2 {\rightarrow} {\bf R}^2,$$

$${\partial}_1 = \left| \begin{array}{rr} -1 & -1 \\ 1 & 1 \end{array} \right| ;$$

$${\partial}_0: C_0(K) {\rightarrow} 0, {\bf R}^2 {\rightarrow} 0,$$ $${\partial}_0 = [0, 0]^T = \left| \begin{array}{} 0 \\ 0 \end{array} \right|.$$

Chain complex:

$$0 {\rightarrow} C_0(K) {\rightarrow} C_0(K) {\rightarrow} C_0(K) {\rightarrow} 0.$$

Step 4: find the cycle groups

$${\partial}_2 = 0 \rightarrow Z_2(K) = \ker {\partial}_2 = C_2(K) = {\rm \hspace{3pt} span \hspace{3pt}} \{\tau \}.$$

$${\partial}_1a = {\partial}_1c = B - A \rightarrow {\partial}_1(a - c) = 0 \rightarrow a - c{\in}Z_1(K).$$

rank ${\partial}_1 = 1 \rightarrow Z_1(K) = {\rm \hspace{3pt} span \hspace{3pt}}\{a - c \}$.

$${\partial}_0 = 0 \rightarrow Z_0(K) = \ker {\partial}_0 = C_0(K) = {\rm \hspace{3pt} span \hspace{3pt}} \{A, B \}$$

Step 5: find the boundary groups

$$B_2(K) = {\partial}_3(0) = 0,$$ $$B_1(K) = {\rm \hspace{3pt} span \hspace{3pt}} \{{\partial}_2({\tau}) \} = {\rm \hspace{3pt} span \hspace{3pt}} \{0 \} = 0,$$ $$B_0(K) = {\rm \hspace{3pt} span \hspace{3pt}} \{{\partial}_1(a), {\partial}_1(c) \} = {\rm \hspace{3pt} span \hspace{3pt}} \{B - A, B - A \} = {\rm \hspace{3pt} span \hspace{3pt}} \{B - A \}.$$

Step 6: find the homology groups

$$H_2(K) = Z_2(K) / B_2(K) = {\rm \hspace{3pt} span \hspace{3pt}} \{{\tau} \} / 0 = {\rm \hspace{3pt} span \hspace{3pt}} \{{\tau} \};$$

$$H_1(K) = Z_1(K) / B_1(K) = {\rm \hspace{3pt} span \hspace{3pt}} \{a - c \} / 0 = {\rm \hspace{3pt} span \hspace{3pt}} \{a - c \};$$

$$H_0(K) = Z_0(K) / B_0(K) = {\rm \hspace{3pt} span \hspace{3pt}} \{A, B \} / {\rm \hspace{3pt} span \hspace{3pt}} \{B - A \} = {\rm \hspace{3pt} span \hspace{3pt}} \{A \}.$$

An easier problem: How to compute Betti numbers.

See also Homology software and Image analysis software.