Structural dependence and systems of equations

Structural dependence in the incidence matrix associated with a system of equations may be used to detect misspecification of the underlying system. The incidence matrix can be represented as a bipartite graph G=(X,Y,E), with the node sets partitioned into the sets X1, X2, Y1 en Y2, such that (a) there are no edges between X1 en Y2, and (b) the cardinality of X1+Y2 is maximum. Such a partition corresponds with the detection of complete and maximal complementary subsets of structually dependent rows and columns. This problem is equivalent to finding a maximum independent vertex set or a minimum edge cover in thebipartite graph under the assumption of no isolated vertices. The problem of finding minimal and complete subsets of structurally dependent rows or columns is shown to be NP-complete. A heuristic approach for the detection of these minimal subsets based on Hall's transversal algorithm has worked satisfactorily in practice.