# Binary rank of binary matrix

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.

• what is SVD in this context? do you mean computing a factorization $M = UV$ with optimal inner dimension? – Sasho Nikolov May 26 '16 at 18:43
• 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 May 26 '16 at 18:47
• 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 for a definition of partition number. – Robin Kothari May 26 '16 at 22:03
• @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 May 27 '16 at 3:55
• @Ram: I believe the partition number is NP-hard to compute. I can look for a reference if that's helpful. This recent paper on binary rank may be of interest to you. – Robin Kothari May 27 '16 at 12:13

## 2 Answers

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. L. Sunil Chandran, Davis Issac, and Andreas Karrenbauer. Published in IPEC 2016

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: , .

• 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 May 28 '16 at 8:21
• 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 May 28 '16 at 20:12