On the Structural Theorem of Persistent Homology

We study the categorical framework for the computation of persistent homology, without reliance on a particular computational algorithm. The computation of persistent homology is commonly summarized as a matrix theorem, which we call the Matrix Structural Theorem. Any of the various algorithms for computing persistent homology constitutes a constructive proof of the Matrix Structural Theorem. We show that the Matrix Structural Theorem is equivalent to the Krull–Schmidt property of the category of filtered chain complexes. We separately establish the Krull–Schmidt property by abstract categorical methods, yielding a novel nonconstructive proof of the Matrix Structural Theorem. These results provide the foundation for an alternate categorical framework for decomposition in persistent homology, bypassing the usual persistence vector spaces and quiver representations.

Authors and Affiliations

1. Hiraoka Laboratory, KUIAS, Kyoto University, Kyoto, 606-8501, Japan

   Killian Meehan

2. Mathematics Department, University of Missouri, 202 Math Sci Bldg, Columbia, MO, 65211, USA

   Andrei Pavlichenko & Jan Segert

Corresponding author

Correspondence to Jan Segert.

Editor in Charge: Kenneth Clarkson

Appendix A: Bruhat Uniqueness Lemma

Here we establish the uniqueness of the persistence canonical form \(\underline{D}\) appearing in the Matrix Structural Theorem 1.4, as well as in the ungraded version Theorem 1.2. Our result generalizes the uniqueness statement for the usual Bruhat factorization of an invertible matrix [2, 18].

It is convenient to make the following definitions. We call an (upper) triangular matrix Uunitriangular if it is unipotent, meaning that each diagonal entry is 1. We call a matrix Mquasi-monomial if each row has at most one nonzero entry and each column has at most one nonzero entry. We remark that a unitriangular matrix is always square, but a quasi-monomial matrix need not be square. The key to proving uniqueness is:

Lemma A.1

Suppose \(M_1\,U = V \,M_2 \), where \(M_1\) and \(M_2\) are quasi-monomial and U and V are unitriangular. Then \(M_2=M_1\).

In the following proof, the term row-pivot denotes a matrix entry that is the leftmost nonzero entry in its row, and column-pivot denotes a matrix entry that is the bottommost nonzero entry in its column.

Proof

The first half of the proof consists of showing that every nonzero entry of \(M_2\) is also an entry of \(M_1\). A nonzero entry of the quasi-monomial matrix \(M_2\) is a column-pivot. Similarly a nonzero entry of the quasi-monomial matrix \(M_1\) is a row-pivot. It now suffices to show that a column-pivot of \(M_2\) is a row-pivot of \(M_1\). Since V is unitriangular, \(VM_2\) has the same column-pivots as \(M_2\). Similarly since U is unitriangular, \(M_1U\) has the same row-pivots as \(M_1\). It now suffices to prove that a column-pivot of \(S = VM_2\) is a row-pivot of \(S =M_1U\). Suppose to the contrary that some column-pivot of S is not a row-pivot of S. Let x be the leftmost such column-pivot. Since x is not a row-pivot, there exists a row-pivot y to the left of x in the same row. If y were a column-pivot of \(S = VM_2\), then it would be a column-pivot of \(M_2\). But the quasi-monomial matrix \(M_2\) cannot have two nonzero entries y and x in the same row. So y is not a column-pivot of S, and there exists a column-pivot z below y in the same column. If z were a row-pivot of \(S = UM_1\), then it would be a row-pivot of \(M_1\). But the quasi-monomial matrix \(M_1\) cannot have two nonzero entries z and y in the same column. So z is a column-pivot of S that is not a row-pivot of S, and z is to the left of (and below) x. This is a contradiction, because x is the leftmost such column-pivot.

The second half of the proof consists of showing that every nonzero entry of \(M_1\) is also an entry of \(M_2\). This is analogous to the first half, and we omit the details. The two matrices then have the same nonzero entries, so they must also have the same zero entries. Since all the entries of the two matrices are the same, we have proved \(M_2=M_1\). \(\square \)

Recall that a matrix M is Boolean if every non-zero entry is 1. An almost-Jordan differential matrix \({\underline{D}}\) is Boolean and quasi-monomial.

Proposition A.2

Suppose \(P_1A=BP_2\) where \(P_1\) and \(P_2\) are Boolean quasi-monomial and A and B are invertible triangular. Then \(P_2=P_1\).

Proof

Factor \(A = T_1U\) as the product of an invertible diagonal matrix \(T_1\) and a unitriangular matrix U. Factor \(B = VT_2\) as the product of a unitriangular matrix V and an invertible diagonal matrix \(T_2\). Then \((P_1 T_1)U = V(T_2 P_2)\), with \((P_1 T_1)\) and \((T_2 P_2)\) quasi-monomial. Lemma A.1 then gives the \(P_1 T_1 =T_2 P_2\). Since the quasi-monomial matrices \(P_1\) and \(P_2\) are Boolean, the conclusion follows. \(\square \)

