1 Introduction

The stability theorem for persistent homology is one of the main results of topological data analysis (TDA). It plays a key role in the statistical foundations of TDA [13], and is used to formulate theoretical guarantees for efficient algorithms to approximately compute persistent homology [6, 18]. The theorem is originally due to Cohen-Steiner et al., who presented a version of the theorem for the persistent homology of \(\mathbb R\)-valued functions [9]. Since then, the theorem has been revisited a number of times, leading to simpler proofs and more general formulations [1,2,3,4,5, 7, 8, 15]. In particular, Chazal et al. introduced the algebraic stability theorem [8], a useful and elegant algebraic generalization, and it was later observed that the (easy) converse to this result also holds [15]. Bubenik and Scott were the first to explore the category-theoretic aspects of the stability theorem, rephrasing some of the key definitions in terms of functors and natural transformations [4].

Letting vect denote the category of finite dimensional vector spaces over a fixed field K, a pointwise finite dimensional (p.f.d.) persistence module is an object of the functor category vect R. The structure theorem for p.f.d. persistence modules [10] tells us that the isomorphism type of a p.f.d. persistence module M is completely described by a unique collection of intervals called the barcode \(\mathcal B(M)\). This barcode specifies how M decomposes into indecomposable summands; such a decomposition is essentially unique. The algebraic stability theorem, together with its converse, tells us that two persistence modules are algebraically similar (in a sense made precise by the language of interleavings) if and only if they have similar barcodes.

In [1], the authors of the present paper introduced the induced matching theorem, an extension of the algebraic stability theorem to a general result about morphisms of persistence modules, with a new, more direct proof. The present paper is intended as a follow-up to [1]. The induced matching theorem can be viewed as a categorification of the stability theorem, and while this viewpoint was already present in [1], it was not fully developed. Our goal here is to complete the development of the categorical viewpoint on induced matchings and algebraic stability. In order to make this paper self-contained, we revisit some of the same territory as [1] along the way, leveraging the categorical perspective to streamline the presentation.

To formulate and prove the induced matching theorem, in [1] we considered the category whose objects are barcodes and whose morphisms are arbitrary matchings (i.e., partial injective functions). In the present paper, we introduce a different category of barcodes, denoted by Barc, for which the morphisms are only those matchings satisfying a certain simple condition on how the matched intervals overlap. We observe that there exists an equivalence of categories E : Barc →Mch R extending the correspondence between barcodes and functors R →Mch given by Edelsbrunner et al. [12]. We use the category Barc to further develop the categorical viewpoint on stability.

Thanks to the equivalence E, it turns out that all of the categorical structure of vect R relevant to algebraic stability (as treated in [1]) has an analogue in Barc. This allows us to present simple reformulations of both the induced matching and algebraic stability theorems, which make clear for the first time that both results can be understood as the preservation of certain categorical structure upon passing from persistence modules to barcodes. Moreover, we show that this viewpoint leads naturally to a more systematic variant of the proof of the induced matching theorem (albeit one closely related to the proof given in [1]).

1.1 Reformulation of the Induced Matching Theorem

To state the induced matching theorem, we need to first define a morphism of barcodes in Barc

$$\displaystyle \begin{aligned}\mathcal X(f):\mathcal B(M) \to \mathcal B(N)\end{aligned}$$

induced by a morphism f : M → N of p.f.d. persistence modules. This is called the induced matching off. To define \(\mathcal X(f)\), one first gives the definition in the case that f is a monomorphism or epimorphism; see Sect. 3.2 for the details.

For any category C, let C ↪ denote the subcategory with the same objects and morphisms the monomorphisms. Similarly, let \(\mathbf C^\twoheadrightarrow \) denote the subcategory with the same objects and morphisms the epimorphisms. The following result is equivalent to [1, Proposition 4.2]; we provide two different proofs, in Sects. 3.2 and 5.

Theorem 1 (Induced Matchings for Monos and Epis)

  1. (i)

    The matchings induced by monomorphisms define a functor

    $$\displaystyle \begin{aligned}\mathcal X:({\mathbf{vect}}^{\mathbf{R}})^{\hookrightarrow} \to {\mathbf{Barc}}^{\hookrightarrow}.\end{aligned}$$
  2. (ii)

    Dually, the matchings induced by epimorphisms define a functor

    $$\displaystyle \begin{aligned}\mathcal X:({\mathbf{vect}}^{\mathbf{R}})^\twoheadrightarrow \to {\mathbf{Barc}}^\twoheadrightarrow.\end{aligned}$$

To extend the definition of the induced matchings \(\mathcal X(f)\) to arbitrary morphisms f : M → N of p.f.d. persistence modules, we take \(\mathcal X(f)=\mathcal X(i)\circ \mathcal X(q)\), where

$$\displaystyle \begin{aligned}M \stackrel{q}\twoheadrightarrow \operatorname{\mathrm{\operatorname{im}}} f\stackrel{i}\hookrightarrow N\end{aligned}$$

is the epi-mono factorization of f. Note that when f is a monomorphism or epimorphism, this definition of \(\mathcal X(f)\) coincides with the one given by Theorem 1 above.

Remark 1

The map \(f\mapsto \mathcal X(f)\) is not functorial on all of vect R [1, Example 5.6], though it is functorial on both the subcategory of monos and the subcategory of epis. Indeed, it is impossible to extend the map \(M \mapsto \mathcal B(M)\) to a functor from vect to Barc [1, Proposition 5.10].

A morphism f in vect R is a monomorphism (epimorphism) if and only if f has a trivial kernel (respectively, cokernel), and it can be checked that the same is true as well for a morphism f in Barc. Thus, Theorem 1 tells us that the matchings induced by morphisms with trivial (co)kernels also have trivial (co)kernels. As formulated in this paper, the induced matching theorem is a generalization of this statement to small (but not necessarily trivial) (co)kernels.

To make this precise, we need the following definition:

Definition 1 (δ-triviality)

For A a pointed category (i.e., a category with a zero object) and δ ≥ 0, we say that a diagram M : R →A is δ-trivial if for all \(t \in \mathbb R\), the internal morphism M t,t+δ : M t → M t+δ is a zero morphism, i.e., it factors through the zero object. The empty set is the zero object in Mch; we say a barcode \(\mathcal C\) is δ-trivial if \(E(\mathcal C)\) is δ-trivial.

Note that M = 0 if and only if M is 0-trivial. Using the definition of the equivalence E given below in Sect. 2.4, it is straightforward to check that a barcode \(\mathcal C\) is δ-trivial if and only if each interval of \(\mathcal C\) is contained in some half-open interval of length δ. Moreover, a persistence module M is δ-trivial if and only if \(\mathcal B(M)\) is δ-trivial.

Theorem 2 (Categorical Formulation of the Induced Matching Theorem)

For any morphism f : M → N of p.f.d. persistence modules, the induced matching \(\mathcal X(f):\mathcal B(M)\to \mathcal B(N)\)is a morphism inBarcsuch that

  1. (i)

    if f has δ-trivial kernel, then so does \(\mathcal X(f)\), and

  2. (ii)

    if f has δ-trivial cokernel, then so does \(\mathcal X(f)\).

Note that taking δ = 0 in Theorem 2, we recover Theorem 1. In Sect. 3, we give a concrete formulation of the induced matching theorem (Theorem 5), similar to the version appearing in [1], and explain why the two formulations are equivalent.

Remark 2

In both the proof of the induced matching theorem given in [1] and the proof given in the present paper, the first step is to prove Theorem 1. In this paper, we show that the proof of Theorem 2 follows readily from Theorem 1 and a simple characterization of the δ-triviality condition for functors R →A taking values in a Puppe-exact categoryA; see Definition 2 and Lemma 1.

Remark 3

Theorem 2 has a simple converse, which we give in Proposition 4.

1.2 Reformulation of the Algebraic Stability Theorem

We next turn to our reformulation of the algebraic stability theorem. The theorem is typically formulated using the interleaving distanced I on persistence modules and the bottleneck distanced B on barcodes; see Sect. 4.2 for the definition. Here, we use the categorical structure on barcodes to state the algebraic theorem purely in terms of interleavings of R-indexed diagrams, without explicitly introducing d B.

Interleavings and the interleaving distance d I can be defined on R-indexed diagrams taking values in an arbitrary category; see Definition 6. By way of the equivalence E, we thus obtain definitions of interleavings and d I on Barc; see Sect. 4.1.1. Our Proposition 6 establishes that the distances d I and d B on barcodes are equal; in fact, we give a slightly sharper statement. From Proposition 6 it follows that the forward and converse algebraic stability theorems, as stated in [1], can be rephrased as follows:

Theorem 3 (Categorical Formulation of Algebraic Stability)

Two p.f.d. persistence modules M and N are δ-interleaved if and only if their barcodes \(\mathcal B(M)\) and \(\mathcal B(N)\) are δ-interleaved. In particular,

$$\displaystyle \begin{aligned}d_I(M,N)=d_I(\mathcal B(M),\mathcal B(N)).\end{aligned}$$

As we show in Sect. 4.2, this formulation of algebraic stability follows easily from Theorem 2.

1.3 Directly Constructing Barcodes as Matching Diagrams

