Elimination Graphs

Why

We want to model the progressive fill-in during Gauss elimination with graphs.

Definition

Let $G = ((V, E), \sigma )$ be an ordered undirected graph with $\nu m{V} = n$. Define $E_0 = E$. The elimination edge sequence of $G$ is a sequence $(E_1, \dots , E_{n-1})$ defined by

\[ \begin{aligned} E_i & = E_{i-1} \union \\ &\Set{\set{v, w}}{v \succ \sigma (i), w \succ \sigma (i), \text{ and } \set{\sigma (i), w} \in E_{i-1}} \end{aligned} \]

for $i = 1, \dots , n-1$. The difference between $E_{i-1}$ and $E$ can be described by saying that the higher neighborhood of the intermediate graph $((V, E_{i-1}), \sigma )$ is made complete by the addition of edges between all non-adjacent vertices.

The elimination graph of $G$ is the graph $((V, E_{n-1}), \sigma )$.