On the Boolean Matrix Equation M ′ =ν i=1 M i
- 1 July 1965
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 12 (3) , 376-382
- https://doi.org/10.1145/321281.321288
Abstract
The equation M′ = V d i -1 M i where M′ is supposed to be given is discussed. First it is proved that there is a necessary and sufficient condition for the existence of a solution and, simultaneously, that under such condition, M′ will itself be a solution. However, the main aim is precisely to present an algorithm which gives the so-called minimal solutions: Boolean matrices M satisfying the equation with the least possible number of unity entries. This is proved by the last theorem. The subject may be studied in the context of graph theory and it seems of interest in various fields of operational research.Keywords
This publication has 1 reference indexed in Scilit:
- A Theorem on Boolean MatricesJournal of the ACM, 1962