In view of the equivalence E : Barc →Mch R, one may wonder whether one can give simple constructions of barcodes of persistence modules and induced matchings directly in the category Mch R. In the final part of this paper, we explore this question. Given a persistence module M, we give a direct construction of a matching diagram \(D^\twoheadrightarrow (M)\) which is equivalent to the usual barcode of M. \(D^\twoheadrightarrow (M)\) is defined only in terms of the ranks of the linear maps in M; the definition does not depend on the structure theorem for persistence modules. \(D^\twoheadrightarrow (M)\) has the appealing property that the sets \(D^\twoheadrightarrow (M)_r\) at each index r are defined in an especially simple way, namely

$$\displaystyle \begin{aligned}D^\twoheadrightarrow(M)_r=\{1,2,\ldots, \dim M_r\}.\end{aligned}$$

We observe that, given an epimorphism of persistence modules \(f:M\twoheadrightarrow N\), the matching induced by f has a simple description as a natural transformation

$$\displaystyle \begin{aligned}D^\twoheadrightarrow(f):D^\twoheadrightarrow(M) \twoheadrightarrow D^\twoheadrightarrow(N),\end{aligned}$$

and this leads to an alternate proof of Theorem 1 (ii). There seems to be no comparably simple, direct description of the matching induced by a monomorphism f : M↪N as a natural transformation \(D^\twoheadrightarrow (M)\to D^\twoheadrightarrow (N)\). But we observe that the matching diagram \(D^\twoheadrightarrow (M)\) has a dual D ↪(M), also equivalent to the usual barcode, such that the matching induced by a monomorphism f : M↪N has a simple description as a natural transformation

$$\displaystyle \begin{aligned}D^{\hookrightarrow}(f):D^{\hookrightarrow}(M)\hookrightarrow D^{\hookrightarrow}(N),\end{aligned}$$

leading (dually) to an alternate proof of Theorem 1 (i).

1.4 Organization of the Paper

We begin Sect. 2 by examining the properties of the category Mch R. We then give the precise definitions of our category of barcodes Barc and of the equivalence E : Barc →Mch R. As applications of this equivalence, we give a concrete description of (co)kernels and images in Barc, and we describe how the δ-triviality of the (co)kernel of a morphism \(f:\mathcal C\to \mathcal D\) in Barc controls the similarity between \(\mathcal C\) and \(\mathcal D\). In Sect. 3, we use these descriptions to show that our categorical formulation of the induced matching theorem (Theorem 2) is equivalent to a concrete formulation similar to that appearing in [1]. We then complete the definition of induced matchings and give our proof of the induced matching theorem. In Sect. 4, we give the details of our reformulation of the algebraic stability theorem, and we prove that this follows easily from the induced matching theorem. Section 5 discusses the construction of barcodes and induced matchings directly in Mch R.

2 Barcodes as Diagrams

2.1 Properties of Mch and Mch R

First, we review some basic properties of the category Mch having sets as objects and matchings (partial injective functions) as morphisms. Mch is a subcategory of the category with sets as objects and relations as morphisms. The composition τ ∘ σ : S → U of two matchings σ : S → T and τ : T → U is thus defined as

$$\displaystyle \begin{aligned} \tau\circ\sigma=\{(s,u) \mid (s,t) \in \sigma,\ (t,u) \in \tau \ \text{ for}\ \text{some }\ t \in T \}. \end{aligned} $$

The monomorphisms in Mch are the injections, while the epimorphisms are the coinjections, i.e., matchings which match each element of the target. The kernel and cokernel of a morphism in Mch consist of the unmatched elements of the source and target, respectively, together with the canonical (co)injections. Similarly, the image and coimage consist of the matched elements (See Fig. 1 for an illustration).

Fig. 1
figure 1

Examples illustrating matchings as a category. Left: the composition of two matchings. Right: kernel, coimage, image, and cokernel of a matching f

Full size image

2.1.1 Mch and Mch R as Puppe-Exact Categories

The category Mch is not Abelian: it does not have all binary (co)products, and is not even pre-additive. Nevertheless, Mch does share some structural similarities with an Abelian category. In specific, Mch is a Puppe-exact category:

Definition 2

A Puppe-exact category [14, 16, 17] is a category with the following properties:

  • it has a zero object,

  • it has all kernels and cokernels,

  • every monomorphism is a kernel, and every epimorphism is a cokernel,

  • every morphism f has an epi-mono factorization.

Every Abelian category is Puppe-exact, and it has been shown in [14] that significant portions of homological algebra can be developed for Puppe-exact categories.

It follows from the definition that a Puppe-exact category also has all (co)images. Just like in Abelian categories, we have that

$$\displaystyle \begin{aligned}\operatorname{\mathrm{\operatorname{im}}} f = \ker \operatorname{\mathrm{coker}} f,\quad \operatorname{\mathrm{coim}} f = \operatorname{\mathrm{coker}} \ker f,\end{aligned}$$

and the coimage is canonically isomorphic to the image. Moreover, the epi-mono factorization of a morphism f is through \( \operatorname {\mathrm {\operatorname {im}}} f\), and is essentially unique.

For any category C and Puppe-exact category A, the category of functors C →A is also Puppe-exact. Thus, Mch R is Puppe-exact. In particular, it has all kernels, cokernels, and images, and these are given pointwise.

2.2 Barcodes

Definition 3 (Multiset Representations)

We say a multiset representation is a subset T ⊆ S × X of sets S and X, called the base set and the indexing set respectively. For s ∈ S, the multiplicity of s in T is the cardinality of the local indexing setX s = {x ∈ X∣(s, x) ∈ T}. In [1], we considered a more restrictive definition of a multiset representation, where the indexing set X is \(\mathbb N=\{1,2,3,\ldots \}\) and each local indexing set X s is required to be a prefix of \(\mathbb N\); we refer to this as a natural multiset representation. (Using the more general definition here allows us to establish the link between barcodes and matching diagrams without imposing any cardinality conditions on the matching diagrams.)

Let T and T′ be multiset representations with the same indexing set S and respective base sets X and X′. We say T′reindexesT, and write T≅T′, if there exists a bijection f : T → T′ such that for all (s, x) ∈ T, f(s, x) = (s, x′) for some x′∈ X′. Note that ≅ is an equivalence relation on multiset representations.

Definition 4 (Barcode)

An interval in \(\mathbb R\) is a non-empty set \(I\subset \mathbb R\) such that if a, c ∈ I and a < b < c, then b ∈ I. A barcode is a multiset representation whose base set consists of intervals in \(\mathbb R\). If the barcode is a natural multiset representation, we call it a natural barcode.

In working with barcodes, we often abuse notation slightly by suppressing the indexing set, and write an element (s, x) of a barcode simply as s.

2.2.1 Barcodes of Persistence Modules

For I an interval, define the interval moduleK I to be the persistence module such that

$$\displaystyle \begin{aligned} K^I_r&= \begin{cases} K &{\mbox{if }}\ r\in I, \\ 0 &{\mbox{ otherwise}.} \end{cases} & K^I_{r,s}= \begin{cases} \operatorname{\mathrm{Id}}_K &{\mbox{if }}\ r,s\in I,\\ 0 &{\mbox{ otherwise}.} \end{cases} \end{aligned} $$

The following well-known theorem tells us that natural barcodes arise as complete isomorphism invariants of p.f.d. persistence modules.

Theorem 4 (Structure of p.f.d. Persistence Modules [10])

For any p.f.d. persistence module M, there exists a unique natural barcode \(\mathcal B(M)\) such that

$$\displaystyle \begin{aligned}M\cong \bigoplus_{I\in \mathcal B(M)} K^I.\end{aligned}$$

Following [7], we call this barcode \(\mathcal B(M)\) the decomposition barcode of M, or simply the barcode of M.

2.3 The Category of Barcodes

For intervals \(I,J\subseteq \mathbb R\), we say that IboundsJabove if for all s ∈ J there exists t ∈ I with s ≤ t. If additionally J bounds I above, we say that I and Jcoincide above. Symmetrically, we say that JboundsIbelow if for all t ∈ I there exists s ∈ J with s ≤ t, and that I and Jcoincide below if additionally I bounds J below. We say that IoverlapsJabove (and symmetrically, JoverlapsIbelow) if each of the following three conditions hold:

  • I ∩ J≠∅,

  • I bounds J above, and

  • J bounds I below.

For example, [1, 3) overlaps [0, 2) above, but neither [0, 4) nor [0, 2) overlap [1, 3) above.

Definition 5 (The Category of Barcodes)

We define an overlap matching between barcodes \(\mathcal C\) and \(\mathcal D\) to be a matching \(\sigma :\mathcal C\to \mathcal D\) such that if σ(I) = J, then I overlaps J above. Note that if \(\sigma :\mathcal B\to \mathcal C\) and \(\tau :\mathcal C\to \mathcal D\) are both overlap matchings, then the composition τ ∘ σ in Mch is not necessarily an overlap matching; for intervals I, J, K such that I overlaps J above, and J overlaps K above, it may be that I ∩ K = ∅, so that I does not overlap K above.

We thus define the overlap composition of overlap matchings σ and τ as the matching

See Fig. 2 for an illustration. It is easy to check that with this new definition of composition, the barcodes and overlap matchings form a category, which we denote as Barc.

Fig. 2
figure 2

