Matrix Analysis of Oriented Graphs with Irreducible Feedback Loops

A generating function is obtained for the nonrepetitive closed loops of a network with unidirectional elements; from this is derived an analogous function for the irreducible loops. Criteria for the existence of loops are then established and the size of the smallest loop present determined; an asymptotic evaluation is made of the number of irreducible loops in a completely connected network. Further application of the generating function permits estimation of bounds for both irreducible and composite closed loops of a given order; less rigorous bounds are found by two perturbation techniques. The generating function is reformulated in terms of determinant-like quantities and application made to small networks. Transformations preserving the irreducible loops of a system are discussed at length, following a delineation of the meaning of loop equivalence. Methods employed include elimination of branches, condensation of nodes, and decomposition of circuits, with criteria for their utilization being set forth. Finally, connection is made between the analysis of the present paper and those prevalent in more avowedly topological treatments.