= Leaf elimination of a tree-pattern positive-definite matrix
Associate an undirected graph with a symmetric matrix's off-diagonal nonzero pattern. Eliminating vertex $i$ updates the remaining matrix by $a_{jk}\mapsto a_{jk}-a_{ji}a_{ik}/a_{ii}$. Only pairs of neighbors of $i$ can acquire <fill-in>. If the graph is a tree, remove leaves successively: each eliminated vertex has at most one remaining neighbor, so only a diagonal entry can change. Every <Schur complement> of a <positive-definite matrix> is positive definite, so no zero pivot forces a different ordering. Leaf removal therefore constructs a <perfect elimination ordering> and a fill-free factorization.
Back to article page
