Decomposing Relations


Authors


Title


Status, Abstract


Gunther Schmidt


Decomposing Relations

Data Analysis Techniques for Boolean Matrices

.pdf .bib


Technical Report

Available also in revised form

.pdf .lhs
Department of Computing Science
University of the Federal Armed Forces Munich
schmidt@informatik.unibw-muenchen.de
December 2002
Known and new methods of decomposing a boolean matrix are presented together with methods of making the decomposition visible. Homogeneous and heterogeneous relations are handled with non-iterative as well as iterative methods.

Such aspects as reducibility, cyclicity, primitivity, difunctionality, Ferrer's relations, Moore-Penrose inverses, independence and line-covering, chainability, game decompositions, matchings, Hall conditions, term rank, chainability, full indecomposability, and others are handled under one common roof.

We have also tried to collect several concepts for nonnegative real-valued matrices and to treat them as concepts for boolean matrices. An additional impetus for this study was to give all this a relation algebraic basis avoiding counting arguments. Several proofs of facts already known are, therefore, quite different from the classical ones.