The Semigroup Generated by Regular Boolean Matrices
by
Janusz Konieczny
Mary Washington College, Fredericksburg, Virginia, USA

The semigroup B_n of Boolean matrices is the set of n×n matrices over the two-element Boolean algebra {0, 1}, where the operation is matrix multiplication. It is isomorphic to the semigroup B_X of binary relations on a set X with n elements, where the operation is composition of relations. For n > 2, the semigroup B_n is not regular.

Let B^r_n be the subsemigroup of B_n generated by the regular elements. In contrast with B_n, whose rank (the cardinality of the smallest possible generating set) grows very fast with n, the rank of B^r_n is 4 for every n > 2. However, it turns out that these two semigroups have similar structure in terms of Green's relations. We characterize the elements of B^r_n, determine Green's relations in B^r_n, and discuss the height of the poset of D-classes in B^r_n.

Janusz Konieczny's Home Page

Date received: March 11, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caec-04.