Counting the number of a certain class of binary matrices

Question

Let $f:\mathbb{N}\cup\{0\}\to\{0,1\}$ be defined as $$ f(x) = \begin{cases} 1,\;\text{if}\ \ x\in\mathbb{N}\\ 0,\;\text{if}\ \ x=0 \end{cases}. $$ Let $\mathbf{B}$ be an $n\times \ell$ binary matrix (with $\{0,1\}$ elements). I am trying to calculate the number of such Binary matrices which gives the same value of $f(\mathbf{B}\mathbf{B}^T)$. Here $f$ acts on matrices element by element.

Answer 1

I can not give you an explicit formula and I doubt that such a formula exists, but I can tell you how I would think about it, which might lead you to a non-polynomial algorithm.

Given $M\in\{0,1\}^{n\times n}$ you want to know how many $B\in\{0, 1\}^{n\times l}$ there are so that $M = f(BB^\top)$.

First note that if $M$ is not symmetric, then there is no such $B$, since products of the form $BB^\top$ are always symmetric.

As hardmath has mentioned, if you have $M = f(BB^\top)$ for any $B\in\{0, 1\}^{n\times \ell}$, then you can think of the rows of $B$ as representing subsets $B_1, ..., B_n \subset \{1,...,\ell\}$ where $k\in B_i$ if and only if the $k$-th entry in the $i$-th row $B_{i,k}$ is $1$. Now the entry $i,j$ in $BB^\top$ counts the number of common elements of $B_i$ and $B_j$, that means $|B_i\cap B_j|$. So $f(BB^\top)_{i,j} = 1$ if and only if $B_i \cap B_j \neq \emptyset$.

Now if $M$ has a zero diagonal entry, say $M_{i,i} = 0$, this translates to $B_i \cap B_i = \emptyset$, which is only possible if $B_i = \emptyset$. But then we also have $B_i \cap B_j = \emptyset$ for all $j$. For this to be true, all the other entries in both the $i$-th row and the $i$-th column of $M$ need to be zero. So if $M$ has a $1$ anywhere in the $i$-th row or $i$-th column, then your problem is answered: No such $B$ exists. Otherwise since $B_i = \emptyset$ you know that the $i$-th row of $B_i$ only contains zeros. Now by removing the $i$-th row and the $i$-th column of $M$ you can reduce the problem to a smaller instance. In conclusion, zero diagonal entries in $M$ are easy to handle and we may assume that the diagonal of $M$ contains only $1$s.

You can see $M$ as the adjacency matrix of a simple, undirected graph with vertex set $V = \{1, ..., n\}$ and an edge between $i$ and $j$ iff $M_{i,j}=1$. Now what you are asking for is the number of representations of this graph as an intersection graph of a subset-family of $\{1, ..., \ell\}$. This is a problem that you can answer manually for small graphs or for graphs with a certain kind of structure, such as being a chain, a circle, a tree and so on. But in general, even answering whether such a representation exists at all, that means whether the number of these $B$'s is larger than zero, is known to be a NP-complete problem. It is equivalent to the edge-clique-cover-problem.

If these concepts are new to you, I recommend you to read the Wikipedia article Intersection number (graph theory). What you can do also is to fix $\ell$ to be equal to $1, 2, n, n-1$ or other values. This might give you some interesting problems.