Induced Matchings and the Algebraic Stability
of Persistence Barcodes
Ulrich Bauer∗ and Michael Lesnick†

arXiv:1311.3681v4 [math.AT] 30 Apr 2016

January 26, 2015

Abstract
We define a simple, explicit map sending a morphism f : M → N of pointwise finite
dimensional persistence modules to a matching between the barcodes of M and N. Our
main result is that, in a precise sense, the quality of this matching is tightly controlled by the
lengths of the longest intervals in the barcodes of ker f and coker f .
As an immediate corollary, we obtain a new proof of the algebraic stability theorem for
persistence barcodes [7, 10], a fundamental result in the theory of persistent homology. In
contrast to previous proofs, ours shows explicitly how a δ-interleaving morphism between
two persistence modules induces a δ-matching between the barcodes of the two modules. Our
main result also specializes to a structure theorem for submodules and quotients of persistence
modules, and yields a novel “single-morphism” characterization of the interleaving relation
on persistence modules.

1

Introduction

Persistent homology, a topological tool for analyzing the global, non-linear, geometric features
of data, is one of the primary objects of study in applied topology. It provides simple, readily
computed invariants, called barcodes, of a variety of types of data, such as finite metric spaces
and R-valued functions. A barcode is simply a collection of intervals in R; we regard each interval
as the lifespan of a topological feature of our data, and we interpret the length of the interval as a
measure of the significance of that feature.
To obtain a barcode from data, we proceed in three steps:
1. We first associate to the data a filtration, a family of topological spaces F = {Ft }t∈R such
that F s ⊆ Ft whenever s ≤ t. For example, if our data is a function γ : T → R, we may
take F = Sγ , where
γ
St = {x ∈ T | γ(x) ≤ t};
we call Sγ the sublevel set filtration of γ.
∗
†

Technische Universität München, Germany. mail@ulrich-bauer.org
Institute for Mathematics and its Applications, Minneapolis, MN, USA. mlesnick@ima.umn.edu

1

2. We then apply ith singular homology with coefficients in a field to each space Ft and each
inclusion F s ,→ Ft . This yields a persistence module Hi (F) for any i ≥ 0, i.e., a diagram
of vector spaces indexed by the totally ordered set R.
3. A persistence module M is said to be pointwise finite dimensional (p.f.d.) if each of the
vector spaces Mt is finite dimensional. The structure theorem of [16] yields a barcode
invariant B M of any p.f.d. persistence M; B M specifies the decomposition of M into
indecomposable summands. Thus, under mild assumptions on F, we obtain a barcode
invariant BHi (F) of our data for each i ≥ 0.
In the last fifteen years, these invariants have been applied widely to the study of scientific data
[5, 19], and have been the subject of a great deal of theoretical interest.
The Algebraic Stability Theorem In 2005, Cohen-Steiner, Edelsbrunner, and Harer introduced a stability result for the persistent homology of R-valued functions [14]. In brief, the result
tells us that the map sending an R-valued function to its persistence barcode is 1-Lipschitz with
respect to suitable choices of metrics.
In 2009, Chazal, Cohen-Steiner, Glisse, Guibas, and Oudot showed that the stability result of
[14] admits a purely algebraic generalization [7]. This generalization, known as the algebraic
stability theorem, asserts that if there exists a δ-interleaving (a sort of “approximate isomorphism”)
between two p.f.d. persistence modules M, N, then there exists a δ-matching (approximate
isomorphism) between the barcodes B M , BN of these persistence modules.
The algebraic stability theorem is perhaps the central theorem in the theory of persistent
homology. It provides the core mathematical justification for the use of persistent homology in
the study of noisy data. The theorem is used, in one form or another, in nearly all available results
on the approximation, inference, and estimation of persistent homology. It has also been the basis
for much subsequent theoretical work on persistence.
While the earlier stability result for the persistent homology of R-valued functions [14] is itself
a powerful result with several important applications, the more general algebraic stability theorem
offers significant advantages. First, it allows us to dispense with some technical conditions on the
stability result for functions of [14], thereby yielding a generalization of that result to a wider
class of functions. Second and perhaps more importantly, the algebraic stability theorem offers a
formalism for comparing the barcode invariants of functions defined on different domains, or for
comparing barcode invariants of data that do not directly arise from functions at all. In practice,
this added flexibility is quite valuable: It allows us to establish fundamental approximation and
inference theorems for persistent homology that would otherwise be much harder to come by
[8, 9, 11, 13, 20]. For one example, the algebraic stability theorem has been applied to establish
the consistency properties of Rips complex-based estimators for the persistent homology of
probability density functions [11].
The Isometry Theorem In fact, the converse to the algebraic stability theorem also holds:
There exists a δ-interleaving between p.f.d. persistence modules M and N if and only if there
exists a δ-matching between B M and BN . The algebraic stability theorem and its converse are
together known as the isometry theorem. A slightly weaker formulation of the isometry theorem
2

establishes a relationship between the interleaving distance (a pseudometric on persistence
modules) and the bottleneck distance (a widely studied pseudometric on barcodes): It says that
the interleaving distance between M and N is equal to the bottleneck distance between B M and
BN .
Given the structure theorem for persistence modules [16], the converse algebraic stability
theorem admits a very simple, direct proof. The converse was first proven for p.f.d. persistence
modules in [23]. Later proofs appeared, independently, in [10] (in a slightly more general setting),
and in [4] (in a special case). We give the proof of the converse algebraic stability theorem in
Section 8, following [23].
The isometry theorem is interesting in part because the definition of the interleaving distance
extends to a variety of generalized persistence settings where the direct definition of the bottleneck
distance does not. For example, interleaving distances can be defined on multidimensional
persistence modules [23] and filtrations [3, 7, 22]. The isometry theorem thus suggests one way
to extend the definition of the bottleneck distance to these settings. Since much of the theory of
topological data analysis is formulated in terms of the bottleneck distance [9, 11, 13, 21], this
opens the door to the adaptation of the theory to more general settings.
Interleaving distances on multidimensional persistence modules and filtered topological
spaces satisfy universal properties, indicating that they are, in certain relative senses, the “right”
generalizations of the bottleneck distance [3, 22, 23].
Earlier Proofs of the Algebraic Stability Theorem The original proof of the algebraic stability theorem is an algebraic adaptation of the stability argument for the persistent homology of
functions given in [14]. Owing to its geometric origins, this argument has a distinctly geometric
flavor. In particular, the argument employs an (algebraic) interpolation lemma for persistence
modules inspired by an interpolation construction for functions appearing in [14].
In 2012, Chazal, Glisse, de Silva, and Oudot [10] presented a reworking of the original proof
of algebraic stability as part of an 80-page treatise on persistence modules, barcodes, and the
isometry theorem. The reworked proof is similar on a high level to the original, but differs in
the details. In particular, it makes use of a characterization of barcodes in terms of rectangle
measures; these are functions from the set of rectangles in the plane to N ∪ {∞} which have
properties analogous to those of a measure.
The original proof of [7] and the proof given in [10] are, to the best of our knowledge, the only
proofs of the algebraic stability theorem in the literature. However, in unpublished work from
2011, Guillaume Troianowski and Daniel Müllner gave a third proof which, in contrast to the
proofs of [7] and [10], establishes the theorem as a corollary of a general fact about persistence
modules.
First, in early 2011, Troianowski showed that if f : M → N is a morphism of persistence
modules such that the length of each interval in the barcodes Bker f and Bcoker f is at most , then
the bottleneck distance between B M and BN is at most 2. Troianowski never made this result
public, but he mentioned it to the second author of this paper. Troianowski’s result implies that if
the interleaving distance between M and N is δ, then the bottleneck distance between B M and
BN is at most 4δ. The result thus implies the algebraic stability theorem, up to a factor of 4.
As we were putting the finishing touches on the present paper, we learned that in a September
3

2011 manuscript never made public [24], Müllner and Troianowski strengthened Troianowksi’s
result to show that under the same assumptions on ker f and coker f as above, the bottleneck
distance between B M( 2 ) and BN is at most 2 ; here M( 2 ) denotes the shift of the persistence
module M to the left by 2 . This stronger result implies the algebraic stability theorem. In turn,
the results of the present paper, obtained independently of [24], strengthen those of [24].
The proof of Müllner and Troianowski’s result is an adaptation of the original proof of the
algebraic stability theorem, and closely follows the technical details of that proof. The three
existing proofs of algebraic stability are thus rather similar to one another. In particular, each
relies in an essential way on some version of the interpolation lemma.
The interpolation lemma is interesting and pretty in its own right, and variants of it have
found applications apart from the proof of algebraic stability [17, 23]. However, reliance on
the interpolation lemma makes the existing proofs of algebraic stability rather indirect: Given a
pair of δ-interleaved persistence modules M and N, these proofs construct a δ-matching between
B M and BN only implicitly, and in a roundabout way, requiring several technical lemmas, a
compactness argument, and consideration of a sequence of interpolating barcodes.

