We use the notation to denote the **i**th row, and to
denote the **j**th column, of a matrix **M**. For a given sparse matrix
**M**, we define

and

In other words, is the sparsity structure of row **i**
of the strict lower triangle of **M**, while is the
sparsity structure of column **j** of the strict lower triangle of **M**.
For the Cholesky factor **L**, we define the * parent* function as
follows:

Thus, is the row index of the first offdiagonal nonzero in
column **j** of **L**, if any, and has the value **j** otherwise. Using the
parent function, we define the * elimination tree* as a graph having
**n** vertices, with an edge between vertices **i** and **j**, for **i > j**,
if . If the matrix is irreducible, then the elimination
tree is indeed a single tree with its root at vertex **n** (otherwise it is
more accurately termed an * elimination forest*). The elimination
tree, which we denote by , is a spanning tree for the filled
graph . The many uses of the elimination tree in analyzing and
organizing sparse Cholesky factorization are surveyed in [57].
We will illustrate these concepts pictorially in several examples
below.