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

1, 2, 11, 175, 15689

Offset: 0

Author

Jeffrey Shallit, Dec 12 2011

Keywords

• nonn
• hard
• more

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

Examples

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

Links

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