Kybernetika 38 no. 5, 503-520, 2002

Characterization of generic properties of linear structured systems for efficient computations

Christian Commault, Jean-Michel Dion and Jacob W. van der Woude


In this paper we investigate some of the computational aspects of generic properties of linear structured systems. In such systems only the zero/nonzero pattern of the system matrices is assumed to be known. For structured systems a number of characterizations of so-called generic properties have been obtained in the literature. The characterizations often have been presented by means of the graph associated to a linear structured system and are then expressed in terms of the maximal or minimal number of certain type of vertices contained in a combination of specific paths. In this paper we give new graph theoretic characterizations of structural invariants of structured systems. It turns out that these new characterizations allow to compute these invariants via standard and efficient algorithms from combinatorial optimization.