持续边界矩阵的列约化证书

算持续同调时，为什么常见算法只往当前列加更早的列，而不随意交换行列？因为列的顺序带着时间：更早的链可以修正现在的代表，未来的链却不能提前借来填洞。普通秩计算允许的许多操作，在这里会抹掉出生和死亡信息。

本页把算法写成一份能独立验证的矩阵证书。第一步得到的 $R$ 是约化边界列；第二步才构造真正同时作用在定义域和值域的新基。二者必须区分，否则很容易把 $R$ 误当成另一个微分，连平方为零都检查错。

形式陈述

一张矩阵收集全部次数，但每项仍有类型

固定域 $\mathbb F$ 。有限链复形有齐次基 $e_0,\ldots,e_{n-1}$ ，每个基带链次数 $|e_i|$ 和过滤级别 $f_i$ 。令 $D$ 的第 $j$ 列为 $de_j$ 在这组基中的坐标。要求

D^2=0,\qquad D_{ij}\ne0\Rightarrow |e_i|=|e_j|-1, \tag{1}

以及 $f_0\le\cdots\le f_{n-1}$ 、 $D_{ij}\ne0\Rightarrow i<j$ 。因此 $D$ 严格上三角，边界只用已出现的链。对单纯过滤，可以按过滤值、维数、同维任意固定次序排列，保证面先于余面。

要计算的是这份持续同调在各次数的条码。最后层以后采用常值延拓；相同过滤值的事件属于同一真实层。

左到右约化，并记住每一次列操作

对非零列向量 $v$ ，定义 $\operatorname{low}(v)$ 为最大非零行号；零列没有low。初始化

R=D,\qquad V=I.

按 $j=0,1,\ldots,n-1$ 处理。若当前非零列 $R_j$ 的low与一个更早的非零列 $R_k$ 相同，记公共行号为 $i$ ，执行

\alpha=R_{ij}/R_{ik},\qquad R_j\leftarrow R_j-\alpha R_k,\quad V_j\leftarrow V_j-\alpha V_k. \tag{2}

重复到当前列为零，或它的low与所有早期非零列不同，再进入下一列。每次操作都把当前low严格降低，所以有限步后停止。整个过程保持

R=DV, \tag{3}

其中 $V$ 上三角、对角全一，因而可逆。相同low的两列具有相同链次数，所以列操作不会混合次数。最终全部非零列的low互不相同。

每个 $i=\operatorname{low}(R_j)$ 形成一个出生—死亡索引对 $(i,j)$ 。未成为任何low、且自身 $R_i=0$ 的索引称未配对出生索引。下文证明这些名称的含义，而不是仅凭术语宣告正确。

输出不仅是一串端点

配对 $(i,j)$ 给次数 $|e_i|$ 的区间 $[f_i,f_j)$ ；若两端相等，丢弃空区间。未配对出生 $i$ 给 $[f_i,\infty)$ 。还可以交出

配对方向的出生循环 $R_j$ ，其链支撑不超过索引 $i$
它在死亡时刻的填充链 $V_j$ ，满足 $D V_j=R_j$
未配对方向的循环 $V_i$ ，满足 $D V_i=0$

最后构造矩阵 $W$ ：对每个配对 $(i,j)$ ，令 $W_i=R_j$ ；其余列令 $W_i=V_i$ 。令 $B_{ij}=1$ 对配对 $(i,j)$ 成立，其余条目为零。正确证书满足

DW=WB. \tag{4}

$W$ 才是完整的新基矩阵， $B=W^{-1}DW$ 才是新基下的微分。配对列 $W_i=R_j$ 的对角条目是原来的非零主元 $R_{ij}$ ，不一定为一；无需假设它已归一化，式(4)中的箭头系数仍恰好为一。

直觉

最晚出现的边界项决定当前冲突

一列边界可能包含很多行。消去它最晚的非零行，意味着用一个已知填充关系替换这部分，继续观察更早的链。当两列的low不再相同，就不能通过继续添加早列把这一项消掉。

不同low的非零列线性无关。若它们存在非平凡线性关系，取参与关系的最大low；只有对应那一列能在这一行贡献非零值，矛盾。这个简单观察既说明算法维护的主元有效，也支撑下面的关键链论证。

被配对的出生列为何一定为零

设 $i=\operatorname{low}(R_j)$ 。由 $R=DV$ 和 $D^2=0$ ， $DR_j=0$ ，所以 $R_j$ 是循环。把它展开到 $V$ 的列基中：

R_j=\sum_{k\le i}\gamma_kV_k,\qquad\gamma_i\ne0.

这是因为 $V$ 上三角且对角一，而 $R_j$ 在索引 $i$ 上非零、更高索引全零。取边界得

0=DR_j=\sum_{k\le i}\gamma_kR_k.

非零的 $R_k$ 线性无关。若 $R_i\ne0$ ，上式的非零系数 $\gamma_i$ 就产生矛盾。因此 $R_i=0$ 。特别地，一个死亡索引不可能同时又是另一个配对的出生索引。

从约化列补出真实过滤基

$W_i=R_j$ 的支撑不超过 $i$ ，且第 $i$ 项非零；保留的 $V_i$ 同样支撑不超过 $i$ 、对角为一。因此 $W$ 是对角非零的上三角矩阵，确实可逆。每列与对应原基同次数，且 $W,W^{-1}$ 都不提高过滤级别，所以它是过滤复形的合法换基。

若 $j$ 是死亡索引，上一步保证 $W_j=V_j$ ，于是 $DW_j=R_j=W_i$ 。配对出生列本来就是循环；未配对出生列的边界为 $R_i=0$ 。这就完整证明了式(4)。