1.1

Induced Matchings of Barcodes

It is natural to ask whether there exists a more direct proof of the algebraic stability theorem
which associates to a δ-interleaving between two persistence modules a δ-matching between their
barcodes in a simple, explicit way.
We present such a proof in this paper. To do so, we define a map X sending each morphism
f : M → N of pointwise finite dimensional persistence modules to a matching X f between
the barcodes B M and BN . This map X is not functorial in general; in fact, we prove that it
is impossible to define such a map in a fully functorial way. However, X is functorial on the
two subcategories of persistence modules whose morphisms are the monomorphisms and the
epimorphisms, respectively. X f is completely determined by the barcodes B M , BN , and Bim f ,
and also completely determines these three barcodes.
The Induced Matching Theorem We establish the algebraic stability theorem for pointwise
finite dimensional persistence modules as an immediate corollary of a general result about the
behavior of the matching X f . This result, which we call the induced matching theorem, tells us
that the quality of the matching X f is tightly controlled by the lengths of the longest intervals in
the barcodes Bker f and Bcoker f . Roughly, it says that for any pair (I, J) ∈ B M × BN of intervals
matched by X f ,
(i) J is obtained from I by moving both the left and right endpoints of I to the left,
(ii) if each interval in Bker f is of length at most , then X f matches all intervals in BN of length
greater than , and the right endpoints of I and J differ by at most , and
(iii) dually, if each interval in Bcoker f is of length at most , then X f matches all intervals in B M
of length greater than , and the left endpoints of I and J differ by at most .
We give the precise statement of the theorem in Section 6.
4

Figure 1: The relationship between a pair of intervals matched by X f , as described by the induced
matching theorem.

A Structure Theorem for Persistence Submodules and Quotients Our proof of the induced
matching theorem uses none of the technical intermediates appearing in the earlier proofs of the
algebraic stability theorem. Instead, our proof centers on an easy but apparently novel structure
theorem for submodules and quotients of persistence modules. This structure theorem is in fact
the specialization of the induced matching theorem to the cases ker f = 0 and coker f = 0,
corresponding to  = 0 in (ii) and (iii) above. A slightly weaker version of our structure theorem
appears, independently, in the unpublished manuscript [24], with a different proof.
Roughly, the structure theorem says that for p.f.d. persistence modules K ⊆ M, there exist
canonical choices of
(i) an injection BK ,→ B M mapping each interval I ∈ BK to an interval in B M which contains
I and has the same right endpoint as I,
(ii) an injection B M/K ,→ B M mapping each interval I ∈ B M/K to an interval in B M which
contains I and has the same left endpoint as I.

Figure 2: Intervals in the barcodes BK and B M/K , together with their images under the canonical injections
BK ,→ B M and B M/K ,→ B M .

Our definition of the matching X f induced by a morphism f : M → N of persistence modules
is derived from the definitions of these canonical injections in a simple way. We consider the
canonical factorization of f through its image,
M  im f ,→ N.
Note that im f is a submodule of N, and up to isomorphism, im f is also a quotient of M. Thus,
the structure theorem gives us canonical injections B M ←- Bim f and Bim f ,→ BN , which we can
interpret as matchings. We define the matching X f as a composition of these two matchings. See
Sections 2.2, 4 and 5 for the formal definitions.
A Single-Morphism Characterization of the Interleaving Relation As an easy corollary of
the induced matching theorem and the converse algebraic stability theorem, we obtain a novel
characterization of interleaved pairs of persistence modules: for any δ ≥ 0, two p.f.d. persistence
modules M and N are δ-interleaved if and only if there exists a morphism f : M → N(δ) such
that all intervals in Bker f and Bcoker f are of length at most 2δ.
5

Figure 3: The matching X f between B M and BN is defined via the canonical injections B M ←- Bim f and
Bim f ,→ BN .

The Isometry Theorem for q-Tame Persistence Modules Because of the structure theorem
[16] and the induced matching theorem, which hold for p.f.d. persistence modules, the setting of
p.f.d. persistence modules is a very convenient one in which to formulate the isometry theorem.
In particular, in this setting we can formulate a sharp version of the isometry theorem, which
appears here for the first time; see Remark 3.4 and Theorem 3.5.
On the other hand, as explained in [10, 13], there is good reason to want a version of the
isometry theorem for q-tame persistence modules. These are persistence modules M for which
the maps M s → Mt are of finite rank whenever s < t ∈ R. Clearly, any p.f.d. persistence modules
is q-tame. q-tame persistence modules that are not necessarily p.f.d. arise naturally in the study
of compact metric spaces and continuous functions on compact triangulable spaces [10, 13].
With this in mind, [10, Theorem 4.11] presents a version of the isometry theorem for q-tame
persistence modules. The chief difficulty in this, relative to the p.f.d. case, is in selecting a suitable
definition the barcode of a q-tame persistence module; see Section 7 and [12].
In Sections 7 and 8, we show that [10, Theorem 4.11] follows easily from the isometry
theorem for p.f.d. persistence modules. In particular, we make clear in Section 7 that the algebraic
stability theorem for q-tame persistence modules is an easy corollary of the induced matching
theorem.

2

Preliminaries

This section presents the basic definitions and notation that we will use throughout the paper.

2.1

Persistence Modules and Barcodes

Persistence Modules For K a field, let Vect denote the category of vector spaces over K, and
let vect ⊂ Vect denote the subcategory of finite dimensional vector spaces. Let R denote the real
numbers, considered as a poset category. That is, homR (s, t) consists of a single morphism for
s ≤ t and is empty otherwise.
As indicated in Section 1, a persistence module is a diagram of K-vector spaces indexed by
R, i.e., a functor R → Vect. The persistence modules form a category VectR whose morphisms
are natural transformations.
Concretely, this means that a persistence module M assigns to each t ∈ R a vector space Mt ,
and to each pair s ≤ t ∈ R a linear map ϕ M (s, t) : M s → Mt in such a way that for all
r ≤ s ≤ t ∈ R,
ϕ M (t, t) = Id Mt

and

ϕ M (s, t) ◦ ϕ M (r, s) = ϕ M (r, t).

6

We call the maps ϕ M (s, t) transition maps. In this notation, a morphism f : M → N of persistence
modules is exactly a collection of maps { ft : Mt → Nt }t∈R such that for all s ≤ t ∈ R the following
diagram commutes:
Ms

ϕ M (s, t)

fs

Ns

Mt
ft

ϕN (s, t)

Nt

We say f is a monomorphism (epimorphism) if ft is an injection (surjection) for all t ∈ R.
As already noted, we say M is pointwise finite dimensional (p.f.d.) if dim Mt < ∞ for
all t ∈ R. Let vectR denote the full subcategory of VectR whose objects are p.f.d. persistence
modules.
Interval Persistence Modules We say I ⊆ R is an interval if I is non-empty and r, t ∈ I implies
s ∈ I whenever r ≤ s ≤ t. Let IR denote the set of all intervals in R. For I ∈ IR , define the
interval persistence module C(I) by



K if t ∈ I,
C(I)t = 

0 otherwise.



IdK if s, t ∈ I,
ϕC(I) (s, t) = 

0
otherwise.
Multisets Informally, a multiset is a collection where elements may repeat multiple times. For
example, {x, x, y} is a multiset, where the element x appears with multiplicity 2 and the element y
appears with multiplicity 1.
Formally, a multiset is a pair (S , m), where S is a set and m : S → N is a function. Here
N denotes the positive integers. One sometimes also allows m to take values in a larger set of
cardinals, but we will not do that here.
For a multiset S = (S , m) define the representation of S to be the set
Rep(S) = {(s, k) ∈ S × N | k ≤ m(s)}.
We will generally work with multisets by way of their representations.
Barcodes We define a barcode to be the representation of a multiset of intervals in R. In
the literature, barcodes are also often called persistence diagrams. Formally, the elements of a
barcode are pairs (I, k), with I ∈ IR and k ∈ N. In what follows, we will denote an element (I, k)
of a barcode simply as I, suppressing the index k, and call such an element an interval.
Using [1, Theorem 1], the authors of [10] observe that in general, if M is a (not necessarily
p.f.d.) persistence module such that
M
M
C(I)
I∈B M

for some barcode B M , then B M is uniquely determined. We say that M is interval-decomposable
and call B M the barcode of M.
7

Theorem 2.1 (Structure of p.f.d. Persistence Modules [16]). Any p.f.d. persistence module is
interval-decomposable.

2.2

The Category of Matchings

