Skip to main content
SpringerLink
Log in

A proof of Devadze’s theorem on generators of the semigroup of Boolean matrices

  • RESEARCH ARTICLE
  • Published:
Semigroup Forum Aims and scope Submit manuscript

Abstract

In 1968 Devadze described, without a proof, minimal sets of generators of the semigroup of n×n Boolean matrices. We provide a proof of Devadze’s theorem.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Chaudhuri, R., Mukherjea, A.: Idempotent Boolean matrices. Semigroup Forum 21, 273–282 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  2. Clifford, A.H.: A proof of the Montague-Plemmons-Schein theorem on maximal subgroups of the semigroup of binary relations. Semigroup Forum 1, 272–275 (1970)

    Article  MathSciNet  MATH  Google Scholar 

  3. de Caen, D., Gregory, D.A.: Prime Boolean matrices. Lect. Notes Math. 829, 169–173 (1980)

    Google Scholar 

  4. de Caen, D., Gregory, D.A.: Primes in the semigroup of Boolean matrices. Linear Algebra Appl. 37, 119–134 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  5. Devadze, H.M.: Generating sets of the semigroup of all binary relations on a finite set. Dokl. Akad. Nauk SSSR 12, 765–768 (1968) (Russian)

    MathSciNet  MATH  Google Scholar 

  6. Diasamidze, Ya.I.: The structure of idempotent binary relations. In: Studies of Semigroups, pp. 25–28. Leningrad. Gos. Ped. Inst., Leningrad (1990) (Russian)

    Google Scholar 

  7. Diasamidze, Ya.I.: Complete semigroups of binary relations. Semigroups of binary relations. J. Math. Sci. (N.Y.) 117, 4271–4319 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  8. Howie, J.M.: Fundamentals of Semigroup Theory. Oxford University Press, New York (1995)

    MATH  Google Scholar 

  9. Kim, K.H.: Boolean Matrix Theory and Applications. Marcel Dekker, New York (1982)

    MATH  Google Scholar 

  10. Kim, K.H., Roush, F.W.: On generating regular elements in the semigroup of binary relations. Semigroup Forum 14, 29–32 (1977)

    Article  MATH  Google Scholar 

  11. Kim, K.H., Roush, F.W.: Inverses of Boolean matrices. Linear Algebra Appl. 22, 247–262 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  12. Konieczny, J.: Reduced idempotents in the semigroup of Boolean matrices. J. Symb. Comput. 20, 471–482 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  13. Montague, J.S., Plemmons, R.J.: Maximal subgroups of the semigroup of relations. J. Algebra 13, 575–587 (1969)

    Article  MathSciNet  MATH  Google Scholar 

  14. Plemmons, R.J., Schein, B.M.: Groups of binary relations. Semigroup Forum 1, 267–271 (1970)

    Article  MathSciNet  MATH  Google Scholar 

  15. Plemmons, R.J., West, M.T.: On the semigroup of binary relations. Pac. J. Math. 35, 743–753 (1970)

    MathSciNet  Google Scholar 

  16. Preston, G.B.: Any group is a maximal subgroup of the semigroup of binary relations on some set. Glasg. Math. J. 14, 21–24 (1973)

    Article  MathSciNet  MATH  Google Scholar 

  17. Schein, B.M.: Regular elements of the semigroup of all binary relations. Semigroup Forum 13, 95–102 (1976)

    Article  MathSciNet  Google Scholar 

  18. Zaretskii, K.A.: Regular elements in the semigroup of binary relations. Usp. Mat. Nauk 17, 177–179 (1962) (Russian)

    Google Scholar 

  19. Zaretskii, K.A.: The semigroup of binary relations. Mat. Sb. 61, 291–305 (1963) (Russian)

    MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, University of Mary Washington, Fredericksburg, VA, 22401, USA

    Janusz Konieczny

Authors
  1. Janusz Konieczny
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Janusz Konieczny.

Additional information

Communicated by Mohan S. Putcha.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Konieczny, J. A proof of Devadze’s theorem on generators of the semigroup of Boolean matrices. Semigroup Forum 83, 281–288 (2011). https://doi.org/10.1007/s00233-011-9305-y

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00233-011-9305-y

Keywords

Search

Navigation