Lecture 3: Homology

Lecture 3: Homology#

Each exercise has a checker cell that prints ok or FAIL, and a cell with hidden solution.
Checkers, plotting and example data are in lecture3_helpers.py.

from typing import Callable
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import gudhi

# Everything below comes from lecture3_helpers.py, next to this notebook.
from lecture3_helpers import (
    Simplex, Chain,                    # type names: a Simplex is a sorted tuple, a Chain is (simplices, coeffs)
    check_is_group,                    # Sec. 1: tests for your is_group
    chain_dim, fmt, trace,             # Sec. 2: dimension of a chain, pretty-printing, show a function's outputs
    check_chain_add, check_chain_add_mod2,
    K, K_COORDS,                       # Sec. 3: the running example complex K, and where to draw its vertices
    draw, draw_chain,                  # Sec. 3: plot a complex, highlight a chain on it
    check_boundary_simplex, check_boundary_chain, SLIDE_EXAMPLES,
    K3, TORUS,                         # Sec. 3: more complexes, to compare with GUDHI
    simplices_of_dim,                  # Sec. 4: the p-simplices of a complex
    check_boundary_matrix,
    check_is_cycle,                    # Sec. 5
    rank_mod2, EMPTY_TRIANGLE,         # Sec. 6: rank over Z_2, and a complex showing why we need it
    check_betti,
    ZOO, draw_abstract,                # Sec. 7: five complexes to predict, and a sketch plot for them
    cech, SHAPES, LETTERS, plot_clouds,  # Sec. 8: Cech complex, point clouds, and a grid plot of clouds
    check_classify, check_group_letters,
)
plt.rcParams["figure.dpi"] = 110

1. Groups#

A group \((G, \ast)\) is a set with an operation such that:

closure: \(a \ast b \in G\);
associativity: \((a \ast b) \ast c = a \ast (b \ast c)\);
identity: there is an \(e\) with \(a \ast e = e \ast a = a\);
inverses: every \(a\) has a \(b\) with \(a \ast b = b \ast a = e\).

It is commutative if also \(a \ast b = b \ast a\).

Example: \(\mathbb{Z}_2 = \{0, 1\}\) with \(+\) mod 2, whose table is:

\(+\)	\(0\)	\(1\)
\(0\)	\(0\)	\(1\)
\(1\)	\(1\)	\(0\)

Closure: every entry is \(0\) or \(1\).
Associativity: check all \(2^3 = 8\) triples, e.g. \((1+1)+1 = 1 = 1+(1+1)\).
Identity: \(e = 0\), because its row repeats the header (applying +0 doesn’t change anything).
Inverses: \(1 + 1 = 0\) and \(0 + 0 = 0\), so each element is its own inverse.
Commutative: yes, the table is symmetric.

Exercise 1.1: `is_group(G, op)`#

Input: G, a finite set; op, a function taking two elements of G.
Output: (True, True) for a commutative group, (True, False) for a non-commutative group, and (False, False) if it is not a group.
Example: is_group({0, 1}, lambda a, b: (a + b) % 2) returns (True, True).

Brute-force it: check the four axioms in order, then commutativity.

def is_group(G: set, op: Callable) -> tuple[bool, bool]:
    # 1. closure:       for every a in G, for every b in G: is op(a, b) in G?
    # 2. associativity: for every a in G, for every b in G, for every c in G: is op(op(a, b), c) == op(a, op(b, c))?
    # 3. identity:      loop over candidates e; keep one with op(a, e) == a == op(e, a) for every a
    # 4. inverses:      for each a, look for SOME b with op(a, b) == e == op(b, a)
    # 5. commutative:   for every a in G, for every b in G: is op(a, b) == op(b, a)?
    raise NotImplementedError

Solution hidden in this cell#

check_is_group(is_group)   # S3 = permutations of (0, 1, 2) under composition: a non-commutative group

Experiment. Here is \(\mathbb{Z}_4 = \{0, 1, 2, 3\}\) with \(+\) mod 4. Change the set or the operation and see what breaks. For example:

