Boolean matrices have a natural interpretation in terms of directed graphs: given a graph *G* on *n* vertices, we put a 1 in row *i* and column *j* of *M* if there is a directed edge in *G* from vertex *i* to vertex *j*, and 0 otherwise. Then the boolean matrix power *M*^{e} has a 1 in row *i* and column *j* if and only if there is a directed path from vertex *i* to vertex *j* of length *e*.

Given an *n* × *n* boolean matrix *M*, a natural question is, what is the largest size *s*(*n*) of the semigroup generated by *M* under boolean matrix multiplication? In other words, how many distinct powers can *M* have, in the worst case? Believe it or not, this natural quantity has received very little attention in the literature. There is a paper by Markowsky in 1977, and another by Denes, Roush, and Kim in 1983, but that's about it. For small *n*, it is known that *s*(*n*) = *n*^{2} - 2*n* + 2, while for larger *n*, it is known that *s*(*n*) is approximately *g*(*n*), Landau's function, which counts the maximal order of an element in the symmetric group of order *n*. It is known that Landau's function is approximately e^{sqrt(n log n)}, so this tells us how *s*(*n*) behaves for large *n*. But to my knowledge nobody knows the exact value, or even small values past *n* = 20. This might be a nice computational challenge for an undergraduate.

## 4 comments:

Just FYI: http://oeis.org/A000793

It goes a tiny bit beyond n=20 there...

Nevermind my last comment, I misread it - sorry ;-)

Maybe you could post the problem on mathoverflow, see if anybody over there has some ideas.

It's A217990 in the OEIS -- Jeffrey Shallit submitted it the same day he wrote this post. According to that sequence it's actually n^2 - 2n + 2 for n < 19 (rather than n^2 - n + 2). Still no progress on a(20) or higher terms.

Charles R Greathouse IV

Post a Comment