# Recover a matrix with minimum number of queries

Alice has a matrix $$A \in \{0,1\}^{n \times m}$$ such that the sum of each row is $$1$$. Bob tries to find the indices of the ones (he knows that the sum of each row is $$1$$). The type of questions Bob can ask Alice is: "Does $$\sum a_{i,j} = 0$$" for some subset $$\{a_{i,j}\}$$ of size $$n$$. How fast (i.e. minimum questions) can Bob recover the ones (even with high probability)?

• Do you have any thoughts on the question? – Yuval Filmus Mar 22 '20 at 21:27

Let me consider the case $$n = m$$ for concreteness. Since the entropy of $$A$$ is $$n\log n$$ and each question results in at most one bit of information, at least $$n\log n$$ queries are needed.
Suppose that a question is selected uniformly at random. The probability that the answer is zero is $$(1-1/n)^n \approx 1/e$$, and in that case, we can mark all the queried entries as zero. Imagine making such queries until $$N$$ are successful. This is the same as making $$N$$ queries, each of which involves $$n$$ zero positions at random. The probability that a particular zero position is never queried is $$\left(1 - \frac{n}{n(n-1)}\right)^N \approx e^{-N/n}.$$ Therefore after $$(2+\epsilon) n\log n$$ queries, the probability that a particular zero position is never queried is at most roughly $$n^{-2-\epsilon}$$, and so the probability that not all zero positions are revealed is at most $$n^{-\epsilon}$$. We conclude that $$(2e+\epsilon) n\log n$$ queries suffice to reveal the matrix with probability $$1-o(1)$$.
We can repeat the calculation for general $$m$$, but the bounds no longer match. For example, when $$m$$ is very large, the answer to most questions will be zero, and so bounding the amount of information obtained from a single query by one bit is too generous.