Izvestiya of Saratov University.

Mathematics. Mechanics. Informatics

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)

For citation:

Poplavskii V. B. Overtones of Oscillatory Boolean Matrices. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2006, vol. 6, iss. 1, pp. 29-37. DOI: 10.18500/1816-9791-2006-6-1-2-29-37, EDN: YZULJW

This is an open access article distributed under the terms of Creative Commons Attribution 4.0 International License (CC-BY 4.0).
Published online: 
Full text:
(downloads: 209)

Overtones of Oscillatory Boolean Matrices

Poplavskii Vladislav Bronislavovich, Saratov State University

We consider a functioning property of a system with a finite set of elements and with different kinds of Boolean binary relations on it. We also construct the square matrices over arbitrary Boolean algebra which determine some Boolean binary relation and generate a cyclic semigroup with the maximum index and period. The looping of the system with a finite set of elements called an oscillator, is accompanied by appearing of subsequences (overtones) in a sequence of elements on the main diagonal of powers of a relevant Boolean matrix. Examples of such overtones of Boolean matrices of small sizes are shown in the paper. 

Key words: 
  1. Luce R.D. A note on Boolean matrix theory // Proc. Ammer Math. Soc. 1952. V. 3. P.382–388
  2. Give’on Y. Lattice matrices // Inform. And Control. 1964. V. 7, № 4. P. 477–484
  3. Kim Ki Hang. Boolean matrix theory and applications. Pure and Applied Mathematics, 70. N. Y.; Basel: Marcel Dekker, Inc., 1982. xiv+ 425 p.
  4. Rosenblatt D. On the graphs and asymptotic forms of finite Boolean relation matrices and stochastic matrices // Naval Res. Logist. Quart. 1957. V. 4. P. 151–167
  5. Li Q., Shao J. The index set problem for Boolean (or nonnegative) matrices // Discrete Math. 1993. V. 123, №1–3. P. 75–92
  6. Клиффорд А., Престон Г. Алгебраическая теория полугрупп. M.: Мир, 1972. Т. 1. 286 с.
  7. Лаллеман Ж. Полугруппы и комбинаторные приложения. М.: Мир, 1985. 440 с.
  8. Hammer P. L., Rudeanu S. Boolean methods in operations research and related areas. Berlin; N. Y.; Springer, 1968. xix+ 329 p.
  9. Лунц А.Г. Приложение матричной булевской алгебры к анализу и синтезу релейно-контактных схем // Докл. АН СССР. 1950. Т. 70, №3. С. 421–423
  10. Rutherford D.E. Inverses of Boolean matrices // Proc. Glasg. Math. Assoc. 1963. V. 6. P. 49–53
  11. Wedderburn J.H.M. Boolean linear associative algebra // Ann. of Math. 1934. V. 35. P. 185–194
  12. Schwarz S. On the semigroup of binary relations on a finite set // Czech. Math. J. 1970. V. 20(95). P. 632–679
  13. Wielandt H. Unzerlegbare, nichnegativen Matrizen//Math. Z. 1950. V. 52. P. 642–648
  14. Gregory D.A., Kirkland S.J., Pullmang N.J. A bound on the exponent of a primitive matrix using Boolean rank // Linear Algebra Appl. 1995. V. 217. P. 101–116
  15. Поплавский В.Б. Определители степеней булевых матриц // Чебышевcкий сборник: Труды VI Междунар. конф. «Алгебра и теория чисел: современные проблемы и приложения». 2004. Т. 5, вып. 3(11). С. 98–111