try * mod 4;
drop an element from Z4;
use max.

Z4 = {0, 1, 2, 3}
add_mod4 = lambda a, b: (a + b) % 4 # this is a convenient way to define a function in one line, but you can use a regular def statement
print("Z_4 with + mod 4:", is_group(Z4, add_mod4))

Exercise 1.2: a group of strings#

A group can be defined for any set. Elements don’t have to be numbers. Pick a set of letters or strings, and define your own op so that is_group returns (True, ...).

letters = {"a", "b", "c"}       # or any set of strings you like

def letter_op(x: str, y: str) -> str:
    return x  # this op does not induce a valid group                  

print(is_group(letters, letter_op))   # (False, False) until you write your own op

2. Chains#

A \(p\)-chain is a formal sum of \(p\)-simplices, \(\alpha = \sum_i a_i \sigma_i\) (slide 6). We store it as a Chain, a pair of lists (simplices, coeffs):

each simplex is a tuple of sorted vertex numbers, e.g. (0, 1) for the edge \([0,1]\).

chain	in Python
\(2[0,1] - [1,2]\)	`([(0, 1), (1, 2)], [2, -1])`
\([2]\)	`([(2,)], [1])`
\(0\)	`([], [])`

Helpers:

chain_dim(chain: Chain) -> int | None: the \(p\) of a \(p\)-chain, None for the zero chain. It raises a ValueError if the chain is invalid (lists of different lengths, unsorted simplex, or mixed dimensions).
fmt(chain: Chain) -> str: the chain as readable text, e.g. '2[0,1] - [1,2]'.
trace(fn, calls) -> None: prints what fn returns or raises for each tuple of arguments in the list calls.

print(fmt(([(0, 1), (1, 2)], [2, -1])))
trace(chain_dim, [(([(0, 1), (1, 2)], [2, -1]),), (([], []),), (([(0, 1), (0, 1, 2)], [1, 1]),)])

Exercise 2.1: `chain_add(a, b)`#

Chains are added coefficient by coefficient (slide 7): \(\sum a_i\sigma_i + \sum b_i\sigma_i = \sum (a_i + b_i)\sigma_i\).

Input: two chains a, b of the same dimension. Either one can be the zero chain.
Output: their sum, simplified: each simplex once, no zero coefficients, simplices sorted. Raise a ValueError for invalid chains or mixed dimensions.
Example: chain_add(([(0, 1)], [1]), ([(0, 1), (1, 2)], [2, 1])) returns ([(0, 1), (1, 2)], [3, 1]).

def chain_add(a: Chain, b: Chain) -> Chain:
    # tip: call chain_dim(a) and chain_dim(b) first: they raise on invalid input, and
    #      give you the two dimensions to compare (None means the zero chain).
    # tip: at the end, keep the simplices with a nonzero total, sorted.
    raise NotImplementedError

Solution hidden in this cell#

check_chain_add(chain_add)

Try it yourself: change a and b below, and add the zero chain ([], []) to something.

a = ([(0, 1), (1, 2)], [1, 1])            # [0,1] + [1,2]
b = ([(1, 2), (2, 3)], [1, 1])            # [1,2] + [2,3]
print("a + b =", fmt(chain_add(a, b)))
print("a + 0 =", fmt(chain_add(a, ([], []))))

Exercise 2.2: `chain_add_mod2(a, b)`#

The same, with coefficients in \(\mathbb{Z}_2\), where \(1 + 1 = 0\).

Input / output: as in chain_add, but every coefficient in the output is \(1\).
Example: chain_add_mod2(([(0, 1), (1, 2)], [1, 1]), ([(1, 2)], [1])) returns ([(0, 1)], [1]), because the two copies of \([1,2]\) cancel.

def chain_add_mod2(a: Chain, b: Chain) -> Chain:
    # tip: call chain_add, then keep only the simplices with an odd coefficient (c % 2 == 1).
    raise NotImplementedError

Solution hidden in this cell#

check_chain_add_mod2(chain_add_mod2)