We remark that any permutation matrix P is Boolean and quasi-monomial, so Proposition A.2 generalizes the standard uniqueness result for Bruhat factorization of an invertible matrix [2, 18].

The uniqueness of the persistence canonical form \(\underline{D}\) appearing in Theorem 1.2 and in the Matrix Structural Theorem 1.4 now follows easily:

Corollary A.3

Suppose D is a differential matrix and \(B_1\) and \(B_2\) are invertible triangular matrices. If both differential matrices \({\underline{D}}_1 = B_1^{-1} D B_1\) and \({\underline{D}_2} = B_2^{-1} D B_2\) are almost-Jordan, then \({\underline{D}}_2 ={\underline{D}}_1\).

Proof

\({\underline{D}_1} (B_1^{-1} B_2) = (B_1^{-1} B_2) {\underline{D}_2}\), and the result follows from Proposition A.2. \(\square \)

Appendix B: Constructively Proving the Matrix Structural Theorem

1.1 B.1 Linear Algebra of Reduction

In this section we discuss column-reduction of a matrix \(M:{\mathbb F}^m \rightarrow {\mathbb F}^n\), including its application to describing the kernel and image of the matrix. Column-reduction of a differential matrix D is a standard tool in the computation of persistent homology, where it is usually just called reduction [12, 16, 35, 36]. We prefer the more precise terminology in order to maintain the distinction with row-reduction, since both are used for Bruhat factorization [2, 18, 23].

As in Appendix A, the term column-pivot denotes a matrix entry that is the bottommost nonzero entry in its column. A matrix R is said to be column-reduced if each row has at most one column-pivot.

Definition B.1

A column-reduction of a matrix M is an invertible triangular matrix V such that \(R = MV\) is column-reduced.

A column-reduction V exists for any matrix M, but is not unique in general. Column-reduction algorithms used for persistent homology [13, 16, 35, 36] usually prioritize computational efficiency. For our computational examples, we will use a column-reduction algorithm that is popular for Bruhat factorization [2, 18]. This algorithm is easy to implement, but is not very efficient computationally. The algorithm starts at the leftmost column of M and proceeds rightward by successive columns as follows:

• If the current column is zero, do nothing.

• If the current column is nonzero, add an appropriate multiple of the current column to each column to the right in order to zero the entries to the right of the column-pivot (in the same row).

Stop if the current column is the rightmost column, otherwise proceed to the column immediately to the right and repeat. By design, the resulting matrix R has the property that any column-pivot has only zeros to the right of it (in the same row). So a row of R cannot contain more than one column-pivot, implying that R is column-reduced. The invertible triangular column-reduction matrix V is constructed by performing the same column operations on the identity matrix I, where I has same number of columns as M.

We briefly discuss some linear-algebraic properties of column-reduction. A column-reduction easily yields a basis for the kernel of a matrix as well as a basis for the image. By contrast, Gaussian elimination easily yields a basis for the image a matrix, but requires additional back-substitution to produce a basis for the kernel. Column-reduction algorithms are therefore a convenient alternative to Gaussian elimination for matrix computations in general, and this fact seems to be underappreciated. We use a variant of the usual adapted basis for a filtered vector space, disregarding the ordering of basis elements. We will say that a basis of a finite-dimensional vector space X is almost-adapted to a subspace \(Y \subseteq X\) if Y is spanned by the set of basis elements that are contained in Y. Definition B.1 yields:

Corollary B.2

Let \(V:{\mathbb F}^m \rightarrow {\mathbb F}^m\) be a column-reduction of a matrix \(M:{\mathbb F}^m \rightarrow {\mathbb F}^n\). Then:

1. 1.

   The nonzero columns of the column-reduced matrix \(R = MV\) are a basis of \({\mathrm{im}}\,M\).

2. 2.

   The columns of the invertible triangular matrix V are a basis of \({\mathbb F}^m\), and this basis is almost-adapted to \(\ker M\).

Proof

1. 1.

   The nonzero columns of R span \({\mathrm{im}}\,M\). The nonzero columns of R are linearly independent because R is column-reduced.

2. 2.

   The columns of V are a basis of \({\mathbb F}^m\) because V is invertible. This basis is almost-adapted to \(\ker M\) because the nonzero columns of \(R = MV\) are linearly independent.

\(\square \)

Example B.3

We compute in detail a column-reduction of the matrix \(M:{\mathbb Q}^4 \rightarrow {\mathbb Q}^3\), which is presented below with a column augmentation by the identity matrix I.

The result of the computation is a factorization \(R = MV\), where R is column-reduced and V is invertible triangular (and unipotent). We describe each step of the computation:

