Wednesday, October 17, 2012

An Interesting but Little-Known Function

A boolean matrix is a matrix whose entries are truth values, usually represented as 1 (true) and 0 (false). We multiply boolean matrices in the same way that we multiply ordinary matrices, except that instead of sum we use the boolean "or" and instead of product we use the boolean "and".

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 Me 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) = n2 - 2n + 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 esqrt(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:

Mike said...

Just FYI: http://oeis.org/A000793
It goes a tiny bit beyond n=20 there...

Mike said...

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

Narad said...

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

Unknown said...

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