Illustration of overlap matchings and their composition. Both the left and right examples depict overlap matchings \(\sigma :\mathcal B\to \mathcal C\) and \(\tau :\mathcal C\to \mathcal D\) between single-interval barcodes \(\mathcal B = \{I\},\) \(\mathcal C = \{J\},\) \(\mathcal D = \{K\}\), with σ = {(I, J)}, τ = {(J, K)}. We have if and only if I ∩ K ≠ ∅, so for the left example, but for the right example

Full size image

Note that two barcodes are isomorphic in Barc if and only if one reindexes the other. Note also that the empty barcode is the zero object in Barc.

2.4 Barcodes as Diagrams

2.4.1 A Functor from Barcodes to Diagrams

We now define the equivalence E : Barc →Mch R. For \(\mathcal D\) a barcode and \(t\in \mathbb R\), we let

$$\displaystyle \begin{aligned}E(\mathcal D)_t := \{I \in \mathcal D \mid t \in I\},\end{aligned}$$

and for each s ≤ t we define the internal matching \(E(\mathcal D)_{s,t}: E(\mathcal D)_s \to E(\mathcal D)_t\) to be the restriction of the diagonal of \(\mathcal D \times \mathcal D\) to \(E(\mathcal D)_s \cap E(\mathcal D)_t\), i.e.,

$$\displaystyle \begin{aligned}E(\mathcal D)_{s,t}:=\{(I,I) \mid I \in \mathcal D, \; s,t \in I\}.\end{aligned}$$

See Fig. 3 for an illustration.

Fig. 3
figure 3

Examples illustrating the matching diagram representation \(E(\mathcal C)\) of a barcode \(\mathcal C\). Left: The intervals of \(E_t(\mathcal C)\) are shown in blue (left). Right: The intervals of \( \operatorname {\mathrm {coim}} E(\mathcal C)_{s,t}= \operatorname {\mathrm {\operatorname {im}}} E(\mathcal C)_{s,t}\) are shown in red

Full size image

We define the action of E on morphisms in Barc in the obvious way: for \(\sigma :\mathcal C\to \mathcal D\) an overlap matching and \(t\in \mathbb R\), we let \(E(\sigma )_t: E(\mathcal C)_t \to E(\mathcal D)_t\) be the restriction of σ to pairs of intervals both containing t, i.e.,

$$\displaystyle \begin{aligned}E(\sigma)_t:=\{(I,J) \in \sigma \mid t \in I \cap J \}.\end{aligned} $$

It is straightforward to check that E is indeed a functor.

2.4.2 A Functor from Diagrams to Barcodes

To see that E is an equivalence, we next define a functor F : Mch R →Barc such that E and F are inverses (up to natural isomorphism).

For D : R →Mch, let

$$\displaystyle \begin{aligned} \mathcal F(D) := \left(\bigcup_{t\in\mathbb R} {\{t\} \times D_t} \right) \bigg/ \sim\end{aligned} $$

where (t, x) ∼ (u, y) if and only if (x, y) ∈ D t,u or (y, x) ∈ D u,t. The functoriality of D implies that the projection onto the first coordinate (t, x)↦t necessarily maps each equivalence class \(Q \in \mathcal F(D)\) to an interval \( \operatorname {\mathrm {supp}}(Q) = \{t \mid (t,x) \in Q \}\subseteq \mathbb R\). We thus may define the barcode F(D) by

$$\displaystyle \begin{aligned}F(D):=\{(\operatorname{\mathrm{supp}}(Q),Q) \mid Q\in \mathcal F(D)\},\end{aligned} $$

where we interpret the above expression as a multiset representation by taking the index of each interval \( \operatorname {\mathrm {supp}}(Q)\) to be the equivalence class Q. We take the action of F on morphisms to be the obvious one: for diagrams C, D : R →Mch and η : C → D a natural transformation (consisting of a family of matchings η t : C t → D t), we take F(η) : F(C) → F(D) to be the overlap matching given by

$$\displaystyle \begin{aligned} \begin{array}{rcl} &\displaystyle &\displaystyle F(\eta):=\big\{\left((\operatorname{\mathrm{supp}}(Q),Q),(\operatorname{\mathrm{supp}}(R),R)\right) \mid Q \in \mathcal F(C),\ R \in \mathcal F(D), \\ &\displaystyle &\displaystyle \qquad \qquad \qquad \qquad \quad \quad \qquad \exists\ t\in \mathbb R,\ (x,y) \in \eta_t : (t,x) \in Q, (t,y) \in R \big\}. \end{array} \end{aligned} $$

It is easy to check that F is a functor and that E and F are indeed inverses up to natural isomorphism.

2.5 Kernels, Cokernels, and Images of Barcodes

In the induced matching approach to algebraic stability, (co)kernels and δ-triviality of persistence modules both play an essential role. We have seen above that the definitions of these extend to functor categories A R for any Puppe-exact category A; in particular, they extend to Mch R. Thus, since Mch is equivalent to Barc, these definitions also carry over to Barc.

We next give concrete descriptions of kernels, cokernels, and images in Barc. We then use these to obtain a simple description of how the δ-triviality of the (co)kernel of a morphism \(f:\mathcal C\to \mathcal D\) in Barc controls the similarity between \(\mathcal C\) and \(\mathcal D\).

For \(\sigma :\mathcal C\to \mathcal D\) an overlap matching of barcodes and \(I\in \mathcal C\), define

$$\displaystyle \begin{aligned}\ker(\sigma,I)= \begin{cases} I &\mbox{if }\ \sigma\ \mbox{ does}\ \mbox{not}\ \mbox{match}\ I,\\ I \setminus J & \mbox{if }\ \sigma(I)=J. \end{cases}\end{aligned}$$

Hence, \(\ker (\sigma ,I)\) is either empty or an interval in \(\mathbb R\). In the latter case, I and \(\ker (\sigma ,I)\) coincide above. Dually, for \(J\in \mathcal D\), we define

$$\displaystyle \begin{aligned}\operatorname{\mathrm{coker}}(\sigma,J)= \begin{cases} J &\mbox{if }\ \sigma\ \mbox{ does}\ \mbox{not}\ \mbox{match}\ J,\\ J \setminus I & \mbox{if }\ \sigma(I)=J. \end{cases}\end{aligned}$$

Proposition 1

For any morphism (i.e., overlap matching) \(\sigma :\mathcal C\to \mathcal D\) in Barc , the categorical kernel, cokernel, and image of σ exist and are given by

$$\displaystyle \begin{aligned} \ker \sigma&= \{\ker(\sigma,I) \neq \emptyset \mid {I\in \mathcal C}\}, \\ \quad \operatorname{\mathrm{coker}} \sigma&= \{\operatorname{\mathrm{coker}}(\sigma,J) \neq \emptyset \mid {J\in \mathcal D}\},\\ \operatorname{\mathrm{\operatorname{im}}} \sigma&= \{ I \cap J \mid {(I,J)\in \sigma}\}. \end{aligned} $$

Proof

Given \(\sigma :\mathcal C\to \mathcal D\) in Barc, applying the equivalence E yields a morphism of matching diagrams E(σ) such that

$$\displaystyle \begin{aligned}(\ker E(\sigma))_t=\{I\in \mathcal C\mid t\in I, I\mbox{ not matched by }\sigma\mbox{ to }J \in \mathcal D\mbox{ with }t \in J\}.\end{aligned}$$

It is then clear that

$$\displaystyle \begin{aligned}F(\ker E(\sigma))= \{\ker(\sigma,I) \neq \emptyset \mid {I\in \mathcal C}\}.\end{aligned}$$

Since

$$\displaystyle \begin{aligned}\ker \sigma \cong F\circ E(\ker \sigma)\cong F(\ker(E(\sigma))),\end{aligned}$$

the result for kernels holds. Similar arguments give the results for cokernels and for images. □

Using this concrete description of (co)kernels in Barc, we now give an explicit description of the notion of δ-triviality for (co)kernels of overlap matchings. Given an interval \(I \subset \mathbb R\) and δ ≥ 0, let

$$\displaystyle \begin{aligned} I(\delta) := \{t \mid t +\delta \in I\} \end{aligned} $$
(1)

be the interval obtained by shifting I downward by δ.

Proposition 2

Let \(\eta :\mathcal C\to \mathcal D\) an overlap matching of barcodes. Then

  1. (i)

    \(\ker \eta \) is δ-trivial if and only if

    1. (a)

      for each (I, J) ∈ η, J bounds I(δ) above, and

    2. (b)

      any interval of \(\mathcal C\) that is not matched by η is contained in a half-open interval of length δ.

  2. (ii)

    \( \operatorname {\mathrm {coker}} \eta \) is δ-trivial if and only if

    1. (a)

      for each (I, J) ∈ η, I(δ) bounds J below, and

    2. (b)

      any interval of \(\mathcal D\) that is not matched by η is contained in a half-open interval of length δ.

Proof

As noted in Sect. 1.1, a barcode \(\mathcal C\) is δ-trivial if and only if each interval in \(\mathcal C\) is contained in a half-open interval of length δ. Given this, the result follows immediately from Proposition 1. □

Recall that a morphism has 0-trivial (co)kernel if and only if it is a monomorphism (epimorphism). We thus have the following corollary of Proposition 2, which gives a concrete interpretation of Theorem 1:

Corollary 1

