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

1, 2, 11, 175, 15689

Offset

0,2

Comments

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]].

Links

Table of n, a(n) for n=0..4.

K. H. Kim and F. W. Roush, Two-generator semigroups of binary relations, J. Mathematical Psychology 17 (1978), 236-246.

Example

For n = 2 the maximum order is 11, generated (for example) by the two matrices [[0,0],[0,1]] and [[1,1],[1,0]].
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]].
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]].

Crossrefs

Sequence in context: A039747 A049531 A031508 * A011806 A012953 A012974

Adjacent sequences: A202137 A202138 A202139 * A202141 A202142 A202143

Keyword

nonn,hard,more

Author

Jeffrey Shallit, Dec 12 2011

Status

approved