• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

On Boolean matrices with full factor rank

Sbornik Mathematics. 2013. Vol. 204. No. 11. P. 1691-1699.

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.