A matching from S to T (written as σ : S → T ) is a bijection σ : S 0 → T 0 , for some S 0 ⊆ S ,
T 0 ⊆ T ; we denote S 0 as coim σ and T 0 as im σ. Formally, we regard σ as a relation σ ⊆ S × T ,
where (s, t) ∈ σ if and only if s ∈ coim σ and σ(s) = t. We define the reverse matching
rev σ : T → S in the obvious way. Note that any injective function is in particular a matching.
For matchings σ : S → T and τ : T → U, we define the composition τ ◦ σ : S → U as
|

|

|

|

|

τ ◦ σ = {(s, u) | (s, t) ∈ σ, (t, u) ∈ τ for some t ∈ T }.
As noted in [20], with this definition we obtain a category Mch whose objects are sets and whose
morphisms are matchings.
Given a matching σ : S → T , there is a canonical matching S → coim σ; this matching is the
categorical coimage of σ in Mch. Similarly, the canonical matching im σ → T is the categorical
image of σ in Mch. This justifies our choice of notation for coim σ and im σ.
|

|

|

2.3

Decorated Endpoints and Intervals

As noted in the introduction, our main results concern matchings of barcodes that move endpoints
of intervals in controlled ways. To make the notion of moving the endpoints of intervals precise
in the R-indexed setting, we need some formalism.
Let D = {−, +}. Adopting a notational and terminological convention of [10], we define the
set E of (decorated) endpoints by E = R × D ∪ {−∞, ∞}. For t ∈ R, we will write the decorated
endpoints (t, −) and (t, +) as t− and t+ , respectively.
We define a total order on D by taking − < +. The lexicographic total ordering on R × D then
extends to a total ordering on E by taking −∞ to be the minimum element and taking ∞ to be the
maximum element.
We define an addition operation ( · ) + ( · ) : E × R → E by taking s± + t = (s + t)± and
±∞ + t = ±∞ for all s, t ∈ R. We define a subtraction operation ( · ) − ( · ) : E × R → E by taking
e − t = e + (−t) for (e, t) ∈ E × R.
There is a sensible bijection from the set {(b, d) ∈ E × E | b < d} to IR , the set of intervals
in R, so that we may regard intervals as ordered pairs of decorated endpoints. This bijection is
specified by the following table:
−∞
s−
s+

t−
(−∞, t)
[s, t)
(s, t)

t+
(−∞, t]
[s, t]
(s, t]

∞
(−∞, ∞)
[s, ∞)
(s, ∞)

For example, for s < t ∈ R the bijection sends (s+ , t− ) to the interval (s, t) and sends (s− , s+ ) to
the one-point interval [s, s]. We will always denote the interval specified by b < d as hb, di to
avoid confusion with the usual notation for open intervals. Note that hb, di ⊆ hb0 , d0 i whenever
b0 ≤ b < d ≤ d 0 .
8

3

The Isometry Theorem

In this section we give the precise statement of the isometry theorem for p.f.d. persistence modules.
We discuss the isometry theorem for q-tame persistence modules in Sections 7 and 8.

3.1

Interleavings and the Interleaving Distance

Distances An extended pseudometric on a class X is a function d : X × X → [0, ∞] with the
following three properties:
1. d(x, x) = 0 for all x ∈ X,
2. d(x, y) = d(y, x) for all x, y ∈ X,
3. d(x, z) ≤ d(x, y) + d(y, z) for all x, y, z ∈ X such that d(x, y), d(y, z) < ∞.
Note that an extended pseudometric d is a metric if d is finite and d(x, y) = 0 implies x = y. In
this paper, by a distance we will mean an extended pseudometric.
Shift Functors For δ ∈ R, we define the shift functor ( · )(δ) : VectR → VectR as follows: For
M a persistence module we let M(δ) be the persistence module such that for all t ∈ R we have
M(δ)t = Mt+δ , and for all s ≤ t ∈ R we have ϕ M(δ) (s, t) = ϕ M (s + δ, t + δ). For a morphism
f ∈ hom(VectR ) we define f (δ) by taking f (δ)t = ft+δ . Note that the barcode B M(δ) is obtained
from B M by shifting all intervals to the left by δ, as in Fig. 4.

Figure 4: Corresponding intervals in B M and B M(δ) .

Transition Morphisms For M a persistence module and δ ≥ 0, let the δ-transition morphism
ϕδM : M → M(δ) be the morphism whose restriction to Mt is the linear map ϕ M (t, t + δ), for all
t ∈ R.
Interleavings We say that two persistence modules M and N are δ-interleaved if there exist
morphisms f : M → N(δ) and g : N → M(δ) such that
g(δ) ◦ f = ϕ2δ
M,
f (δ) ◦ g = ϕ2δ
N.
We refer to such f and g as δ-interleaving morphisms. The definition of δ-interleaving morphisms
was introduced in [7].
Remark 3.1. It is easy to show that if L and M are δ-interleaved, and M and N are δ0 -interleaved,
then L and N are (δ + δ0 )-interleaved. Similarly, if 0 ≤ δ ≤ δ0 and M and N are δ-interleaved,
then M and N are also δ0 -interleaved.
9

Example 3.2. Here is one of the central examples of a δ-interleaving in topological data analysis:
For T a topological space and functions γ, κ : T → R, let
d∞ (γ, κ) = sup |γ(y) − κ(y)|.
y∈T

Suppose d∞ (γ, κ) = δ. Then for each t ∈ R, we have inclusions
γ

St ⊆ Sκt+δ ,
γ

Sκt ⊆ St+δ .

Applying the ith homology functor with coefficients in K to the collection of all such inclusion
maps yields a δ-interleaving between Hi (Sγ ) and Hi (Sκ ).
The Interleaving Distance We define dI : obj(VectR ) × obj(VectR ) → [0, ∞], the interleaving
distance, by taking
dI (M, N) = inf {δ ∈ [0, ∞) | M and N are δ-interleaved}.
It is not hard to check that dI is a distance on persistence modules. In addition, if M, M 0 , and N
are persistence modules with M  M 0 , then dI (M, N) = dI (M 0 , N), so dI descends to a distance
on isomorphism classes of persistence modules.

3.2 δ-Matchings and the Bottleneck Distance
For D a barcode and  ≥ 0, let
D = {hb, di ∈ D | b +  < d} = {I ∈ D | [t, t + ] ⊆ I for some t ∈ R}.
Note that D0 = D. We define a δ-matching between barcodes C and D to be a matching
σ : C → D such that
|

1. C2δ ⊆ coim σ,
2. D2δ ⊆ im σ,
3. if σhb, di = hb0 , d0 i, then
hb, di ⊆ hb0 − δ, d0 + δi,
hb0 , d0 i ⊆ hb − δ, d + δi.
See Fig. 5 for an example.
Remark 3.3. Note that for barcodes C, D, and E, σ1 : C → D a δ1 -matching, and σ2 : D → E
a δ2 -matching, σ2 ◦ σ1 : C → E is a (δ1 + δ2 )-matching.
|

|

We define the bottleneck distance dB by
dB (C, D) = inf {δ ∈ [0, ∞) | ∃ a δ-matching between C and D}.
The triangle inequality for dB follows immediately from Remark 3.3.
dB is the most commonly considered distance on barcodes in the persistent homology literature. This is in part because dB is especially well behaved from a theoretical standpoint.
10

Figure 5: A δ-matching between two barcodes C and D. Endpoints of matched intervals are at most δ
apart, and unmatched intervals are of length at most 2δ.

Remark 3.4. Our definition of a δ-matching is slightly stronger than the one appearing in [10,
Section 4.2], which is insensitive to the decoration of the endpoints of intervals. Using the
stronger definition of δ-matching allows us to state slightly sharper stability results. However,
regardless of which definition of δ-matching one uses, the definition of the bottleneck distance
one obtains is the same.
Bottleneck Distance as an Interleaving Distance As an aside, note that we can regard a
barcode D as an object in MchR , the category whose objects are functors R → Mch and whose
morphisms are natural transformations: For each real number t we let Dt be the subset of D
consisting of all intervals which contain t, and for each s ≤ t we define the transition matching
φD (s, t) : D s → Dt to be the identity on D s ∩ Dt .
Viewing barcodes as objects of MchR in this way, it is possible to define interleavings and
an interleaving distance on barcodes in essentially the same way as for persistence modules.
The reader may check that δ-interleavings of barcodes as thus defined correspond exactly to
δ-matchings of barcodes. Thus, dB is equal to the interleaving distance on barcodes. See [2] for
details.
|

3.3

The Isometry Theorem

