Directed graphs, 2D state models and characteristic polynomials of irreducible matrix pairs

The definition and main properties of a 2D digraph, namely a directed graph with two kinds of arcs, are introduced. Under the assumption of strong connectedness, the analysis of its paths and cycles is performed, based on an integer matrix whose rows represent the compositions of all circuits, and on the corresponding row module. Natural constraints on the composition of the paths connecting each pair of vertices lead to the definition of a 2D strongly connected digraph. For a 2D digraph of this kind the set of vertices can be partitioned into disjoint 2D-imprimitivity classes, whose number and composition are strictly related to the structure of the row module. Irreducible matrix pairs, i.e. pairs endowed with a 2D strongly connected digraph, are subsequently discussed. Equivalent descriptions of irreducibility, naturally extending those available for a single irreducible matrix, are obtained. These refer to the free evolution of the 2D state models described by the pairs and to their characteristic polynomials. Finally, primitivity is viewed as a special case of irreducibility, and completely characterized in terms of 2D-digraphs, characteristic polynomials, and 2D system dynamics.