The same a and b, now over \(\mathbb{Z}_2\). The results differ: \([1,2]\) appears twice, so it disappears. Try a few more chains, and think about how many times a simplex has to appear to survive. What is \(a + a\)?

print("over Z  : a + b =", fmt(chain_add(a, b)), "    a + a =", fmt(chain_add(a, a)))
print("over Z_2: a + b =", fmt(chain_add_mod2(a, b)), "            a + a =", fmt(chain_add_mod2(a, a)))

Solution hidden in this cell#

3. Boundary maps#

Over \(\mathbb{Z}_2\) the boundary of a simplex is the sum of the faces obtained by dropping one vertex (slide 10):

\[\partial_p [v_0, \dots, v_p] = \sum_{j=0}^{p} [v_0, \dots, \hat{v}_j, \dots, v_p], \qquad \text{e.g.}\quad \partial_2 [1,2,4] = [2,4] + [1,4] + [1,2].\]

Our running example is the complex \(K\) from Dr. Munch’s notebook, drawn below.

Helpers:

K: this complex, as a GUDHI SimplexTree with vertices \(0, \ldots, 4\).
K_COORDS: a \(5 \times 2\) array, where row \(i\) holds the position of vertex \(i\) (only used for drawing).
draw(points, complex, ax=None, labels=None, title=None) -> Axes: draws a SimplexTree, placing vertex \(i\) at points[i]. labels=True writes the vertex numbers.

print([tuple(s) for s, _ in K.get_simplices()])
draw(K_COORDS, K, labels=True, title="K")
plt.show()

Exercise 3.1: `boundary_simplex(simplex, p)`#

This is the definition above, applied to a single simplex.

Input: a \(p\)-simplex as a sorted tuple, and \(p\).
Output: its boundary, as a chain. Raise a ValueError if simplex does not have \(p + 1\) vertices. \(\partial_0\) of a vertex is the zero chain.
Example: boundary_simplex((1, 2, 4), 2) returns ([(1, 2), (1, 4), (2, 4)], [1, 1, 1]).

def boundary_simplex(simplex: Simplex, p: int) -> Chain:
    # tip: sort the faces, so that the output looks like chain_add's.
    raise NotImplementedError

Solution hidden in this cell#

check_boundary_simplex(boundary_simplex)

In GUDHI, SimplexTree.get_boundaries(simplex) lists the faces of a simplex, each with its filtration value, which we ignore. Let’s compare it with your function on every simplex of K, K3 (the complex of Section 7) and TORUS (a 7-vertex torus), all SimplexTrees:

def gudhi_boundary(st: gudhi.SimplexTree, simplex: Simplex) -> Chain:
    faces = sorted(tuple(f) for f, _ in st.get_boundaries(list(simplex)))
    return faces, [1] * len(faces)


print("GUDHI: d[1,2,4] =", fmt(gudhi_boundary(K, (1, 2, 4))))
for label, st in [("K", K), ("K3", K3), ("TORUS", TORUS)]:
    simplices = [tuple(s) for s, _ in st.get_simplices()]
    agree = sum(boundary_simplex(s, len(s) - 1) == gudhi_boundary(st, s) for s in simplices)
    print(f"{'ok  ' if agree == len(simplices) else 'FAIL'} {label}: {agree}/{len(simplices)} simplices agree")

Exercise 3.2: `boundary_chain(chain)`#

Use linearity (slide 11): \(\partial\big(\sum_i a_i\sigma_i\big) = \sum_i a_i\,\partial\sigma_i\).

Input: a chain over \(\mathbb{Z}_2\).
Output: its boundary, as a chain.
Example: \(\partial([0,4] + [1,4]) = [0] + [4] + [1] + [4] = [0] + [1]\), so boundary_chain(([(0, 4), (1, 4)], [1, 1])) returns ([(0,), (1,)], [1, 1]).

def boundary_chain(chain: Chain) -> Chain:
    # tip: p = chain_dim(chain); if it is None (the zero chain) the boundary is ([], []).
    # tip: start from result = ([], []) and, for each simplex in chain[0], add its boundary to result using chain_add_mod2.
    raise NotImplementedError

