On the Boolean Matrix Equation M′=∨i=1Mi

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the Boolean Matrix Equation M^′=∨i=1Mⁱ

Full text

Pdf (531 KB)

Source

Journal of the ACM (JACM) archive
Volume 12 , Issue 3 (July 1965) table of contents

Pages: 376 - 382

Year of Publication: 1965

ISSN:0004-5411

Author

J. M. S. Simões Pereira

Gulbenkian Scientific Computing Cerder, Lisbon, Portugal

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 20, Citation Count: 1

Additional Information:

abstract references cited by index terms

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/321281.321288 What is a DOI?

ABSTRACT

The equation M′ = Vdi-1 Mi 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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Stephen Warshall, A Theorem on Boolean Matrices, Journal of the ACM (JACM), v.9 n.1, p.11-12, Jan. 1962 [doi>10.1145/321105.321107]
	2	BIRKHOFF, G. Lattice Theory. Amer. Math. Soe. Colloq. Publ., Providence, 1948.
	3	ORE, O. Theory of Graphs.