A matrix for counting paths in acyclic digraphs
Let \(\Gamma\) be an acyclic digraph without multiple edges on the vertex set \(\{x_1,\dots,x_n\}\). Define the \(n\times n\)-matrix \(A=A_\Gamma\), putting \(A_{ij}=0\) if \((x_i,x_j)\) is an arc of \(\Gamma\) and \(A_{ij}=1\) otherwise. It is proved that the coefficient of \(z^k\) in the characteristic polynomial \(\text{det}(I+zA)\) is the number of \(j\)-vertex paths in \(\Gamma\).
scientific article; zbMATH DE number 883810