This site is being phased out.
How to compute homology
In this article we summarize the procedure for computing the homology of a cell complex, by hand.
Contents
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:
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:
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:
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:
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:
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|.$$
$$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).$$
$${\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.