Theorem 3.5 (Isometry Theorem for p.f.d. Persistence Modules). Two p.f.d. persistence modules
M and N are δ-interleaved if and only if there exists a δ-matching between B M and BN . In
particular,
dB (B M , BN ) = dI (M, N).
As noted earlier, the algebraic stability theorem (Theorem 6.4) is the “only if” half of the
isometry theorem: It says that if M and N are δ-interleaved, then there exists a δ-matching between
B M and BN . We give a proof of the algebraic stability theorem as an immediate consequence of
our induced matching theorem in Section 6.1. In Section 8, we present a proof of the converse,
following [23].
As one illustration of the utility of the algebraic stability theorem, note that in view of
Example 3.2, the theorem yields the following strengthening of the original stability result for
barcodes of R-valued functions [14]:
Corollary 3.6 ([7, 14]). For any topological space T , functions γ, κ : T → R, and i ≥ 0 such
that Hi (Sγ ) and Hi (Sκ ) are p.f.d.,
dB (BHi (Sγ ) , BHi (Sκ ) ) ≤ d∞ (γ, κ).
11

3.4

Dualization of Persistence Modules

To close this section on preliminaries, we examine the behavior of barcodes under dualization of
persistence modules. For more on duality in the context of persistence, see [6, 15, 18].
Let Rop denote the opposite category of R and let Neg : R → Rop be the isomorphism of
categories such that for all objects t ∈ R, Neg(t) = −t. Given any persistence module M, taking
the dual of all vector spaces and all linear maps in M gives us a functor M † : Rop → Vect. We
define M ∗ , the dual persistence module of M, by M ∗ = M † ◦ Neg : R → Vect. If M is p.f.d., M ∗∗
is canonically isomorphic to M.
If f : M → N is a morphism of persistence modules, we define f ∗ : N ∗ → M ∗ by taking
( f ∗ )t = ( f−t )∗ . With these definitions, ( · )∗ is a contravariant endofunctor on VectR . When M and
N are p.f.d., under the canonical identifications of M ∗∗ with M and N ∗∗ with N, we have f ∗∗ = f .
For D a barcode, let D∗ be the barcode {−I | I ∈ D}, where we define −I = {t | −t ∈ I} for
any interval I . We then have the following easy observation, which we state without proof:
Proposition 3.7. If M is p.f.d., then B M∗ = (B M )∗ .

4

The Structure of Persistence Submodules and Quotients

As a starting point for the main results of this paper, in this section we describe the relationship
between the barcode of a p.f.d. persistence module M and the barcode of a submodule or quotient
of M.

4.1

Canonical Injections

To prepare for the main result of the section, we first introduce the definition of a canonical
injection between barcodes.
Canonical Injections between Enumerated Sets Define an enumerated set S to be a totally
ordered set S such that there exists an order-preserving bijection S → N or S → {1, . . . , n}. For
S , T enumerated sets with |S | ≤ |T |, we define the canonical injection αST : S ,→ T by
αST (si ) = ti ,
where si and ti denote the ith element of S and T , respectively.
Remark 4.1. Clearly, for S , T, U enumerated sets with |S | ≤ |T | ≤ |U|, the canonical injections
satisfy
αSU = αTU ◦ αST
Partitions of Barcodes into Enumerated Sets Suppose S = (S , m) is a multiset. A total order
on S induces a canonical total order on Rep(S), which is obtained by restricting the lexicographic
total order on S × N to Rep(S).

12

For M a p.f.d. persistence module and b ∈ E, let hb, · i M denote the intervals in B M of the
form hb, di for some d ∈ E. Symmetrically, for d ∈ E, let h · , di M denote the intervals in B M of
the form hb, di for some b ∈ E. Note that
a
a
BM =
h · , di M =
hb, · i M .
d∈E

b∈E

For each b, d ∈ E, we regard both hb, · i M and h · , di M as totally ordered sets, with the total
order on each set induced by the reverse inclusion relation on intervals, so that larger intervals are
ordered before smaller ones. Thus, for example, if hb, di, hb, d0 i ∈ B M and d0 > d, we have that
hb, d0 i < hb, di in the total order on hb, · i M . With these choices of total orders, each of the sets
hb, · i M and h · , di M is an enumerated set.
Canonical Injections Between Barcodes If M, N are p.f.d. persistence modules and |h · , di M | ≤
|h · , diN | for each d ∈ E, then the canonical injections h · , di M ,→ h · , diN assemble into an injection B M ,→ BN , which we also call a canonical injection. Note that this injection maps the ith
largest interval of h · , di M to the ith largest interval of h · , diN for all d ∈ E, 1 ≤ i ≤ |h · , di M |, as
in Fig. 6.

Figure 6: The canonical injection h · , di M ,→ h · , diN matches intervals in order of decreasing length.

Dually, if we have |hb, · i M | ≥ |hb, · iN | for each b ∈ E, then the canonical injections
hb, · i M ←- hb, · iN assemble into a canonical injection B M ←- BN which maps the ith largest
interval of hb, · iN to the ith largest interval of hb, · i M .

4.2

Structure Theorem

We now turn to the main result of this section, our structure theorem for submodules and quotients
of persistence modules.
Theorem 4.2 (Structure of Persistence Submodules and Quotients). Let M and N be p.f.d.
persistence modules.
(i) If there exists a monomorphism M ,→ N, then for each d ∈ E
|h · , di M | ≤ |h · , diN |,
and the canonical injection B M ,→ BN maps each hb, di ∈ B M to an interval hb0 , di with
b0 ≤ b.
(ii) Dually, if there exists an epimorphism M  N, then for each b ∈ E
|hb, · i M | ≥ |hb, · iN |,
13

and the canonical injection B M ←- BN maps each interval hb, di ∈ BN to an interval hb, d0 i
with d ≤ d0 .
For M a p.f.d. persistence module and I = hb, di, let h · , Ii M ⊆ B M denote the intervals in
h · , di M which contain I. The key step in our proof of Theorem 4.2 (i) is the following.
Lemma 4.3. If j : M → N is a monomorphism between p.f.d. persistence modules, then for each
interval I,
|h · , Ii M | ≤ |h · , IiN |.
Proof. Write I = hb, di. We may assume without loss of generality that
M
M
M=
C(J),
N=
C(J).
J∈B M

Let

M

U=

J∈BN

M

V=

C(J),

J∈h · , Ii M

C(J).

J∈h · , IiN

Clearly, U ⊆ M and V ⊆ N.
For J any interval and t ∈ R, we write t > J if t > s for all s ∈ J. Since M and N are p.f.d.,
there exists some t ∈ I such that t > J for all intervals J = hb0 , d0 i ∈ B M ∪ BN with b0 ≤ b and
d0 < d. Note that dim Ut = |h · , Ii M | and dim Vt = |h · , IiN |.
We claim that jt (Ut ) ⊆ Vt . To see this, note that by the choice of t,
\
\
Ut =
im ϕ M (s, t) ∩
ker ϕ M (t, r),
Vt =

s∈I
s≤t

r>I

\

\

im ϕN (s, t) ∩

s∈I
s≤t

ker ϕN (t, r).

r>I

For each s ∈ I such that s ≤ t, we have jt (im ϕ M (s, t)) ⊆ im ϕN (s, t) by the commutativity of the
following diagram:
Ms

ϕ M (s, t)

Mt

js

Ns

jt
ϕN (s, t)

Nt

Similarly, for each r > I, we have jt (ker ϕ M (t, r)) ⊆ ker ϕN (t, r). Thus jt (Ut ) ⊆ Vt as claimed.
Since jt is an injection, we have dim Ut ≤ dim Vt , and the lemma follows.

Proof of Theorem 4.2. To show that |h · , di M | ≤ |h · , diN |, it is enough to observe that for all
i ≤ |h · , di M |, we have i ≤ |h · , diN |. Let I = hb, di be the ith interval of the enumerated set h · , di M .
Note that for 1 ≤ j ≤ i, h · , Ii M contains the jth interval of h · , di M . Hence
i ≤ |h · , Ii M | ≤ |h · , IiN | ≤ |h · , diN |,
where the second inequality follows from Lemma 4.3.
14

Now let I 0 denote the ith interval of h · , diN . Recall that the canonical injection B M ,→ BN
matches I to I 0 . Since |h · , Ii M | ≤ |h · , IiN | we must have I 0 ∈ h · , IiN , so I 0 = hb0 , di for some
b0 ≤ b. This establishes Theorem 4.2 (i).
Theorem 4.2 (ii) follows from Theorem 4.2 (i) by a simple duality argument: Suppose
q : M → N is an epimorphism of p.f.d. persistence modules. Then q∗ : N ∗ → M ∗ is a
monomorphism. Theorem 4.2 (i) yields the canonical injection BN ∗ ,→ B M∗ mapping each
hb, di ∈ BN ∗ to an interval hb0 , di ∈ B M∗ with b0 ≤ b. By Proposition 3.7, this map in turn
induces an injection ι : BN ,→ B M , which is exactly the canonical injection. Since ι maps each
hb, di ∈ BN to an interval hb, d0 i ∈ B M with d ≤ d0 , the result follows.

