# Characterization of the Computed Homology and Cohomology Bases

Yann-Situ Gazull, Aldo Gonzalez-Lorenzo, Alexandra Bac

► To cite this version:

Yann-Situ Gazull, Aldo Gonzalez-Lorenzo, Alexandra Bac. Characterization of the Computed Homology and Cohomology Bases. Discrete Geometry and Mathematical Morphology, Michael H. F. Wilkinson, Jiří Kosinka, Nov 2025, Groningen, Netherlands. pp.163-177, 10.1007/978-3-032-09544-2_12. hal-05357027

HAL Id: hal-05357027

https://hal.science/hal-05357027v1

Submitted on 10 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Characterization of the Computed Homology and Cohomology Bases

Yann-Situ Gazull¹, Aldo Gonzalez-Lorenzo¹, and Alexandra Bac¹

Aix Marseille Univ, CNRS, LIS, Marseille, France

**Abstract.** Computing homology and cohomology is at the heart of many recent works and a key issue for topological data analysis. Among homological objects, homology generators are useful to locate or understand holes (especially for geometric objects). The present paper provides a characterization of the class of homology bases that are computed by standard algorithmic methods. The proof of this characterization relies on the Homological Discrete Vector Field, a combinatorial structure for computing homology, which encompasses several standard methods (persistent homology, tri-partitions, Smith Normal Form, discrete Morse theory). These results refine the combinatorial homology theory and provide novel ideas to gain more control over the computation of homology generators.

**Keywords:** Computational Homology · Combinatorial Topology · Homological Discrete Vector Field · Persistent Homology

## 1 Introduction

After having been a branch of mathematics from early 20th century, homology and cohomology have become a key issue in computer science since the 80's to study holes of data independently of geometry. Later in the 90's, persistent homology even became a central tool for topological data analysis. Indeed, it formalizes “hole changes” along a time-varying sequence of objects and computes a notion of “hole importance” or “duration”, stable against noise.

(Co)homology computation can be carried out in several ways. Algebraic computation, as a pseudo-diagonalization (Smith Normal Form) is widely used, for instance, for persistent homology. On the other hand, effective homology provides a “categorical” approach (see [16]), while Discrete Morse Theory proposes a combinatorial approach (see [7]). In 2017, Aldo-Gonzalez Lorenzo et al. [11] introduced Homological Discrete Vector Field (which we refer to as *HDVF* in the present paper), which provides a framework in between combinatorial approaches (such as discrete Morse theory) and algebraic approaches (such as Smith normal form), encompassing these state-of-art approaches but distinct from them.

It has long been known that not all homology basis can be computed by standard algorithmic approaches (Smith Normal Form, persistent homology, tri-partitions, Discrete Morse Theory). For instance, 1-dimensional computed generators are
elementary cycles. In the present paper, we introduce a precise characterization of homology bases computed by HDVFs, which we call explicit bases. We then show (or recall) the equivalence between specific HDVFs and other algorithmic methods and thus deduce that all of them actually compute such explicit bases.

The paper is organised as follows: Section 2 introduces homology and HDVFs. Section 3 contains our main contribution; we define and discuss the notion of explicit homology bases, and prove that being explicit is equivalent to being induced by a perfect HDVF. In Section 4, we explain how this characterization applies to homology bases computed by other standard methods. In particular, we prove that tri-partitions (defined in [5]) can be seen as layers of perfect HDVFs (and vice versa) and show that a homology basis is explicit if and only if it is induced by a tri-partition. We also explain how this characterization applies to persistent homology bases.

# 2 Preliminaries

## 2.1 Homology, complexes and notations

The present work considers homology over a field $\mathcal{F}$. In the rest of the paper, we consider that $\mathcal{F} = \mathbb{Z}/2\mathbb{Z}$ but results hold for any field. In this section, we quickly introduce the main concepts of homology theory. For more information on homology theory, see [12].

A cellular complex $\mathcal{C}$ is a topological structure that consists of cells of different dimensions ($\mathcal{C}_q$ the set of cells of dimension $q$) attached together by “gluing” maps (for a more precise definition, see [12]). Depending on the type of cells, cellular complexes are categorized into a variety of combinatorial structures: simplicial complexes and delta-complexes (triangles, tetrahedra, etc.), cubical complexes (squares, cubes, etc.), or general cellular complexes. In this article, we mainly use cubical complexes, but the results apply to any cellular complex.

The definition of homology for these structures is based on the algebraic version of the concept of boundary. The boundary morphism $\partial_q$ must associate to a $q$-cell a linear combination of $(q-1)$-cells corresponding to its geometric faces, while respecting the constraint that $\partial_q \circ \partial_{q+1} = 0$. When such a definition is possible, we obtain a chain complex, an abstract algebraic structure on which we can compute homology:

**Definition 1 (chain complex [12]).** A chain complex $(K, \partial)$ is a sequence of $\mathcal{F}$-vector fields $K_q$ with linear maps $\partial_q : K_q \to K_{q-1}$ satisfying $\partial_q \circ \partial_{q+1} = 0$:

$$K_n \xrightarrow{\partial_n} \dots \xrightarrow{\partial_{q+1}} K_q \xrightarrow{\partial_q} K_{q-1} \xrightarrow{\partial_{q-1}} \dots \xrightarrow{\partial_1} K_0 \xrightarrow{\partial_0} 0$$

$K_q$ is the space of $q$-chains and $\partial_q$ is the $q$-boundary map. When $(K, \partial)$ is derived from a cellular complex $\mathcal{C}$, the $q$-chains are defined as the linear combinations of $q$-cells: $K_q = \text{Span} \mathcal{C}_q$. The boundary map $\partial$ is defined as the algebraization of the geometric boundary (see [12]).
The notion of HDVF is deeply related to the relation between cells and chains. That is why this paper only considers chain complexes that are derived from cellular complexes, which we simply refer to as *complexes*.

Given a complex $(K, \partial)$, we denote $K := \bigoplus_{q=0}^{n} K_q$ the whole chain space and $\partial := \bigoplus_{q=0}^{n} \partial_q$ the boundary operator. We also denote $\bar{K}_q := \mathscr{C}_q$ the set of $q$-cells and $\bar{K} := \bigcup_{q=0}^{n} \bar{K}_q$ the set of every cell in the associated cellular complex. We respectively call $q$-cycles and $q$-boundaries the chains in $\ker \partial_q$ and in $\im \partial_{q+1}$.

**Definition 2 (homology group [12]).** Given a complex $(K, \partial)$, its $q$-homology group is defined as the quotient space of $q$-cycles over $q$-boundaries:

$$H_q(K) = \ker \partial_q / \im \partial_{q+1}$$

As $\mathcal{F}$ is a field, there exists an integer $\beta_q$ (called the $q$-th Betti number) such that $H_q(K)$ is isomorphic to $\mathcal{F}^{\beta_q}$. Intuitively, $\beta_q$ counts the number of holes of dimension $q$ in the associated cellular complex.

We denote $[\cdot]_q^K : \ker \partial \to H_q(K)$ the map that associates a $q$-cycle to its corresponding $q$-homology class: $[x]_q^K = [y]_q^K \iff x - y \in \im \partial_{q+1}$.

**Definition 3 (homology bases and generators).** A family $(g_i)_{i \le \beta}$ of $q$-cycles is a $q$-homology basis of $(K, \partial)$ if and only if $([g_i]_q^K)_{i \le \beta}$ is a basis of $H_q(K)$. The cycles $g_i$ are called $q$-homology generators.

*Notations and conventions:* given two complexes $(K, \partial)$ and $(K', \partial')$, we will write $(K, \partial) \subseteq (K', \partial')$ if $(K, \partial)$ is a sub-complex of $(K', \partial')$ i.e. if $K \subseteq K'$ and $\partial'$ agrees with $\partial$ on $K$. For simplicity, we will often identify $\partial$ and $\partial'$. If $A$ is a set of cells, we will write $i_A$ the inclusion map from the subspace $\mathrm{Span} A$ into the full chain space $K$, $j_A$ the corresponding projection map from $K$ to $\mathrm{Span} A$ and $\mathrm{id}_A$ the identity map on $\mathrm{Span} A$. Given two sets of cells $A$ and $B$, we also denote $\partial_{AB} := j_B \circ \partial \circ i_A$ the boundary induced by $\mathrm{Span} A$ restricted to $\mathrm{Span} B$.

## 2.2 Reductions and HDVFs

Effective homology theory was introduced in the 90's in [16]. It defines the notion of *reduction* between two chain complexes (usually from a large to a small complex), which ensures that their homology groups are isomorphic. Reductions play an important role in understanding the homology of complexes.

