DOE OSTI · 22365881
On Boolean matrices with full factor rank
Abstract
It is demonstrated that every (0,1)-matrix of size n×m having Boolean rank n contains a column with at least √n/2−1 zero entries. This bound is shown to be asymptotically optimal. As a corollary, it is established that the size of a full-rank Boolean matrix is bounded from above by a function of its tropical and determinantal ranks. Bibliography: 16 titles.
Explore related subjects
Keep this discovery
Explore connections, maps & timelines
Shitov, Ya. 2013-11-30. On Boolean matrices with full factor rank. https://doi.org/10.1070/sm2013v204n11abeh004355
Cite the original work for its findings. Save a collection to share your selection of sources.