Remark 4.4. After we announced our results, Primož Škraba and Mikael Vejdemo-Johansson
shared with us a nice alternate proof of Theorem 4.2 (ii) for the special case of finitely generated
N-indexed persistence modules. By duality, this yields Theorem 4.2 (i) for the special case as
well.
The proof uses the graded Smith Normal Form algorithm for matrices with homogeneous
k[t]-coefficients, as discussed in [25, 26]. Here is a brief outline of the argument: Given an
epimorphism M  N of finitely generated N-graded persistence modules and a presentation
matrix P M for M in graded Smith Normal Form, we can extend P M to a presentation matrix
PN for N by adding more columns; see [25]. By considering the behavior of the graded Smith
Normal Form algorithm on PN , we can show that the barcode of N is obtained from the barcode
of M by moving the right endpoints of intervals in the barcode of M to the left. In fact, for this
it suffices to consider just the column operations performed by the algorithm, since these are
enough to reduce PN to a form from which we can read off the barcode of N [26]. The special
case of Theorem 4.2 (ii) follows readily.

5

Induced Matchings of Barcodes

We now define the map X sending each morphism f : M → N of pointwise finite dimensional
persistence modules to a matching X f : B M → BN .
We first define the map for monomorphisms and epimorphisms. For j : M ,→ N a monomorphism, we define X j : B M → BN to be the canonical injection B M ,→ BN of Theorem 4.2,
considered as a matching. Dually, for q : M  N an epimorphism, we define Xq : B M → BN to
be the reverse of the canonical injection B M ←- BN .
Now consider an arbitrary morphism f : M → N of p.f.d. persistence modules. f factors
(canonically) as a composition of morphisms
|

|

|

jf

qf

M  im f ,→ N,
where q f is an epimorphism and j f is a monomorphism. We define
X f = X j f ◦ Xq f .
Remark 5.1. To build intuition for our definition of X f , the reader may find it helpful to consider
the definition in the generic case that |hb, · i M | ≤ 1 and |h · , diN | ≤ 1 for all b, d ∈ E. In
15

this case, the definition becomes especially simple: for each interval I = hb, di ∈ Bim f , there
is a unique interval I M = hb, d0 i ∈ B M and a unique interval IN = hb0 , di ∈ BN . We have
X f = {(I M , IN ) | I ∈ Bim f }.

Figure 7: Barcodes of M, im f , and N, as in Example 5.2. Matched intervals are grouped together.

Example 5.2. Let M = C[1, 2) ⊕ C[1, 3), N = C[0, 2) ⊕ C[3, 4). Let f : M → N be a morphism
which maps the summand C[1, 2) injectively into the summand C[0, 2) and maps the summand
C[1, 3) to 0. Then im f  C[1, 2). The barcodes B M , Bim f , and BN are plotted in Fig. 8. We
have X f = {([1, 3), [0, 2))}.

5.1

Properties of Induced Matchings

Several key facts about the induced matchings X f follow almost immediately from the definition.
We record them here.
Proposition 5.3. Let f : M → N be a morphism of p.f.d. persistence modules and suppose
X f hb, di = hb0 , d0 i. Then
b0 ≤ b < d0 ≤ d.

Figure 8: A pair of intervals matched by X f , together with the corresponding interval in Bim( f ) .

Proof. By the definition of X f , we have Xq f hb, di = hb, d0 i and X j f hb, d0 i = hb0 , d0 i. By
Theorem 4.2,
b0 ≤ b < d0 ≤ d,
where the middle inequality holds because hb, d0 i is an interval.



Our induced matching theorem, presented in Section 6, is a refinement of Proposition 5.3.
Proposition 5.4. For any morphism f : M → N of p.f.d. persistence modules, X f is completely
determined by B M , BN , and Bim f . Conversely, X f completely determines these three barcodes.

16

Proof. It is clear from the definition that X f depends only on B M , BN , and Bim f . X f is a matching
between B M and BN , so by definition X f determines B M and BN . To prove the converse then, it
is enough to check that
Bim f = {I ∩ J | (I, J) ∈ X f },
where we interpret the right hand side as the representation of a multiset in the obvious way.
By the definition of X f , the map X f → Bim f which sends each matched pair (I, J) ∈ X f to
Xq f (I) ∈ Bim f is a bijection. To obtain the result, we note that if X f hb, di = hb0 , d0 i, then
Xq f hb, di = hb, d0 i = hb, di ∩ hb0 , d0 i,


where the second equality follows from Proposition 5.3.

Induced Matchings and Duality We next observe that the matching X f ∗ is, up to indexing
considerations, the reverse of the matching X f .
For D a barcode, recall our definition of D∗ from Section 3.4. A matching σ : C → D
between barcodes canonically induces a matching σ0 : C∗ → D∗ , and hence a matching
σ∗ : D∗ → C∗ obtained simply by reversing σ0 . With these definitions, ( · )∗ is a contravariant
endofunctor on the full subcategory of Mch whose objects are barcodes.
The following is a counterpart of Proposition 3.7 for induced matchings:
|

|

|

Proposition 5.5. If f : M → N is a morphism of p.f.d. persistence modules, then X f ∗ = X∗f .
Proof. If q is an epimorphism of persistence modules and j is a monomorphism of persistence
modules, then q∗ is a monomorphism of persistence modules and j∗ is an epimorphism of
persistence modules. Thus, for f = j f ◦ q f we have
X f ∗ = X( j f ◦q f )∗ = Xq∗f ◦ j∗f = Xq∗f ◦ X j∗f .
It is easy to check that if g is an epimorphism or a monomorphism, then X∗g = Xg∗ . Therefore,
Xq∗f ◦ X j∗f = X∗q f ◦ X∗j f = (X j f ◦ Xq f )∗ = X∗f .
We thus have X f ∗ = X∗f as desired.

5.2



Partial Functoriality of Induced Matchings

Let
B : obj(vectR ) → obj(Mch)
denote the map sending a p.f.d. persistence module M to its barcode B M . Given that
X : hom(vectR ) → hom(Mch)
maps each morphism f : M → N of persistence modules to a matching between B M and BN , one
might hope that the pair (B, X) defines a functor vect → Mch. However, as the next example
shows, X does not respect composition of morphisms, so is not functorial.
17

Example 5.6. Consider persistence modules
L = C[3, ∞) ⊕ C[4, ∞),
M = C[2, ∞) ⊕ C[1, ∞),
N = C[0, ∞).
Define f : L → M by f (s, t) = (s, 0); define g : M → N by g(s, t) = t. We have im f  C[3, ∞)
and im g  C[1, ∞).
X f matches the interval [3, ∞) ∈ BL to [1, ∞) ∈ B M , and leaves [4, ∞) ∈ BL and [2, ∞) ∈ B M
unmatched. Xg matches [1, ∞) ∈ B M to [0, ∞) ∈ BN and leaves [2, ∞) ∈ B M unmatched. Thus
Xg ◦ X f matches [3, ∞) ∈ BL to [0, ∞) ∈ BN and leaves [4, ∞) ∈ BL unmatched. On the other
hand g ◦ f = 0, so Xg◦ f is the trivial matching (i.e., Xg◦ f = ∅).
Though X is not functorial in general, we have the following partial functoriality result for X:
Proposition 5.7. X is functorial on the two subcategories of vectR whose morphisms are, respectively, the monomorphism and epimorphisms.
Proof. It is clear from the definition that X sends identity morphisms to identity morphisms. If
j : M → N is a monomorphism of p.f.d. persistence modules, then by definition X j factors as
the disjoint union of the canonical injections h · , di M ,→ h · , diN indexed by endpoints d ∈ E.
It thus follows by Remark 4.1 that if j1 : L → M and j2 : M → N are monomorphisms of
p.f.d. persistence modules, then X j2 ◦ X j1 = X j2 ◦ j1 . Thus, X is functorial on the subcategory of
monomorphisms in vectR .
Using essentially the same argument, together with the fact that the operation of reversing a
matching is functorial, we find that, dually, X is functorial on the subcategory of epimorphisms
in vectR .

Example 5.8. Given p.f.d. persistence modules M, N, P, Q and morphisms f : M → N, g :
P → Q we can define the direct sum f ⊕ g : M ⊕ P → N ⊕ Q in the obvious way. In view
`
of Proposition 5.7, one might hope that when f and g are monomorphisms, X f ⊕g = X f Xg .
However, this equality does not hold in general. For example, we can take M = N = C[1, 2),
`
P = 0, and Q = C[0, 2), with f : M → N the identity map. Then X f Xg = {([1, 2), [1, 2))} but
X f ⊕g = {([1, 2), [0, 2))}.
Non-Functoriality of Persistence Barcodes It is natural to ask whether there exists some
other, fully functorial definition of a map sending each morphism M → N of p.f.d. persistence
modules to a matching B M → BN . Proposition 5.10 below makes clear that the answer is no.
|