**Definition 4 (reduction [16]).** A reduction from a complex $(K, \partial)$ to a complex $(K', d)$ is a triplet of maps $(f, g, h)$ with $f_q : K_q \to K'_q$, $g_q : K'_q \to K_q$ and $h_q : K_q \to K_{q+1}$ satisfying the following properties:

$$1. f\partial = df \quad 2. \partial g = gd \quad 3. fh, hg, hh = 0 \quad 4. fg = id_{K'} \quad 5. gf = id_K - \partial h - h \partial$$
<figure><img src="image_2.png" /></figure>

Then we have $\forall q, H_q(K) \simeq H_q(K')$.

**Definition 5 (perfect reduction [16]).** A reduction from $(K, \partial)$ to $(K', d)$ is perfect iff $d = 0$. In this case, the $q$-homology group of both complexes is isomorphic to $K'_q$. In addition, $(g_q(\gamma))_{\gamma \in \overline{K'_q}}$ is a $q$-homology basis.

Homological discrete vector fields emerged as a generalization of Discrete Morse Theory [7]. Discrete Morse theory uses acyclic graphs (called discrete gradient vector fields) defined on the cells of the complex and provides bounds on Betti numbers. However, it was shown that it fails to compute homology, for instance, for well-known contractible but not collapsible complexes such as the Bing's house. HDVFs were first developed to bypass this limitation.

**Definition 6 (homological discrete vector field [9] (HDVF)).** Given a complex $(K, \partial)$, a homological discrete vector field is a triplet $X = (P, S, C)$ with $P, S$, and $C$ forming a partition of $\bar{K}$ such that $\partial_{SP}$ is invertible. The cells of $P, S$ and $C$ are respectively called primary, secondary and critical cells. It is proved in [9] that the invertibility of $\partial_{SP}$ implies that the following $(f, g, h)$ is a well defined reduction from $(K, \partial)$ to $(\text{Span } C, d)$:

$$ g := \begin{pmatrix} C \\ \begin{pmatrix} 0 & P \\ G & S \\ id & C \end{pmatrix} \end{pmatrix} \qquad f := (P \ S \ C) \qquad h := \begin{pmatrix} P & S & C \\ 0 & 0 & 0 \\ H & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix} \qquad d := (D) C $$

with $H = (\partial_{SP})^{-1}$, $F = -\partial_{SC} \cdot H$, $G = -H \cdot \partial_{CP}$ and $D = \partial_{CC} - \partial_{SC} \cdot H \cdot \partial_{CP}$. Given an HDVF this reduction is called the associated reduction, an example is detailed in the appendix (see Example 1).

In figures, primary, secondary and critical cells are respectively colourized in green, red and blue (see Figures 1 and 3 for some examples).

Let us point out that HDVFs are singular objects, in between algebra and combinatorics, interleaving the notions of cells and chains. Indeed, HDVFs are not mere reductions as they rely on a cell partition and not on a space decomposition; but they are not purely combinatorial objects either, as HDVF validity condition is algebraic (matrix invertibility).

**Definition 7 (perfect HDVF [9]).** A HDVF is perfect if its induced reduction is perfect, i.e. if the reduced boundary $d = 0$. In this case, $\text{Span } C_q$ is isomorphic to $H_q(K)$ and $g$ maps every critical cell to its associated homology generator:
$(g_q(\gamma))_{\gamma \in C_q}$ is the q-homology basis associated to $(P, S, C)$. Similarly, $f^*$ (the transpose of $f$) maps every critical cell to its associated cohomology generator: $(f_q^*(\gamma))_{\gamma \in C_q}$ is the q-cohomology basis associated to $(P, S, C)$. See Section 5.4 for more details on duality and cohomology, and see Figure 2 for an illustration.

<figure><img src="image_3.png" /><figcaption>**Fig. 1.** Examples of three complexes with partitions of the cells between primary (in green), secondary (in red) and critical (in blue) cells. The first two partitions are HDVFs whereas the last one is not a HDVF: $\partial_{SP}$, the boundary of the secondary cells restricted to the primary cells, is not invertible because $\partial_{SP}(\sigma_1 + \sigma_2) = 0$.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>**Fig. 2.** A perfect HDVF $(P, S, C)$ with $C_1 = \{\gamma_1, \gamma_2\}$ (left), its associated 1-homology basis $(g(\gamma_1), g(\gamma_2))$ (middle) and 1-cohomology basis $(f^*(\gamma_1), f^*(\gamma_2))$ (right).</figcaption></figure>

Inspired by [5], we define two maps which we call the *canonical cycle* and *co-cycle* maps. Given a perfect HDVF $(P, S, C)$ with reduction $(f, g, h)$, they are respectively defined as follows:

$$z_q = \mathrm{id} - h_{q-1} \partial_q \qquad z^q = \mathrm{id} - h_q^* \partial_{q+1}^*$$

In particular, if $\gamma \in C_q$, the maps $z_q$ and $z^q$ coincide with the homology and cohomology generators: $z_q(\gamma) = g_q(\gamma)$ and $z^q(\gamma) = f_q^*(\gamma)$. This is a consequence of Definition 4(5.) combined with the action of $f, g$ and $h$ on critical cells (see Definition 6). Now let us state our first contribution; the following lemma will play a central role in what follows:

**Lemma 1.** In a perfect HDVF $(P, S, C)$:

$$\forall x \in K_q \qquad (x + \mathrm{Span} S) \cap \ker \partial = \{z_q(x)\} \qquad (x + \mathrm{Span} P) \cap \ker \partial^* = \{z^q(x)\}$$

In particular, if $c \in \mathrm{Span} C_q$ we have $(c + \mathrm{Span} S) \cap \ker \partial = \{g_q(c)\}$.

In addition, we get $z_q \circ i_{S_q} = 0$ and $z^q \circ i_{P_q} = 0$.

*Proof.* The proof can be found in the appendix (see Proof of Lemma 1). □
A core result of [9] is the following: in a non perfect HDVF, it is always possible to pair some critical cells (i.e. transform two critical cells to one primary and one secondary cell) in order to obtain a perfect HDVF. In particular, this proves the existence of a perfect HDVF for every cellular complex. This process is called the completion of a HDVF:

**Proposition 1 (completion of a HDVF [9]).** Given two complexes $(K, \partial) \subseteq (K', \partial')$ and a HDVF $X = (P, S, C)$ for $(K, \partial)$, there exists a perfect HDVF $X' = (P', S', C')$ for $(K', \partial')$ such that $P \subseteq P'$ and $S \subseteq S'$.

Three operations were defined in [9] to locally modify a HDVF (and hence homology an cohomology generators) by swapping the status of two set of cells. We present two of them, that are used in our proofs:

**Definition 8 (HDVF operations [9]).** Given a homological discrete vector field $X = (P, S, C)$ with induced reduction $(f, g, h)$ and $\Pi \subseteq P$, $\Sigma \subseteq S$ and $\Gamma \subseteq C$. The $W$ operation swaps secondary cells with critical cells whereas the $M$ operation swaps primary cells with critical cells:

$$W_{\Sigma}^{\Gamma} X = (P, (S \cup \Gamma) \setminus \Sigma, (C \cup \Sigma) \setminus \Gamma) \qquad M_{\Pi}^{\Gamma} X = ((P \cup \Gamma) \setminus \Pi, S, (C \cup \Pi) \setminus \Gamma)$$

$W_{\Sigma}^{\Gamma} X$ is a HDVF if and only if $j_{\Sigma} \circ g \circ i_{\Gamma}$ is invertible. $M_{\Pi}^{\Gamma} X$ is a HDVF if and only if $j_{\Gamma} \circ f \circ i_{\Pi}$ is invertible<fnref n="1" />. See Figure 3 for illustrations.

Recall that these results only hold for homology over a field, and some limitations appear when we consider homology over a ring.

<figure><img src="image_5.png" /><figcaption>**Fig. 3.** Five HDVFs on the same complex: $X_1, \dots, X_5$. $X_1$ and $X_2$ are not perfect as the number of critical $q$-cells is larger than the corresponding $q$-th Betti number. $X_2$ is a completion of $X_1$ (three pairs of secondary-primary cells were added) and $X_3$ is a completion of $X_2$. $X_3, X_4$ and $X_5$ are perfect. Using Definition 8 we can write $X_4 = M_{\{\pi\}}^{\{\gamma\}} X_3$ and $X_5 = W_{\{\sigma\}}^{\{\gamma\}} X_3$. Note that $W$ and $M$ respectively preserves the homology generators (in orange) and cohomology generators (in purple) of the cells involved in the operation.</figcaption></figure>

## 3 HDVF and Homology Bases

Given a complex, a number of homology bases can be obtained using a perfect HDVF, while others cannot (see Figure 4 for examples). This section is our main contribution. We first define and characterize bases induced by HDVFs (we call

<footnote n="1">¹ By a cardinality argument on critical cells, valid $W$ and $M$ operations transform a perfect HDVF into another perfect HDVF.</footnote>
them “explicit” bases). In Theorem 1 we show that the homology basis induced by a HDVF is explicit. Then, in Theorem 2, we derive the construction of a HDVF from an explicit homology basis. As a result, we prove that a homology basis is explicit if and only if it is induced by a HDVF.

Actually, this result goes beyond HDVFs and we show in section 4 that it extends to other standard approaches (such as persistent homology, Smith Normal Form or tri-partitions).

## 3.1 Explicit homology bases

In this section we introduce explicit homology bases and their properties. In what follows, $(K, \partial)$ is a chain complex derived from a cellular complex $\mathcal{C}$. The following results tightly intricate combinatorics (cells) and algebra (chains), which is consistent with the nature of HDVFs. To avoid confusion between chains and cells, we use lowercase Greek letters for cells and lowercase Latin letters for chains. Cells are also considered as chains, therefore we identify a cell $\tau$ with the chain consisting of one $\tau$. Given a chain $x \in K$ we denote $\bar{x}$ the set of cells that appear in it: $\bar{x} := \{\tau \in \bar{K} / \langle \tau, x \rangle \neq 0\}$ (with $\langle \cdot, \cdot \rangle$ the standard inner product on $K$). As a consequence, if $A$ is a set of cells we have $a \in \operatorname{Span} A \iff \bar{a} \subseteq A$.

Proposition 2 gives various equivalent definitions of explicit bases and Proposition 3 shows that the generators of an explicit basis are elementary. First, let us introduce the notion of sub-complex induced by a set of cells:

**Definition 9 (induced complex).** Given a set of cells $A$ in a complex $(K, \partial)$, we denote $(K(A), \partial)$ the minimum sub-chain complex containing $A$. Precisely, $K(A)_q$ is generated by the faces of dimension $q$ of cells in $A$.

Given a $q$-homology basis $(g_i)_{i \le \beta}$ for a complex $(K, \partial)$ and $J \subseteq \{1, \dots, \beta\}$ a set of indices, we denote $K^J := K(\bigcup_{i \in J} \bar{g}_i)$ the space of chains generated by the cells in the generators<fnref n="2" /> indexed by $J$. We denote $\iota_q^J$ the homology map induced by the inclusion $(K^J, \partial) \subseteq (K, \partial)$. With this notation, we also denote $(K^\beta, \partial) := (K^{\{1, \dots, \beta\}}, \partial)$ the sub-complex induced by the whole basis (see Figure 4) and $\iota_q^\beta$ its associated homology map.

**Definition 10 (Explicit homology bases).** A $q$-homology basis $(g_i)_{i \le \beta}$ for a complex $(K, \partial)$ is said to be explicit if it satisfies the following property:

$$ \forall k, \bar{g}_k \setminus \bigcup_{i \ne k} \bar{g}_i \ne \emptyset \quad \text{and} \quad \dim(H_q(K^\beta)) = \beta $$

Intuitively, a homology basis is explicit if and only if no generator is included in the others and the sub-complex induced by the generators have no more than $\beta$ holes of dimension $q$ (see Figure 4 for examples of non explicit homology bases).

<footnote n="2">² Note that $K_q^J$ is the span of a combinatorial object $(\bigcup_{i \in J} \bar{g}_i)$; it is not necessarily equal to $\operatorname{Span}((g_i)_{i \in J})$ (the “natural” algebraic object defined from generators).</footnote>
<figure><img src="image_6.png" /><figcaption>**Fig. 4.** Examples of 1-homology bases which are not explicit (right images: sub-complexes induced by the basis). By Theorem 1 they cannot be obtained from a HDVF. In $(K_1)$, $\bar{g}_3 \setminus (\bar{g}_1 \cup \bar{g}_2) = \emptyset$ so the basis is not explicit. In $(K_2)$, the complex $(K^\beta, \partial)$ induced by the basis has three 1-holes instead of two: $3 = \dim (H_1(K^\beta)) \neq \beta = 2$. Similarly, in $(K_3)$, the complex induced by the basis has five 1-holes instead of four.</figcaption></figure>

**Proposition 2 (Explicit bases equivalent definitions).** *Given a $q$-homology basis $(g_i)_{i \le \beta}$ for a complex $(K, \partial)$, the three following properties are equivalent:*

$$1. \quad \forall k, \bar{g}_k \setminus \bigcup_{i \neq k} \bar{g}_i \neq \emptyset \quad \text{and} \quad \forall J, \iota_q^J : H_q(K^J) \to H_q(K) \text{ injective of rank } |J|$$

$$2. \quad \forall J \subseteq \{1, \dots, \beta\}, \quad \ker \partial \cap K_q^J \subseteq \text{Span}((g_i)_{i \in J})$$

$$3. \quad \forall k, \bar{g}_k \setminus \bigcup_{i \neq k} \bar{g}_i \neq \emptyset \quad \text{and} \quad \dim (H_q(K^\beta)) = \beta$$

*Proof.* The proof can be found in the appendix (see Proof of Proposition 2). □

Interestingly, all these definitions combine combinatorics (cells) and algebra (chains), but cannot be fully captured by either. Even 2. of Proposition 2 entails an intersection with $K_q^J$, which definition relies on cells. This dual nature of bases computed by standard approaches is an important result of the present article. Moreover, we have the following property:

**Proposition 3.** *The generators of an explicit homology basis are elementary. A cycle is said to be elementary if it is not composed of smaller (non-zero) cycles.*

*Proof.* Let $(g_i)_{i \le \beta}$ be an explicit $q$-homology basis of $(K, \partial)$ and $a, b$ be cycles such that $\bar{a} \sqcup \bar{b} = \bar{g}_k$ (and so $a + b = g_k$). Denote $J := \{k\}$. We get that $a$ and $b$ are in $\ker \partial \cap K_q^J$ so by Proposition 2(2) they are in $\text{Span}(g_k) = \{0, g_k\}$. Hence, either $a$ or $b$ is 0, otherwise we would have $g_k = g_k + g_k = 0$. □

## 3.2 Characterization of HDVF homology bases

We now prove that the homology bases obtained from HDVFs are explicit.

**Theorem 1.** Let $X = (P, S, C)$ be a perfect HDVF for $(K, \partial)$ with reduction $(f, g, h)$. Then, for all $q$, its associated $q$-homology basis $(g_q(\gamma))_{\gamma \in C_q}$ is explicit.

*Proof.* This proof uses the characterization 2. of Proposition 2 and can be found in the appendix (see Proof of Theorem 1). □
As stated by the following theorem, the converse also holds:

**Theorem 2.** Given $(g_i)_{i \le \beta_q}$ an explicit $q$-homology basis for $(K, \partial)$, there exists a perfect HDVF $X = (P, S, C)$ for $(K, \partial)$ with reduction $(f, g, h)$ such that $(g_q(\gamma))_{\gamma \in C_q} = (g_i)_{i \le \beta_q}$.

We prove Theorem 2 by building a perfect HDVF from an explicit basis. To do so, we need the following lemmas about existence and completion of HDVFs. Firstly, given $(K, \partial) \subseteq (K', \partial)$, it is possible to complete a perfect HDVF for $(K, \partial)$ to a perfect HDVF for $(K', \partial)$ while preserving some critical cells (specifically the ones associated with holes of $(K, \partial)$ that were not filled in $(K', \partial)):

**Lemma 2 (critical preservation during completion).** Let $(K, \partial) \subseteq (K', \partial)$ and let $X = (P, S, C)$ be a perfect HDVF for $(K, \partial)$ with reduction $(f, g, h)$.

Suppose that there is $C^* \subseteq C_q$ such that $([g_q(\gamma)]^{K'})_{\gamma \in C^*}$ is linearly independent in $H_q(K')$. Then there exists $X' = (P', S', C')$ a perfect HDVF for $(K', \partial)$ such that $P \subseteq P'$, $S \subseteq S'$ and $C^* \subseteq C'$.

*Proof.* The proof is technical and can be found in the appendix (see Proof of Lemma 2). □

Secondly, the critical cells preserved in a completion process keep their associated homology generators:

**Lemma 3 (generator preservation during completion).** Suppose $(K, \partial) \subseteq (K', \partial)$ and let $X = (P, S, C)$ and $X' = (P', S', C')$ be perfect HDVFs for $(K, \partial)$ and $(K', \partial)$ such that $S \subseteq S'$. Then $\forall x \in K_q$, $z_q(x) = z'_q(x)$. In particular, $\forall \gamma \in C \cap C'$, $g(\gamma) = g'(\gamma)$.

*Proof.* Let $x \in K \subseteq K'$. $X$ and $X'$ are perfect so Lemma 1 gives:

$$z_q(x) \in \ker \partial \cap (x + \operatorname{Span} S) \subseteq \ker \partial \cap (x + \operatorname{Span} S') = \{z'_q(x)\} \quad \square$$

Finally, given an explicit homology basis, it is possible to build a perfect HDVF $X^\beta$ for the sub-complex $(K^\beta, \partial)$ induced by the basis, such that $X^\beta$ is still associated to the same basis:

**Lemma 4 (HDVF of the basis complex).** Let $(g_i)_{i \le \beta}$ be an explicit $q$-homology basis for $(K, \partial)$. Then there exists $X^\beta = (P^\beta, S^\beta, C^\beta)$ a perfect HDVF for $(K^\beta, \partial)$ with reduction $(f^\beta, g^\beta, h^\beta)$ such that $(g_q^\beta(\gamma))_{\gamma \in C_q^\beta} = (g_i)_{i \le \beta}$.

*Proof.* The construction of this HDVF is done by induction on $k \in \{0, \dots, \beta\}$ and can be found in the appendix (see Proof of Lemma 4). □

The full proof of Theorem 2 is technical and can be found in appendix (see Proof of Theorem 2). However, once previous lemmas are known, it becomes intuitive and Figure 5 illustrates it.

As a result, Theorems 1 and 2 imply that a homology basis is explicit if and only if it is induced by a perfect HDVF. Note that the proof of Theorem 2 provides an algorithm to build a perfect HDVF given an explicit homology basis.
<figure><img src="image_7.png" /><figcaption>**Fig. 5.** Illustration of the constructions involved in the proof of Theorem 2.
The first row represents four generators forming an explicit 1-homology basis of a complex ($K, \partial$). The second row shows steps of the proof. It starts (a) with ($K(\bigcup \bar{g}_i)$, $\partial$) the complex induced by this basis (which has four 1-holes as the basis is explicit). (b) represents a choice of cells $\gamma_k$ that are respectively in $\bar{g}_k \setminus \bigcup_{i \neq k} \bar{g}_i$ (which is non-empty as the basis is explicit). (c) is the perfect HDVF $X^\beta$ obtained with Lemma 4. By construction, we get $g^\beta(\gamma_i) = g_i$. Finally, (d) is $X$ the perfect HDVF for $(K, \partial)$ obtained by completing $X^\beta$ using Lemma 2.
The 1-homology basis induced by $X$ is $(g_1, g_2, g_3, g_4)$ by construction using Lemma 3.</figcaption></figure>

# 4 Characterization of Homology Bases Obtained by Other Methods

In this section we discuss how the characterization of Section 3 transfers to bases computed by other methods.

First, it is important to distinguish computational homology approaches (such as HDVFs, but also Smith Normal Form, persistent homology and tri-partitions) and heuristics for computing small homology generators (the question of computing minimal ones is NP-difficult, see for instance [1]). Methods related to this later question usually combine former approaches together with solvers and heuristics to minimize generators, hence homology bases may not be explicit (see for instance Figure 4, $K_3$). Now, the remainder of this section examines the links between HDVFs and other approaches and deduces properties on the bases they compute.

*Discrete Morse theory.* It has been proven in [11] that HDVFs generalize Discrete Morse Theory, in particular a *discrete gradient vector field* is a HDVF. Therefore, Theorem 1 naturally applies, and Discrete Morse Theory computes only explicit bases.

*Smith Normal Form (SNF).* Homology is commonly computed by reducing the boundary matrix of a complex to the Smith-Normal-Form (SNF). It has been shown in [11] that a HDVF can emulate this SNF computation. Precisely, pairing secondary and primary cells is equivalent to performing a boundary
matrix reduction step. Some works, such as [14], deduce homology bases from the
SNF of the boundary matrix (or a modified version of it). Therefore, Theorem 1
applies, and such methods (when homology is computed over a field) actually
compute explicit bases.

**4.1 Characterization of homology bases computed by tri-partitions**

In a recent paper [5], the authors defined the notion of tri-partition. A tri-
partition is a combinatorial object that provides homological information using
the notion of tree and cotree:

**Definition 11 (trees and cotrees).** A q-tree is a set of q-cells A that does not generate non-zero cycles, i.e $\text{Span } A \cap \ker \partial = \{0\}$. Similarly, a q-cotree is a set of q-cells A that does not generate non-zero cocycles, i.e $\text{Span } A \cap \ker \partial^* = \{0\}$. A q-tree A (resp. q-cotree) is maximal if there is no other q-tree (resp. q-cotree) A' such that $A \subset A'$.

**Definition 12 (tri-partition [5]).** Given a complex $(K, \partial)$, a tri-partition of dimension $q$ is a triplet $(A^q, A_q, E_q)$ forming a partition of the $q$-cells of $K$ such that $A^q$ is a maximal $q$-cotree, $A_q$ is a maximal $q$-tree and $|E_q| = \beta_q$.

It has been proved that a complex always admits tri-partitions for every
dimension $q$ (see Theorem 3.1 in [5]). Tri-partitions also provide homology and
cohomology bases.

**Definition 13 (canonical cycle [5]).** Let $(A^q, A_q, E_q)$ be a tri-partition for a complex $(K, \partial)$. If $\tau \in A^q \sqcup E_q$, there is a unique $q$-cycle $z_q(\tau)$ in $\tau + \text{Span } A_q$. By duality, if $\tau \in A_q \sqcup E_q$, there is a unique $q$-cocycle $z^q(\tau)$ in $\tau + \text{Span } A^q$.

It was proved that $(z_q(\epsilon))_{\epsilon \in E_q}$ is a $q$-homology basis and $(z^q(\epsilon))_{\epsilon \in E_q}$ is a $q$-cohomology basis (see Theorem 4.3 in [5]). Proposition 4 states that tri-partitions are closely related to perfect HDVFs. Precisely, they can be viewed as “dimensional layers” of perfect HDVF. Conversely, a perfect HDVF can be viewed as a “stack” of tri-partitions.

**Proposition 4.** If $(P, S, C)$ is a perfect HDVF for $K$, then $(P_q, S_q, C_q)$ is a $q$-tri-partition for every dimension $q$. Conversely, if for every $q$, $(A^q, A_q, E_q)$ is a $q$-tri-partition of $K$, then $(\bigcup A^q, \bigcup A_q, \bigcup E_q)$ is a perfect HDVF for $K$.

*Proof.* The proof can be found in the appendix (see Proof of Proposition 4). □

This proposition underlines the fact that perfect HDVFs and tri-partitions
represent the same object, but the former uses a “vertical” point of view whereas
the latter uses a “horizontal” point of view. As a consequence, Definition 13 coincides with the canonical (co)cycle maps defined for HDVF. This is a consequence of Proposition 4 and Lemma 1. Finally, the characterization from Section 3 and the link between tri-partitions and HDVF implies the following result:

**Theorem 3.** A $q$-homology basis is explicit iff it is induced by a $q$-tri-partition.
## 4.2 Characterization of persistent homology bases

Persistent homology studies changes in the homology of a filtration. Formally, a filtration is a growing sequence of complexes $K^0 \subseteq K^1 \subseteq \dots \subseteq K^N$. The inclu- sions between complexes induces maps between the homology groups associated with the complexes. For each dimension $q$ we have:

$$H_q(K^0) \xrightarrow{\iota_q^0} H_q(K^1) \xrightarrow{\iota_q^1} \dots \xrightarrow{\iota_q^{N-1}} H_q(K^N)$$

Given $i < j$, the image of $\iota_q^i \circ \dots \circ \iota_q^{j-1}$ represents the $q$-homology classes of $K^i$ that remain in the filtration until $K^j$. Intuitively, it represents the $q$-holes of $K^i$ that were not filled between $K^i$ and $K^j$. It is then possible to define a *birth* and a *death* index for each homology class that appears in the filtration. Thus, every homology class in the filtration is associated with a *lifetime* interval $[i, j]$ ($j$ eventually equals to $\infty$ if the homology class never dies). These information can be summed up in a *persistence diagram*, which can be defined as a multiset over $\mathbb{R}^2$. See [4,19] for a detailed explanation of persistent homology.

It has been shown in [11] that persistent homology can be computed by tweaking the algorithm that computes a perfect HDVF. Given a filtration $\emptyset = K^0 \subseteq \dots \subseteq K^N = K$, the method starts with an empty HDVF and completes it into a perfect HDVF $X^i = (P^i, S^i, C^i)$ for $(K^i, \partial)$ at the $i$-th iteration. Precisely, when a cell $\tau_i$ is added to the filtration at step $i$, it is paired (as a secondary-primary pair) with the youngest possible cell $\tau_j$ already present. If no such $\tau_j$ exists, $\tau_i$ is left as a critical cell. This algorithm actually reproduces how positive-negative pairs are chosen in [3]. Its complexity is the same as for computing a perfect HDVF – at most cubic in the number of cells.

This method not only computes persistence intervals, but also HDVFs and reductions at each step of the filtration. In particular, it computes a $q$-homology basis for each $(K^i, \partial)$, which is called the *i-th persistent $q$-homology basis* and whose elements are called *persistent $q$-homology generators*. Formally, if $(f^i, g^i, h^i)$ is the reduction associated to $X^i$, the $i$-th persistent $q$-homology basis is given by $(g_q^i(\gamma))_{\gamma \in C_q^i}$. Note that it is a *persistent basis* in the sense of [2,18,13].

A direct consequence of Lemma 3 is that persistent generators are preserved during the lifetime of the homology class they represent. Equivalently, for all $\gamma \in C_q^i$, we have $z_q(\gamma) = g_q^i(\gamma)$, where $z_q$ is the canonical cycle map of the final HDVF $X^N$. Note that in [8], the authors prove similar results and define a similar “tweaking” of the algorithm computing *AT-models* (i.e. perfect reductions) to emulate persistent homology.

As a result, every point $(i, j)$ in the persistence diagram can be associated to a unique cell $\gamma$ (which was critical between step $i$ and $j$) and to a unique persistent homology generator $z_q(\gamma)$. Theorem 1 implies that the persistent homology bases of a filtration are explicit. An illustration of persistent homology bases computed by HDVF is given in Figure 6. Note that other works such as [15,17] deduce persistent homology bases from boundary matrix reductions. Again, as boundary matrix reductions can be reproduced by a HDVF completion, the persistent homology bases computed by these methods are explicit.
<figure><img src="image_8.png" /><figcaption>**Fig. 6.** Example of persistent homology computed by HDVF. First row: the filtration $K_0 \subseteq \dots \subseteq K_4$ and its HDVFs $X^0, \dots, X^4$. Second row: the $i$th-persistent homology bases for $i = 0, \dots, 4$ (bases of dimension 0 and 1 are represented). On the right: the persistence diagram of the filtration, each point $(i, j)$ corresponds to a homology class whose lifetime is $[i, j]$, its color matches the color of the corresponding persistent generator.</figcaption></figure>

# 5 Conclusion and Future Works

This paper introduced a characterization of the homology bases computed by standard computational homology methods. We first proved that a class of homology bases called explicit is equivalent to being induced by a HDVF. We then showed how this result applies to other methods, in particular to tri-partitions (which we proved are closely related to perfect HDVFs), Discrete Morse Theory and boundary matrix reduction methods (and thus standard persistent homology algorithms). Note that a similar result (yet less intuitive) holds for cohomology bases (see Section 5.4 in the appendix).

This work suggests that the HDVF framework provides a way to study computational homology methods. In particular, these results might give some insights on the isomorphisms computed in [10] and on the hole closing and opening operations defined in [6]. In addition, they also raise computational homology questions. For instance, can the set of explicit bases over a complex give information about the topology? Can we use HDVF operations to adapt a perfect HDVF to a given explicit basis? Are minimal explicit bases easier to compute than standard minimal homology bases?

Another open area is the study of HDVFs when homology is computed over a ring. In this case, the existence of a perfect reduction is not guaranteed due to the presence of torsion. However, it might be possible to define a reduction that is somehow “optimal” and investigate the HDVFs related to it.

**Disclosure of Interests.** On behalf of all authors, the corresponding author declares that there is no conflict of interest.
References

1. Dey, T., Hou, T., Mandal, S.: Computing Minimal Persistent Cycles: Polynomial and Hard Cases, pp. 2587–2606 (01 2020). https://doi.org/10.1137/1.9781611975994.158

2. Dey, T.K., Hou, T., Mandal, S.: Persistent 1-cycles: Definition, computation, and its application. In: Marfil, R., Calderón, M., Díaz del Río, F., Real, P., Bandera, A. (eds.) Computational Topology in Image Context. pp. 123–136. Springer International Publishing, Cham (2019)

3. Edelsbrunner, Letscher, Zomorodian: Topological persistence and simplification. Discrete Comput. Geom. 28(4), 511–533 (Nov 2002). https://doi.org/10.1007/s00454-002-2885-2, https://doi.org/10.1007/s00454-002-2885-2

4. Edelsbrunner, H., Harer, J.: Persistent homology—a survey. Discrete and Computational Geometry - DCG 453 (01 2008). https://doi.org/10.1090/conm/453/08802

5. Edelsbrunner, H., Ölsböck, K.: Tri-partitions and bases of an ordered complex. Discrete & Computational Geometry 64, 759 – 775 (2020), https://apisemanticscholar.org/CorpusID:210173079

6. Edelsbrunner, H., Ölsböck, K.: Holes and dependences in an ordered complex. Computer Aided Geometric Design 73, 1–15 (2019). https://doi.org/https://doi.org/10.1016/j.cagd.2019.06.003, https://www.sciencedirect.com/science/article/pii/S0167839619300561

7. Forman, R.: Morse theory for cell complexes. Advances in Mathematics 134(1), 90–145 (1998). https://doi.org/https://doi.org/10.1006/aima.1997.1650

8. Gonzalez-Diaz, R., Ion, A., Jiménez, M., Poyatos, R.: Incremental-decremental algorithm for computing at-models and persistent homology. In: Computer Analysis of Images and Patterns. pp. 286–293. Springer Berlin Heidelberg, Berlin, Heidelberg (01 2011). https://doi.org/10.1007/978-3-642-23672-3_35

9. Gonzalez-Lorenzo, A.: Computational Homology Applied to Discrete Objects. Theories, Aix-Marseille Université ; Universidad de Sevilla (Nov 2016), https://hal.archives-ouvertes.fr/tel-01477399

10. Gonzalez-Lorenzo, A., Bac, A., Gazull, Y.S.: A constructive approach of Alexander duality. Journal of Applied and Computational Topology 9(2) (12 2024). https://doi.org/10.1007/s41468-024-00198-1, https://doi.org/10.1007/s41468-024-00198-1

11. Gonzalez-Lorenzo, A., Bac, A., Mari, J.L., Real, P.: Allowing cycles in discrete Morse theory. Topology and its Applications 228, 1–35 (2017). https://doi.org/https://doi.org/10.1016/j.topol.2017.05.008

12. Hatcher, A., Press, C.U., of Mathematics, C.U.D.: Algebraic Topology. Algebraic Topology, Cambridge University Press (2002), https://books.google.fr/books?id=BjKs86kosqgC

13. Obayashi, I.: Volume-optimal cycle: Tightest representative cycle of a generator in persistent homology. SIAM Journal on Applied Algebra and Geometry 2 (12 2017). https://doi.org/10.1137/17M1159439

14. Peltier, S., Alayrangues, S., Fuchs, L., Lachaud, J.O.: Computation of homology groups and generators. Computers & Graphics 30(1), 62–69 (2006). https://doi.org/https://doi.org/10.1016/j.cag.2005.10.011, https://www.sciencedirect.com/science/article/pii/S0097849305002104

15. Pham, T., Wagner, H.: Computing representatives of persistent homology generators with a double twist (2024), https://arxiv.org/abs/2403.04100
16. Rubio, J., Sergeraert, F.: 1. Homologie effective. Cours de l'Institut Fourier 20(17), 15-38 (1986), http://eudml.org/doc/272555

17. Čufar, M., Virk, v.: Fast computation of persistent homology representatives with involuted persistent homology. Foundations of Data Science 5(4), 466-479 (2023). https://doi.org/10.3934/fods.2023006, http://dx.doi.org/10.3934/fods.2023006

18. Wu, P., Chen, C., Wang, Y., Zhang, S., Yuan, C., Qian, Z., Metaxas, D., Axel, L.: Optimal topological cycles and their application in cardiac trabeculae restoration. pp. 80-92 (05 2017). https://doi.org/10.1007/978-3-319-59050-9_7

19. Zomorodian, A., Carlsson, G.: Computing persistent homology. Discrete and Computational Geometry 33, 249-274 (02 2005). https://doi.org/10.1007/s00454-004-1146-y

# Appendix

## 5.1 Example and Proofs of Section 2

*Example 1 (reduction of a HDVF).* Let us state Definition 6 again: a HDVF $(P, S, C)$ induces a reduction $(f, g, h)$ from $(K, \partial)$ to $(\mathrm{Span}C, d)$ with:

$$ g := \begin{pmatrix} C \\ G \\ id \end{pmatrix}^{P} \qquad f := (F \ 0 \ id)_{C} \qquad h := \begin{pmatrix} P & S & C \\ 0 & 0 & 0 \\ H & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix}^{P} \qquad d := (D)_{C} $$

where $H = (\partial_{SP})^{-1}$, $F = -\partial_{SC} \cdot H$, $G = -H \cdot \partial_{CP}$ and $D = \partial_{CC} - \partial_{SC} \cdot H \cdot \partial_{CP}$

<figure><img src="image_9.png" /><figcaption>**Fig. 7.** An example of a HDVF $(P, S, C)$ on a complex $(K, \partial)$ (on the left) and a representation of the reduced complex $(\mathrm{Span}C, d)$ induced by the reduction of this HDVF (on the right).</figcaption></figure>

In the example of Figure 7, Definition 6 implies the following matrices:

$$ \begin{array}{ccc} \partial_1 = \begin{pmatrix} a & b & c & d & e \\ 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 \end{pmatrix} & \partial_2 = \begin{pmatrix} \phi \\ 1 \\ 1 \\ 1 \\ 0 \\ 0 \end{pmatrix} & H_1 = (1) \phi \\ H_0 = \begin{pmatrix} B & C \\ 1 & 0 \\ 0 & 1 \end{pmatrix} & & \end{array} $$
A D

$$d_1 = D_1 = \partial_{C_1 C_0} - \partial_{S_1 C_0} \cdot H_0 \cdot \partial_{C_1 P_0}$$

$$d_2 = 0$$

$$d_0 = (0 \ 0)$$

$$= \begin{pmatrix} 0 & 0 \\ 1 & 1 \end{pmatrix} - \begin{pmatrix} 1 & 1 \\ 0 & 0 \end{pmatrix} \cdot \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \cdot \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$$

d e

$$= \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix} \begin{matrix} \text{A} \\ \text{D} \end{matrix}$$

As reductions preserve homology, the homology of $(K, \partial)$ is the same as the homology of $(\operatorname{Span} C, d)$. In particular:

$$H_1(K) \approx \frac{\ker d_1}{\operatorname{im} d_2} = \frac{\operatorname{Span}\{d+e\}}{\{0\}} = \operatorname{Span}\{d+e\} \approx \mathbb{Z}/2\mathbb{Z}$$

**Proof of Lemma 1.** We only prove the first equation as the second equation is the same result stated on the dual complex (see Definition 14 and Proposition 5 for more details on this duality).

First, $z_q(x) \in x + \operatorname{Span} S$ because $z_q(x) = x - h\partial(x)$ and $\operatorname{im} h \subseteq \operatorname{Span} S$. Moreover, $z_q(x) \in \ker \partial$ because $z_q(x) = gf(x) + \partial h(x)$ which is a sum of cycles because the HDVF is perfect.

Second, suppose $x + s \in (x + \operatorname{Span} S) \cap \ker \partial$. This implies that $y := z_q(x) - (x + s)$ is a cycle in $\operatorname{Span} S$. With the reduction properties we have $y = gf(y) + \partial h(y) + h\partial(y) = 0$ (because $h \circ i_S = 0$, $\partial(y) = 0$ and $f \circ i_S = 0$, see Definition 4). Hence, $x + s = z_q(x)$. $\square$

## 5.2 Proofs of Section 3

**Proof of Proposition 2.** For simplicity we write $[\cdot]$ instead of $[\cdot]_q^K$ and $[\cdot]_q^J$ instead of $[\cdot]_q^{K^J}$. Firstly, we state some results about the $q$-homology basis $(g_i)_{i \le \beta}$:

- $([g_i])_{i \le \beta}$ is a basis of $H_q(K)$ (by Definition 3).

- $\iota_q^J([x]^J) = [x]$ for every $x$ in $K^J$ (by functoriality of the homology functor).

- For every $J$, $([g_i]^J)_{i \le J}$ is linearly independent. Indeed, $\sum \epsilon_i [g_i]^J = 0$ implies $\sum \epsilon_i [g_i] = 0$, so every $\epsilon_i$ is 0 because $([g_i])_{i \le \beta}$ is a basis.

1. $\implies$ 2.: Let $x \in \ker \partial \cap K_q^J$, let us show that it is in $\operatorname{Span} ((g_i)_{i \in J})$

$\iota_q^J$ has rank $|J|$ and $([g_i])_{i \in J} = (\iota_q^J([g_i]^J))_{i \le J}$ is a linearly independent set of cardinal $|J|$ in $\operatorname{im} \iota_q^J$, therefore $([g_i])_{i \le J}$ is a basis of $\operatorname{im} \iota_q^J$. Hence, there exist $(\epsilon_i)_{i \in J}$ coefficients such that:

$$\iota_q([x]^J) = \sum_{i \in J} \epsilon_i [g_i] = \iota_q \left( \left[ \sum_{i \in J} \epsilon_i g_i \right]^J \right)$$

By injectivity of $\iota_q$, we have $[x]^J = [\sum_{i \in J} \epsilon_i g_i]^J$, therefore there exists a $(q+1)$-chain $y \in K^J$ such that $x = \sum_{i \in J} \epsilon_i g_i + \partial y$. However, the maximal dimension of cells in $K^J$ is $q$, so $y = 0$. As a result, $x = \sum_{i \in J} \epsilon_i g_i \in \operatorname{Span} ((g_i)_{i \in J})$.
2. $\implies$ 3.: Firstly, by contradiction suppose that $\overline{g_k} \setminus \bigcup_{i \neq k} \overline{g_i} = \emptyset$.

Let $J := \{1, \dots, \beta\} \setminus \{k\}$. We then have $\overline{g_k} \subseteq \bigcup_{i \in J} \overline{g_i} = \overline{K^J}$, therefore $g_k \in K^J$. In addition, $g_k$ is a $q$-cycle (because it is a $q$-generator). By assumption, we obtain that $g_k \in \text{Span}((g_i)_{i \in J})$ which contradicts the fact that $([g_i]^\beta)_{i \le \beta}$ is linearly independent. As a consequence $\overline{g_k} \setminus \bigcup_{i \neq k} \overline{g_i} \neq \emptyset$.

Then, $([g_i]^\beta)_{i \le \beta}$ is linearly independent, let us show it is a basis for $H_q(K^\beta)$. Let $[x]^\beta \in H_q(K^\beta)$. We have that $x$ is a $q$-cycle in $K^\beta$. By assumption we get that $x \in \text{Span}((g_i)_{i \le \beta})$, therefore $[x]^\beta \in \text{Span}((\overline{[g_i]}^\beta)_{i \le \beta})$. Hence, $([g_i]^\beta)_{i \le \beta}$ generates $H_q(K^\beta)$ and is linearly independent so it is a basis for $H_q(K^\beta)$. As a result $\text{dim}(H_q(K^\beta)) = \beta$.

3. $\implies$ 1.: Given $J$, $([g_i]^J)_{i \in J}$ is linearly independent, let us show that it is a basis for $H_q(K^J)$.

Consider a $q$-cycle $x$ in $K^J$ and its associated homology class $[x]^J \in H_q(K^J)$. Let $\iota_q^{J \to \beta} : H_q(K^J) \to H_q(K^\beta)$ be the homology morphism induced by the inclusion $(K^J, \partial) \subseteq (K^\beta, \partial)$. We have $\iota_q^{J \to \beta}([x]^J) = [x]^\beta$.

$H_q(K^\beta)$ has dimension $\beta$ by assumption. $([g_i]^\beta)_{i \le \beta}$ is a linearly independent set of $H_q(K^\beta)$ with cardinal $\beta$ so it is a basis of it.

Hence, there exist $(\epsilon_i)_{i \in J}$ coefficients such that $[x]^\beta = \sum_{i \le \beta} \epsilon_i [g_i]^\beta$. Thus, there exists a $(q+1)$-chain $y \in K^\beta$ such that $x = \sum_{i \le \beta} \epsilon_i g_i + \partial y$. As $K_{q+1}^\beta = \{0\}$ we obtain $y = 0$ and $x = \sum_{i \le \beta} \epsilon_i g_i$.

By contradiction: suppose that there is $j \notin J$ such that $\epsilon_j \neq 0$. Then, as $\overline{g_j} \setminus \bigcup_{i \neq j} \overline{g_i} \neq \emptyset$, let $\gamma$ be a cell in $\overline{g_j}$ that is not in the other $\overline{g_i}$. We have:

$$ \langle x, \gamma \rangle = \sum_{i \le \beta} \epsilon_i \langle g_i, \gamma \rangle = \epsilon_j \langle g_j, \gamma \rangle \neq 0 \quad \text{because } \gamma \in \overline{g_j} \text{ and } \epsilon_j \neq 0 $$

Hence, $\gamma \in \bar{x}$. However, $x \in K^J$ so $\bar{x} \subseteq \overline{K^J} = \bigcup_{i \in J} \overline{g_i}$ but $\gamma$ is not in any $\overline{g_i}$ with $i \in J$ by definition. As a consequence, $\forall j \notin J, \epsilon_j = 0$.

This implies that $x = \sum_{i \in J} \epsilon_i g_i$ and $[x]^J \in \text{Span}((\overline{[g_i]}^J)_{i \in J})$. As a result $([g_i]^J)_{i \in J}$ is a basis for $H_q(K^J)$ with cardinal $|J|$. Therefore, as $([g_i])_{i \in J} = (\iota_q^J(\overline{[g_i]}^J))_{i \in J}$ is a linearly independent family of $\text{im} \, \iota_q^J$ we obtain that $\iota_q^J$ is an injective map with $\text{rank} \, |J|$. $\square$

**Proof of Theorem 1.** In this proof, we denote $P^\perp := S \sqcup C$. Denote $C_q = \{\gamma_1, \dots, \gamma_\beta\}$. For this proof, we use the second characterization of an explicit homology basis in Proposition 2. Let $J \subseteq \{1, \dots, \beta\}$ and $K^J := K(\bigcup_{i \in J} \overline{g(\gamma_i)})$. Let $x \in \text{ker} \, \partial \cap K_q^J$, we will show that $x \in \text{Span}(g(\gamma_i))_{i \in J}$.

As $\text{im} \, g \subseteq \text{Span} \, P^\perp$ (see Definition 6), we have that $\bar{x} \subseteq \overline{K_q^J} = \bigcup_{i \in J} \overline{g(\gamma_i)} \subseteq P^\perp$. Hence $x \in \text{Span} \, P^\perp$ and there exists $s \in \text{Span} \, S$ and $c \in \text{Span} \, C$ such that $x = c + s$ and $\bar{x} = \bar{c} \sqcup \bar{s}$.

By Lemma 1 we have that for all $i$, $(g(\gamma_i) - \gamma_i) \in \text{Span} \, S$ so $\overline{g(\gamma_i)} \cap C = \{\gamma_i\}$. This implies:

$$ \overline{K_q^J} \cap C = \bigcup_{i \in J} \overline{g(\gamma_i)} \cap C = \bigcup_{i \in J} \{\gamma_i\} $$
As $x \in K_q^J$, we obtain $\bar{x} \cap C = \bar{c} \subseteq \{\gamma_i, i \in J\}$. This implies that there exist $(\epsilon_i)_{i \in J}$ elements of the field $\mathcal{F}$ such that $c = \sum_{i \in J} \epsilon_i \gamma_i$. Thus with reduction properties (see Definition 4):

$$
\begin{align*}
x &= gf(x) + \partial h(x) + h \partial(x) \\
&= gf(c+s) && \text{as } h \circ i_{P^{\perp}} = 0 \text{ and } x \in \text{Span } P^{\perp} \text{ and } x \in \ker \partial \\
&= g(c) && \text{as } f \circ i_C = id_C \text{ and } f \circ i_S = 0 \\
&= \sum_{i \in J} \epsilon_i g(\gamma_i) && \text{As a result } x \in \text{Span } (g(\gamma_i))_{i \in J}.
\end{align*}
$$

□

**Proof of Lemma 2.** Using the completion Proposition 1, there exists $X'' = (P'', S'', C'')$ a perfect HDVF for $(K', \partial)$ with reduction $(f'', g'', h'')$ such that $P \subseteq P''$ and $S \subseteq S''$, but a priori $C^*$ is not included in $C''$.

The idea of the proof is to first show the injectivity of $j_{C''\setminus C^*} \circ f'' \circ i_{P''\cap C^*}$ and then use it to find a set $\Gamma \subseteq C''\setminus C^*$ such that $X' := M_{P''\cap C^*}^{\Gamma} X''$ is a valid operation.

1. First, we show that $f'' \circ i_{C^*}$ is injective:

Suppose that there is $c \in \operatorname{Span} C^*$ such that $f''(c) = 0$. By Lemma 1, we write $g(c) = c+s$ with $s \in \operatorname{Span} S \subseteq \operatorname{Span} S''$. With Definition 4-5. we have:

$$
\begin{align*}
g(c) &= g''f''g(c) + \partial h''g(c) + h''\partial g(c) \\
&= g''f''(c+s) + \partial h''g(c) && \text{because } \partial g = 0 \\
&= g''f''(c) + g''f''(s) + \partial h''g(c) \\
&= g''f''(c) + \partial h''g(c) && \text{as } f'' \circ i_{S''} = 0 \text{ and } s \in \operatorname{Span} S'' \\
&= \partial h''g(c) \in \partial(K') && \text{because } f''(c) = 0
\end{align*}
$$

Hence, $g(c)$ is a boundary in $K'$ so $[g(c)]^{K'} = 0$. By assumption, $([g_q(\gamma)]^{K'})_{\gamma \in C^*}$ is linearly independent, and $c \in \operatorname{Span} C^*$, therefore we obtain that $c = 0$.

2. Second, we show the injectivity of $j_{C''\setminus C^*} \circ f'' \circ i_{P''\cap C^*}$:

Suppose that there is $c \in \operatorname{Span}(P'' \cap C^*)$ such that $j_{C''\setminus C^*} f''(c) = 0$. As $\operatorname{im} f'' \subseteq \operatorname{Span} C''$, this implies that $f''(c) \in \operatorname{Span}(C'' \cap C^*)$.

As $f'' \circ i_{C''} = id_{C''}$ (see Definition 6), we obtain that $f''(f''(c)) = f''(c)$.

As a consequence, we have $f''(c - f''(c)) = 0$ which implies $c = f''(c)$ by injectivity of $f'' \circ i_{C^*}$ (1). However, we have $c \in \operatorname{Span}(P'' \cap C^*)$ and $f''(c) \in \operatorname{Span}(C'' \cap C^*)$, so $c = 0$ (because $P'' \cap C'' = \emptyset$).

3. Third, we show that $C^* = (P'' \cap C^*) \sqcup (C'' \cap C^*)$:

By contradiction suppose $\gamma \in S'' \cap C^*$. Lemma 1 implies that $g(\gamma) \in \gamma + \operatorname{Span} S \subseteq \gamma + \operatorname{Span} S''$. Moreover, $g(\gamma)$ is a cycle (because $X$ is perfect) so we have $g(\gamma) \in \ker \partial \cap (\gamma + \operatorname{Span} S'')$. Therefore, $g(\gamma) = z''_q(\gamma)$ by Lemma 1. In addition, we have $z''_q \circ i_{S''} = 0$ (by Lemma 1 again) and $\gamma \in S''$ so $g(\gamma) = 0$, which is not possible by injectivity of $g$. As a result, $S'' \cap C^* = \emptyset$ and we obtain $C^* = (C^* \cap P'') \sqcup (C^* \cap C'')$ because $(P'', S'', C'')$ is a partition.
Finally, we can define the suited HDVF $X'$:

As $j_{C''\setminus C^*} \circ f'' \circ i_{P''\cap C^*}$ is injective (2.), it admits a invertible sub-matrix of maximal rank. Hence, there exists a subset $\Gamma \subseteq C''\setminus C^*$ such that $j_\Gamma \circ j_{C''\setminus C^*} f'' i_{P''\cap C^*}$ is an invertible square matrix. Therefore, $j_\Gamma f'' i_{P''\cap C^*}$ is invertible, so by Definition 8 $M_{P''\cap C^*}^\Gamma$ is a valid operation for $X''$.

Let $X' = (P', S', C') := M_{P''\cap C^*}^\Gamma X''$, we have:

$$P' = (P'' \sqcup \Gamma) \setminus (P'' \cap C^*) \quad S' = S'' \quad C' = (C'' \sqcup (P'' \cap C^*)) \setminus \Gamma$$

$$- P \subseteq P' \text{ because } P \subseteq P'' \text{ and } P \cap (P'' \cap C^*) = \emptyset.$$

$$- S \subseteq S' \text{ because } S \subseteq S''.$$

$$- C^* \subseteq C' \text{ because } C^* = (C'' \cap C^*) \sqcup (P'' \cap C^*) \quad (3.) \text{ and } \Gamma \cap C^* = \emptyset.$$

□

**Proof of Lemma 4.** For simplicity we will write $K^k$ instead of $K^{\{1...k\}}$ and $[\cdot]^k$ instead of $[\cdot]_{q}^{K^k}$. We will also write $\iota^k$ instead of $\iota_q^{K^k}$ and omit the $q$ subscripts for reduction maps.

Let $(g_i)_{i \le \beta}$ an explicit $q$-homology basis for $(K, \partial)$. Let $k \le \beta$. Because $\overline{g_k} \cup \bigcup_{i \ne k} \overline{g_i} \ne \emptyset$, let us fix an element $\gamma_k$ in $\overline{g_k}$ that is not in the other $\overline{g}_i$.

We will build by induction for $k = 0, \dots, \beta$ a perfect HDVF $X^k = (P^k, S^k, C^k)$ for the complex $(K^k, \partial)$ (with reduction $(f^k, g^k, h^k)$) such that $C_q^k = \{\gamma_i, i \le k\}$ and $\forall i \le k, g^k(\gamma_i) = g_i$.

**Base case:** $k = 0$.

$K^0 = \{0\}, X^0 = (\emptyset, \emptyset, \emptyset)$ with reduction $(f^0, g^0, h^0)$, such that $f^0, g^0$ and $h^0$ are the zero function $\{0\} \to \{0\}$.

**Induction step:** $k+1$.

Suppose that there exists $X^k = (P^k, S^k, C^k)$ a perfect HDVF for the complex $(K^k, \partial)$ (with reduction $(f^k, g^k, h^k)$) such that $C_q^k = \{\gamma_i, i \le k\}$ and $\forall i \le k, g^k(\gamma_i) = g_i$.

We have $\overline{K}^{k+1} = \overline{K}^k \cup \overline{g_{k+1}}$. Denote $\iota^k, \iota^{k+1}$ and $\iota^{k \to k+1}$ the following $q$-homology maps induced the inclusions $(K^k, \partial) \subseteq (K, \partial)$, $(K^{k+1}, \partial) \subseteq (K, \partial)$ and $(K^k, \partial) \subseteq (K^{k+1}, \partial)$:

$$\iota^k : H_q(K^k) \to H_q(K) \quad \iota^{k+1} : H_q(K^{k+1}) \to H_q(K) \quad \iota^{k \to k+1} : H_q(K^k) \to H_q(K^{k+1})$$

By functoriality of the homology functor we have $\iota^k = \iota^{k+1} \circ \iota^{k \to k+1}$.

$(g_i)_{i \le \beta}$ is explicit so $\iota^k$ is injective by Proposition 2(1.), therefore $\iota^{k \to k+1}$ is also injective. In addition, $([g^k(\gamma)]^k)_{\gamma \in C_q^k}$ is linearly independent (because $X^k$ is perfect). Hence, $([g^k(\gamma)]^{k+1})_{\gamma \in C_q^k} = (\iota^{k \to k+1}[g^k(\gamma)]^k)_{\gamma \in C_q^k}$ is linearly independent.

Using Lemma 2 with $C^* := C_q^k$, it is then possible to complete $X^k$ into a perfect HDVF $X = (P, S, C)$ for $(K^{k+1}, \partial)$ such that $P^k \subseteq P$ and $S^k \subseteq S$ and $C_q^k \subseteq C_q$. We will now slightly modify $X$ to have the desired properties.
It remains to prove the maximality of $S_q$ and $P_q$. Let us consider $S_q$ first: we prove that if we add a cell $\tau$ to $S_q$, it creates a cycle. Let $\tau$ be a $q$-cell that is not in $S_q$. As $(P_q, S_q, C_q)$ is a partition of the $q$-cells, $\tau \in P_q \sqcup C_q$.

Consider $x := gf(\tau) + \partial h(\tau) = \tau - h\partial(\tau)$ (by Definition 4). $(P, S, C)$ is perfect so $\partial g = gd = 0$. This implies that $gf(\tau)$ is a cycle. It follows that $x$ is also a cycle because $gf(\tau)$ and $\partial h(\tau)$ are cycles.

In addition, $h\partial(\tau) \in \text{Span } S_q$ (by Definition 6) but $\tau \notin S_q$ so $x = \tau - h\partial(\tau)$ is not zero and is composed of cells in $S_q \sqcup \{\tau\}$. Thus, $x$ is a non zero cycle of $S_q \sqcup \{\tau\}$, so $S_q$ is maximal.

The proof of the maximality of $P_q$ is similar: if $\tau \notin P_q$, then $f^*g^*(\tau) + \partial^*h^*(\tau)$ is a non zero cocycle with cells in $P_q \sqcup \{\tau\}$.

### A “stack” of tri-partitions is a perfect HDVF:

We first prove that $(P, S, C) = (\bigcup A^q, \bigcup A_q, \bigcup E_q)$ is a HDVF. To do that we need to show that $\partial|_{A^q}^{A_{q+1}}$ is a squared invertible matrix for every $q$.

To begin with we prove the injectivity of $\partial|_{A^q}^{A_{q+1}}$: let $x \in \ker \partial|_{A^q}^{A_{q+1}}$. We have that $x \in \text{Span } A_{q+1}$ and that $\partial(x) \in \text{Span } A_q \oplus \text{Span } E_q$. Hence there exist $t \in \text{Span } A_q$ (a tree) and $e \in \text{Span } E_q$ such that $\partial(x) = t + e$.

By Definition 13, we have that $z_q(e) - e \in \text{Span } A_q$ and $z_q(e) \in \ker \partial$. This implies:

$$ 
\begin{aligned}
\partial(x) - e &= t \\
\partial(x) - e - (z_q(e) - e) &= t - (z_q(e) - e) \\
\partial(x) - z_q(e) &= t - (z_q(e) - e)
\end{aligned}
$$

However, as $\partial(x)$ and $z_q(e)$ are cycles, $\partial(x) - z_q(e) \in \ker \partial$. In addition, $t$ and $z_q(e) - e$ are in $\text{Span } A_q$ so $t - (z_q(e) - e) \in \text{Span } A_q$. Since $\text{Span } A_q \cap \ker \partial = \{0\}$ we obtain that $\partial(x) - z_q(e) = t - (z_q(e) - e) = 0$ so $\partial(x) = z_q(e)$.

This directly implies $[z_q(e)] = [\partial(x)] = 0$. By Theorem 4.3 in [5], $(z_q(\epsilon))_{\epsilon \in E_q}$ is a homology basis, so $[z_q(e)]$ is not the 0 homology class unless $e = 0$. Thus, we get $\partial(x) = t + e = t$ so $\partial(x) \in \text{Span } A_q \cap \ker \partial = \{0\}$. Thus, $\partial(x) = 0$ and $x \in \ker \partial$. This implies that $x \in \text{Span } A_{q+1} \cap \ker \partial = \{0\}$ so $x = 0$ and $\ker \partial|_{A^q}^{A_{q+1}} = \{0\}$.

This directly implies the injectivity of $\partial|_{A^q}^{A_{q+1}}$ and the fact that $|A_{q+1}| \le |A^q|$.

By duality (doing the proof for $x \in \ker \partial^*|_{A_{q+1}}^{A^q}$), we obtain the injectivity of $\partial^*|_{A_{q+1}}^{A^q}$ and the fact that $|A_{q+1}| \ge |A^q|$. This implies that $\partial^*|_{A^q}^{A_{q+1}}$ is squared and injective so it is invertible.

Hence, $(P, S, C)$ is a HDVF. Moreover, it is perfect because we have $|C_q| = |E_q| = \beta_q$. $\square$

## 5.4 Duality and Explicit Cohomology Bases

**Definition 14 (dual complex).** Given a complex $(K, \partial)$, its dual complex is the chain complex $(K^*, \partial^*)$ induced by the cells of $K$ but in reverse order, and
equipped with the coboundary operator: $K_q^* := K_{n-q}$ and $\partial^*$ is the transpose of $\partial$. The q-homology of $(K, \partial)$ corresponds to the $(n-q)$-cohomology of $(K^*, \partial^*)$ and vice versa.

**Proposition 5.** If $(P, S, C)$ is a HDVF for $(K, \partial)$ with reduction $(f, g, h)$, then $(S, P, C)$ is a HDVF for the dual complex $(K^*, \partial^*)$ with reduction $(g^*, f^*, h^*)$.

The notation for the induced complex also transfers to $(K^*, \partial^*)$: given a set of cells $A$ in a complex $(K, \partial)$, $(K^*(A), \partial^*)$ is the minimum sub-chain complex of $(K^*, \partial^*)$ containing $A$. Precisely, $K^*(A)_q$ is generated by the cofaces of dimension $q$ of cells in $A$.

Given a q-cohomology basis $(f_i)_{i \le \beta}$ for a complex $(K, \partial)$ (which is by duality a $(n-q)$-homology basis for $(K^*, \partial^*)$), we denote $(K^{*\beta}, \partial^*) := (K^*(\bigcup_{i \le \beta} \bar{f}_i), \partial^*)$ the sub-complex of $(K^*, \partial^*)$ induced by $(f_i)_{i \le \beta}$.

**Definition 15 (Explicit cohomology bases).** A q-cohomology basis $(f_i)_{i \le \beta}$ for a complex $(K, \partial)$ is said to be explicit if it satisfies the following property:

$$ \forall k, \bar{f}_k \setminus \bigcup_{i \ne k} \bar{f}_i \ne \emptyset \quad \text{and} \quad \dim(H_{n-q}(K^{*\beta})) = \beta $$

By definition, $(f_i)_{i \le \beta}$ is an explicit q-cohomology basis for a complex $(K, \partial)$ if and only if $(f_i)_{i \le \beta}$ is an explicit $(n-q)$-homology basis for $(K^*, \partial^*)$.

Proposition 5 and Theorems 1 and 2 implies the following characterization of cohomology bases:

**Theorem 4.** Given a perfect HDVF $(P, S, C)$ for $(K, \partial)$ with reduction $(f, g, h)$, $(f_q^*(\gamma))_{\gamma \in C_q}$ is an explicit cohomology basis. Conversely, given $(f_i)_{i \le \beta}$ an explicit q-cohomology basis for a complex $(K, \partial)$, there exists a perfect HDVF $(P, S, C)$ for $(K, \partial)$ with reduction $(f, g, h)$ such that $(f_q^*(\gamma))_{\gamma \in C_q} = (f_i)_{i \le \beta}$.