Let \(\eta :\mathcal C\to \mathcal D\) an overlap matching of barcodes. Then

  1. (i)

    η is a monomorphism if and only if

    1. (a)

      for each (I, J) ∈ η, I and J coincide above, and

    2. (b)

      every interval of \(\mathcal C\) is matched (i.e., η is an injection).

  2. (ii)

    η is an epimorphism if and only if

    1. (a)

      for each (I, J) ∈ η, I and J coincide below, and

    2. (b)

      every interval of \(\mathcal D\) is matched (i.e., η is a coinjection).

3 The Induced Matching Theorem

In this section, we observe that the categorical formulation of the induced matching theorem (Theorem 2) is equivalent to a more concrete statement, similar to the formulation appearing in [1]. We then define the matchings induced by epimorphisms and monomorphisms of persistence modules, thereby completing the definition of induced matchings given in Sect. 1.1. To finish the section, we prove the induced matching theorem, working directly with the categorical formulation of the theorem.

3.1 Concrete Formulation of the Induced Matching Theorem

It follows from Propositions 1 and 2 that our categorical reformulation of the induced matching theorem (Theorem 2) is equivalent to the following. See Fig. 4 for an illustration.

Fig. 4
figure 4

Illustration for part (ii) of the induced matching theorem: the right endpoint of the interval \(J \in \mathcal B(N)\) coincides with that of an interval in \(\mathcal B( \operatorname {\mathrm {\operatorname {im}}} f)\) and lies between the right endpoint of the interval \(I \in \mathcal B(M)\) and that of the shifted interval \(I(\delta ) \in \mathcal B(M(\delta ))\)

Full size image

Theorem 5 (Induced Matching Theorem [1])

Let f : M → N be a morphism of p.f.d. persistence modules.

  1. (i)

    The induced matching \(\mathcal X(f):\mathcal B(M)\to \mathcal B(N)\)is an overlap matching.

  2. (ii)

    If \(\ker f\)is δ-trivial, then

    1. (a)

      for each \((I,J) \in \mathcal X(f)\), J bounds I(δ) above, and

    2. (b)

      any interval of \(\mathcal B(M)\)not matched by \(\mathcal X(f)\)is contained in a half-open interval of length δ.

  3. (iii)

    If \( \operatorname {\mathrm {coker}} f\)is δ-trivial, then

    1. (a)

      for each \((I,J) \in \mathcal X(f)\), I(δ) bounds J below, and

    2. (b)

      any interval of \(\mathcal B(N)\)not matched by \(\mathcal X(f)\)is contained in a half-open interval of length δ.

3.2 Matchings Induced by Monos and Epis of Persistence Modules

We now define the matching \(\mathcal X(f)\) induced by a monomorphism or epimorphism f of persistence modules. The way we will present the definition will depend on a structural result, Proposition 3 below, which also leads almost immediately to a proof of Theorem 1.

Let \(\mathcal I\) denote the set of intervals in \(\mathbb R\). For \(I,J\in \mathcal I\), write I ∼aJ if I and J coincide above. ∼a is an equivalence relation on \(\mathcal I\). For \(\mathcal B\) a barcode, ∼a induces an equivalence relation on \(\mathcal B\), which we also denote as ∼a. For each equivalence class \(e\in \mathcal I/{\sim _a}\), let \(\mathcal B^e\) denote the corresponding equivalence class of \(\mathcal B/{\sim _a}\) if \(\mathcal B\) contains any intervals in e. Otherwise let \(\mathcal B^e=\emptyset \). If \(\mathcal B\) is the barcode of a p.f.d. module, then each \(\mathcal B^e\) is finite or countable. In addition, if \(\mathcal B^e\) is non-empty then it contains a maximal interval under inclusion. We endow \(\mathcal B^e\) with a total order by taking (I, n) < (J, n′) if I strictly contains J or I = J and n < n′. \(\mathcal B^e\) is then a countable, well-ordered set, hence isomorphic to a prefix of \(\mathbb N\).

Proposition 3 (Induced Matchings for Monos)

If f : M → N is a monomorphism of persistence modules, then

  1. (i)

    for each \(e\in \mathcal I/{\sim _a}\),

    $$\displaystyle \begin{aligned}|\mathcal B(M)^e|\leq|\mathcal B(N)^e|.\end{aligned}$$

    Thus, we have a well defined injection \(\mathcal X(f):\mathcal B(M) \hookrightarrow \mathcal B(N)\), which sends the i thelement of \(\mathcal B(M)^e\)to the i thelement of \(\mathcal B(N)^e\).

  2. (ii)

    \(\mathcal X(f)\)is in fact a monomorphism inBarc.

A simple proof of Proposition 3 is given in [1, Section 4]. Here, we present a variant of that argument.

Proof of Proposition 3

For any interval \(I\subset \mathbb R\), we define a functor F I : vect R →vect such that

  1. 1.

    for all p.f.d. persistence modules M, \(\dim F^I(M)\) is the number of intervals in \(\mathcal B(M)\) which contain I and coincide with I above, and

  2. 2.

    F I maps monomorphisms to monomorphisms.

To define F I, we choose t ∈ I and let

$$\displaystyle \begin{aligned}\ker^+= \bigcap_{u\not \in I: t<u} \ker M_{t,u}, \quad \ker^-= \bigcup_{u \in I: t \leq u} \ker M_{t,u}, \quad \operatorname{\mathrm{\operatorname{im}}}^+=\bigcap_{s\in I: s \leq t} \operatorname{\mathrm{\operatorname{im}}} M_{s,t}.\end{aligned}$$

We take

$$\displaystyle \begin{aligned}F^I(M)=(\ker^+\cap \operatorname{\mathrm{\operatorname{im}}}^+)/(\ker^-\cap \operatorname{\mathrm{\operatorname{im}}}^+).\end{aligned}$$

The map M↦F I(M) is easily checked to be functorial. From the structure theorem 4, it is clear that \(\dim F^I(M)\) has the desired property, and it is straightforward to check that F preserves monomorphisms.

The proposition follows easily from the existence of the functors F I: Let I be the jth interval in \(\mathcal B(M)^e\). We have

$$\displaystyle \begin{aligned}j\leq \dim F^I(M)\leq \dim F^I(N)\leq |\mathcal B(N)^e|.\end{aligned}$$

If \(\mathcal B(M)^e\) is finite, then taking \(j=|\mathcal B(M)^e|\) gives that \(|\mathcal B(M)^e|\leq |\mathcal B(N)^e|\). If \(\mathcal B(M)^e\) is countably infinite, then we have that \(j\leq |\mathcal B(N)^e|\) for all j ≥ 0, hence \(|\mathcal B(N)^e|\) is infinite as well. This proves (i).

To prove (ii), note that for each \(I\in \mathcal B(M)\), I and \(\mathcal X(f)(I)\) coincide above by construction of \(\mathcal X(f)\), so in view of Corollary 1, it suffices to show that \(I\subset \mathcal X(f)(I)\). Suppose that I is the jth interval in \(\mathcal B(M)^e\). Since \(\dim F^I(M)\leq \dim F^I(N)\), \(\mathcal B(N)^e\) has at least j intervals containing I. \(\mathcal X(f)(I)\) is by definition the jth interval of \(\mathcal B(N)^e\), so we have \(I\subset \mathcal X(f)(I)\), as desired. □

To define \(\mathcal X(f)\) for an epimorphism f, we simply dualize the above construction, taking two intervals to be equivalent if and only if they coincide below. The dual argument shows that \(\mathcal X(f)\) is an epimorphism in Barc.

Proof of Theorem 1 (Induced Matchings for Monos and Epis)

It is easy to see that the map \(f\mapsto \mathcal X(f)\) of the Proposition 3 is in fact functorial, so this defines a functor \(\mathcal X\) from monomorphisms of persistence modules to monomorphisms in Barc, proving Theorem 1 (i). The dual observation yields Theorem 1 (ii). □

Example 1

Interestingly, the map \(f\mapsto \mathcal X(f)\) may strictly decrease the triviality of (co)kernels: we give an example of a monomorphism f : M↪N such that \( \operatorname {\mathrm {coker}} f\) is not 2-trivial but \( \operatorname {\mathrm {coker}} \mathcal X(f)\) is 2-trivial. Let

$$\displaystyle \begin{aligned}M = K^{[2,4)},\quad N= K^{[0,4)} \oplus K^{[1,3)},\quad \mbox{and}\quad f = \begin{pmatrix} 1\\1 \end{pmatrix}.\end{aligned}$$

Then \(\mathcal B( \operatorname {\mathrm {coker}} f) = \{[0,3),[1,2)\}\) but \( \operatorname {\mathrm {coker}} \mathcal X(f) = \{[0,2),[1,3)\}\). In contrast, note that for any morphism f, we have by construction that \( \operatorname {\mathrm {\operatorname {im}}} \mathcal X(f) = \mathcal B( \operatorname {\mathrm {\operatorname {im}}} f)\).

3.3 A Characterization of Morphisms with δ-Trivial (Co)kernel

We now turn our attention to the proof of the induced matching theorem. First, we introduce some notation.

3.3.1 Shifts of R-Indexed Diagrams and Barcodes

Consider the translation t↦t + δ of the real line by \(\delta \in \mathbb R\) as an endofunctor S δ : R →R. For any category A and diagram M : R →A, we write M(δ) := M ∘ S δ. Thus, M(δ) is the diagram obtained by shifting each vector space and linear map in M downward by δ. Given M, N : R →A, a morphism f : M → N induces a morphism f(δ) : M(δ) → N(δ).

