cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

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

This page as a plain text file.
%I A202140 #28 Nov 30 2022 12:39:50
%S A202140 1,2,11,175,15689
%N A202140 Size of the largest semigroup generated by two n X n Boolean matrices.
%C A202140 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 A202140 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 A202140 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 A202140 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 A202140 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 A202140 nonn,hard,more
%O A202140 0,2
%A A202140 _Jeffrey Shallit_, Dec 12 2011