Linear-time LUP decomposition of forest-like matrices

A square matrix M has an LUP decomposition if it can be written as LUP, where L is a unit lower-triangular matrix, U is an upper-triangular matrix, and P is a permutation matrix. We present a linear-time algorithm for finding an LUP decomposition for a nonsingular neighborhood matrix of a tree. We also identify a more general class of matrices we call forest-like for which the algorithm can be modified.