Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

Linear representations of semigroups of Boolean matrices


Authors: Ki Hang Kim and Fred W. Roush
Journal: Proc. Amer. Math. Soc. 63 (1977), 203-207
MSC: Primary 20M30
DOI: https://doi.org/10.1090/S0002-9939-1977-0444823-9
MathSciNet review: 0444823
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ {B_n}$ be the multiplicative semigroup of $ n \times n$ matrices over the semiring 0, 1 under the operations ``or'' and ``and". We show that the least possible degree of a faithful representation of $ {B_n}$ over a field is $ {2^n} - 1$ by studying representations of a subsemigroup of $ {B_n}$. By different methods we answer the same question for the subsemigroups of Boolean matrices greater than or equal to some permutation matrix (Hall matrices) and greater than or equal to the identity (reflexive Boolean matrices). We prove every representation of the latter semigroup can be triangularized.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 20M30

Retrieve articles in all journals with MSC: 20M30


Additional Information

DOI: https://doi.org/10.1090/S0002-9939-1977-0444823-9
Keywords: Cross-vector, faithful representation, linear representation, module, Hall matrix, reflexive matrix
Article copyright: © Copyright 1977 American Mathematical Society

American Mathematical Society