fill-in の経路定理

$A\in M_n(\mathbb{R})$ を対称行列とし、$E_k$ を 定義 6.3 の消去グラフの辺集合とする。

1. $k\le i,j$, $i\ne j$ について、$\{i,j\}\in E_k$ であることと、$G(A)$ に $i$ から $j$ への歩道 $i=v_0,v_1,\ldots,v_m=j$（$m\ge1$、隣り合う頂点は $G(A)$ の辺で結ばれ、頂点の重複を許す）で、途中の頂点 $v_1,\ldots,v_{m-1}$ がすべて $k$ より小さいものがあることは同値である。
2. $A$ が正定値で、$A^{(k)}$ をその $k$ 段目の Schur 補行列、$R$ を Cholesky 因子とする。$k\le i,j$, $i\ne j$ で $a^{(k)}_{ij}\ne0$ なら $\{i,j\}\in E_k$ であり、$i\lt j$ で $r_{ij}\ne0$ なら $\{i,j\}\in E_i$ である。
3. 2 で、さらに消去の途中で打ち消しが起こらない（各段の $a^{(k+1)}_{ij}=a^{(k)}_{ij}-a^{(k)}_{ik}a^{(k)}_{kj}/a^{(k)}_{kk}$ の右辺の 2 項のうち少なくとも一方が非零なら左辺も非零）とすると、$i\lt j$ について $$r_{ij}\ne0\iff G(A)\text{ に }i\text{ から }j\text{ への、途中の頂点がすべて }i\text{ より小さい歩道がある}.$$