8
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 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$
    – Thatchaphol
    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

0

Reset to default

Your Answer

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