Structural graphs and ordered symmetric elimination

Let $F$ be a field, let $n\in \mathbb{N}$ (including $0$), and let $A\in M_{n\times n}(F)$ satisfy $A_{ij}=A_{ji}$ for every $i,j<n$ (that is, $A$ is symmetric). Its structural graph is the simple undirected graph $G_0=(V,E_0)$ with vertex set $V=\{0,\dots ,n-1\}$ and edge set

$E_0:=\{\{i,j\}:0\le i<j<n,A_{ij}\mathrm{\ne }0\}\mathrm{.}$

An elimination ordering is a listing $v_0,\dots ,v_{n-1}$ in which every vertex of $V$ occurs exactly once. Define the current vertex set by $V_k=\{v_{\mathrm{\ell }}:k\le \mathrm{\ell }<n\}$, starting with the structural graph $G_0$. At step $k$, the later neighbors of $v_k$ are

$N_k(v_k):=\{u\in V_k\setminus \{v_k\}:\{u,v_k\}\in E_k\}\mathrm{.}$

The filled graph $G_{k+1}=(V_{k+1},E_{k+1})$ is obtained by deleting $v_k$ and its incident edges, retaining all edges between remaining vertices, and adding every edge between two distinct vertices of $N_k(v_k)$. An edge added at step $k$ that was not already in $E_k$ is a fill edge. Repeating this rule defines the symbolic elimination pattern for the ordering; it is defined from the initial graph and ordering alone, without numerical pivot values.

If $N_k(v_k)$ is nonempty, the parent of $v_k$ is the later neighbor $v_{\mathrm{\ell }}$ with least position $\mathrm{\ell }>k$ in the ordering. If $N_k(v_k)$ is empty, $v_k$ is a root. Each non-root has a unique parent, and positions strictly increase along parent edges, so there is no directed cycle. If the underlying undirected graph had a cycle with $q$ vertices, orient its $q$ edges from child to parent. Each vertex has at most one outgoing parent edge, so these $q$ edges force every cycle vertex to have one outgoing edge along the cycle; following them gives a directed cycle, contradicting strict increase. Thus the parent relation is an elimination forest.