An $n \times n$ Boolean matrix $B$ has Boolean rank $k$ if there exist matrices $L \in \{0,1\}^{n \times k}$ and $R \in \{0,1\}^{k \times n}$, s.t. $B = L \circ R$. Here $\circ$ denotes the Boolean matrix product (i.e. $1+1 = 1$).

What is the best upper bound we know for $|\{B \in \{0,1\}^{n \times n} : B \text{ has Boolean rank } \leq k\}|$?

An equivalent question in terms of bipartite graphs is as follows:

How many bipartite graphs $G = (V \cup U, E)$ with $|U| = |V| = n$ which can be covered with at most $k$ bicliques exist?

  • 2
    $\begingroup$ A trivial upper bound is $2^{2nk}$ because $B$ is determined by $L$ and $R$. A trivial lower bound is around $\binom{n}{k}2^{nk}=2^{(n+\Theta(\log n))k}$ because any matrix with $k$ non-zero column vectors has rank at most $k$. $\endgroup$ Feb 15, 2016 at 20:21
  • $\begingroup$ @Turbo: No, it's Boolean rank, i.e. + is given by the bitwise OR and we get 1+1=1. In $\mathbb{F}_2$ you have 1+1=0 (which makes $\mathbb{F}_2$ a field). $\endgroup$
    – tranisstor
    Feb 16, 2016 at 9:23
  • $\begingroup$ @tranisstor is there a relation between this rank and $\Bbb R$ rank and $\Bbb F_2$ rank? $\endgroup$
    – Turbo
    Feb 16, 2016 at 10:40
  • $\begingroup$ @Turbo: Yes and no. Yes: They all define a rank on binary matrices. No: Boolean Rank is NP-hard even to approximate, the other two can be computed in poly time using e.g. Gaussian Elimination (as they are fields; the Boolean algebra does not give field as you lack an inverse for +). Otherwise, Boolean Rank and Standard Rank cannot be compared (i.e., none is upper bound to the other); see Monson, Pullman, Rees: "A survey of clique and biclique coverings and factorizations of (0; 1)-matrices". For Boolean rank and $\mathbb{F}_2$ I'm not sure, but I'd be surprised if there was a clear relation. $\endgroup$
    – tranisstor
    Feb 16, 2016 at 14:20
  • $\begingroup$ @Turbo We also cannot compare $\mathbb{F}_2$ and Boolean rank: Consider the matrix [1,0,1; 1,1,1; 0,1,1]. It has Boolean rank 2, but $\mathbb{F}_2$ rank 3. On the other hand, the matrix [1,1,0; 0,1,1; 1,0,1] has Boolean rank 3, but $\mathbb{F}_2$ rank 2. $\endgroup$
    – tranisstor
    Feb 16, 2016 at 15:13


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.