Isolation number versus Boolean rank

DOI10.1016/J.LAA.2011.12.013MaRDI QIDQ417483zbMATH OpenOpenAlexFDO

Authors Leroy B. Beasley

Publication date 14 May 2012

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.laa.2011.12.013

zbMATH Keywords

Boolean algebraBoolean matricesBoolean rankfactorisation rankisolated oneisolation number

Mathematics Subject Classification ID

Vector spaces, linear dependence, rank, lineability (15A03) Factorization of matrices (15A23) Boolean and Hadamard matrices (15B34)

Review text

Let \(\mathbb B=\{0,1\}\) be the binary Boolean algebra, and let \(A\) be an \(m\times n\) matrix over \(\mathbb B\). The author exhibits the relationship between the following two numbers: The \textit{Boolean rank}, or factorisation rank, of \(A\) is the smallest \(k\) such that \(A\) can be factored as an \(m\times k\) times a \(k\times n\) matrix. The \textit{isolation number} of \(A\) is the largest number of entries equal to \(1\) in the matrix such that: (i) no two ones are in the same row, (ii) no two ones are in the same column, and (iii) no two ones are in a \(2\times 2\) submatrix of all ones.NEWLINENEWLINEIt is known that the isolation number of \(A\) is always at most the Boolean rank. The main results of this paper are as follows: For \(k\in\{1,2\}\) the isolation number of \(A\) equals \(k\) if, and only if, the Boolean rank is \(k\). Also, for \(1\leq m\leq n\) necessary and sufficient conditions for the Boolean rank and the isolation number to be both equal to \(m\) are given.

Recommendations

• Isolation number versus Boolean rank in tournaments
• Possible isolation number of a matrix over nonnegative integers.
• Linear operators that preserve graphical properties of matrices: Isolation numbers
• A characterization of linear operators that preserve isolation numbers
• Separability of distinct Boolean rank-1 matrices

Cites work

• Biclique coverings of regular bigraphs and minimum semiring ranks of regular matrices
• scientific article; zbMATH DE number 3781471 (Why is no real title available?)

Cited in

(14)

• The augmentation property of binary matrices for the binary and Boolean rank
• Separability of distinct Boolean rank-1 matrices
• The complexity of tropical matrix factorization
• Isolation number versus Boolean rank in tournaments
• Possible isolation number of a matrix over nonnegative integers.
• Tropical lower bound for extended formulations. II: Deficiency graphs of matrices
• On maximal isolation sets in the uniform intersection matrix
• Isolation numbers of integer matrices and their preservers
• Circulant almost cross intersecting families
• On Boolean matrices with full factor rank
• Linear operators that preserve graphical properties of matrices: Isolation numbers
• On minimally non-firm binary matrices
• A study of the binary and Boolean rank of matrices with small constant real rank
• A study of the binary and Boolean rank of matrices with small constant real rank

This page was built for publication: Isolation number versus Boolean rank

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