1. 1.

   The first column of M is nonzero, so it has a column-pivot. At the next processing step, boldface the column-pivot for clarity, and add an appropriate multiple of the first column to each column to the right in order to zero the entries to the right of the column-pivot (in the same row).

2. 2.

   At this point the second column is zero, so requires no processing step.

3. 3.

   At this point the third column is nonzero, so it has a column-pivot. At the next processing step, boldface the column pivot, and add an appropriate multiple of the third column to each column to the right in order to zero the entries to the right of the column-pivot (in the same row).

4. 4.

   At this point the fourth column is zero, so requires no processing step.

Columns 1 and 3 of R are the nonzero columns, so they are a basis of \({\mathrm{im}}\,M \subseteq {\mathbb Q}^3\). The four columns of V are a basis of \({\mathbb Q}^4\) that is amost-adapted to \(\ker M\). Columns 2 and 4 of V correspond to the zero columns of R, so they are a basis of \(\ker M\subseteq {\mathbb Q}^4\).

1.2 B.2 Matrix Structural Theorem via Reduction

The standard algorithm of persistent homology [16, 35, 36] starts with a differential matrix D and constructs a matrix B satisfying the conditions of:

Theorem 1.2

(Ungraded Matrix Structural Theorem) Any differential matrix D factors as \(D = B {\underline{D}} B^{-1}\) where \({\underline{D}}\) is an almost-Jordan differential matrix and B is a triangular matrix.

The matrix formulation of the standard algorithm constructs a matrix \(B = \widehat{V}\) from a column-reduction V of a differential matrix D, as discussed in [5, 13] for \({\mathbb F} = {\mathbb Z}/2 {\mathbb Z}\). Since \(R = DV\) is column-reduced, there exists at most one nonzero column of R that has its column-pivot in row k. Here \(1 \le k \le m\) where m is the number of rows of the square matrix D. \(\widehat{V}\) is constructed one column at a time using the following rule:

• If there exists a nonzero column of R that has its column-pivot in row k, then column k of \(\widehat{V}\) is equal to this column of R.

• If there does not exist a nonzero column of R that has its column-pivot in row k, then column k of \(\widehat{V}\) is equal to column k of V.

The matrix \(\widehat{V}\) is invertible triangular, because each column is nonzero and has its column-pivot on the diagonal.

Unlike its progenitor V, the matrix \(\widehat{V}\) contains all of the nonzero columns of R. We introduce the “pivot matrix” of R to encode the combinatorial data needed to recover R. For any column-reduced matrix M, the pivot matrix of M is constructed by replacing every column-pivot of M with 1, and every other nonzero entry of M with 0. It follows that the pivot matrix is is Boolean and quasi-monomial (Appendix A).

Lemma B.4

Let \(\underline{D}\) be the pivot matrix of R. Then \(\widehat{V} \underline{D} = R\).

Proof

Supposing column k of R is nonzero, let j be the row number of the unique nonzero entry in column k of \(\underline{D}\). Then by construction, column j of \(\widehat{V}\) is equal to column k of R. \(\square \)

But like its progenitor V, the matrix \(\widehat{V}\) is a column-reduction of the differential D:

Lemma B.5

\(D \widehat{V} = R\).

Proof

The triangular matrix V is a column-reduction of D, as per Definition B.1. We now show that the triangular matrix \(\widehat{V}\) is also a column-reduction of D. Recall that \(\widehat{V}\) is constructed as a modification of V, by replacing a (possibly empty) subset of the columns of V with columns of R. Every column of R is in \(\ker D\), because \(D R = D^2 V = 0\). So \(\widehat{R} := D \widehat{V}\) is constructed as a modification of \(R = D V\), by replacing a (possibly empty) subset of the nonzero columns of R by zero columns. This particular modification preserves the column-reduced property, so \(\widehat{R} = D \widehat{V}\) is column-reduced. It follows that \(\widehat{V}\) is a column-reduction of D, as per Definition B.1.

Since \(\widehat{V}\) and V are column-reductions of the same matrix D, we see from Corollary B.2 that \(\widehat{R}\) and R have the same number (namely \({\mathrm{rank}}\,D\)) of nonzero columns. It follows that in the construction of \(\widehat{R}\) as a modification of R, none of the nonzero columns of R can be replaced by zero columns. This establishes the equality \(\widehat{R} = R\), and the conclusion \(D \widehat{V} = R\) follows. \(\square \)

We can now complete the constructive proof of Theorem 1.2:

Proof

Letting \(B = \widehat{V}\), Lemmas B.4 and B.5 give \(B {\underline{D}} = R = D B\). The pivot matrix \({\underline{D}} =B^{-1} D B\) is a differential matrix, since it is conjugate to the differential matrix D. It only remains to check that the differential matrix \({\underline{D}}\) is almost-Jordan. This requires constructing a permutation matrix P such that \(P^{-1} {\underline{D}} P\) is Jordan. Since the differential matrix \({\underline{D}}\) is furthermore Boolean and quasi-monomial, P can be constructed by the procedure previously explained in Example 4.4. \(\square \)

