# 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

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.
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.
• 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