于是链复形在这组过滤基下拆成两类独立小块：一条出生循环和一条后来填充它的链，或只有一条始终未被填充的循环。每个两项块直接给出 $[f_i,f_j)$ ；同级两项块在出现时已经可缩，不贡献同调。各块直和便给全部条码与映射，而不只是每个时刻的Betti数。

例子与边界

四边形的列轨迹

使用主例的过滤，基顺序固定为

0,1,2,3,01,12,03,23,02,012,023,

对应过滤值 $0,0,0,0,1,1,2,2,3,3,5$ 。顶点列为零；最初三条连接边 $01,12,03$ 的low分别为 $1,2,3$ 。边 $23$ 的边界为 $3-2$ ，可依次减去边 $03$ 、再加边 $12$ 与 $01$ 的边界而变为零，得到循环

V_7=[23]-[03]+[12]+[01].

边 $02$ 也约化为零。三角形 $012$ 的边界

R_9=[12]-[02]+[01]

以行 $8$ （边 $02$ ）为low。三角形 $023$ 原边界的该行系数为一，而 $R_9$ 的该行系数为负一，因此式(2)要求加上 $R_9$ ，不是减去。结果为

R_{10}=[01]+[12]-[03]+[23],\qquad V_{10}=[023]+[012]. \tag{5}

全部索引对为

(1,4),(2,5),(3,6),(8,9),(7,10).

前面三对产生零维死亡， $(8,9)$ 的真实端点同为三，应丢弃； $(7,10)$ 给一维区间 $[2,5)$ 。未配对顶点零给普通零维的无穷尾。式(5)还交出真正的死亡见证。

约化矩阵R未必平方为零

上例中， $R$ 的第 $7,8$ 列已经为零，但第 $4,5,6$ 列仍分别是 $1-0,2-1,3-0$ 。因此把 $R$ 当成作用在原坐标上的算子，会得到

R R_{10}=(1-0)+(2-1)-(3-0)=2-3\ne0. \tag{6}

这里右边的 $2,3$ 是顶点基，不是普通数字相减。故确有 $R^2\ne0$ 。与此同时 $D R_{10}=0$ 完全正确，因为它是旧边界下的循环。

根源是式(3)只改变列的输入坐标，输出仍用原坐标；同一换基下的算子应左右同时变换。若检查者只验证 $R^2=0$ ，反而会拒绝这份正确的持续约化。应检查 $D^2=0$ 、 $R=DV$ 、唯一low与式(4)。

三种顺序错误

把未来列加到过去列，可能使早期代表提前利用尚不存在的填充链，破坏过滤。把同一时刻的面排到边之前，则 $D$ 不再满足边界先于列的索引条件。把索引差当实际寿命，又会给主例中 $(8,9)$ 制造一条虚假的正长度区间。

可以改变同级内部的合法顺序，但每次都要按原始过滤值还原端点；合法排序保证的是同一实际条码，未保证每次得到同一索引配对或同一循环代表。完整枚举检查应比较端点及重数，而非要求所有中间矩阵逐字相同。

推论与应用

同级消去与循环恢复

可先用单位主元消去删除同一过滤级别的可缩对，保留其 $\iota,\rho,h$ 。在小复形中算出循环 $z'$ 与填充链 $w'$ 后，原复形中的链为 $\iota z'$ 与 $\iota w'$ ，仍满足 $d\iota w'=\iota z'$ ，且没有提高出现级别。

主例的 $[012]$ 与 $[02]$ 可这样删除。剩下的二维生成元边界直接就是四边环；包含把它送到 $[023]+[012]$ ，因此条码与式(5)一致。若把面 $012$ 延迟到时刻四，这对不再同级，预处理必须拒绝，否则会错误抹掉新增的 $[3,4)$ 。

成本、精度与验收

朴素稠密实现中，每次消去处理长为 $n$ 的列，每列至多下降 $n$ 次low，共至多 $O(n^3)$ 次域运算，存储 $D,R,V,W$ 为 $O(n^2)$ 。这里统计的是域运算次数；有理数分子分母可能增长，不能把它自动解释成相同的位复杂度。

保留完整 $V,W$ 可以交循环证书，也可能比只存条码更耗空间。稀疏约化、清除策略和专用复形的隐式枚举属于额外优化，不能从这份稠密成本直接宣称达到它们的性能。

输入验证应先核次数、真实级别、严格上三角与 $D^2=0$ 。输出验证再核可逆三角基、式(3)–(4)、配对重数与空区间处理。还可独立按早期循环与晚期边界直接计算每个持续映射的秩，与条码计数比较。域上为零是精确判断；浮点数接近零时若随意设阈值，可能改变主元、秩和全部端点，本页未提供这样的近似容差保证。

参考资料

Ulrich Bauer，Ripser: efficient computation of Vietoris–Rips persistence barcodes，2021，§3.1 Proposition 3.1与Algorithm 1。本文展开一般有限链情形的完整过滤基证明，并明确保留非单位一的主元，不声称实现Ripser专用优化。

形式陈述 ​

一张矩阵收集全部次数，但每项仍有类型 ​

左到右约化，并记住每一次列操作 ​

输出不仅是一串端点 ​

最晚出现的边界项决定当前冲突 ​

被配对的出生列为何一定为零 ​

从约化列补出真实过滤基 ​

四边形的列轨迹 ​

约化矩阵R未必平方为零 ​

三种顺序错误 ​

同级消去与循环恢复 ​

成本、精度与验收 ​

反向链接