Computing Indexes and Periods of All Boolean Matrices Up to Dimension n=8

Authors

  • Pavol Zajac Institute of Computer Science and Mathematics, Faculty of Electrical Engineering and Informatics, Slovak Technical University in Bratislava
  • Matus Jokay Institute of Computer Science and Mathematics, Faculty of Electrical Engineering and Informatics, Slovak Technical University in Bratislava

Keywords:

Boolean matrix, enumeration, directed graphs

Abstract

A set of n x n Boolean matrices along with the Boolean matrix multiplication operation form a semigroup. For each matrix A it is possible to find index r and period  , such that A, = A ++ and  , , are the smallest positive integers with this property. We are concerned with a question: How many n times n Boolean matrices have the given index, and period? A new algorithm is presented that was used to compute index and period statistics of all square Boolean matrices up to n=8. Computed statistics are presented in the appendix of the paper.

Downloads

Download data is not yet available.

Downloads

Published

2013-01-24

How to Cite

Zajac, P., & Jokay, M. (2013). Computing Indexes and Periods of All Boolean Matrices Up to Dimension n=8. COMPUTING AND INFORMATICS, 31(6), 1329–1344. Retrieved from https://www.cai.sk/ojs/index.php/cai/article/view/1310