On extremal matrices of second largest exponent by Boolean rank (Q869927)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On extremal matrices of second largest exponent by Boolean rank |
scientific article |
Statements
On extremal matrices of second largest exponent by Boolean rank (English)
0 references
9 March 2007
0 references
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.
0 references
exponent
0 references
Boolean matrix
0 references
rank factorization
0 references