The path matrix of a graph, its construction and its use in evaluating certain products (Q793752)

Let \(G=(V,E)\) be a finite connected digraph without self-loops or multiple edges. Its incidence matrix S is a \(| V| \times | E|\)-matrix defined by \[ S_{i,a} = \begin{cases} +1\quad&\text{,if \(i\) is start vertex of }a\\ -1\quad&\text{,if \(i\) is end vertex of }a\\ 0\quad&\text{,otherwise}\end{cases} \] for \(0\leq i\leq | V| -1,\quad 1\leq a\leq | E|.\) The reduced incidence matrix \(\hat S\) is obtained from S by eliminating row 0, corresponding to an arbitrary reference vertex. \(\hat S\) still contains all incidence information and is square, iff G is a tree. The generalized left inverse T (called path matrix, here) can be derived by the (weak) ordering implied by any directed spanning tree rooted in vertex 0. It is used in dynamic simulations of multi-body mechanical systems. Storage variants of \(\hat S\) and T are described. A depth-first algorithm for deriving T directly from \(\hat S\) is given, and some pseudo-algol programs for evaluating matrix-vector products involving T.