# Counting the number of a certain class of binary matrices

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.

• I'd make first some experiments in Matlab or whatnot. – Wuestenfux Sep 29 '18 at 13:07
• Another way to think about your matrix $\mathbf B$ is that the rows denote subsets of $S=\{1,\ldots,\ell\}$ according to which row entries are $1$. The computation of $f(\mathbf B \mathbf{B}^T)$ reveals the relations among these subsets as being disjoint ($0$ entry) or not ($1$ entry). – hardmath Sep 29 '18 at 13:33
• @hardmath that’s right. But is this fact really helping in counting the number of such matrices. – J.John Sep 30 '18 at 7:12
• It helps to identity values of $f(\mathbf B \mathbf B^T)$ that are unobtainable, i.e. whose count is zero. There is no context for the problem statement, so I'll let you address whether that is helpful or not. – hardmath Sep 30 '18 at 7:31

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.

• Thanks! I see. How about upper bounds? Is there any interesting way to get a “good” upper bound on the count? – J.John Sep 30 '18 at 13:47
• If one solution $\mathbf B$ is known that gives specified $f(\mathbf B \mathbf B^T)$, additional solutions (not exhaustive) may be generated by permuting the columns of $\mathbf B$. I.e., if $\mathbf P$ is an $\ell\times \ell$ permutation matrix, then $$\mathbf B \mathbf B^T = (\mathbf B \mathbf P)(\mathbf B \mathbf P)^T$$ How many additional solutions this generates depends on the distinct column counts of $\mathbf B$ (if all columns were equal, no additional solutions by permuting them), so this becomes a multinomial calculation. – hardmath Sep 30 '18 at 15:07
• Right, but permutations are not the only possible solutions, right? So this will not give an upper bound? – J.John Sep 30 '18 at 15:14
• Right, not all solutions will arise in this fashion. However it allows the search for solutions to focus on matrices $\mathbf B$ whose columns are "sorted" in specified fashion, e.g. a reverse lexicographic ordering (so duplicate columns are grouped together). – hardmath Sep 30 '18 at 15:23