On extremal matrices of second largest exponent by Boolean rank (Q869927)

A Boolean matrix is a matrix over the binary Boolean algebra \((0,1)\). Given an \(m \times n\) Boolean matrix \(A\), its Boolean rank \(b(A)\) is defined to be the smallest integer such that for some \(m \times k\) Boolean matrix \(F\) and \(k \times n\) Boolean matrix \(G\), the equality \(A = FG\) holds. If \(A = 0\), then \(b(A)\) is defined to be \(0\). The product \(A=FG\) is called a Boolean rank factorization of \(A\). A Boolean \(n \times n\) matrix \(A\), considered as a real matrix, is primitive if there exists an integer \(k \geq 1\) such that \(A^k\) has only positive entries. The smallest such \(k\) is called the primitive exponent of \(A\), in symbols \(exp(A)\). The authors first review results by \textit{H. Wielandt} [Math. Z. 52, 642--648 (1950; Zbl 0035.29101)] and by \textit{D. A. Gregory, S. J. Kirkland}, and \textit{N. J. Pullman} [Linear Algebra Appl. 217, 101--116 (1995; Zbl 0822.15005)], and then show that for each \(3 \leq b \leq n-1\) there exist \(n \times n\) primitive Boolean matrices \(A\) with \(b(A) = b\) such that \(exp(A) = (b-1)^2+1\). Moreover, the authors explicitly describe all such matrices.