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
MathSciNet review: 0444823
Full-text PDF Free Access

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?)

  • [1] Ki Hang Kim, The semigroup of Hall relations, Semigroup Forum 9 (1974), 253-260. MR 0376910 (51:13085)
  • [2] M. Petrich, Translational hull and semigroups of binary relations, Glasgow Math. J. 9 (1968), 12-21. MR 37 #5314. MR 0229740 (37:5314)
  • [3] Štefan Schwarz, The semigroup of fully indecomposable relations and Hall relations, Czechoslovak Math. J. 23 (1973), 151-163. MR 0316612 (47:5159)

Similar Articles

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

Retrieve articles in all journals with MSC: 20M30

Additional Information

Keywords: Cross-vector, faithful representation, linear representation, module, Hall matrix, reflexive matrix
Article copyright: © Copyright 1977 American Mathematical Society

American Mathematical Society