<p>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$).</p>

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

<p>An equivalent question in terms of bipartite graphs is as follows:</p>

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

CC BY-SA 3.0
2016-02-15T20:21:17.463Z
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$.
Thatchaphol
CC BY-SA 3.0
2016-02-16T09:23:25.543Z
@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).
tranisstor
CC BY-SA 3.0
2016-02-16T10:40:13.317Z
@tranisstor is there a relation between this rank and $\Bbb R$ rank and $\Bbb F_2$ rank?
Turbo
CC BY-SA 3.0
2016-02-16T14:20:11.477Z
@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.
tranisstor
CC BY-SA 3.0
2016-02-16T15:13:15.537Z
@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.
tranisstor
<reference-request><graph-theory><co.combinatorics><upper-bounds><boolean-matrix>
Upper Bound on Number of $n \times n$ Boolean matrices of Boolean rank at most $k$
tranisstor
# Upper Bound on Number of $n \times n$ Boolean matrices of Boolean rank at most $k$

(Asked by: username_0 on 2016-02-15)

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?

**Tags:** reference-request, graph-theory, co.combinatorics, upper-bounds, boolean-matrix
> **Comments:**
> **username_1**: 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$.  
> **username_0**: @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).  
> **username_2**: @tranisstor is there a relation between this rank and $\Bbb R$ rank and $\Bbb F_2$ rank?  
> **username_0**: @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.  
> **username_0**: @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.  

---

## 0 answers

