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

The scrambling index \(k(A)\) of a square matrix \(A\) is the smallest positive integer \(k\) such that \(A^k(A^t)^k\) is a matrix of all ones. The authors show that \(k(A)\leq 1+ \lceil \frac{1+(b-1)^2}2\rceil\), where \(b\) denotes the Boolean rank of \(A\). Here, the Boolean rank of an \(m\times n\) Boolean matrix \(M\) is the smallest \(b\) such that \(M=AB\) for some \(m\times b\) Boolean matrix \(A\) and \(b\times n\) Boolean matrix \(B\).