login
Size of the largest semigroup generated by two n X n Boolean matrices.
2

%I #28 Nov 30 2022 12:39:50

%S 1,2,11,175,15689

%N Size of the largest semigroup generated by two n X n Boolean matrices.

%C Of course, the matrices are multiplied using "Boolean matrix multiplication", which is not the same as multiplication over GF(2). It is known that a(5) >= 6732481, as evidenced by the matrices [[0,0,0,0,1],[1,0,0,0,0],[0,1,0,0,0],[0,0,1,0,0],[0,0,0,1,0]] and [[0,0,1,0,0],[1,1,0,0,0],[0,1,0,0,0],[0,0,0,1,0],[0,0,0,0,1]].

%H K. H. Kim and F. W. Roush, <a href="https://doi.org/10.1016/0022-2496(78)90018-4">Two-generator semigroups of binary relations</a>, J. Mathematical Psychology 17 (1978), 236-246.

%e For n = 2 the maximum order is 11, generated (for example) by the two matrices [[0,0],[0,1]] and [[1,1],[1,0]].

%e For n = 3 the maximum 175 is achieved by (for example) by the two matrices [[0,0,1],[1,0,0],[0,1,0]] and [[0,0,1],[0,1,0],[1,0,1]].

%e For n = 4 the maximum 15689 is achieved by (for example) by the two matrices [[0,0,0,1],[0,1,0,0],[0,1,1,0],[1,0,0,0]] and [[0,0,0,1],[0,0,1,0],[1,0,0,0],[0,1,0,0]].

%K nonn,hard,more

%O 0,2

%A _Jeffrey Shallit_, Dec 12 2011