For δ ≥ 0, the internal morphisms \(\{M_{t,t+\delta }\}_{t\in \mathbb R}\) assemble into a natural transformation M → M(δ), which we denote by S M, δ. Note that since (M(−δ))(δ) = M, we have a natural transformation S M(−δ), δ : M(−δ) → M.

For \(\mathcal C\) a barcode, let

$$\displaystyle \begin{aligned}\mathcal C(\delta):=\{I(\delta)\mid I\in \mathcal C\},\end{aligned}$$

where I(δ) is as defined in Eq. 1, and let \(S^{\mathcal C,\delta }:\mathcal C\to \mathcal C(\delta )\) be the overlap matching given by

$$\displaystyle \begin{aligned}S^{\mathcal C,\delta}:=\{(I,I(\delta))\mid I\ \mbox{ is}\ \mbox{not }\ \delta\mbox{-trivial}\}.\end{aligned}$$

Note that for E : Barc →Mch R the equivalence of Sect. 2.4, \(E(S^{\mathcal C,\delta })=S^{E(\mathcal C),\delta }\).

The following proposition is one of the key ingredients in our proof of the induced matching theorem:

Lemma 1

Given diagrams M, N : R →AwithAPuppe-exact, and a morphism f : M → N with epi-mono factorization

$$\displaystyle \begin{aligned}M \stackrel{q}\twoheadrightarrow \operatorname{\mathrm{\operatorname{im}}} f \stackrel{i}\hookrightarrow N,\end{aligned}$$

the following are equivalent:

  1. (i)

    \(\ker f\) is δ-trivial;

  2. (ii)

    the image epimorphism \(r:M \twoheadrightarrow \operatorname {\mathrm {\operatorname {im}}} S^{M,\delta }\) factors as

    for some epimorphism \(p: \operatorname {\mathrm {\operatorname {im}}} f \twoheadrightarrow \operatorname {\mathrm {\operatorname {im}}} S^{M,\delta }\).

Dually, the following are equivalent:

  1. (i)

    \( \operatorname {\mathrm {coker}} f\) is δ-trivial;

  2. (ii)

    the image monomorphism \(h: \operatorname {\mathrm {\operatorname {im}}} (S^{N(-\delta ),\delta }) \hookrightarrow N\) factors as

    for some monomorphism \(j: \operatorname {\mathrm {\operatorname {im}}} S^{N(-\delta ),\delta } \hookrightarrow \operatorname {\mathrm {\operatorname {im}}} f\).

Proof

We give the proof for \(\ker f\), the dual case of \( \operatorname {\mathrm {coker}} f\) being analogous. Let

$$\displaystyle \begin{aligned}\kappa : \ker f \hookrightarrow M\quad \mbox{and} \quad \mu: \ker {S^{M,\delta}} \hookrightarrow M\end{aligned}$$

denote the kernel monomorphisms, and let

$$\displaystyle \begin{aligned}q : M \twoheadrightarrow \operatorname{\mathrm{\operatorname{im}}} f\quad \mbox{and} \quad r: M \twoheadrightarrow \operatorname{\mathrm{\operatorname{im}}} {S^{M,\delta}}\end{aligned}$$

denote the image epimorphisms.

To show that (i) implies (ii), assume that \(\ker f\) is δ-trivial, i.e.,

$$\displaystyle \begin{aligned}S^{\ker f,\delta}:\ker f \to \ker f(\delta)\end{aligned}$$

is the zero morphism. Then we also have

$$\displaystyle \begin{aligned}S^{M,\delta} \circ \kappa = \kappa(\delta) \circ S^{\ker f,\delta}=0.\end{aligned}$$

The universal property of the kernel monomorphism μ thus provides a unique morphism \(v:\ker f \to \ker {S^{M,\delta }}\) such that κ = μ ∘ v.

Since κ is a monomorphism, v must be a monomorphism too. We have r ∘ μ = 0, so

$$\displaystyle \begin{aligned} r \circ \kappa = r \circ \mu \circ v=0\end{aligned}$$

as well. Now by the universal property of q as the cokernel epimorphism of κ, there is a unique epimorphism \(p: \operatorname {\mathrm {\operatorname {im}}} f \to \operatorname {\mathrm {\operatorname {im}}} {S^{M,\delta }}\) such that r = p ∘ q.

To show that (ii) implies (i), assume that there is an epimorphism p factoring r = p ∘ q. We have q ∘ κ = 0, so

$$\displaystyle \begin{aligned}r \circ \kappa = p \circ q \circ \kappa=0\end{aligned}$$

as well. Thus

$$\displaystyle \begin{aligned}S^{M,\delta} \circ \kappa = \kappa(\delta) \circ S^{\ker f,\delta}=0,\end{aligned}$$

and since κ(δ) is a monomorphism, this implies that \(S^{\ker f,\delta }=0\). □

3.4 Proof of the Induced Matching Theorem

To prove the induced matching theorem (Theorem 2) we will need the following lemma, which follows easily from the definition of induced matchings and the structure theorem for persistence modules (Theorem 4).

Lemma 2

For any p.f.d. persistence module M, we have \(S^{\mathcal B(M),\delta }=\mathcal X(S^{M,\delta })\).

Proof of Theorem 2 (Induced Matching Theorem)

We prove (i); the proof dualizes to a proof of (ii). Write s = S M, δ, and let f = i ∘ q and s = j ∘ r be the epi-mono factorizations. By Lemma 1, we obtain an epimorphism \(p: \operatorname {\mathrm {\operatorname {im}}} f \twoheadrightarrow \operatorname {\mathrm {\operatorname {im}}} s\) such that the following diagram commutes:

By Theorem 1 and the way we construct induced matchings, we have epi-mono factorizations \(\mathcal X(f)=\mathcal X(i)\circ \mathcal X(q)\) and \(\mathcal X(s) = \mathcal X(j)\circ \mathcal X(r)\). Moreover, \(\mathcal X\) is functorial on epimorphisms by Theorem 1, so the following diagram also commutes:

By Lemma 2, we have \(S^{\mathcal B(M),\delta } = \mathcal X(s)\). Thus, since epi-mono factorizations are unique (up to unique isomorphism), we have \( \operatorname {\mathrm {\operatorname {im}}} S^{\mathcal B(M),\delta } = \mathcal B( \operatorname {\mathrm {\operatorname {im}}} s), \) and \(\mathcal X(r)\) is the image epimorphism \(\mathcal B(M)\twoheadrightarrow \operatorname {\mathrm {\operatorname {im}}} S^{\mathcal B(M),\delta }\). Since \(\mathcal X(r)=\mathcal X(q)\circ \mathcal X(p)\), Lemma 1 now gives that \(\ker \mathcal X(f)\) is δ-trivial, as desired. □

3.5 Converse to the Induced Matching Theorem

Letting Vect denote the category of (not necessarily finite dimensional) vector spaces over the field K. We have a functor Fr : Mch →Vect, which takes a set S to the vector space with basis S. Let ζ : Barc →Vect denote the functor which sends a barcode \(\mathcal C\) to \(\mathrm {Fr}\circ E(\mathcal C)\).

It is easy to prove the following converse to the induced matching theorem:

Proposition 4

  1. (i)

    \(\zeta (\mathcal B(M))\cong M\) for any p.f.d. persistence module M.

  2. (ii)

    If \(f:\mathcal C \to \mathcal D\)is a morphism inBarcwith δ-trivial (co)kernel, then ζ(f) has δ-trivial (co)kernel as well.

4 Interleavings of Barcodes and the Bottleneck Distance

In this section, we consider interleavings and the bottleneck distance on barcodes. We observe that the bottleneck distance can be interpreted as an interleaving distance, and we prove the algebraic stability theorem.

4.1 Interleavings

4.1.1 Interleavings of R-Indexed Diagrams

The definition of interleavings of R-indexed diagrams was introduced in [8], building on ideas in [9], and was first stated in categorical language in [4]. Though interleavings over more general indexing categories can be defined and are also of interest in TDA [5, 11, 15, 19], we focus here on the R-indexed case. We use the definitions and notation introduced in Sect. 3.3.

Definition 6 (Interleavings and Interleaving Distance)

A δ-interleaving between two diagrams M, N : R →A is a pair of natural transformations

$$\displaystyle \begin{aligned}f: M \to N(\delta),\quad g: N \to M(\delta)\end{aligned}$$

such that g(δ) ∘ f = S M, 2δ and f(δ) ∘ g = S N, 2δ. We call f and gδ-interleaving morphisms.

The interleaving distance on objects of A R is then given by

$$\displaystyle \begin{aligned}d_I(M,N):=\inf\, \{\delta\geq 0\mid M\ \mbox{ and }\ N\ \mbox{ are }\ \delta\ \mbox{-interleaved}\}.\end{aligned}$$

4.1.2 Interleavings in Barc

Note that as for natural transformations of R-indexed diagrams, an overlap matching \(f:\mathcal C\to \mathcal D\) induces an overlap matching \(f(\delta ):\mathcal C(\delta )\to \mathcal D(\delta )\). We define a δ-interleaving between barcodes \(\mathcal C\) and \(\mathcal D\) to be a pair of overlap matchings

$$\displaystyle \begin{aligned}f:\mathcal C\to \mathcal D(\delta),\qquad g:\mathcal D\to \mathcal C(\delta)\end{aligned}$$

