A bound on the scrambling index of a primitive matrix using Boolean rank

AbstractThe scrambling index of an n×n primitive matrix A is the smallest positive integer k such that Ak(At)k=J, where At denotes the transpose of A and J denotes the n×n all ones matrix. For an m×n Boolean matrix M, its Boolean rank b(M) is the smallest positive integer b such that M=AB for some m×b Boolean matrix A and b×n Boolean matrix B. In this paper, we give an upper bound on the scrambling index of an n×n primitive matrix M in terms of its Boolean rank b(M). Furthermore we characterize all primitive matrices that achieve the upper bound