Solution hidden in this cell#

check_boundary_chain(boundary_chain)   # the examples of slide 12, on K

The same examples as pictures, with each chain on top and its boundary below.

Helpers:

SLIDE_EXAMPLES: a list of (description, chain, its boundary) triples.
draw_chain(points, chain: Chain, ax) -> None: highlights the simplices of chain in red on a plot made by draw.

fig, axes = plt.subplots(2, 4, figsize=(13, 6.4))
for k, (desc, chain, _) in enumerate(SLIDE_EXAMPLES):
    for row, c in enumerate([chain, boundary_chain(chain)]):
        draw(K_COORDS, K, ax=axes[row, k], labels=True)
        draw_chain(K_COORDS, c, axes[row, k])
        axes[row, k].set_title(("chain: " if row == 0 else "boundary: ") + fmt(c), fontsize=9)
plt.tight_layout(); plt.show()

Slide 20: \(\partial\partial = 0\). By hand: \(\partial_1\partial_2[1,2,4] = \partial_1([1,2] + [1,4] + [2,4]) = [1] + [2] + [1] + [4] + [2] + [4] = 0\). Your code agrees:

d = boundary_chain(([(1, 2, 4)], [1]))
print("d [1,2,4]   =", fmt(d))
print("d d [1,2,4] =", fmt(boundary_chain(d)))

4. Boundary matrices#

\(\partial_p\) is linear, so it has a matrix (slide 13):

one column per \(p\)-simplex;
one row per \((p-1)\)-simplex;
a \(1\) where the row simplex is a face of the column simplex.

We can build these matrices for the complex \(K\) that we showed above, by hand:

vertex_list = ['0', '1', '2', '3', '4']
edge_list = ['04', '03', '12', '14', '23', '24']
triangle_list = ['124']

B1_df = pd.DataFrame(0, index=vertex_list, columns=edge_list)
for edge in B1_df.columns:          # the two vertices of each edge
    B1_df.loc[edge[0], edge] = 1
    B1_df.loc[edge[1], edge] = 1

B2_df = pd.DataFrame(0, index=edge_list, columns=triangle_list)
B2_df.loc['12', '124'] = 1          # the three edges of the triangle, typed by hand
B2_df.loc['14', '124'] = 1
B2_df.loc['24', '124'] = 1

display(B1_df, B2_df)

Exercise 4.1: `boundary_matrix(st, p)`#

Build the same matrices automatically: column \(j\) is boundary_simplex of the \(j\)-th \(p\)-simplex.

Input: a SimplexTree and \(p\).
Output: (D, rows, cols), where D is a 0/1 numpy array, rows is the list of \((p-1)\)-simplices and cols is the list of \(p\)-simplices.
Edge cases: for \(p = 0\), D has 0 rows; above the top dimension, it has 0 columns.
Helper: simplices_of_dim(st, p: int) -> list[Simplex] gives the sorted \(p\)-simplices, e.g. simplices_of_dim(K, 2) returns [(1, 2, 4)].
Example: boundary_matrix(K, 2) returns (array([[0], [0], [1], [1], [0], [1]]), [(0, 3), (0, 4), (1, 2), (1, 4), (2, 3), (2, 4)], [(1, 2, 4)]).

def boundary_matrix(st: gudhi.SimplexTree, p: int) -> tuple[np.ndarray, list[Simplex], list[Simplex]]:
    # tip: cols = simplices_of_dim(st, p) and rows = simplices_of_dim(st, p - 1)  (use [] if p == 0).
    # tip: row_index = {s: i for i, s in enumerate(rows)} tells you the row of each face.
    # tip: You can usenp.zeros((len(rows), len(cols)), dtype=int) creating a matrix of the correct size with all zeros.
    # You don't have to use a pandas DataFrame like in the example above.
    raise NotImplementedError

Solution hidden in this cell#

check_boundary_matrix(boundary_matrix)   # compares with B1_df and B2_df; row/column order doesn't matter

5. Cycles and boundaries#

