A202140 -id:A202140 - cp's OEIS frontend

A217990 Size of largest semigroup generated by one Boolean n X n matrix.

1, 2, 5, 10, 17, 26, 37, 50, 65, 82, 101, 122, 145, 170, 197, 226, 257, 290, 420

Offset: 1

Jeffrey Shallit, Oct 17 2012

			a(4) = 10: the matrix [[0,0,0,1], [0,0,1,0], [1,0,0,0], [0,1,1,0]] generates a semigroup of order 10 under Boolean matrix multiplication.

J. Denes, K. H. Kim, and F. W. Roush, Automata on one symbol, in Studies in Pure Mathematics: To the Memory of Paul Turan, Birkhäuser, 1983, pp. 127-134.

George Markowsky, Bounds on the index and period of a binary relation on a finite set, Semigroup Forum 13 (1977), 253-259.

Cf. A000793, A202140.

For n < 19, a(n) = n^2 - 2n + 2. For large n, l(n) <= a(n) < n^2 - 2n + 2 + l(n), where l(n) is Landau's function (A000793). It seems the exact value is still unknown.

A358784 Size of largest semigroup generated by three n X n boolean matrices.

Original entry on oeis.org

2, 16, 440

Offset: 1

Jeffrey Shallit, Nov 30 2022

Here the semigroup is under boolean matrix multiplication (not the same as GF(2) matrix multiplication). It is known that a(4) >= 24846, generated by the three matrices [[0,0,0,1],[1,0,0,0],[0,1,0,0],[0,0,1,0]] and [[0,0,0,1],[0,0,1,0],[0,1,0,0],[1,0,0,1]] and [[0,0,0,0],[0,0,0,1],[0,0,1,0],[0,1,0,0]].

			For n = 1 the maximum size is 2, generated by the three matrices [0] and [1] and [1].
For n = 2 the maximum size is 16, generated by the three matrices [[0,1],[1,1]] and [[0,1],[1,0]] and [[0,0],[0,1]].
For n = 3 the maximum size is 440, generated by the three matrices [[0,0,1],[1,0,0],[0,1,0]] and [[0,0,1],[0,1,0],[1,0,1]] and [[0,0,0],[0,0,1],[0,1,0]].

Cf. A217990 (for one matrix); A202140 (for two matrices).

cp's OEIS Frontend

A217990 Size of largest semigroup generated by one Boolean n X n matrix.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Formula