Status, Abstract

Gunther Schmidt

Decomposing Relations - Data Analysis Techniques for Boolean Matrices

.pdf .bib

Technical Report - Available also in revised form

Department of Computing Science
University of the Federal Armed Forces Munich
85577 Neubiberg, Germany

October 2004
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, Ferrers'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.