cycles: \(Z_p = \ker \partial_p\), the chains with \(\partial_p\alpha = 0\) (slide 17);
boundaries: \(B_p = \operatorname{im} \partial_{p+1}\) (slide 19);
since \(\partial\partial = 0\), every boundary is a cycle.

Exercise 5.1: `is_cycle(chain)`#

This is the definition of a cycle.

Input: a chain over \(\mathbb{Z}_2\).
Output: True if its boundary is zero.
Example: the square \([0,3] + [0,4] + [2,3] + [2,4]\) is a cycle; \([0,4] + [1,4]\) is not.

def is_cycle(chain: Chain) -> bool:
    # tip: one line: the boundary (boundary_chain) has no simplices.
    raise NotImplementedError

Solution hidden in this cell#

check_is_cycle(is_cycle)

Every boundary is a cycle, but not every cycle is a boundary.

\(\partial[1,2,4]\) is a boundary, and it is a cycle, since \(\partial\partial = 0\).
The square is a cycle too, but it is not a boundary. \(K\) has a single triangle, so its only boundaries are \(0\) and \(\partial[1,2,4]\). The square goes around a hole that no triangle fills.

triangle_edges = boundary_chain(([(1, 2, 4)], [1]))
square = ([(0, 3), (0, 4), (2, 3), (2, 4)], [1, 1, 1, 1])
boundaries = [([], []), triangle_edges]        # the boundaries of the 2-chains 0 and [1,2,4]

fig, axes = plt.subplots(1, 2, figsize=(7, 3.6))
for ax, (label, z) in zip(axes, [("d[1,2,4]", triangle_edges), ("square", square)]):
    draw(K_COORDS, K, ax=ax, labels=True)
    draw_chain(K_COORDS, z, ax)
    ax.set_title(f"{label}\ncycle: {is_cycle(z)},  boundary: {z in boundaries}", fontsize=9)
plt.tight_layout(); plt.show()

Homology classes. Two cycles are in the same class when they differ by a boundary. \(K\) has four 1-cycles, and they fall into two classes: \([0]\) (blue) and \([\text{square}]\) (red). So \(H_1(K) = Z_1/B_1 \cong \mathbb{Z}_2\) and \(\beta_1 = 1\) (slides 27–29).

classes = {"[0]": [([], []), triangle_edges], "[square]": [square, chain_add_mod2(square, triangle_edges)]}

fig, axes = plt.subplots(1, 4, figsize=(13, 3.4))
ax_iter = iter(axes)
for (label, cycles), color in zip(classes.items(), ["#2E86C1", "crimson"]):
    for z in cycles:
        ax = next(ax_iter)
        draw(K_COORDS, K, ax=ax, labels=True)
        draw_chain(K_COORDS, z, ax, color=color)
        ax.set_title(f"class {label}: {fmt(z)}", fontsize=8)
plt.tight_layout(); plt.show()

Lecture 3: Homology

Contents

Lecture 3: Homology#

1. Groups#

Exercise 1.1: is_group(G, op)#

Solution hidden in this cell#

Exercise 1.2: a group of strings#

2. Chains#

Exercise 2.1: chain_add(a, b)#

Solution hidden in this cell#

Exercise 2.2: chain_add_mod2(a, b)#

Solution hidden in this cell#

Solution hidden in this cell#

3. Boundary maps#

Exercise 3.1: boundary_simplex(simplex, p)#

Solution hidden in this cell#

Exercise 3.2: boundary_chain(chain)#

Solution hidden in this cell#

4. Boundary matrices#

Exercise 4.1: boundary_matrix(st, p)#

Solution hidden in this cell#

5. Cycles and boundaries#

Exercise 5.1: is_cycle(chain)#

Solution hidden in this cell#

Exercise 1.1: `is_group(G, op)`#

Exercise 2.1: `chain_add(a, b)`#

Exercise 2.2: `chain_add_mod2(a, b)`#

Exercise 3.1: `boundary_simplex(simplex, p)`#

Exercise 3.2: `boundary_chain(chain)`#

Exercise 4.1: `boundary_matrix(st, p)`#

Exercise 5.1: `is_cycle(chain)`#