Geodesic
On Boolean matrices with full factor rank
Sbornik. Mathematics, Tome 204 (2013) no. 11, pp. 1691-1699 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

It is demonstrated that every $(0,1)$-matrix of size $n\times m$ having Boolean rank $n$ contains a column with at least $\sqrt{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.
Keywords: Boolean rank, isolation number.
Mots-clés : $(0,1)$-matrices 
@article{SM_2013_204_11_a7,
     author = {Ya. N. Shitov},
     title = {On {Boolean} matrices with full factor rank},
     journal = {Sbornik. Mathematics},
     pages = {1691--1699},
     year = {2013},
     volume = {204},
     number = {11},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_2013_204_11_a7/}
}
TY  - JOUR
AU  - Ya. N. Shitov
TI  - On Boolean matrices with full factor rank
JO  - Sbornik. Mathematics
PY  - 2013
SP  - 1691
EP  - 1699
VL  - 204
IS  - 11
UR  - http://geodesic.mathdoc.fr/item/SM_2013_204_11_a7/
LA  - en
ID  - SM_2013_204_11_a7
ER  - 
%0 Journal Article
%A Ya. N. Shitov
%T On Boolean matrices with full factor rank
%J Sbornik. Mathematics
%D 2013
%P 1691-1699
%V 204
%N 11
%U http://geodesic.mathdoc.fr/item/SM_2013_204_11_a7/
%G en
%F SM_2013_204_11_a7
Ya. N. Shitov. On Boolean matrices with full factor rank. Sbornik. Mathematics, Tome 204 (2013) no. 11, pp. 1691-1699. http://geodesic.mathdoc.fr/item/SM_2013_204_11_a7/

[1] L. B. Beasley, N. J. Pullman, “Semiring fank versus column rank”, Linear Algebra Appl., 101 (1988), 33–48 | DOI | MR | Zbl

[2] M. Akian, S. Gaubert, A. Guterman, “Linear independence over tropical semirings and beyond”, Tropical and idempotent mathematics, Contemp. Math., 495, Amer. Math. Soc., Providence, RI, 2009, 1–38 | DOI | MR | Zbl

[3] J. E. Cohen, U. G. Rothblum, “Nonnegative ranks, decompositions, and factorizations of nonnegative matrices”, Linear Algebra Appl., 190 (1993), 149–168 | DOI | MR | Zbl

[4] M. Develin, F. Santos, B. Sturmfels, “On the rank of a tropical matrix”, Combinatorial and computational geometry, Math. Sci. Res. Inst. Publ., 52, Cambridge Univ. Press, Cambridge, 2005, 213–242 | MR | Zbl

[5] P. C. Fishburn, P. L. Hammer, “Bipartite dimensions and bipartite degrees of graphs”, Discrete Math., 160:1–3 (1996), 127–148 | DOI | MR | Zbl

[6] L. B. Beasley, “Isolation number versus Boolean rank”, Linear Algebra Appl., 436:9 (2012), 3469–3474 | DOI | MR | Zbl

[7] D. A. Gregory, N. J. Pullman, K. F. Jones, J. R. Lundgren, “Biclique coverings of regular bigraphs and minimum semiring ranks of regular matrices”, J. Combin. Theory Ser. B, 51:1 (1991), 73–89 | DOI | MR | Zbl

[8] G. Shu, D. Lee, M. Yannakakis, “A note on broadcast encryption key management with applications to large scale emergency alert systems”, Proceedings of the 20th International Parallel and Distributed Processing Symposium, IEEE Computer Society, Washington, 2006

[9] A. Ene, W. G. Horne, N. Milosavljevic, P. Rao, R. Schreiber, R. E. Tarjan, “Fast exact and heuristic methods for role minimization problems”, Proceedings of the 13th ACM Symposium on Access Control Models and Technologies, ACM, New York, 2008

[10] D. de Caen, D. A. Gregory, “Primes in the semigroup of Boolean matrices”, Linear Algebra Appl., 37 (1981), 119–134 | DOI | MR | Zbl

[11] R. A. Brualdi, R. Manber, J. A. Ross, “On the minimum rank of regular classes of matrices of zeros and ones”, J. Combin. Theory Ser. A, 41:1 (1986), 32–49 | DOI | MR | Zbl

[12] K. A. S. Hefner, J. R. Lundgren, “Minimum matrix rank of $k$-regular $(0,1)$ matrices”, Linear Algebra Appl., 133 (1990), 43–52 | DOI | MR | Zbl

[13] S. Bezrukov, D. Froncek, S. J. Rosenberg, P. Kovar, “On biclique coverings”, Discrete Math., 308:2–3 (2008), 319–323 | DOI | MR | Zbl

[14] D. de Caen, D. A. Gregory, N. J. Pullman, “The Boolean rank of zero-one matrices”, Proceedings of the Third Caribbean Conference on Combinatorics and Computing (Bridgetown, 1981), Univ. West Indies, Cave Hill Campus, Barbado, 1981, 169–173 | MR | Zbl

[15] M. Aigner, G. M. Ziegler, Proofs from the book, Springer-Verlag, Berlin, 1999 | MR | Zbl

[16] V. B. Poplavskii, “On ranks, Green classes, and the theory of determinants of Boolean matrices”, Discrete Math. Appl., 18:6 (2008), 641–658 | DOI | DOI | MR | Zbl