Digraph Branchings and Matrix Determinants

Abstract

We present a version of the matrix-tree theorem, which relates the determinant of a matrix to sums of weights of arborescences of its directed graph representation. Our treatment allows for non-zero column sums in the parent matrix by adding a root vertex to the usually considered matrix directed graph. We use our result to prove a version of the matrix-forest, or all-minors, theorem, which relates minors of the matrix to forests of arborescences of the matrix digraph. We apply the theorems to calculations of the time-evolution of a system with discrete states and then consider two strategies using these theorems to compute determinants.

The authors have moved the 'moving-arcs' theorem and factoring algorithm in the original version of this manuscript to a separate paper, as these sections were appropriate for the other article. We intend to submit the second article to arXiv soon