An immediate corollary of the proof is the important and generally known fact that the almost-Jordan differential \(\underline{D}\) can be easily constructed as the pivot matrix of the column-reduced matrix \(R = DV\). Furthermore, while R may depend on the choice of column-reduction V, Corollary A.3 guarantees that the pivot matrix \(\underline{D}\) is an invariant of D (which we call the persistence canonical form of D in Sect. 1.3) independent of the choice of column-reduction V. The matrix \(\underline{D}\) contains all of the data for the multiplicities of the summands in a decomposition, and this is independent of the choice of decomposition because of the Krull–Schmidt property. The data required to compute a particular decomposition is conveniently encoded by in the matrix \(\widehat{V}\), which is a column-reduction with additional special properties. These points are illustrated in the example at the end of the section. In the language of the standard framework, one says that the “barcodes” are contained in \(\underline{D}\), and the “creators and destroyers” of persistent homology are contained in \(\widehat{V}\).

We also note that the invertible triangular matrix \(B = \widehat{V}\) produced by the standard algorithm is not in general normalized (see the discussion in Sect. 1.3 following Theorem 1.2). But it is easy to construct a diagonal matrix T such that the invertible diagonal matrix \(B = \widehat{V} T\) is normalized. This will also be illustrated in the example at the end of the section.

The graded case is an easy modification:

Theorem 1.4

(Matrix Structural Theorem) Any block-superdiagonal differential matrix D factors as \(D = B {\underline{D}} B^{-1}\) where \({\underline{D}}\) is a block-superdiagonal almost-Jordan differential matrix and B is a block-diagonal triangular matrix.

Proof

Let D be a block-superdiagonal differential matrix D. Then the invertible triangular column-reduction marix V produced by a reduction algorithm, such as [16, 35, 36] or our Appendix B.1, is block-diagonal. If V is block-diagonal, then so is the invertible triangular matrix \(B = \widehat{V}\) constructed by the standard algorithm from V and \(R = D V\). \(\square \)

The following example of a standard algorithm computation illustrates both block-structure and normalization.

Example B.6

We work with block-superdiagonal differential \(D:{\mathbb Q}^7 \rightarrow {\mathbb Q}^7\) of Example 1.5, which is presented below with a column augmentation by the identity matrix I. The identity matrix is block-diagonal with respect to the grading structure inherited from D. We first compute a column-reduction of D:

The result of the computation is a factorization \(R = DV\), where R is column-reduced and V is invertible triangular (and unipotent). The intervening steps are omitted for brevity. The block-superdiagonal almost-Jordan differential \(\underline{D}\) is now easily computed as the pivot matrix of R, by setting every column-pivot to 1 and every other nonzero entry to 0:

The barcode invariants can be computed from the matrix \(\underline{D}\) and the filtration levels of the basis elements.

Proceeding to compute a particular decomposition as in Example 4.4, we use the standard algorithm to construct \(\widehat{V}\) as a modification of V. Each nonzero column of R replaces the column of V that has its column-pivot in the same row. Then \(\widehat{V}\) inherits the block-diagonal structure of V:

We list the columns of \(\widehat{V}\) that are equal to columns of R; this data is also encoded by the nonzero entries of the pivot matrix \(\underline{D}\):

• Column 2 of \(\widehat{V}\) is equal to column 4 of R; row 2 column 4 of \(\underline{D}\) has entry 1.

• Column 3 of \(\widehat{V}\) is equal to column 5 of R; row 3 column 5 of \(\underline{D}\) has entry 1.

• Column 6 of \(\widehat{V}\) is equal to column 7 of R; row 6 column 7 of \(\underline{D}\) has entry 1.

Each of the remaining columns of \(\widehat{V}\) is equal to the corresponding column of V. One may now check by matrix multiplication that \({\widehat{V}^{-1}} D \, \widehat{V}={\underline{D}}\), where \({\underline{D}}\) is the pivot matrix of R as above.

The invertible triangular matrix \(\widehat{V}\) is not normalized: column 6 of \(\widehat{V}\) corresponds to a zero column of \({\underline{D}}\), but its diagonal entry is not equal to 1. We can normalize by scalar multiplication of the appropriate columns. Let T be the diagonal matrix with 1 in the first five diagonal entries and \(-1\) in the last two. Then the invertible triangular matrix \(B = {\widehat{V}}T\) is normalized, and this is the matrix that appears in Example 1.5. Note that \(B^{-1} D B = {\underline{D}} = {\widehat{V}}^{-1} D\, {\widehat{V}}\) by Corollary A.3.

Reprints and permissions