such that , and . This definition is equivalent to the definition of interleavings in Mch R in the sense that a pair of overlap matchings f, g is a δ-interleaving if and only if the pair E(f), E(g) is a δ-interleaving in Mch R.

4.1.3 Interleavings and Smallness of Kernels

It is easily checked that for A a Puppe-exact category, a δ-interleaving morphism f : M → N(δ) has 2δ-trivial kernel and cokernel. The converse is not true in general; one can easily construct a counterexample in the case that A is the category of persistence modules. However, the converse holds in the two cases studied in this paper:

Proposition 5

In both the categoriesvect RandBarc, two objects M, N are δ-interleaved if and only if there exists a morphism f : M → N(δ) with 2δ-trivial kernel and cokernel.

The statement of Proposition 5 for vect R first appeared as [1, Corollary 6.6].

Proof

The result for Barc follows easily from Proposition 2. To prove the result for vect R, we apply both the induced matching and converse algebraic stability theorems: If f : M → N(δ) is a morphism with 2δ-trivial kernel and cokernel, then by Theorem 2, \(\mathcal X(f)\) has the same property. Hence \(\mathcal X(f)\) is a δ-interleaving morphism. The converse direction of Theorem 3 (whose easy proof we give below) then tells us that M and N are δ-interleaved. □

4.2 Algebraic Stability

4.2.1 Bottleneck Distance

For \(I\subset \mathbb R\) an interval and δ ≥ 0, let the interval U δ(I) be given by

$$\displaystyle \begin{aligned}U_\delta(I):=\{t\in \mathbb R\mid \exists\, s\in I\mbox{ with }|s-t|\leq \delta\}.\end{aligned}$$

We define a δ-matching between barcodes \(\mathcal C\) and \(\mathcal D\) to be a (not necessarily overlap) matching \(\sigma :\mathcal C \to \mathcal D\) with the following two properties:

  • σ matches each interval in \(\mathcal C \cup \mathcal D\) that is not 2δ-trivial,

  • if σ(I) = J, then I ⊂ U δ(J) and J ⊂ U δ(I).

We define the bottleneck distanced B by taking

$$\displaystyle \begin{aligned}d_B(\mathcal C,\mathcal D):=\inf\, \{\delta\geq 0\mid\exists\mbox{ a }\delta\mbox{-matching between }\mathcal C\mbox{ and }\mathcal D\}.\end{aligned}$$

4.2.2 Interleaving Distance Equals Bottleneck Distance on Barcodes

For \(\mathcal D\) any barcode, let \(r_\delta :\mathcal D(\delta )\to \mathcal D\) be the obvious bijection.

Proposition 6

An overlap matching of barcodes \(f:\mathcal C\to \mathcal D(\delta )\)is a δ-interleaving morphism if and only if r δ ∘ f is a δ-matching. In particular, for any barcodes \(\mathcal C\)and \(\mathcal D\),

$$\displaystyle \begin{aligned}d_I(\mathcal C,\mathcal D)=d_B(\mathcal C,\mathcal D).\end{aligned}$$

Proof

According to Proposition 5, an overlap matching \(f:\mathcal C\to \mathcal D(\delta )\) is a δ-interleaving morphism if and only if f has 2δ-trivial kernel and cokernel. In addition, it is easy to check that an overlap matching \(f:\mathcal C\to \mathcal D(\delta )\) has 2δ-trivial kernel and cokernel if and only if r δ ∘ f is a δ-matching. □

We are now deduce the algebraic stability theorem as a corollary of the induced matching theorem. Figure 5 illustrates the barcode matching underlying the argument.

Fig. 5
figure 5

Illustration of the proof of algebraic stability via induced matchings. For a δ-interleaving morphism of persistence modules f : M → N, the barcodes of M, \( \operatorname {\mathrm {\operatorname {im}}} f\), N(δ), and N are shown as persistence diagrams, which are multisets of points in the plane whose coordinates correspond to the left and right endpoints of the intervals. The dotted lines in the figure depict the induced matching \(\mathcal B(M) \to \mathcal B( \operatorname {\mathrm {\operatorname {im}}} f) \to \mathcal B(N(\delta )) \to \mathcal B(N)\). The shaded box around each point \(p\in \mathcal B(M)\cup \mathcal B(N)\) indicates the set of points to which p can match in a δ-matching

Full size image

Proof of Theorem 3 (Algebraic Stability)

The forward direction follows almost immediately from the induced matching theorem: If there exists a δ-interleaving morphism f : M → N(δ), then f has 2δ-trivial kernel and cokernel. By Theorem 2, the same is true for \(\mathcal X(f):\mathcal B(M)\to \mathcal B(N(\delta ))\). Since \(\mathcal B(N(\delta ))=\mathcal B(N)(\delta )\), Proposition 5 tells us that \(\mathcal B(M)\) and \(\mathcal B(N)\) are δ-interleaved in Barc.

The proof of converse algebraic stability is nearly trivial: Given a δ-interleaving

$$\displaystyle \begin{aligned}f:\mathcal B(M)\to \mathcal B(N)(\delta),\quad g:\mathcal B(N)\to \mathcal B(M)(\delta),\end{aligned}$$

ζ(f) and ζ(g) form a δ-interleaving in vect R; here ζ is the functor defined in Sect. 3.5. By Proposition 4 (i) then, M and N are δ-interleaved. □

5 Constructing Barcodes and Induced Matchings in Mch R

In this section, we consider the construction of barcodes of persistence modules and induced matchings directly in the category of matching diagrams Mch R. Our barcode constructions come in two dual (canonically isomorphic) variants, which are readily extended to functors on epis and monos, respectively. These functors are equivalent to the induced matchings for epis and monos described in Sect. 3.2 and lead naturally to an alternate proof of Theorem 1.

Let M be a p.f.d. persistence module. We now construct a matching diagram \(D^\twoheadrightarrow (M)\) equivalent to \(\mathcal B(M)\) in a way that depends only on the ranks of the internal maps of M. While our construction does not require an interval decomposition of M, the intuition is best conveyed by assuming initially that we have this.

Order the intervals in \(\mathbb R\) lexicographically, first by increasing lower bound, then (for intervals with the same lower bound) by decreasing upper bound, as shown in Fig. 6. For example, with respect to this order, we have

$$\displaystyle \begin{aligned}{}[0,3]<[1,2]<(1,3]<(1,2]. \end{aligned}$$

Now at each index t, enumerate the intervals of \(\mathcal B(M)\) containing t in that order. This defines a canonical bijection \(g_t \colon E(\mathcal B(M))_t \to D^\twoheadrightarrow (M)_t\) between the set \(E(\mathcal B(M))_t\), consisting of the intervals in \(\mathcal B(M)\) containing t, and the set

$$\displaystyle \begin{aligned}D^\twoheadrightarrow(M)_t := \{1 ,2, \dots , \dim M_t \}.\end{aligned}$$

For any two indices t ≤ u, let

$$\displaystyle \begin{aligned}D^\twoheadrightarrow(M)_{t,u} := g_u^{-1} \circ E(\mathcal B(M))_{t,u} \circ g_t.\end{aligned}$$

Thus, \(D^\twoheadrightarrow (M)_{t,u}\) is the matching between the sets \(D^\twoheadrightarrow (M)_t\) and \(D^\twoheadrightarrow (M)_u\) such that under the bijections g t and g u, matched pairs correspond to intervals of \(\mathcal B(M)\) containing both t and u; see Fig. 6. By construction, the matchings \((D^\twoheadrightarrow (M)_{t,u})_{t\leq u\in \mathbb R}\) form a functor \(D^\twoheadrightarrow (M):{\mathbf {R}}\to {\mathbf {Mch}}\), and the bijections \((g_t)_{t\in \mathbb R}\) form a natural isomorphism of matching diagrams \(g:E(\mathcal B(M))\to D^\twoheadrightarrow (M)\). A dual construction, denoted by D ↪, is obtained by ordering the intervals in \(\mathbb R\) lexicographically by decreasing upper bound, then by increasing lower bound. We summarize:

Fig. 6
figure 6

Example illustrating the matching diagram \(D^\twoheadrightarrow (M)\) on top of the barcode \(\mathcal B(M)\), with intervals ordered lexicographically by increasing lower bound and deceasing upper bound. Each set \(D^\twoheadrightarrow (M)_t \subset \mathbb N\) is identified by an order-preserving bijection with the intervals of \(\mathcal B(M)\) containing t. The example shows a matching of cardinality 3, corresponding to \( \operatorname {\mathrm {rk}} M_{t,u} = 3\)

Full size image

Proposition 7

The matching diagrams \(D^\twoheadrightarrow (M)\)and D ↪(M) are naturally isomorphic to \(E(\mathcal B(M))\).

In a similar spirit, we can also map the induced matchings for epimorphisms and monomorphisms to equivalent morphisms of matching diagrams. Consider an epimorphism \(f : M \twoheadrightarrow N\) and \(D^\twoheadrightarrow (M), D^\twoheadrightarrow (N)\) as above. Now, for any \(t \in \mathbb R\), let \(g_t \colon E(\mathcal B(M))_t \to D^\twoheadrightarrow (M)_t\) and \(h_t \colon E(\mathcal B(N))_t \to D^\twoheadrightarrow (N)_t\) be the canonical bijections described above. Using the induced matching \(\mathcal X(f) \colon \mathcal B(M) \to \mathcal B(N)\) from Sect. 3.2, define

