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

2, 16, 440

Offset

1,1

Comments

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

Links

Table of n, a(n) for n=1..3.

Example

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

Crossrefs

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

Sequence in context: A009397 A229023 A009700 * A012030 A012682 A012678

Adjacent sequences: A358781 A358782 A358783 * A358785 A358786 A358787

Keyword

nonn,hard,more,bref

Author

Jeffrey Shallit, Nov 30 2022

Status

approved