Lemma 5.9. There exists no functor vect → Mch sending each vector space of dimension d to a
set of cardinality d.
Proof. Assume for a contradiction that such a functor S exists. We first show that S must send
each linear map f : V → W of rank r to a matching S ( f ) of cardinality |S ( f )| = r. We begin with
the case of f an injection. In this case, f has a left inverse g : W → V. We have
S (g) ◦ S ( f ) = S (g ◦ f ) = S (IdV ),
18

so
r = |S (IdV )| = |S (g) ◦ S ( f )| ≤ |S ( f )| ≤ dim V = r,
which gives the result. By an analogous argument, the result also holds when f is a surjection.
qf

jf

For the general case, consider f as a composition of maps V  im f ,→ W. Since rank q f =
rank j f = rank f = r, we have |S (q f )| = |S ( j f )| = r. Since |S (im f )| = r as well, this implies that
both S (q f ) and S ( j f ) match every element of S (im f ). It follows that |S ( f )| = r.
Now let i1 , i2 , i3 : K → K 2 be injective linear maps with left inverses p1 , p2 , p3 : K 2 → K,
respectively, such that p1 ◦ i2 = p2 ◦ i1 = 0 and p1 ◦ i3 = p2 ◦ i3 = IdK . For instance,
i1 : x 7→ (x, 0),

i2 : x 7→ (0, x),

i3 : x 7→ (x, x),

p1 : (x, y) 7→ x,

p2 : (x, y) 7→ y,

p3 : (x, y) 7→ x.

Each of these six maps is of rank 1 and thus matches exactly one element of S (K 2 ). Write
S (K 2 ) = {a, b} and assume without loss of generality that S (i1 ) matches a. Since S (p1 ) ◦ S (i1 ) =
S (p1 ◦ i1 ) = S (IdK ) = IdS (K) , S (p1 ) must also match a. Moreover, S (i2 ) must match b; otherwise,
S (i2 ) would have to match a, and we would have S (p1 ) ◦ S (i2 ) , ∅ and S (p1 ◦ i2 ) = S (0) = ∅,
violating the functoriality of S . By an analogous argument, S (p2 ) must match b as well.
If i3 matches a, then S (p2 ) ◦ S (i3 ) = ∅. But S (p2 ◦ i3 ) = S (IdK ) , ∅, violating functoriality.
On the other hand, if i3 matches b, then S (p1 ) ◦ S (i3 ) = ∅ but S (p1 ◦ i3 ) , ∅, again violating
functoriality. We conclude that the functor S cannot exist.

Proposition 5.10. There exists no functor vectR → Mch sending each persistence module to its
barcode.
Proof. Assume for a contradiction that there exists a functor B : vectR → Mch sending each
persistence module to its barcode. Consider the functor P : vect → vectR that sends a vector
space V to the persistence module M with M0 = V and Mt = 0 for t , 0. The functor
B ◦ P : vect → Mch then sends each vector space of dimension d to a barcode of cardinality d.
But by Lemma 5.9, such a functor cannot exist. We conclude that there cannot exist a functor
vectR → Mch sending each persistence module to its barcode.


6

The Induced Matching Theorem

We now come to our main result, the induced matching theorem.
For  ≥ 0, we say a persistence module M is -trivial if the transition morphism ϕM : M →
M() is the zero morphism. Recall that in Section 3.2, for a barcode D and  ≥ 0 we defined
D = {hb, di ∈ D | b +  < d} = {I ∈ D | [t, t + ] ⊆ I for some t ∈ R}.

Theorem 6.1 (Induced Matching Theorem). Let f : M → N be a morphism of pointwise finite
dimensional persistence modules and suppose X f hb, di = hb0 , d0 i. Then
(i) b0 ≤ b < d0 ≤ d.
19

(ii) If coker f is -trivial, then BN ⊆ im X f and
b0 ≤ b ≤ b0 + .
(iii) Dually, if ker f is -trivial, then BM ⊆ coim X f and
d −  ≤ d0 ≤ d.

Figure 9: The relationship between a pair of intervals matched by X f , as described by the induced
matching theorem.

Proof of Theorem 6.1. Theorem 6.1 (i) is exactly Proposition 5.3.
To prove Theorem 6.1 (ii), let N  be the submodule of N given by Nt = im ϕ M (t − , t) for all
t ∈ R. Note that
BN  = {hc +  , ei | hc, ei ∈ BN }.
Put informally, we obtain the barcode BN  from BN by first removing the intervals of length less
than  from BN , and then moving the left endpoint of each remaining interval to the right by .
Our proof strategy will be to sandwich Bim f between BN  and BN via canonical injections.
Let j : N  ,→ N denote the inclusion. We see from the definition of X j that im X j = BN ,
and if hc, ei ∈ BN , then
X j hc +  , ei = hc, ei.

Figure 10: The relationship between a pair of intervals matched by X j : BN  ,→ BN .

Now assume that coker f is -trivial. Then N  ⊆ im f . (To see this, note that for all t ∈ R,
ϕcoker f (t − , t) = 0 if and only if im ϕN (t − , t) ⊆ im ft .) Thus the following diagram commutes,
where each map is the inclusion:
j

N

N
jf

j

im f

20

By Proposition 5.7, we have X j = X j f ◦X j . Moreover, by definition we have that X f = X j f ◦Xq f ,
so the following diagram of matchings commutes:

X j

BN

Xf

Xjf

BN 
Xj

Bim f

BM
Xq f

By the commutativity of the left triangle, BN = im X j ⊆ im X j f . By our definition of induced
matchings, we have that im X j f = im X f , so
BN ⊆ im X f
as claimed.

Figure 11: To show that b ≤ b0 + , we sandwich b between b0 and b0 + , using that X j = X j f ◦ X j .

To finish the proof of Theorem 6.1 (ii), we need to show that for b, b0 as in the statement of
the result, b ≤ b0 + . This follows from the commutativity of the left triangle as well. To see this,
recall that X j f hb, d0 i = hb0 , d0 i. If hb0 , d0 i ∈ BN , then we also have that X j hb0 +  , d0 i = hb0 , d0 i,
so X j hb0 +  , d0 i = hb, d0 i by commutativity of the triangle; see Fig. 11. By Theorem 4.2 (i), we
have that
b ≤ b0 + .
If, on the other hand, hb0 , d0 i < BN , then d0 ≤ b0 + . Since b < d0 , we again have that
b ≤ b0 + .
It remains to prove Theorem 6.1 (iii). Our proof of Theorem 6.1 (ii) dualizes readily. Alternatively, Theorem 6.1 (iii) follows directly from Theorem 6.1 (ii) via a straightforward duality
argument. This latter argument requires the use of Proposition 5.5 and Lemma 6.2 below, whose
proof we omit.

Lemma 6.2. For f : M → N a morphism of p.f.d. persistence modules, ker f is -trivial if and
only if coker f ∗ is -trivial.

6.1

Algebraic Stability via Induced Matchings

We now establish an explicit form of the algebraic stability theorem for pointwise finite dimensional persistence modules as a corollary of the induced matching theorem.
21

Lemma 6.3. If f : M → N(δ) is a δ-interleaving morphism, then ker f and coker f are both
2δ-trivial.
Proof. This follows from the definition of a δ-interleaving.



For any persistence module N and δ ∈ [0, ∞), we have a bijection
rδ : BN(δ) → BN
such that rδ hb, di = hb + δ, d + δi for each interval hb, di ∈ BN(δ) .
Theorem 6.4 (Explicit Formulation of Algebraic Stability). If M, N are pointwise finite dimensional persistence modules and f : M → N(δ) is a δ-interleaving morphism, then rδ ◦ X f : B M →
BN is a δ-matching. In particular,
|

dB (B M , BN ) ≤ dI (M, N).
Proof. By Lemma 6.3, ker f and coker f are both 2δ-trivial. The Induced Matching Theorem 6.1
2δ
0 0
thus tells us that B2δ
M ⊆ coim X f , BN(δ) ⊆ im X f , and each matched pair of bars X f hb, di = hb , d i
satisfies
b0 ≤ b ≤ b0 + 2δ and d − 2δ ≤ d0 ≤ d.
It now follows from the definition of rδ that rδ ◦ X f is a δ-matching.



Figure 12: A pair of intervals in the δ-matching rδ ◦ X f : B M → BN of Theorem 6.4, together with the
corresponding intervals in Bim f and BN(δ) .
|

