Search NASA⌕ Search

Engineering topics

Shitov, Ya

Publications and source records attributed to Shitov, Ya.

On Boolean matrices with full factor rank

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.

97 MATHEMATICS AND COMPUTING↗