$$\displaystyle \begin{aligned}D^\twoheadrightarrow(f)_{t} := h_u^{-1} \circ E(\mathcal X(f))_{t} \circ g_t.\end{aligned} $$

See Fig. 7 for an example. For a monomorphism f, we define D ↪(f)t in an analogous way. Similarly to the above, we obtain:

Fig. 7
figure 7

Example illustrating the induced epimorphism of matching diagrams \(D^\twoheadrightarrow (f): D^\twoheadrightarrow (M) \twoheadrightarrow D^\twoheadrightarrow (N)\) and the corresponding overlap matching of barcodes \(\mathcal B(M) \twoheadrightarrow \mathcal B(N)\)

Full size image

Proposition 8

For an epimorphism \(f : M \twoheadrightarrow N\), the morphism \(D^\twoheadrightarrow (f)\)is naturally isomorphic to \(E(\mathcal X(f))\). Similarly, for a monomorphism f, the morphism D ↪(f) is naturally isomorphic to \(E(\mathcal X(f))\).

Next, we describe the matching \(D^\twoheadrightarrow (M)_{t,u}\) directly in terms of the internal maps of M, avoiding the explicit use of the barcode \(\mathcal B(M)\).

Proposition 9

For M : R →Vectbe a p.f.d. persistence module and \(t \leq u \in \mathbb R\), we have

$$\displaystyle \begin{aligned} D^\twoheadrightarrow(M)_{t,u} = \big\{(i,j) \in \mathbb N^2 \mid j &\leq \operatorname{\mathrm{rk}} M_{t,u} , \\ i &= j + \max\,\{\operatorname{\mathrm{rk}} M_{s,t} - \operatorname{\mathrm{rk}} M_{s,u} \mid s < t, \operatorname{\mathrm{rk}} M_{s,u} < j \} \big\} , \\ D^{\hookrightarrow}(M)_{t,u} = \big\{(i,j) \in \mathbb N^2 \mid i &\leq \operatorname{\mathrm{rk}} M_{t,u} , \\ j &= i + \max\,\{\operatorname{\mathrm{rk}} M_{u,v} - \operatorname{\mathrm{rk}} M_{t,v} \mid v > u, \operatorname{\mathrm{rk}} M_{t,v} < i \} \big\} , \end{aligned} $$

(where the maximum over an empty set is taken to be 0).

Proof

We first observe that the image of \(D^\twoheadrightarrow (M)_{t,u}\) is precisely the set \( \{j \mid j \leq \operatorname {\mathrm {rk}} M_{t,u}\}. \) To see this, note that \( \operatorname {\mathrm {rk}} M_{t,u}\) equals the cardinality of the matching \(E(\mathcal B(M))_{t,u}\), i.e., the number of intervals in \(\mathcal B(M)\) containing both t and u. In the lexicographic order on \(E(\mathcal B(M))_{t} \subseteq \mathcal B(M)\), those intervals precede the intervals containing u but not t. Thus, \( \operatorname {\mathrm {coim}} E(\mathcal B(M))_{t,u}\) is a prefix of \(E(\mathcal B(M))_{t}\), which is mapped by the order-preserving bijection

$$\displaystyle \begin{aligned}g_t \colon E(\mathcal B(M))_t \to D^\twoheadrightarrow(M)_t = \{1 ,2, \dots , \dim M_t \}\end{aligned}$$

to the prefix \(D^\twoheadrightarrow (M)_{t,u} = \{j \mid j \leq \operatorname {\mathrm {rk}} M_{t,u}\}\).

Next, in order to determine for a given matched number \(j \in \operatorname {\mathrm {\operatorname {im}}} D^\twoheadrightarrow (M)_{t,u}\) the corresponding number \(i \in D^\twoheadrightarrow (M)_t\) to which is it matched, we further observe that the difference i − j is precisely the number of intervals of \(\mathcal B(M)\) that

  • are born before the jth interval of \(\mathcal B(M)\) (in the lexicographic order) containing u.

  • die after t and before u.

Letting I be the jth interval of \(\mathcal B(M)\) containing u, the set of lower bounds of I in \(\mathbb R\) (i.e., the set of values \(s \in \mathbb R\) satisfying s < r for all r ∈ I) is

$$\displaystyle \begin{aligned} \{s < u \mid \operatorname{\mathrm{rk}} M_{s,u} < j\}. \end{aligned}$$

Since \(j\in \operatorname {\mathrm {\operatorname {im}}} D^\twoheadrightarrow (M)_{t,u}\), we have t ∈ I, so all of the above lower bounds s also satisfy s < t. For any lower bound s, the number of intervals of \(\mathcal B(M)\) containing both s and t but not u is

$$\displaystyle \begin{aligned}\dim (\operatorname{\mathrm{\operatorname{im}}} M_{s,t} \cap \ker M_{t,u}) = \operatorname{\mathrm{rk}} M_{s,t} - \operatorname{\mathrm{rk}} M_{s,u}.\end{aligned}$$

Hence, the number of intervals that are born before I and die after t and before u is

$$\displaystyle \begin{aligned}\max_s\,\{\operatorname{\mathrm{rk}} M_{s,t} - \operatorname{\mathrm{rk}} M_{s,u} \mid s < t,\, \operatorname{\mathrm{rk}} M_{s,u} < j \}.\end{aligned}$$

The result follows. □

In an analogous way, we also obtain formulas for \(D^\twoheadrightarrow (f)_{t}\) and D ↪(f)t in terms of the morphism f and the internal maps, which can be proven in a similar way.

Proposition 10

  1. (i)

    Let \(f: M \twoheadrightarrow N\) be an epimorphism of p.f.d. persistence modules. For \(t\in \mathbb R\) , we have

    $$\displaystyle \begin{aligned} D^\twoheadrightarrow(f)_{t} = \big\{(i,j) \in \mathbb N^2 \mid j &\leq \dim N_{t} , \\ i &= j + \max\,\{\operatorname{\mathrm{rk}} M_{s,t} - \operatorname{\mathrm{rk}} N_{s,t} \mid s < t, \operatorname{\mathrm{rk}} N_{s,t} < j \} \big\}. \end{aligned} $$
  2. (ii)

    Let \(f: M \twoheadrightarrow N\) be a monomorphism of p.f.d. persistence modules. For \(t\in \mathbb R\) , we have

    $$\displaystyle \begin{aligned} D^{\hookrightarrow}(f)_{t} = \big\{(i,j) \in \mathbb N^2 \mid i &\leq \dim M_{t} , \\ j &= i + \max\,\{\operatorname{\mathrm{rk}} N_{s,t} - \operatorname{\mathrm{rk}} M_{s,t} \mid s < t, \operatorname{\mathrm{rk}} M_{s,t} < i \} \big\}. \end{aligned} $$

Note that these formulas rely only on the existence of an epimorphism or monomorphism; the right hand sides depend only on the ranks of the internal maps of M and N, not on the morphism f.

The formulas of Proposition 9 describe the functors \(D^\twoheadrightarrow (M), D^{\hookrightarrow }(M) \colon {\mathbf {R}}\to {\mathbf {Mch}}\) in terms of ranks, and it is clear from Proposition 7 that each of these functors encodes \( \operatorname {\mathrm {rk}} M_{u,t}\) for all \(u\leq t\in \mathbb R\). In the sprit of constructing and studying \(D^\twoheadrightarrow (M)\) and D ↪(M) in a way that is independent of the structure theorem, we next give elementary proofs of these facts, proceeding directly from the description of \(D^\twoheadrightarrow (M)\) and D ↪(M) in terms of ranks.

Proposition 11

Let M : R →Vectbe a p.f.d. persistence module.

  1. (i)

    For all \(t\leq u\in \mathbb R\), the relations \(D^\twoheadrightarrow (M)_{t,u}\)and D ↪(M)t,uof Proposition 9are both order-preserving matchings. In particular, for t < u,

    $$\displaystyle \begin{aligned}\operatorname{\mathrm{card}} D^\twoheadrightarrow(M)_{t,u} = \operatorname{\mathrm{card}} D^{\hookrightarrow}(M)_{t,u} = \operatorname{\mathrm{rk}} M_{t,u} .\end{aligned}$$
  2. (ii)

    The sets and matchings of Proposition 9are functorial, i.e., they define functors

    $$\displaystyle \begin{aligned} D^\twoheadrightarrow(M),D^{\hookrightarrow}(M)&: {\mathbf{R}} \to \mathbf{Mch}. \end{aligned} $$

Proof

We prove the results for \(D^\twoheadrightarrow (M)\) only, the proof for D ↪(M) being completely analogous. Let \((i,j), (m,n) \in D^\twoheadrightarrow (M)_{t,u}\). Clearly j = n implies i = m. Moreover, if j < n, then from

$$\displaystyle \begin{aligned} i = j + \max\,\{\operatorname{\mathrm{rk}} M_{s,t} - \operatorname{\mathrm{rk}} M_{s,u} \mid s < t, \operatorname{\mathrm{rk}} M_{s,u} < j \} , \\ m = n + \max\,\{\operatorname{\mathrm{rk}} M_{s,t} - \operatorname{\mathrm{rk}} M_{s,u} \mid s < t, \operatorname{\mathrm{rk}} M_{s,u} < n \} . \end{aligned} $$

