<p>I had the following recent paper giving an fpt algorithm for binary rank.
Our algorithm checks whether the given matrix has binary rank $k$ in $\mathcal{O}(2^{3k^2})poly(n+m)$ time, and if yes it also ouputs the corresponding decomposition.</p>

<p><a href="http://drops.dagstuhl.de/opus/volltexte/2017/6929/" rel="nofollow noreferrer">On the Parameterized Complexity of Biclique Cover and Partition.</a>
L. Sunil Chandran, Davis Issac, and Andreas Karrenbauer. 
Published in IPEC 2016</p>

CC BY-SA 3.0
2017-10-09T14:11:07.893Z
2017-11-16T15:51:02.997Z
2017-11-16T15:51:02.997Z
Davis Issac
<p>This is equivalent to the biclique partition number of a bipartite graph. You can think of M as representing a bipartite graph $G$ on $[n] \times [m]$ in the natural way: $M_{i,j}$ is 1 if and only if there is an edge $(i,j)$ in G (where $i$ is an element of the left partition, and $j$ an element of the right partition). Then $M$ has binary rank $r$ if and only if the edges of the corresponding bipartite graph $G$ can be partitioned into $r$ complete bipartite subgraphs. To see this, take an optimal factorization $M = UV^\intercal$, denote the columns of $U$ by $u_1, \ldots, u_r$, and the columns of $V$ by $v_1, ..., v_r$. $M=UV^\intercal$ is equivalent to $M = \sum_{i = 1}^r{u_i v_i^\intercal}$, and $u_i v_i^\intercal$ represents a complete bipartite graph on the vertices $S_i \cup T_i$, where $S_i$ is the set of left vertices for which $u_i$ is the indicator vector, and $T_i$ is the set of right vertices for which $v_i$ is the indicator vector.</p>

<p>Computing the biclique partition number is NP-hard, and hard to approximate. See these two papers for some results and references: <a href="http://www.sciencedirect.com/science/article/pii/S0166218X98000390" rel="nofollow">[1]</a>, <a href="http://people.mpi-inf.mpg.de/~karrenba/papers/CHHK2014.pdf" rel="nofollow">[2]</a>.</p>

CC BY-SA 3.0
2016-05-28T08:21:54.453Z
Thanks for the insight. A little correction in your answer possibly, $M=\Sigma_{i=1}^r u_iv_i$. Could you comment something on the SVD of M which respect this factorization.
Ram
CC BY-SA 3.0
2016-05-28T20:12:38.927Z
I still have no clue what you mean by SVD in this setting? You cannot hope the $u_i$ and $v_i$ vectors to be orthogonal.
Sasho Nikolov
CC BY-SA 3.0
2016-05-27T20:38:40.447Z
2016-05-29T13:22:12.067Z
2016-05-29T13:22:12.067Z
Sasho Nikolov
<p>Let $M$ be a binary ($0-1$) matrix of size $n \times m$. We define binary rank of $M$ as the smallest positive integer $r$ for which there exists a product decomposition $M = UV$, where $U$ is $n \times r$ and $V$ is $r \times m$, and all entries of $U$ and $V$ come from $\{0, 1\}$. </p>

<p>My question is that is there known algorithmic way to determine the binary rank of $M$; and Singular value decomposition that support the binary rank. Any reference in this regard would highly help.</p>

