Elimination graph

One step of symmetric Gaussian elimination removes the pivot vertex and connects its remaining neighbors into a clique. The rule follows from the Schur complement update $a_{ij}\leftarrow a_{ij}-a_{ik}{a}_{kj}/a_{kk}$. Repeating it predicts the generic factor sparsity; exceptional numerical cancellations can remove structurally predicted entries.

After eliminating a vertex set $E$, a generic edge between remaining vertices $i,j$ exists exactly when the original matrix graph contains a path from $i$ to $j$ whose internal vertices all belong to $E$. Inductively, the new edges at pivot $k$ concatenate two such paths through $k$; conversely split any allowed path at $k$, or retain it when it avoids $k$. This characterizes fill by graph reachability.