1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'd make first some experiments in Matlab or whatnot. $\endgroup$ – Wuestenfux Sep 29 '18 at 13:07
  • 3
    $\begingroup$ 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). $\endgroup$ – hardmath Sep 29 '18 at 13:33
  • $\begingroup$ @hardmath that’s right. But is this fact really helping in counting the number of such matrices. $\endgroup$ – J.John Sep 30 '18 at 7:12
  • $\begingroup$ 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. $\endgroup$ – hardmath Sep 30 '18 at 7:31
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks! I see. How about upper bounds? Is there any interesting way to get a “good” upper bound on the count? $\endgroup$ – J.John Sep 30 '18 at 13:47
  • $\begingroup$ 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. $\endgroup$ – hardmath Sep 30 '18 at 15:07
  • $\begingroup$ Right, but permutations are not the only possible solutions, right? So this will not give an upper bound? $\endgroup$ – J.John Sep 30 '18 at 15:14
  • 1
    $\begingroup$ 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). $\endgroup$ – hardmath Sep 30 '18 at 15:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.