<Fill-in> consists of new nonzero positions created by <Gaussian elimination>, absent from the original <sparse matrix> in the same ordering. For a <Cholesky decomposition> $PAP^T=CC^T$, compare $C$ with the lower triangle of $PAP^T$, not with the unpermuted input. Each new undirected <edge> of the <elimination graph> contributes one structural position in $C$. The <sparse elimination of a four-leaf star> gives six such positions when the center is eliminated first, and none when the leaves are eliminated first.

<Symbolic factorization> predicts possible nonzeros from the pattern alone. An initially zero $a_{ij}$ becomes nonzero in a single scalar step if both $a_{ik}$ and $a_{kj}$ are nonzero; however, at later steps several contributions can cancel. For an exact example, let
$$
H=\begin{pmatrix}2&1&1&0\\1&2&0&1\\1&0&3&-1/3\\0&1&-1/3&3\end{pmatrix}.
$$
Eliminate indices $1,2$ in that order. The first <Schur complement>, in order $(2,3,4)$, is
$$
\begin{pmatrix}3/2&-1/2&1\\-1/2&5/2&-1/3\\1&-1/3&3\end{pmatrix}.
$$
The second <pivot element> updates the $(3,4)$ entry to $-1/3-(-1/2)(1)/(3/2)=0$. The remaining block is $\operatorname{diag}(7/3,7/3)$, so all four <pivot elements> are positive and $H$ is a <symmetric positive-definite matrix>. The <elimination graph> retains the structural <edge> $3-4$, but this exact choice of coefficients makes the numerical entry vanish. A small change to $H_{34}=H_{43}$ generally removes the cancellation.

Such an exact zero is different from discarding a small value computed with <floating-point arithmetic>. The <symbolic factorization> deliberately reserves space for possible entries without depending on special numerical identities. A <perfect elimination ordering> creates no structural <fill-in> at all; an ordering with cancellations need not have that property.


 Fill-in (source code)