CC BY-SA 3.0
2016-05-26T18:43:28.113Z
what is SVD in this context? do you mean computing a factorization $M = UV$ with optimal inner dimension?
Sasho Nikolov
CC BY-SA 3.0
2016-05-26T18:47:23.023Z
I am not sure if  SVD could be defined in this context. I was wondering if it could be defined in this case in a similar analogy of the usual SVD of matrix.
Ram
CC BY-SA 3.0
2016-05-26T22:03:47.150Z
This sounds a lot like the partition number in communication complexity (or perhaps the one-sided partition number). Is that what you want? See [this question](http://cstheory.stackexchange.com/questions/21608/deterministic-communication-complexity-vs-partition-number) for a definition of partition number.
Robin Kothari
CC BY-SA 3.0
2016-05-27T03:55:55.267Z
@RobinKothari Yes, it appears to be like partition number. However, I am not well aware of communication complexity literature in this context. I wanted to understand the significance of $U, V$ in the factorization; SVD of the matrix (if it is well defined) ; and possible algorithmic way to compute them.
Ram
CC BY-SA 3.0
2016-05-27T12:13:27.427Z
@Ram: I believe the partition number is NP-hard to compute. I can look for a reference if that's helpful. This [recent paper](http://cjtcs.cs.uchicago.edu/articles/2016/2/contents.html) on binary rank may be of interest to you.
Robin Kothari
<cc.complexity-theory><communication-complexity><combinatorics>
Binary rank of binary matrix
Ram
# Binary rank of binary matrix

(Asked by: username_0 on 2016-05-26)

Let $M$ be a binary ($0-1$) matrix of size $n \times m$. We define binary rank of $M$ as the smallest positive integer $r$ for which there exists a product decomposition $M = UV$, where $U$ is $n \times r$ and $V$ is $r \times m$, and all entries of $U$ and $V$ come from $\{0, 1\}$.

My question is that is there known algorithmic way to determine the binary rank of $M$; and Singular value decomposition that support the binary rank. Any reference in this regard would highly help.

**Tags:** cc.complexity-theory, communication-complexity, combinatorics

> **Comments:**
> **username_1**: what is SVD in this context? do you mean computing a factorization $M = UV$ with optimal inner dimension?  
> **username_0**: I am not sure if  SVD could be defined in this context. I was wondering if it could be defined in this case in a similar analogy of the usual SVD of matrix.  
> **username_2**: This sounds a lot like the partition number in communication complexity (or perhaps the one-sided partition number). Is that what you want? See [this question](http://cstheory.stackexchange.com/questions/21608/deterministic-communication-complexity-vs-partition-number) for a definition of partition number.  
> **username_0**: @RobinKothari Yes, it appears to be like partition number. However, I am not well aware of communication complexity literature in this context. I wanted to understand the significance of $U, V$ in the factorization; SVD of the matrix (if it is well defined) ; and possible algorithmic way to compute them.  
> **username_2**: @username_0: I believe the partition number is NP-hard to compute. I can look for a reference if that's helpful. This [recent paper](http://cjtcs.cs.uchicago.edu/articles/2016/2/contents.html) on binary rank may be of interest to you.  

---

## 2 answers

### Answer by username_3 on 2017-10-09. Score: 4 | Accepted answer

I had the following recent paper giving an fpt algorithm for binary rank.
Our algorithm checks whether the given matrix has binary rank $k$ in $\mathcal{O}(2^{3k^2})poly(n+m)$ time, and if yes it also ouputs the corresponding decomposition.

[On the Parameterized Complexity of Biclique Cover and Partition.](http://drops.dagstuhl.de/opus/volltexte/2017/6929/)
L. Sunil Chandran, username_3, and Andreas Karrenbauer.
Published in IPEC 2016


---

### Answer by username_1 on 2016-05-27. Score: 8

This is equivalent to the biclique partition number of a bipartite graph. You can think of M as representing a bipartite graph $G$ on $[n] \times [m]$ in the natural way: $M\_{i,j}$ is 1 if and only if there is an edge $(i,j)$ in G (where $i$ is an element of the left partition, and $j$ an element of the right partition). Then $M$ has binary rank $r$ if and only if the edges of the corresponding bipartite graph $G$ can be partitioned into $r$ complete bipartite subgraphs. To see this, take an optimal factorization $M = UV^\intercal$, denote the columns of $U$ by $u\_1, \ldots, u\_r$, and the columns of $V$ by $v\_1, ..., v\_r$. $M=UV^\intercal$ is equivalent to $M = \sum\_{i = 1}^r{u\_i v\_i^\intercal}$, and $u\_i v\_i^\intercal$ represents a complete bipartite graph on the vertices $S\_i \cup T\_i$, where $S\_i$ is the set of left vertices for which $u\_i$ is the indicator vector, and $T\_i$ is the set of right vertices for which $v\_i$ is the indicator vector.

Computing the biclique partition number is NP-hard, and hard to approximate. See these two papers for some results and references: [[1]](http://www.sciencedirect.com/science/article/pii/S0166218X98000390), [[2]](http://people.mpi-inf.mpg.de/~karrenba/papers/CHHK2014.pdf).

> **Comments:**
> **username_0**: Thanks for the insight. A little correction in your answer possibly, $M=\Sigma_{i=1}^r u_iv_i$. Could you comment something on the SVD of M which respect this factorization.  
> **username_1**: I still have no clue what you mean by SVD in this setting? You cannot hope the $u_i$ and $v_i$ vectors to be orthogonal.  

---

