On product of companion matrices

This paper describes an explicit combinatorial formula for the product of companion matrices. The method relies on the connections between matrix algebra and associated combinatorial structures to enumerate the paths in an unweighted digraph. As an application, we obtain bases for the solution space of the linear difference equation with variable coefficients.