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
    0 references
    0 references
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references