Remark 6.5. For M and N δ-interleaved persistence modules, our proof of the algebraic stability
theorem gives a construction of a δ-matching between B M and BN depending only on a single
δ-interleaving morphism f : M → N(δ); to construct the δ-matching, one does not need an
explicit choice of morphism g : N → M(δ) such that
g(δ) ◦ f = ϕ2δ
M,
f (δ) ◦ g = ϕ2δ
N.
This is in contrast to the proof strategy via interpolation used in [7] and [10]: The construction of
a matching given in those proofs depends in an essential way on an explicit choice of both f and
g.

22

6.2

Single-Morphism Characterization of the Interleaving Relation

As an another application of Theorem 6.1, we have the following:
Corollary 6.6. Two p.f.d. persistence modules M and N are δ-interleaved if and only if there
exists a morphism f : M → N(δ) with ker f and coker f both 2δ-trivial.
Proof. The forward direction is Lemma 6.3. The converse direction follows from the induced
matching theorem and the converse algebraic stability theorem 8.2.

Remark 6.7. Our definitions of δ-interleavings and δ-trivial persistence modules extend readily
to multidimensional persistence modules; see [23]. Given this, it is natural to ask whether
Corollary 6.6 generalizes to the multidimensional setting.
It is easy to check that the forward direction of the theorem (i.e., Lemma 6.3) does generalize
to multidimensional persistence modules, with the same easy proof. Conversely, by considering
the canonical factorization of a morphism though its image, it is not hard to check that the
converse direction of Corollary 6.6 holds for multidimensional persistence modules, up to a factor
of 2. Perhaps surprisingly, the next example shows that showing that this factor of 2 is tight. Thus,
while Corollary 6.6 does adapt to the multidimensional setting, the general result is not as strong
as the result in one dimension.
Example 6.8. In this example, we freely use the notation and terminology for multidimensional
persistence modules established in [23]. First, for δ ≥ 0 we define a 2-D persistence module P to
be δ-trivial if ϕP (δ) : P → P(δ), as defined in [23], is the trivial morphism.
We will describe 2-D persistence modules M and N and a morphism f : M → N(1) with
2-trivial kernel and cokernel, such that M, N are δ-interleaved if and only if δ ≥ 2.
We specify M and N via presentations. We take
M  h(a, (3, 2)), (b, (2, 3)) | x2 y3 a − x3 y2 bi.
That is, M has a generator a at grade (3, 2), a generator b at (2, 3), and a relation x2 y3 a − x3 y2 b at
grade (5, 5). We take
N  h(c, (2, 1)), (d, (1, 2)) | yc − xdi.
Thus
N(1)  h(c0 , (1, 0)), (d0 , (0, 1)) | yc0 − xd0 i.
We define f : M → N(1) by taking f (a) = x2 y2 c0 , f (b) = x2 y2 d0 . It is easy to check that f has
2-trivial kernel and cokernel, and that M and N are δ-interleaved if and only if δ ≥ 2.

7

Algebraic Stability for q-Tame Persistence Modules

In the remaining two sections, we show that the isometry theorem for q-tame persistence modules, as presented in [10, Theorem 4.11], follows readily from the isometry theorem for p.f.d.
persistence modules.
First, we derive the algebraic stability theorem for q-tame persistence modules, as stated in [10,
Theorem 4.20], from the algebraic stability theorem for p.f.d. persistence modules, Theorem 6.4.
23

The last section treats the converse algebraic stability theorem in both the p.f.d. and q-tame
settings.
Neither [10, Theorem 4.20] nor our Theorem 6.4 immediately implies the other. On the one
hand, [10, Theorem 4.20] applies to q-tame persistence modules, whereas Theorem 6.4 only
applies to p.f.d. persistence modules. On the other hand, Theorem 6.4 is slightly sharper than
the restriction of [10, Theorem 4.20] to p.f.d. persistence modules, because [10, Theorem 4.20]
concerns undecorated barcodes (see below), and because as noted in Remark 3.4, the definition
of δ-matching used in the present paper is stronger than the one used in [10].

7.1

Undecorated Barcodes of q-Tame Persistence Modules

Recall that we say a persistence module M is q-tame if ϕ M (s, t) has finite rank whenever s < t. A
q-tame persistence module does not necessarily decompose into interval summands [10, Section
4.5], and thus our definition of barcode does not extend to q-tame persistence modules.
However, it is observed in [12] that if we are willing to use a slightly coarser notion of
barcode, then we can define the barcode of a q-tame persistence module M by way of the interval
summand decomposition of an approximation of M. We recall the definition here. See [12] for a
thorough study of the definition, including an interpretation in terms of quotient categories.
Undecorated Barcodes Adapting a definition of [10], we define an undecorated barcode to be
a barcode for which every interval is open. In what follows, we will sometimes refer to barcodes
as decorated barcodes, to emphasize the distinction between general barcodes and the special
case of undecorated barcodes.
There is an obvious map U from the set of decorated barcodes to the set of undecorated
barcodes, which removes all intervals of the form [t, t] from a barcode and forgets the decorations
of the endpoints of all other intervals in the barcode. For example, we have

