### On the Boolean Matrix Equation $M^{′}=∨i=1M^{i}$On the Boolean Matrix Equation $M^{′}=∨i=1M^{i}$

Access Restriction
Subscribed

 Author Simes Pereira, J. M. S. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1965 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract The equation $\textit{M′}$ = $V\textit{d}\textit{i}-1$ $\textit{Mi}$ where $\textit{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 $\textit{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. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1965-07-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 12 Issue Number 3 Page Count 7 Starting Page 376 Ending Page 382

#### Open content in new tab

Source: ACM Digital Library