Hall exponents of Boolean matrices

From MaRDI portal





Let \(B_ n\) denote the multiplicative semigroup of matrices of order \(n\) over the Boolean algebra \(\{0,1\}\). There is a one to one correspondence between the set \(B_ n\) and the set \(\Gamma_ n\) of digraphs with vertices \(1,\ldots,n\) given as follows: \(A=[a_{ij}]\in B_ n\) corresponds to \(\Gamma(A)\in \Gamma_ n\) where there is an arc from vertex \(i\) to vertex \(j\) in \(\Gamma(A)\) if and only if \(a_{ij}=1\). A matrix \(A\in B_ n\) is primitive provided for some positive integer \(k\), \(A^ k=J_ n\), the all 1's matrix in \(B_ n\). The exponent \(e(A)\) of \(A\) is the smallest integer \(k\) for which \(A^ k=J_ n\). A matrix \(A\in B_ n\) is called a Hall matrix if there exists a permutation matrix \(Q\leq A\). Let \(H_ n\) be the set of all Hall matrices in \(B_ n\), \(H_ n=\{A\in B_ n:A^ k\in H_ n\) for some \(k\)\}, and \(H^*_ n=\{A\in B_ n:A^ k\in H_ n\) for all \(k\) sufficiently large\}. The authors characterize the sets \(H_ n\) and \(H^*_ n\). Moreover, the bounds for the Hall exponent are given.











This page was built for publication: Hall exponents of Boolean matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3982734)