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 performe d, based on an integer matrix whose rows represent the compositions of all circuits, and on the corresponding row module. Natural constraint s on the composition of the paths connecting each pair of vertices lea d to the definition of a 2D strongly connected digraph. For a 2D digra ph of this kind the set of vertices can be partitioned into disjoint 2 D-imprimitivity classes, whose number and composition are strictly rel ated 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 exten ding those available for a single irreducible matrix, are obtained. Th ese refer to the free evolution of the 2D state models described by th e pairs and to their characteristic polynomials. Finally, primitivity is viewed as a special case of irreducibility, and completely characte rized in terms of 2D-digraphs, characteristic polynomials, and 2D syst em dynamics. (C) 1997 Elsevier Science Inc.