we obtain i < m. Thus \(D^\twoheadrightarrow (M)_{t,u}\) is an order-preserving matching.

In order to show functoriality of \(D^\twoheadrightarrow (M)\), we first establish that for all s < t ≤ u, we have \( \operatorname {\mathrm {rk}} M_{s,t} < i\) if and only if \( \operatorname {\mathrm {rk}} M_{s,u} < j\). To see this, note that for all s < u with \( \operatorname {\mathrm {rk}} M_{s,u} < j\), we have s < t and

$$\displaystyle \begin{aligned}i \geq j + (\operatorname{\mathrm{rk}} M_{s,t} - \operatorname{\mathrm{rk}} M_{s,u}) > \operatorname{\mathrm{rk}} M_{s,t}.\end{aligned}$$

Conversely, for all r < u with \( \operatorname {\mathrm {rk}} M_{r,u} \geq j\), we have s < r for all s < t with \( \operatorname {\mathrm {rk}} M_{s,u} < j\), which in turn by elementary linear algebra yields

$$\displaystyle \begin{aligned} \operatorname{\mathrm{rk}} M_{s,t} - \operatorname{\mathrm{rk}} M_{s,u} &= \dim (\operatorname{\mathrm{\operatorname{im}}} M_{s,t} \cap \ker M_{t,u}) \leq \dim (\operatorname{\mathrm{\operatorname{im}}} M_{r,t} \cap \ker M_{t,u}) \\ &= \operatorname{\mathrm{rk}} M_{r,t} - \operatorname{\mathrm{rk}} M_{r,u} \end{aligned} $$

and thus

$$\displaystyle \begin{aligned}i = j + \max\{\operatorname{\mathrm{rk}} M_{s,t} - \operatorname{\mathrm{rk}} M_{s,u} \mid s < t, \operatorname{\mathrm{rk}} M_{s,u} < j \} \leq j + (\operatorname{\mathrm{rk}} M_{r,t} - \operatorname{\mathrm{rk}} M_{r,u}) \leq \operatorname{\mathrm{rk}} M_{r,t} .\end{aligned}$$

We conclude that \( \operatorname {\mathrm {rk}} M_{s,t} < i \) if and only if \( \operatorname {\mathrm {rk}} M_{s,u} < j\).

It remains to show that \((i,k) \in D^\twoheadrightarrow (M)_{t,v}\) if and only if \((i,j) \in D^\twoheadrightarrow (M)_{t,u}\) and \((j,k) \in D^\twoheadrightarrow (M)_{u,v}\) for some \(j \in D^\twoheadrightarrow (M)_{u}\). First let \((i,j) \in D^\twoheadrightarrow (M)_{t,u}\) and \((j,k) \in D^\twoheadrightarrow (M)_{u,v}\). By the above we have \( \operatorname {\mathrm {rk}} M_{s,u} < j\) if and only if \( \operatorname {\mathrm {rk}} M_{s,v} < k\), and so substituting

$$\displaystyle \begin{aligned}j = k + \max\,\{\operatorname{\mathrm{rk}} M_{s,u} - \operatorname{\mathrm{rk}} M_{s,v} \mid s < t, \operatorname{\mathrm{rk}} M_{s,v} < k \}\end{aligned}$$

gives

$$\displaystyle \begin{aligned} i = k &+ \max\, \{\operatorname{\mathrm{rk}} M_{s,u} - \operatorname{\mathrm{rk}} M_{s,v} \mid s < t, \operatorname{\mathrm{rk}} M_{s,v} < k \} \\&+ \max\,\{\operatorname{\mathrm{rk}} M_{s,t} - \operatorname{\mathrm{rk}} M_{s,u} \mid s < t, \operatorname{\mathrm{rk}} M_{s,u} < j \} \\ = k &+ \max\,\{\operatorname{\mathrm{rk}} M_{s,t} - \operatorname{\mathrm{rk}} M_{s,v} \mid s < t, \operatorname{\mathrm{rk}} M_{s,v} < k \} , \end{aligned} $$

which is equivalent to \((i,k) \in D^\twoheadrightarrow (M)_{t,v}\). Conversely, given \((i,k) \in D^\twoheadrightarrow (M)_{t,v}\), the above equation for j yields \((i,j) \in D^\twoheadrightarrow (M)_{t,u}\) and \((j,k) \in D^\twoheadrightarrow (M)_{u,v}\). We conclude that \(D^\twoheadrightarrow (M)\) is a functor R →Mch. □

Similarly, we can also show directly from the description of Proposition 10 that \(D^\twoheadrightarrow (f)\) and D ↪(f) are natural transformations, turning \(D^\twoheadrightarrow \) and D ↪ into functors. We omit the proof, which is essentially the same as the proof of Proposition 11.

Proposition 12

  1. (i)

    Let \(f: M \twoheadrightarrow N\) be an epimorphism. Then, for all t, \(D^\twoheadrightarrow (f)_{t}\) is an order-preserving epimorphism in Mch . Moreover, these matchings are natural, so they define an epimorphism

    $$\displaystyle \begin{aligned}D^\twoheadrightarrow(f):D^\twoheadrightarrow(M) \twoheadrightarrow D^\twoheadrightarrow(N)\end{aligned}$$

    in a functorial way, i.e., \(D^\twoheadrightarrow (g \circ f) = D^\twoheadrightarrow (g) \circ D^\twoheadrightarrow (f)\)for any epi \(g: N \twoheadrightarrow O\).

  2. (ii)

    Let f : M↪N be a monomorphism. Then, for all t, D ↪(f)tis an order-preserving monomorphism inMch. Moreover, these matchings are natural, so they define a monomorphism

    $$\displaystyle \begin{aligned}D^{\hookrightarrow}(f):D^{\hookrightarrow}(M) \hookrightarrow D^{\hookrightarrow}(N).\end{aligned}$$

    in a functorial way, i.e., D ↪(g ∘ f) = D ↪(g) ∘ D ↪(f) for any mono g : N↪O.

Remark 4

As an aside, we note that the formulas of Propositions 10 and 11 extend to any q-tame persistence module M (i.e., one for which \( \operatorname {\mathrm {rk}}(M_{s,t})<\infty \) whenever s < t), even though the usual structure theorem for p.f.d. persistence modules does not extend to the q-tame setting [7]. However, since in this setting Proposition 7 does not apply, it is not guaranteed that the resulting matching diagrams \(D^\twoheadrightarrow (M)\) and D ↪(M) are isomorphic.

Remark 5 (Matchings Induced by Arbitrary Morphisms)

While \(D^\twoheadrightarrow (M)\) and D ↪(M) are typically not equal, we have seen above that there is a distinguished isomorphism from each of these matching diagrams to \(E(\mathcal B(M))\). This in turn gives us a distinguished isomorphism

$$\displaystyle \begin{aligned}\zeta_M:D^\twoheadrightarrow(M)\to D^{\hookrightarrow}(M).\end{aligned}$$

Using this, we can define the matching \(D^\twoheadrightarrow (M)\to D^\twoheadrightarrow (N)\) induced by a morphism f : M → N of p.f.d. persistence modules as the composition of matching diagrams

where f = i ∘ q is the epi-mono factorization of f. By construction, this is equivalent to the induced matching \(\mathcal X(f)\) in Barc. A definition of the matching D ↪(M) → D ↪(N) induced by f can be given in a similar way.

Because \(\zeta _{ \operatorname {\mathrm {\operatorname {im}}} f}\) and ζ N are defined in terms of barcodes, our definition of the matching \(D^\twoheadrightarrow (M)\to D^\twoheadrightarrow (N)\) induced by f is defined in terms of barcodes as well. This is at odds with the goal of giving a barcode-free construction of induced matchings directly in Mch R, as we have done when restricting attention to monos or epis f. However, we do not see a simple way to define the matching \(D^\twoheadrightarrow (M)\to D^\twoheadrightarrow (N)\) induced by an arbitrary morphism f without appealing to the connection with barcodes. This suggests to us that to define matchings induced by arbitrary morphisms, it is more natural to work in the category Barc, as we have done elsewhere in this paper, than to work in Mch R.

6 Discussion

In this paper, we have established some basic facts about the category Barc≅Mch R of barcodes and used these observations to give simple new formulations of the induced matching and algebraic stability theorems. We have seen that the new formulations lead to variant of the proof of the induced matching theorem which emphasizes the preservation of categorical structure.

In fact, our definition of the category Barc extends to barcodes indexed over arbitrary posets, as defined in [3], and many of the ideas presented here extend either to arbitrary posets or to R n-indexed barcodes for any n. In particular, Proposition 6 extends to R n-indexed barcodes, and this provides alternative language for expressing generalized algebraic stability results appearing in [2, 3]. While it remains to be seen what role the categorical viewpoint on barcodes might play in the further development of TDA theory, we hope that it might offer some perspective on how algebraic stability ought to generalize to other settings.

As already mentioned, our new formulations of the algebraic stability and induced matching theorems make clear that both results can be interpreted as the preservation of some categorical structure as we pass from vect R to Barc. Can more of interest be said about how the passage from persistence modules to barcodes preserves categorical structure? We wonder whether our results can be understood as part of a larger story about how homological algebra in the Abelian category vect R relates to homological algebra in Barc.