U({[0, 1), [0, 2], (−∞, ∞), [0, 0]}) = (0, 1), (0, 2), (−∞, ∞) .
If M is an interval-decomposable persistence module, we define the undecorated barcode U M of
M to be U(B M ).
Undecorated Barcodes of q-Tame persistence modules As in the proof of Theorem 6.1,
for M a persistence module and  ≥ 0, let M  denote the submodule of M defined by Mt =
im ϕ M (t − , t) for all t ∈ R.
For M any persistence module, define rad M, the radical of M, as
[
rad M =
M .
>0

Note that rad M is a submodule of M. It is easy to see that dI (M, rad M) = 0; in this sense, rad M
is an infinitesimally close approximation of M.
Theorem 7.1 (Structure of Radical q-Tame Persistence Modules [12, Corollary 3.6]). For M any
q-tame persistence module, rad M is interval decomposable.
24

See also [12, Theorem 3.2] for a simultaneous generalization of both Theorem 7.1 and the
structure theorem for p.f.d. persistence modules [16].
We state the following easy result without proof:
Proposition 7.2. For any interval-decomposable persistence module M, Urad M = U M .
For M q-tame, we define U M , the undecorated barcode of M, by taking U M = Urad M . In view
of Proposition 7.2, for M a persistence module that is both q-tame and interval-decomposable,
this definition coincides with the definition of U M given above.
Remark 7.3. [10] defines the undecorated barcode of a q-tame persistence module by first
defining the decorated barcode of a q-tame persistence module M using the rectangle measure
formalism introduced in that paper, and then taking the undecorated barcode of M to be the image
of the decorated barcode of M under U; it follows from the results of [10] that the two definitions
of the undecorated barcode of a q-tame persistence module are equivalent.

7.2

Algebraic Stability for q-Tame Persistence Modules

Using the algebraic stability theorem for p.f.d. persistence modules, we now give our alternative
proof of the algebraic stability theorem for q-tame persistence modules.
Theorem 7.4 (Algebraic Stability for q-Tame Modules [10, Theorem 4.20]). If M and N are
q-tame and are (δ + )-interleaved for all  > 0, then there is a δ-matching between U M and UN .
In particular,
dB (U M , UN ) ≤ dI (M, N).
To prepare for the proof of the theorem, we make some easy technical observations, leaving
the proofs to the reader:
Lemma 7.5. Let M be a q-tame persistence module.
(i) M and M  are -interleaved.
(ii) For any  > 0, M  is p.f.d.
(iii) There is a canonical -matching Brad M → B M .
|

Lemma 7.5 (i,ii) implies in particular that a q-tame persistence module can be approximated
arbitrarily well by a p.f.d. persistence module.
Proof of Theorem 7.4. M and N are (δ+)-interleaved for all  > 0, so by Lemma 7.5 (i,ii) and the
triangle inequality for interleavings (Remark 3.1), M  and N  are p.f.d. and are (δ+3)-interleaved.
By Theorem 6.4, there is a (δ + 3)-matching between B M and BN  . Thus by Lemma 7.5 (iii)
and the triangle inequality for δ-matchings (Remark 3.3), there is a (δ + 5)-matching between
Brad M and Brad N . This induces a (δ + 5)-matching between U M = Urad M and UN = Urad N .
Since this is true for all  > 0, we conclude that
dB (U M , UN ) ≤ dI (M, N).
Finally, the existence of a δ-matching between U M and UN follows by Theorem 7.6 below. 
25

Theorem 7.6 ([10, Theorem 4.10]). If there is a (δ + )-matching between U M and UN for all
 > 0, then there is a δ-matching between U M and UN .
We note that the proof of Theorem 7.6 is self-contained; in invoking this result and its proof,
we are not implicitly invoking any other results of [10].

8

Converse Algebraic Stability

Since the algebraic stability theorem and its converse go hand in hand, for completeness we
include a proof of the converse here. We first present the result under the assumption that the
persistence modules are interval-decomposbale, following [23]. Together with Theorem 6.4, this
establishes the isometry theorem for p.f.d. persistence modules, Theorem 3.5.
Following [10], we then establish a version of converse algebraic stability for q-tame persistence modules, as an easy corollary of the result in the interval-decomposable setting. Together
with Theorem 7.4, this gives the isometry theorem for q-tame persistence modules.

8.1

Converse Algebraic Stability for Interval-Decomposable Persistence Modules

Lemma 8.1. Let δ ≥ 0.
(i) If hb, di, hb0 , d0 i are intervals such that
hb, di ⊆ hb0 − δ, d0 + δi,
hb0 , d0 i ⊆ hb − δ, d + δi,
then Chb, di and Chb0 , d0 i are δ-interleaved.
(ii) If b +  ≥ d, then Chb, di and the trivial module are δ-interleaved.


Proof. We leave the straightforward details to the reader.

Theorem 8.2 ([23, Theorem 3.3]). If M and N are interval-decomposable persistence modules
and there exists a δ-matching between B M and BN , then M and N are δ-interleaved. In particular,
dB (B M , BN ) ≥ dI (M, N).
Proof. We may assume without loss of generality that
M
M
M=
C(I),
N=
C(I).
I∈B M

I∈BN

Let σ : B M → BN be a δ-matching, and let
M
M• =
C(I),
|

N• =

I∈coim(σ)

M◦ =

M

M

C(I),

I∈im(σ)

N◦ =

C(I),

M
I∈coker(σ)

I∈ker(σ)

26

C(I),

where ker(σ) and coker(σ) denote the complements of coim(σ) and im(σ) in B M and BN ,
respectively.
Clearly, M = M• ⊕ M◦ and N = N• ⊕ N◦ . By Lemma 8.1 (i), for each (I, J) ∈ σ we may
choose a pair of δ-interleaving morphisms
fI : C(I) → C(J)(δ),

g J : C(J) → C(I)(δ).

These morphisms induce a pair of δ-interleaving morphisms
f• : M• → N• (δ),

g• : N• → M• (δ).

Define a morphism f : M → N by taking the restriction of f to M• to be equal to f• and
taking the restriction of f to M◦ to be the trivial morphism. Symmetrically, define a morphism
g : N → M by taking the restriction of g to N• to be equal to g• and taking the restriction of g to
N◦ to be the trivial morphism. By Lemma 8.1 (ii),
2δ
ϕ2δ
M (M◦ ) = ϕN (N◦ ) = 0.

From this fact and the fact that f• and g• are δ-interleaving morphisms, it follows that f and g are
δ-interleaving morphisms as well.


8.2

Converse Algebraic Stability for q-Tame Persistence Modules

The converse algebraic stability theorem for q-tame persistence modules, as presented in [10],
follows easily from Theorem 8.2:
Corollary 8.3 ([10, Theorem 4.1100 ]). For M and N q-tame persistence modules,
dB (U M , UN ) ≥ dI (M, N).
Proof. Let δ = dB (U M , UN ). By definition, dB (Urad M , Urad N ) = δ. Clearly, then, we also
have that dB (Brad M , Brad N ) = δ, so by Theorem 8.2, dI (rad M, rad N) ≤ δ. dI (M, rad M) = 0 =
dI (N, rad N), so by the triangle inequality, we conclude that dI (M, N) ≤ δ.

Together, Theorem 7.4 and Corollary 8.3 give the isometry theorem for q-tame persistence
modules:
Theorem 8.4 ([10, Theorem 4.11]). For M and N q-tame persistence modules,
dB (U M , UN ) = dI (M, N).

27

Acknowledgments
We thank Vin de Silva, Peter Landweber, Daniel Müllner, and the anonymous referees for valuable
feedback on this work; this paper has benefitted from their input in several ways. We also thank
Guillaume Troianowski and Daniel for providing us with a copy of their manuscript [24] and for
helpful correspondence regarding their related work. In addition, we thank William CrawleyBoevey and Vin for enlightening discussions about q-tame persistence modules. UB was partially
supported by the Toposys project FP7-ICT-318493-STREP. ML thanks the Institute for Advanced
Study and the Institute for Mathematics and its Applications for their support and hospitality
during the course of this project. ML was partially supported by NSF grant DMS-1128155. Any
opinions, findings, and conclusions or recommendations expressed in this material are those of
the authors and do not necessarily reflect the views of the National Science Foundation.

References
[1] G. Azumaya. Corrections and supplementaries to my paper concerning Krull–Remak–
Schmidt’s theorem. Nagoya Mathematical Journal, 1:117–124, 1950.
[2] U. Bauer and M. Lesnick. Persistence diagrams are really diagrams. In preparation.
[3] A. Blumberg and M. Lesnick. Universality of the homotopy interleaving distance. In
preparation.
[4] P. Bubenik and J. A. Scott. Categorification of persistent homology. Discrete & Computational Geometry, 51(3):600–627, 2014.
[5] G. Carlsson. Topological pattern recognition for point cloud data. Acta Numerica, 23:
289–368, 2014.
[6] G. Carlsson, V. de Silva, and D. Morozov. Zigzag persistent homology and real-valued
functions. In Proceedings of the 25th Annual Symposium on Computational Geometry,
SCG ’09, pages 247–256. ACM, 2009.
[7] F. Chazal, D. C. Steiner, M. Glisse, L. J. Guibas, and S. Y. Oudot. Proximity of persistence modules and their diagrams. In Proceedings of the 25th Annual Symposium on
Computational Geometry, SCG ’09, pages 237–246. ACM, 2009.
[8] F. Chazal, D. C. Steiner, L. J. Guibas, F. Mémoli, and S. Y. Oudot. Gromov–Hausdorff stable
signatures for shapes using persistence. In Proceedings of the Symposium on Geometry
Processing, SGP ’09, pages 1393–1403. Eurographics Association, 2009.
[9] F. Chazal, L. Guibas, S. Oudot, and P. Skraba. Scalar field analysis over point cloud data.
Discrete & Computational Geometry, 46(4):743–775, 2011.
[10] F. Chazal, V. de Silva, M. Glisse, and S. Oudot. The structure and stability of persistence
modules. Preprint, 2012. arXiv:1207.3674.
28

[11] F. Chazal, L. J. Guibas, S. Y. Oudot, and P. Skraba. Persistence-based clustering in
Riemannian manifolds. Journal of the ACM, 60(6), 2013. Article No. 41.
[12] F. Chazal, W. Crawley-Boevey, and V. de Silva. The observable structure of persistence
modules. Preprint, 2014. arXiv:1405.5644.
[13] F. Chazal, V. Silva, and S. Oudot. Persistence stability for geometric complexes. Geometriae
Dedicata, 173(1):193–214, 2014.
[14] D. Cohen-Steiner, H. Edelsbrunner, and J. Harer. Stability of persistence diagrams. Discrete
& Computational Geometry, 37(1):103–120, 2007.
[15] D. Cohen-Steiner, H. Edelsbrunner, and J. Harer. Extending persistence using Poincaré and
Lefschetz duality. Foundations of Computational Mathematics, 9(1):79–103, 2008.
[16] W. Crawley-Boevey. Decomposition of pointwise finite-dimensional persistence modules.
Preprint, 2012. arXiv:1210.0819.
[17] V. de Silva and V. Nanda. Geometry in the space of persistence modules. In Proceedings of
the 29th Annual Symposium on Computational Geometry, SoCG ’13, pages 397–404. ACM,
2013.
[18] V. de Silva, D. Morozov, and M. Vejdemo-Johansson. Dualities in persistent (co)homology.
Inverse Problems, 27(12):124003, 2011.
[19] H. Edelsbrunner and J. Harer. Computational Topology. An Introduction. American
Mathematical Society, 2010.
[20] H. Edelsbrunner, G. Jabłoński, and M. Mrozek. The persistent homology of a self-map.
Foundations of Computational Mathematics, 2014. Available online.
[21] B. T. Fasy, F. Lecci, A. Rinaldo, L. Wasserman, S. Balakrishnan, and A. Singh. Confidence
sets for persistence diagrams. The Annals of Statistics, 42(6):2301–2339, 2014.
[22] M. Lesnick. Multidimensional Interleavings and Applications to Topological Inference.
PhD thesis, Stanford University, 2012.
[23] M. Lesnick. The theory of the interleaving distance on multidimensional persistence
modules. Foundations of Computational Mathematics, 2015. To appear. arXiv:1106.
5305.
[24] D. Müllner and G. Troianowski. Proximity of persistence modules. Unfinished manuscript,
2011.
[25] P. Skraba and M. Vejdemo-Johansson. Persistence modules: Algebra and algorithms.
Preprint, 2013. arXiv:1302.2015.
[26] A. Zomorodian and G. Carlsson. Computing persistent homology. Discrete & Computational Geometry, 33(2):249–274, 2005.
29

