Partial matchings induced by morphisms between persistence modules

Computational Geometry: Theory and Applications 112 (2023) 101985 Contents lists available at ScienceDirect Computational Geometry: Theory and Applications journal homepage: www.elsevier.com/locate/comgeo Partial matchings induced by morphisms between persistence modules R. Gonzalez-Diaz, M. Soriano-Trigueros ∗, A. Torras-Casas Departamento de Matemática Aplicada I, Universidad de Sevilla, Av. de Reina Mercedes, Seville, 41012, Andalusia, Spain a r t i c l e i n f o a b s t r a c t Article history: Received 9 July 2021 Received in revised form 11 September 2022 Accepted 19 January 2023 Available online 3 February 2023 Keywords: Partial matchings Persistence modules Topological data analysis Block functions We study how to obtain partial matchings using the block function Mf, induced by a morphism fbetween persistence modules. Mfis defined algebraically and is linear with respect to direct sums of morphisms. We study some interesting properties of Mf, and provide a way of obtaining Mfusing matrix operations. ©2023 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/). 1. Introduction Persistent homology has become one of the most important tools in Topological Data Analysis [1,2]. Persistence modules help to understand persistent homology [3–5]. Specifically, persistence modules indexed by a totally ordered set Tare functors from Tto the category Vectk, where kis a fixed field. In this setting, under mild assumptions, a persistence module can be completely described by a multiset of intervals of Tcalled its barcode [6]. In practice, TDA software take discrete data as an input, and give a barcode as the output [7–9]. In some situations, the user may want to repeat the procedure, after applying some minor modifications to the original data. In such case, two questions arise. Could we reuse the calculations previously made to obtain the new barcode, taking advantage of the similarities in the input? Is there any relation between both barcodes? Answering the first question would speed up the calculations significantly. Answering the second question would allow, for example, to describe how intervals in the barcode change (or are kept unchanged) when the data is modified. More concretely, if a change in data induces a morphism f:V→ → →Ubetween persistence modules indexed by T, then answering the second question means to know how finduces a partial matching Rep B(V) → Rep B(U)between representations of the corresponding barcodes. It is known that such a partial matching cannot be functorial [10]. Trying to answer both questions, we could think of two possible research directions: (1) Considering the morphism fas a persistence module in its own right and describing it in terms of “simple pieces”, that may have an interpretation at the barcode level. (2) Trying to define rules that produce a partial matching induced by f, guaranteeing that it satisfies some desirable properties. Before going into details, let us comment on the state of the art in both directions. *Corresponding author. E-mail addresses: [email protected] (R. Gonzalez-Diaz), [email protected] (M. Soriano-Trigueros), [email protected] (A. Torras-Casas). https://doi.org/10.1016/j.comgeo.2023.101985 0925-7721/©2023 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http:// creativecommons .org /licenses /by /4 .0/). R. Gonzalez-Diaz, M. Soriano-Trigueros and A. Torras-Casas Computational Geometry: Theory and Applications 112 (2023) 101985 1. Decomposition of persistence modules We say that a persistence module Vis decomposable when V≃U⊕Wwith U, W= 0. Otherwise, Vis said to be indecomposable. Under mild assumptions, indecomposable modules indexed over Tare wellknown and are called interval modules [3,6]. Indecomposable modules of the form U V f≃ U1U2... Un V1V2... Vn (1) where f:V→Uis a morphism between persistence modules, are also well understood for all n ≤4. When n >4, the theory becomes increasingly complex, and for n ≥6there is no way to parametrize the set of indecomposable modules since the underlying graph (the quiver) is of “wild” type (see, for example, [11–13]for the use of quivers in TDA). Recall that the category of modules of the form (1), also known as ladder modules, is isomorphic to the category of morphisms between persistence modules indexed by the set n ={1, ..., n}(see [14]). 2. The induced partial matching χfIn [10] and [15], given f:V→U, the authors provided a procedure to construct a partial matching between representations of the barcodes, Rep B(V)and Rep B(U), denoted by χf. The aim of providing such a construction was to give an explicit proof of the Stability Theorem for barcodes [10]. However, this partial matching has some limitations when applied to real data. In particular, it produces the following undesired result. Consider the morphism fof persistence modules determined by the following commutative diagram: U V f≃ 000 0kk Id ⊕ kk0 0k0. Id Id (2) Then Rep B(V) ={[2, 3]1, [2, 2]1}and Rep B(U) ={[1, 2]1}. Note that, looking at the decomposition of f, one would expect to obtain the following matching: [2,3]1−→ ∅ ,[2,2]1−→ [1,2]1. However, χfproduces the following partial matching: [2,3]1 χf −→ [1,2]1,[2,2]1 χf −→ ∅ which is counter-intuitive. In opposition to χf, we propose Mf, a block function induced by the morphism f, which gives a better insight of how fworks. As we will see in Example 5.2: Mf([2,2],[1,2])=1,Mf([2,3]1,[1,2])=0. More concretely, Mfis defined entirely algebraically, is linear with respect to the direct sum of morphisms and can be easily calculated using matrix column reductions. As explained in Subsection 5.1, Mfalso allows to induce partial matchings efficiently. The paper is organized as follows. Firstly, the background is introduced in Section 2. In Section 3, we introduce the operators Im±and Ker±and illustrate them by using persistence bases. In Section 4, the aforementioned operators are used to define the block function Mfinduced by a morphism f:V→Uand we prove it is well-defined. Its main properties, together with an explanation of how Mfcan be used to compute partial matchings, are given in Section 5. In Section 6, we give a method to compute Mfusing matrix calculations. Finally, the main conclusions and some open questions are discussed in Section 7. 2. Preliminaries We recall the notions of persistence modules, decorated endpoints, barcodes and partial matchings. We also introduce some necessary algebraic tools. 2.1. Persistence modules All vector spaces considered in this paper are defined over a fixed field kwith unit denoted by 1kand they can be infinite dimensional, except in Section 6, where they are finite dimensional. Vectors are expressed in column form. A persistence module Vindexed by a totally ordered set Tis a functor from Tto Vectk. Then Vconsists of a set of vector spaces Vpfor p ∈Tand a set of linear maps ρpq :Vp→Vqfor p ≤qsatisfying that ρqlρpq =ρpl if p ≤q ≤l; and ρpp being the identity map. The set of linear maps {ρpq}p≤qis denoted by ρand its elements are known as the structure 2 R. Gonzalez-Diaz, M. Soriano-Trigueros and A. Torras-Casas Computational Geometry: Theory and Applications 112 (2023) 101985 maps of V. Since the category of persistence modules is abelian, the direct sum of persistence modules together with the intersection and quotient of persistence modules are also persistence modules (see for example [4, Sec. 2]). We consider the functor category of persistence modules. In other words, given two persistence modules, Vand U, with structure maps, ρand φ, a morphism, f:V→U, is given by a set of linear maps {fp}p∈T, such that fqρpq =φpq fpif p ≤q. A morphism fis injective (surjective) if all its linear maps fp, p ∈T, are injective (surjective). Notice that Im fand Ker fare particular cases of persistence modules. We assume that all persistence modules that appear in this paper satisfy the descending chain condition (d.c.c.) for images and kernels. In other words, for t≥p1≥p2≥... and t≤...≤q2≤q1, the following chains stabilize: Vt⊇Im ρp1t⊇Im ρp2t⊇... and Vt⊇Ker ρtq1⊇Ker ρtq2⊇... 2.2. Decorated points and interval modules In this subsection, we use the notation appearing in [10]based on the one introduced in [3, Sec. 2.4]. Let Edenote the set of decorated endpoints defined as E := R ×D ∪{−∞, ∞}, where D ={−, +}. In what follows, decorated points (r, −)and (r, +)are denoted by r−and r+, respectively. Note that Ecan be seen as a totally ordered set stating that r−<r+together with the order inherited by the extended reals. The sum + :E ×R →Eis defined as r±+s := (r+s)±. There is a bijection between the pairs {(a, b) ∈E×E:a <b}and the intervals of R. The following table shows all possible cases: s−s+∞ −∞ (−∞,s)(−∞,s](−∞,∞) r−[r,s)[r,s][r,∞) r+(r,s)(r,s](r,∞) From now on, an interval of Rrepresented by (a, b) ∈E ×E, with a <b, is denoted by ❲a,b❳. Intervals of any other totally ordered set may turn up. We use the letters a, b, cand dto denote elements of E; the letters r, sand tto denote elements of R; and the letters p, qand lto denote elements of a general, totally ordered set T. Given an interval Iof R, the interval module, kI, is composed by kIt =kfor all t∈Iand kIt =0otherwise, while the structure maps are given by the identity whenever possible. As shown in the next subsection, interval modules are the building blocks of persistence modules. 2.3. Decomposition of persistence modules The results that appear in this section are directly taken from [6] where the following statement is proven. Theorem 2.1 (Theorem 1.2 of [6]). For any persistence module Vindexed by Rsatisfying the d.c.c. for images and kernels, we have: V≃ I∈SV⊕mIkI where SVis a set of intervals of Rand mIis the multiplicity of kI. The proof of the theorem uses the operators Im±and Ker±(which are introduced in Section 3) as well as the concept of section. A section of a vector space Ais a pair of vector spaces (F−, F+)such that F−→F+→A. We say that a set {(F− λ, F+ λ) :λ ∈}of sections (with its index set) of Ais disjoint if, for all λ = μ, either F+ λ→F− μor F+ μ→F− λ. Sections are used in Lemma 4.5 and Theorem 5.5. In particular, we use the following result, whose justification is part of the proof of Theorem 6.1 in [6]. Lemma 2.2. Suppose that {(F− λ, F+ λ) :λ ∈}is a disjoint set of sections of a vector space A. Then  λ∈F+ λF− λ→A. 2.4. Barcodes and partial matchings A multiset is a pair (S, m)where Sis a set and m :S→N∪{∞} represents the multiplicity of the elements of S. An element of the multiset (S, m)is denoted by the pair (I, mI)where I∈Sand mI=m(I). The barcode of a persistence module Vis the multiset B(V) =(SV, m)where SVis the set of intervals that appear in the decomposition of V, and mIis the multiplicity of I∈S. The representation of a multiset (S, m)is the set Rep(S,m)={(I,i)∈S×N:i≤mI)}. From now on, we use the notation Iiinstead of (I, i). 3 R. Gonzalez-Diaz, M. Soriano-Trigueros and A. Torras-Casas Computational Geometry: Theory and Applications 112 (2023) 101985 Example 2.3. Consider the persistence module U≃k2k3k 10 01 00 [001 ] that can be decomposed as k[1,2]⊕k[1,2]⊕k[2,3]. Then its barcode is B(U) ={([1, 2], 2), ([2, 3], 1)}and the representation of its barcode is Rep B(U)={[1, 2]1, [1, 2]2, [2, 3]1}, which can be displayed as: Given two barcodes, B1and B2, a partial matching between Rep B1and Rep B2is a bijection σ:R1→R2where R1⊂ Rep B1and R2⊂Rep B2. By abuse of notation, we might write instead σ:Rep B1→Rep B2, and say σ(I) =∅when we mean I/∈R1. Definition 2.4. A block function between two barcodes B1=(S1, m)and B2=(S2, n)is a function M :S1×S2−→ Z≥0∪{∞} such that:  J∈S2 M(I,J)≤mI. Remark 2.5. Note that when a block function satisfies  I∈S1 M(I,J)≤nJ, it is straightforward to show that Minduces a partial matching between Rep B1and Rep B2. 2.5. Persistence bases A persistence basis [16,3]for a persistence module Vis an isomorphism α: i∈ k❲ai,bi❳→V, where is an index set. By Theorem 2.1, such persistence bases exist for all persistence modules satisfying the d.c.c. condition for images and kernels. The persistence generator αi:k❲ai,bi❳→Vis defined as the morphism αrestricted to k❲ai,bi❳for i ∈. When we write αi∼❲ai,bi❳, we mean that k❲ai,bi❳is the domain of αi. We also specify a persistence basis αby its set of persistence generators, A ={αi}i∈and we denote its cardinality by #A. Definition 2.6. Given a subset S={αi}i∈of A, we define the span of S, denoted by S, as the image of the sum of persistence generators of S, that is S=Im  i∈ αi: i∈ k❲ai,bi❳→V. For t∈R, we define St:= {α1 it :i ∈and t∈❲ai,bi❳}where α1 it means αit(1k)by abuse of notation. In particular, Vt=At and St=St, where Atand Stare linearly independent sets of vectors in Vt. Notice that in general, the submodule S of Vdepends on α. The following result is later used to prove that Mfis well-defined. Lemma 2.7. Let Vbe a submodule of a persistence module Uindexed by Rsuch that Vt=0for all t∈❲d, ∞❳for some d ∈E. Then, given a persistence basis αfor U, we have that Vis also a submodule of W=αi:αi∼❲·,b❳with b≤d. 4 R. Gonzalez-Diaz, M. Soriano-Trigueros and A. Torras-Casas Computational Geometry: Theory and Applications 112 (2023) 101985 Proof. By contradiction, assume that Vis not a submodule of W. Then, for some s ∈❲−∞, d❳, there exists x ∈Vssuch that x /∈Ws. Thus, x= i∈1 xiα1 is + j∈2 xjα1 js for coefficients xi, xj∈k \{0}for all i ∈1and j ∈2; where 1and 2are two disjoint indexing subsets 1⊆{i :αi∼ ❲·, b❳with b≤d}and 2⊆{j :αj∼❲·, b❳with d <b}. Note that 2is non empty since x /∈Wsby hypothesis. We choose jin 2, such that α1 js= 0 and xj= 0. Denote the right endpoint of αjas d. Let t∈❲d, d❳. Then 0=ρst x= j∈ 2 xjα1 jt , where  2={j ∈2:ρst(α1 js) = 0}, so that j∈ 2. However, as {α1 jt}j∈ 2is linearly independent by Definition 2.6, xjmust be zero for all j ∈ 2, including j, leading to a contradiction.  In particular, notice that the submodule Wof Vfrom Lemma 2.7 is independent for the chosen persistence basis α, as given another persistence basis αwith the corresponding submodule W, we would obtain W⊆Wand also W⊇W; thus W=W. Finally, let f:V→Wbe a morphism between persistence modules and let Aand Bbe persistence bases for Vand U, respectively. If fis an injection, then #A ≤#Bwhile if fis a projection, then #A ≥#B. This is a consequence of the result of persistence submodules and quotients given in [10, Thm. 4.2]. 2.6. Direct limits We need the notion of direct limits to define the block function Mfand the notion of sections to prove it is welldefined. The definition of direct limit and some useful lemmas involving direct limits are given in Appendix A. In this section, we just give a characterization of direct limits for our context. Proposition 2.8 (Characterization of direct limits for persistence modules). Let V be a persistence module indexed by an interval ❲a, b❳, and consider the endpoint a <d ≤b. Then lim −→ t∈❲a,d❳ Vt≃p∈❲a,d❳Vp Z where Zis the vector space generated by vp⊕−ρpq(vp) ∈Vp⊕Vq, with p ≤qand p, q ∈❲a, d❳. Proof. See [3, Def. 3.41] and [3, Prop. 3.43].  The direct limit lim −→t∈❲a,d❳Vtdoes not depend on aand, intuitively, it is isomorphic to the vector space generated by the intervals ❲c,b❳with c≤d ≤b. Actually, if drepresents a closed right endpoint, i.e. d =s+, it follows from the characterization that lim −→t∈❲a,s+❳Vt=Vs. Example 2.9. Consider a persistence module Visomorphic to k[1,3)⊕k(1,3]⊕k[0,4) and a persistence basis A ={α1, α2, α3}for V. For example, if v ∈V2, then v =x1α1 12 +x2α1 22 +x3α1 32 for some x1, x2, x3∈k. Note that for 1+<a <b ≤3−and t, s ∈❲a, b❳, all structure maps ρst are injective. Then, Z=α1 it ⊕−α1 is :i=1,2,3;t≤s∈❲a,b❳. Applying Proposition 2.8, for a fixed i, all α1 it represent the same class in lim −→ t∈❲a,b❳ Vt. Then, denoting this class by α1 i, we have lim −→ t∈❲a,b❳ Vt=α1 i:i=1,2,3. On the contrary, for b =3+, we have that (α1 1t⊕0) ∈Zfor t∈❲a,3−❳since ρt3α1 1t=0, then lim −→ t∈❲a,3+❳ Vt=V3=α1 i3:i=2,3. 5 R. Gonzalez-Diaz, M. Soriano-Trigueros and A. Torras-Casas Computational Geometry: Theory and Applications 112 (2023) 101985 3. The operators Im±and Ker± The operators Im±and Ker±were used in [6]to prove Theorem 2.1. In this section, we introduce these operators from the point of view of persistence bases with the aim of using them later to construct Mf. Let Vbe a persistence module indexed by Rwith structure maps ρand with persistence basis A ={αi}i∈. Let c∈E. We consider the following subsets of A: •I+ c(A) =αi∈A|αi∼❲ai,bi❳such that ai≤c, •I− c(A) =αi∈A|αi∼❲ai,bi❳such that ai<c, •K+ c(A) =αi∈A|αi∼❲ai,bi❳such that bi≤c, •K− c(A) =αi∈A|αi∼❲ai,bi❳such that bi<c. As a convention, given t∈R, we write I± ct (A)instead of I± c(A)tand K± ct(A)instead of K± c(A)t. As Lemma 3.1 shows, I± ct (A)and K± ct(A)generate the following vector spaces, which were first introduced in [6]: Im+ ct(V):=  s∈❲c,t+❳ Im ρst ,Im− ct(V):=  s∈❲−∞,c❳ Im ρst ,for t∈❲c,∞❳; Ker+ ct(V):=  r∈❲c,∞❳ Ker ρtr ,Ker− ct(V):=  r∈❲t−,c❳ Ker ρtr ,for t∈❲−∞,c❳. By convention, Im− ct(V) := 0if c=−∞, and Ker+ ct(V) := V(t)if c=∞. Lemma 3.1. For all c∈E, we have the equalities: (a) Im± ct(V) =I± ct (A)for all t∈❲c, ∞❳, (b) Ker± ct(V) =K± ct(A)for all t∈❲−∞, c❳. Proof. See the first proof in Appendix B Example 3.2. Consider a persistence module Visomorphic to k[1,2]⊕k[2,3]and a persistence basis A ={α1, α2}for Vwhere the generators are given by α1= kk 2k kk0 1 0[01] Id Id 1 0and α2= kk 2k 0kk. 1 0[01] Id 0 1Id Using Lemma 3.1, the subspaces Im± 22(V)and Ker± 32(V)of V2=k2are given by I+ 22(A)=K+ 32(A)=α1 12,α1 22=k2,I− 22(A)=K− 32(A)=α1 12=1 0. As shown in the following result, Im±and Ker±are linear. Proposition 3.3. Let c∈Eand let V1and V2be two persistence modules. Then, Im± ct(V1⊕V2)=Im± ct(V1)⊕Im± ct(V2)for all t ∈❲c,∞❳and Ker± ct(V1⊕V2)=Ker± ct(V1)⊕Ker± ct(V2)for all t ∈❲−∞,c❳. Proof. First, notice that we have the following equalities Im− ct(V)=lim −→ s∈❲−∞,c❳ Im ρst Ker− ct(V)=lim −→ r∈❲t−,c❳ Ker ρtr, and since direct sums commute with limits (see Lemma A.1), the result holds for these operators. In the other case, by the d.c.c. for images and kernels, we know there exists s ∈❲c, t+❳and r∈❲c, ∞❳such that, Im+ ct(V)=Im ρst ,Im+ ct(V1)=Im ρst|V1,Im+ ct(V2)=Im ρst|V2, Ker+ ct(V)=Ker ρtr ,Ker+ ct(V1)=Ker ρtr|V1,Ker+ ct(V2)=Ker ρtr|V2, see [6, Lemma 2.1] for details. In such cases, the linearity follows directly from the linearity of Im and Ker.  6 R. Gonzalez-Diaz, M. Soriano-Trigueros and A. Torras-Casas Computational Geometry: Theory and Applications 112 (2023) 101985 Let Vbe a persistent module and let I=❲a, b❳be an interval of R. We use the operators Im±and Ker±to define the persistence modules V+ I, V− Iand VIpointwisely. For t∈I, define V+ It := Im+ at(V)∩Ker+ bt(V) V− It := Im− at(V)∩Ker+ bt(V)+Im+ at(V)∩Ker− bt(V) VIt := V+ It V− It and, for t/∈I, let them all be 0. These modules played an important role in Theorem 2.1. Specifically, VIis isomorphic to the direct sum ⊕mIkI. As we will see later, such modules are also a key ingredient for the definition of Mf. We end this section with an interpretation of VIin terms of persistence bases. Define A+ I=I+ a(A)∩K+ b(A) A− I=(I+ a(A)∩K− b(A)) ∪(I− a(A)∩K+ b(A)) , which can also be described as: A+ I={αi∈A|ai≤aand bi≤b} A− I={αi∈A|(ai<aand bi≤b)or (ai≤aand bi<b)}. We define AIt as A+ It \A− It and obtain: AI={αi∈A|(ai=aand bi=b)}. Proposition 3.4. V+ It =A+ Itand V− It =A− Itfor all t∈I. Proof. Let I=❲a, b❳with a, b ∈E. From Lemma 3.1 and Lemma B.1, we have: V+ It =Im+ at(V)∩Ker+ bt(V)=I+ at (A)∩K+ bt(A)=I+ at (A)∩K+ bt(A)=A+ It. And, similarly, V− It =Im− at(V)∩Ker+ bt(V)+Im+ at(V)∩Ker− bt(V) = I− at (A)∩K+ bt(A)+I+ at (A)∩K− bt(A) = I− at (A)∩K+ bt(A)+I+ at (A)∩K− bt(A)=A− It. We are now ready to present an interpretation of VIin terms of persistence bases. Theorem 3.5. VIt ≃AItfor all t∈I. Proof. Using Proposition 3.4 and Lemma B.2, we obtain: VIt =V+ It V− It =A+ It A− It≃ A+ It \A− It=AIt. Example 3.6. Going back to Example 3.2, we know that the interval [2, 3]has multiplicity 1. Then, V[2,3]2must be a space of dimension 1. Using Theorem 3.5, this can be rapidly checked by the following computation: V[2,3]2≃A[2,3]2=A+ [2,3]2\A− [2,3]2={α1 12,α1 22}\{α1 12} = α1 22. 4. The block function Mf The definition of Mfis formulated algebraically, via operators of persistence modules. Recall from Subsection 2.3 that given a persistence module V, the multiplicity mIof an interval Iin the barcode B(V)is completely determined by the persistence module VIdefined in Section 3. Given a morphism f:V→Ubetween persistence modules, our aim is to create a new persistence module, XIJ, relating VIand UJvia f. Hence, denoting the respective barcodes of Vand Uby B(V) =(SV, m)and B(U) =(SU, n), from XIJ, we obtain the block function Mfrelating (I, mI)and (J, nJ)for all pairs of intervals I∈SVand J∈SU. 7 R. Gonzalez-Diaz, M. Soriano-Trigueros and A. Torras-Casas Computational Geometry: Theory and Applications 112 (2023) 101985 For this, let us assume that Vand U, with structure maps ρand φ, respectively, are indexed by R. Let I=❲a, b❳and J=❲c, d❳. For t∈I∩J, define the vector space: XIJt:= fV+ It ∩U+ Jt fV− It ∩U+ Jt +fV+ It ∩U− Jt . If t/∈I∩J, then XIJt := 0. Notice that when we write fV± It we mean ft(V± It ). Observe that, since XIJ is made up of sums, intersections and quotient of persistence modules, XIJ is also a persistence module. Intuitively, XIJt is equal to the intersection f(VIt) ∩UJt. Inspecting such an intersection on the limit, we obtain a way to relate the elements (I, mI)and (J, mJ)which is induced by f. Definition 4.1. Let B(V) =(SV, m)and B(U) =(SU, n). We define the function Mf:SV×SU→Z≥0∪{∞} as, Mf(I,J):= dim lim −→ t∈I∩J XIJt . Example 4.2. Consider the morphism between persistence modules f:V→Ugiven by the following commutative diagram: U V f≃ kk 2k 0kk . 1 0[01] Id 1 1Id The respective barcodes are B(V)={([2,3],1)}and B(U)={([1,2],1), ([2,3],1)}. We calculate the set fA ={fα1}which will be used later. Concatenating both functions, α1and f, we get fα1=k[2,3] Id →Vf →U=f. If I=[2, 3]and J=[1, 2], then we can calculate XIJ and XII as follows. First, fV+ I2∩U+ J2=1 1∩1 0=0andXIJ 2=0. Moreover fV+ I2∩U+ I2=1 1∩10 01 =1 1, fV− I2∩U+ I2+fV+ I2∩U− I2=0 0∩10 01 +1 1∩1 0=0; and fV+ I3∩U+ I3=1∩1=1, fV− I3∩U+ I3+fV+ I3∩U− I3=0∩1+1∩0=0. From these computations, we conclude that the only non-zero case for Xis the submodule X[2,3][2,3]:0−→  1 1 [01] −→ k, and then Mf([2,3],[1,2])=0andMf([2,3],[2,3])=1. As the following result shows, the cases of study can be reduced considerably. Proposition 4.3. Let I=❲a, b❳and J=❲c, d❳. If Mf(I,J)= 0, then c≤a≤d≤b. Proof. By definition, a <band c<d. Moreover, if I∩Jis empty, then Mf(I,J)is zero. Then we just have to prove that Mf(I,J)is zero when a <cor b <d. Following the definitions of Im±and Ker±given in Section 3, we have: ft(Im+ at(V)) →Im+ at(U)ft(Ker+ bt(V)) →Ker+ bt(U), 8 R. Gonzalez-Diaz, M. Soriano-Trigueros and A. Torras-Casas Computational Geometry: Theory and Applications 112 (2023) 101985 and: Im+ at(U)→Im− ct(U)Ker+ bt(U)→Ker− dt(U), when a <cor b <drespectively (see Lemma 7.1 in [6]for details). If a <c, fV+ It ∩U+ Jt →ft(Im+ at(V)) ∩Ker+ dt(U)→Im− ct(U)∩Ker+ dt(U)→U− Jt ,(3) then fV+ It ∩U+ Jt →fV+ It ∩U− Jt and XIJt =0. Exchanging Im±by Ker±in Expresion (3), the same reasoning works when b <d. This is an expected result due to the commutativity of fwith respect to the structure maps. An equivalent result for χf is given in [10, Prop. 5.3]. 4.1. Mfis well-defined Given a morphism f:V→Ubetween persistence modules Vand Uwith barcodes B(V) =(SV, m)and B(U) =(SU, n), respectively, the aim of this subsection is to prove the following theorem. Theorem 4.4. Mfis well-defined, that is, it is a block function. Given I=❲a, b❳ ∈SV, we have to prove that J∈SUMf(I, J) ≤mI. Fixing J=❲c, d❳ ∈SU, we can assume that d ≤b without loss of generality (see Proposition 4.3). In such case, I∩Jhas das the right endpoint. To prove Theorem 4.4, we would like to relate the vector spaces XIJt with fVIt and use that dim fVIt ≤mI(since by definition fVIt means fV+ It /fV− It ). However, the vector spaces XIJt and fVIt are subspaces of different vector spaces and there is no straightforward way of relating them. For this reason, we define a new intermediate vector space, and use it to compare the dimension of J∈SUXIJt and fVIt. Lemma 4.5 makes this statement precise. To prove it, for fixed I∈SVand c, d ∈E, we use the following persistence modules indexed by t∈R: Ad ct := fV− It ∩U+ ❲c,d❳t+fV+ It ∩U− ❲c,d❳t fV− It ∩U+ ❲c,d❳t and, Bd ct := fV+ It ∩U+ ❲c,d❳t fV− It ∩U+ ❲c,d❳t . The choice of the vector spaces is justified by the following property, Bd ct Ad ct ≃XIJt . Due to our previous assumption about I∩J, the following limits are equivalent: ˜ Ad c:= lim −→ t∈I∩J Ad ct =lim −→ t∈❲−∞,d❳ Ad ct and ˜ Bd c:= lim −→ t∈I∩J Bd ct =lim −→ t∈❲−∞,d❳ Bd ct . In the following, we write either I∩Jor ❲−∞, d❳when taking limits, since it does not affect the calculation. Due to Lemma A.2, we also have: ˜ Bd c ˜ Ad c ≃lim −→ t∈I∩J XIJt. Moreover, varying c, we can see the vector spaces ˜ Ad cand ˜ Bd cas persistence modules indexed by c∈E. Lemma 4.5. For a fixed d ∈E, we have:  c<d lim −→ t∈I∩J XI❲c,d❳t→lim −→ c<d ˜ Bd c→lim −→ t∈❲−∞,d❳ fVIt . Proof. First, let us prove the second injection. Notice that, for each t∈I∩J, fV+ It ∩U+ Jt →fV+ It and (fV+ It ∩U+ Jt)∩fV− It =fV− It ∩U+ Jt , so that Bd ct →fVIt. By Lemma A.3, we also have that, for each c, 9 R. Gonzalez-Diaz, M. Soriano-Trigueros and A. Torras-Casas Computational Geometry: Theory and Applications 112 (2023) 101985 7. Conclusions and future work In this paper, we have provided an entirely algebraic definition of a block function Mfinduced by a morphism between two persistence modules Vand U. We have proven that Mfis linear with respect to the direct sum of morphisms. We have also discussed how to derive partial matchings from Mfand provided a combinatorial method to compute Mfbased on matrix operations. We are developing an efficient algorithm to compute partial matchings from morphisms between persistence modules, taking Section 6as a starting point. A specially interesting case is the morphism obtained from a function between point clouds and the corresponding Vietoris-Rips filtrations. Moreover, since in some special cases the proposed induced partial matching is defined ad-hoc from Mfand not algebraically, we are investigating if it is possible to find an alternative algebraic definition of Mfsuch that Mfalways gives directly a partial matching. Some additional research directions can be followed from this paper, for example, the relation between Mfand indecomposable modules. We believe that, when IMf(I, J) >nJ, there should exist non-trivial indecomposable modules containing J. Finally, relations between persistence modules which come from dynamical systems are not usually given by morphisms but through diagrams of the form V←W→U[17,18]. Then, another research line could be to construct block functions in that context. Declaration of competing interest The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper. Data availability No data was used for the research described in the article. Acknowledgments and Funding The authors would like to thank Victor Carmona for his valuable help during the development of this research. This research was funded by the Agencia Estatal de Investigación/10.13039/501100011033 under grant PID2019-107339GB-100, by the European Union’s Horizon 2020 Research and Innovation Program under grant agreement 101070028-2, and by the Agencia Andaluza del Conocimiento under grant P20-01145. The author Soriano-Trigueros is partially funded by the grant VI-PPITUS from University of Seville. Appendix A. Direct limits Let Jbe filtered category, and consider a functor F:J→Vectk. We consider the direct limit lim −→j∈JF∈Vectk, which is a particular case of the general definition of colimits (see [19, Sec. 3.1.] and [20, Sec. 3.]). Since Vectkis an abelian category, lim −→i∈JFexists. Examples of colimits include direct sums of vector spaces, j∈JVi, and cokernels, coker(f), of linear maps f:A →B. By [19, Thm. 3.8.1], colimits commute with colimits, deducing Lemma A.1 below. Lemma A.1. Consider a set of functors {Fi:J→Vectk}i∈, then: lim −→ j∈J i∈I Fi(j)≃ i∈I lim −→ j∈J Fi(j), Lemma A.2. Consider a pair of functors F1, F2:J→Vectksuch that F1(j) ⊆F2(j)for all j ∈J. Thus: lim −→ j∈JF2(j)F1(j)≃lim −→ j∈J F2(j)lim −→ j∈J F1(j). Proof. This holds since F2(j)F1(j)is a cokernel, and so a colimit.  Lemma A.3. Let U, V and W be persistence modules indexed by an interval ❲a, b❳, and let d ∈Ewith a <d ≤b. A short exact sequence of persistence modules 0→V→U→W→0, produces the following short exact sequence of vector spaces: 16 R. Gonzalez-Diaz, M. Soriano-Trigueros and A. Torras-Casas Computational Geometry: Theory and Applications 112 (2023) 101985 0→lim −→ t∈❲a,d❳ Vt→lim −→ t∈❲a,d❳ Ut→lim −→ t∈❲a,d❳ Wt→0. In particular, if Vt→Utfor all t∈❲a, d❳, then lim −→ t∈❲a,d❳ Vt→lim −→ t∈❲a,d❳ Ut. Proof. Since colimits are the categorical definition of direct limits, Vectkis an abelian category and any totally ordered set is a filtered category, then the first result is a direct consequence of the characterization of abelian categories (see [21, Appendix A.4]; the original result comes from [22]). The second result follows directly, since injections can be defined in terms of exact sequences.  Lemma A.4. Consider a persistence module Vwith structure maps ρ, indexed by an interval ❲a, b❳, and let d ∈Esuch that a <d ≤b. If all structure maps ρsr with s, r∈❲a, d❳are injective, then Vs→lim −→ t∈❲a,d❳ Vt. Proof. Fix s ∈❲a, d❳. Let us consider the persistence module Cas the constant space Vsin ❲s−, d❳and 0in ❲a, s−❳. Since all structure maps in Vare injective, we have C→V. Then by Lemma A.3, lim −→ t∈❲s−,d❳ Ct→lim −→ t∈❲s−,d❳ Vt, and, by definition, lim −→ t∈❲s−,d❳ Ct=Vsand lim −→ t∈❲s−,d❳ Vt=lim −→ t∈❲a,d❳ Vt, concluding the proof.  Lemma A.5. Let Jbe a filtered category and consider three functors from Jto Vectkwhich we call A, Band C. Further, suppose that A(j), B(j)are both subspaces of C(j)for all j ∈J. Then (a) lim −→j∈JA(j) ∩B(j)≃lim −→j∈JA(j)∩lim −→j∈JB(j), and (b) lim −→j∈JA(j) +B(j)≃lim −→j∈JA(j)+lim −→j∈JB(j). Proof. First, as Vectkis an abelian category, filtered direct limits are exact (see [21, Appendix A.4]), and so they commute with kernels and cokernels. We proceed to prove (a). For each j ∈J, consider the exact sequence 0A(j)∩B(j)A(j)⊕B(j)C(j) ιjj where ιjsends v ∈A(j) ∩B(j)to (v, −v) ∈A(j) ⊕B(j)and jsends (v, w) ∈A(j) ⊕B(j)to v +w ∈C(j). Since A(j) ∩ B(j) ≃ker(j)for all j ∈J, the isomorphism (a) follows from using Lemma A.1. That is, lim −→ j∈JA(j)∩B(j)≃lim −→ j∈J ker A(j)⊕B(j)→C(j) ≃ker ⎛ ⎝lim −→ j∈J A(j)⊕lim −→ j∈J B(j)→lim −→ j∈J C(j)⎞ ⎠≃ lim −→ j∈J A(j)!∩ lim −→ j∈J B(j)!. Next, we prove (b). For each j ∈J, consider the short exact sequence 0A(j)∩B(j)A(j)⊕B(j)A(j)+B(j)0. ιjj Since A(j) +B(j) ≃coker(ιj)for all j ∈J, (b) follows by Lemma A.1 together with part (a). That is, 17 R. Gonzalez-Diaz, M. Soriano-Trigueros and A. Torras-Casas Computational Geometry: Theory and Applications 112 (2023) 101985 lim −→ j∈JA(j)+B(j)≃lim −→ j∈JcokerA(j)∩B(j)→A(j)⊕B(j) ≃coker lim −→ j∈JA(j)∩lim −→ j∈JB(j)→lim −→ j∈JA(j)⊕lim −→ j∈JB(j)! ≃lim −→ j∈JA(j)+lim −→ j∈JB(j). Appendix B. Technical lemmas and proofs related to persistence bases Proof of Lemma 3.1.First we prove (a), i.e. Im± ct(V) =I± ct (A)for all t∈❲c,∞❳. We start by showing that the inclusion ⊇ holds. Given α1 it ∈I+ ct (A)(resp. α1 it ∈I− ct (A)), we have that ρst(α1 is) =α1 it for all s ∈❲c, t+❳(resp. for some s ∈❲−∞, c❳). In particular, α1 it ∈Im+ ct(V)(resp. α1 it ∈Im− ct(V)). Since Im± ct(V)are well-defined subspaces of Vt, we obtain Im+ ct(V) ⊇I+ ct (A) (resp. Im− ct(V) ⊇I− ct (A)). Let us now show that ⊆holds. Consider v ∈Im± ct. Let any s ∈❲c, t+❳(resp. some s ∈❲−∞, c❳) such that there exists w ∈Vswith ρst (w) =v. Since At={α1 it}i∈(t)is a persistence basis for Vt, there exists a subindex set  ⊆(t), together with coefficients xi∈k \{0}for all i ∈such that i∈xiα1 it =v. Similarly, there exists a subset K⊆(s), together with coefficients x i∈k \{0}for all i ∈Ksuch that i∈Kx iα1 is =w. Altogether, we obtain: ρst(w)= i∈K x iρst(α1 is)= i∈K∩(t) x iα1 it =v= i∈ xiα1 it , which, by linear independence of At, implies that K∩(t) =and also x i=xifor all i ∈. Hence, we have that given i ∈with αi∼❲ai, bi❳, we must have s ∈❲ai, bi❳. In particular, since we picked up any s ∈❲c, t+❳(resp. some s ∈❲−∞, c❳), we have that αi∈I+ c(A)(resp. αi∈I− c(A)) for all i ∈. This implies that v ∈I+ ct (A)(resp. v ∈I− ct (A)) as claimed. The proof of (b) is analogous to that of (a), although for completeness we reproduce it here. That is, we are going to show that Ker± ct(V) =K± ct(A)for all t∈❲−∞,c❳. So, let us show first that the inclusion ⊆holds. Given α1 it ∈K+ ct(A)(resp. α1 it ∈K− ct(A)), we have that ρts(α1 it) =0for all s ∈❲c, ∞❳(resp. for some s ∈❲t−, c❳). In particular, α1 it ∈Ker+ ct(V)(resp. α1 it ∈Ker− ct(V)). As Ker± ct(V)are subspaces of Vt, we obtain the inclusions Ker+ ct(V) ⊇K+ ct(A)and Ker− ct(V) ⊇K− ct(A). Finally, the inclusion ⊆from (b) follows from Lemma 2.7; notice that in the case Ker− ct(V) ⊆K− ct(A), if cis decorated by +we need to change the decoration to −to apply Lemma 2.7. Lemma B.1. Consider a basis Wfor a vector space W, together with a pair of subsets S, T⊆W. Then S∩T=S∩T. Proof. The inclusion ⊇is clear, so we only need to prove ⊆. We use the notation W={wi}i∈, S={wi}i∈(S)and T= {wi}i∈(T), where (S)and (T)denote the corresponding subindex sets of . Consider a vector v ∈S∩T, then there exist coefficients xi∈kfor all i ∈(S)and x i∈kfor all j ∈(T)so that v =i∈(S)xiwiand also v =j∈(T)x iwj. We define xi=0for all i ∈ \(S)and also x i=0for all j ∈ \(T). Altogether, we obtain i∈(S)xiwi−j∈(T)x iwj= i∈(xi−x i)wi=0, and by linear independence of W, we have that xi=x ifor all i ∈. In particular, xi= 0if and only if x i= 0, and so if xi= 0then i ∈(S) ∩(T). Therefore v =i∈(S)∩(T)xiwiand v ∈S∩Tas claimed.  Lemma B.2. Consider a basis Wfor a vector space W, together with a subset S⊆W. Then W\S≃WS. Proof. Define a linear map φ:W\S→WSsending w ∈W\Sto its class w +S∈WS. It is clear that φis surjective. On the other hand, dim(W\S) =dim(WS)and so φmust be an isomorphism.  References [1] G.E. Carlsson, Topology and data, Bulletin of the American Mathematical Society 46 (2009) 255–308. [2] H. Edelsbrunner, J. Harer, Computational Topology: An Introduction, American Mathematical Society, 2009. [3] F. Chazal, V. de Silva, M. Glisse, S. Oudot, The Structure and Stability of Persistence Modules, Briefs in Mathematics, Springer International Publishing, 2016. [4] P. Bubenik, J. Scott, Categorification of persistent homology, Discrete and Computational Geometry 51 (2014) 600–627. [5] S. Oudot, Persistence Theory -from Quiver Representations to Data Analysis, Mathematical Surveys and Monographs, vol. 209, AMS, 2015. [6] W. Crawley-Boevey, Decomposition of pointwise finite-dimensional persistence modules, Journal of Algebra and Its Applications 14 (5) (2015) 1550066. [7] The GUDHI project, GUDHI user and reference manual, 3.6.0 edition, GUDHI editorial board, https://gudhi .inria .fr /doc /3 .6 .0/, 2022. [8] G. Tauzin, U. Lupo, L. Tunstall, J.B. Pérez, M. Caorsi, A. Medina-Mardones, A. Dassatti, K. Hess, giotto-tda: a topological data analysis toolkit for machine learning and data exploration, arXiv:2004 .02551, 2020. [9] N. Saul, C. Tralie, Scikit-tda: topological data analysis for python, https://scikit -tda .org/, 2019. [10] U. Bauer, M. Lesnick, Induced matchings and the algebraic stability of persistence barcodes, Journal of Computational Geometry 6(2) (2015) 162–191. 18 R. Gonzalez-Diaz, M. Soriano-Trigueros and A. Torras-Casas Computational Geometry: Theory and Applications 112 (2023) 101985 [11] M. Buchet, E. Escolar, Realizations of indecomposable persistence modules of arbitrarily large dimension, in: 34th Int. Symposium on Computational Geometry, vol. 99, SoCG 2018, 2018, 15. [12] E. Escolar, Y. Hiraoka, Persistence modules on commutative ladders of finite type, Discrete and Computational Geometry 55 (2014) 100–157. [13] M. Botnan, V. Lebovici, S. Oudot, On rectangle-decomposable 2-parameter persistence modules, in: 36th Int. Symposium on Computational Geometry, vol. 164, SoCG 2020, 2020, 22. [14] H. Asashiba, E. Escolar, Y. Hiraoka, H. Takeuchi, Matrix method for persistence modules on commutative ladders of finite type, Japan Journal of Industrial and Applied Mathematics 36 (2019) 97–130. [15] U. Bauer, M. Lesnick, Persistence Diagrams as Diagrams: A Categorification of the Stability Theorem, Topological Data Analysis. Abel Symposia, vol. 15, Springer, Cham, 2020, pp. 67–96. [16] A. Torras Casas, Distributing persistent homology via spectral sequences, arXiv:1907.05228, 2020. [17] H. Takeuchi, The persistent homology of a sampled map: from a viewpoint of quiver representations, Journal of Applied and Computational Topology 5 (2021) 179–213. [18] H. Edelsbrunner, G. Jabło ´ nski, M. Mrozek, The persistent homology of a self-map, Foundations of Computational Mathematics 15 (2015) 511–533. [19] E. Riehl, Category Theory in Context, Dover Modern Math Originals, Dover Publications, Aurora, 2017. [20] S. MacLane, Categories for the Working Mathematician, Graduate Texts in Mathematics, vol. 5, Springer-Verlag, New York, 1971. [21] C. Weibel, An Introduction to Homological Algebra, Cambridge Studies in Advanced Mathematics, Cambridge University Press, 1994. [22] A. Grothendieck, Sur quelques points d’algèbre homologique, ii, Tohoku Mathematical Journal 9(3) (1957) 119–221. 19