# Finding an algorithm to fill in a matrix subject to conditions

I have a combinatorics problem and I am asking for a solution or a reference in order to solve it.

Since the problem is rather long, I will translate it mathematically.

Suppose I have a $$n \times m$$ matrix with no entries.

I want to fill the matrix with entries equal to $$0$$ or $$1$$, subject to some conditions.

We define a sum operation, which I denote by $$\vee$$, which is the or operation (attention: not XOR / $$\oplus$$ / addition modulo $$2$$ / exclusive-or operation): $$\begin{array}{c|c|c|c|} \vee& 0 & 1 \\ \hline 0 & 0 & 1 \\ \hline 1 & 1 & 1 \\ \hline \end{array}$$ We will use the same symbol $$\vee$$ to sum rows of a matrix component by component. The result is thus a row vector.

Let $$t \in \{1,\ldots,n\}$$.

Condition 1: For each subset $$S \subseteq \{1,\ldots,n\}$$ of cardinal $$t$$, the sum of the $$S$$-rows is equal to $$(1,\ldots,1)$$.

Condition 2: For each subset $$S \subseteq \{1,\ldots,n\}$$ of cardinal $$t-1$$, the sum of the $$S$$-rows is not equal to $$(1,\ldots,1)$$.

Trivial consequence: Each column has to have at least $$t$$ ones.

And that's it! Brute-force is not an option, since in worst-case it would take $$\binom{n}{t}^m$$ attempts. If, for example, $$t=\frac{n}{2}$$, brute-force is exponential-time. I am looking for a polynomial-time algorithm. On the other hand, I could simply randomly generate a matrix with entries equal to $$0$$ or $$1$$ and check the conditions. But again, by the same reason, checking the conditions would be exponential-time.

• This is equivalent to placing several locks on a treasure chest and distributing copies of the keys various subsets of $n$ pirates so that any $t$ pirates can open the chest, but any $t-1$ cannot. This is also discussed here. – Mike Earnest Feb 7 at 20:29

Let $$M$$ be your matrix.
For each $$S \subset \{1,\ldots,n\}$$, let $$Z(S) = \{j \in \{1,\ldots,m\}: \sum_{i \in S} M_{ij} = 0\}$$. The condition says $$Z(S)$$ is nonempty if $$|S|=t-1$$, but empty if $$|S|=t$$. In particular, for any distinct $$S_1, S_2$$ with $$|S_1| = |S_2| = t-1$$, $$Z(S_1)$$ and $$Z(S_2)$$ are disjoint. Thus we need $$m \ge {n \choose t-1}$$.

Conversely, if $$m \ge {n \choose t-1}$$ we can construct such an $$M$$. For simplicity, suppose $$m={n \choose t-1}$$ (we can always add more columns of all $$1$$'s). Namely, let $$S_1, \ldots, S_{m}$$ be an enumeration of the subsets of $$\{1,\ldots,n\}$$ of cardinality $$t-1$$, and define $$M_{ij} = 0$$ if $$i \in S_{j}$$, $$1$$ otherwise.

• Thank you for answering. I don't understand the statement ''In particular, (...), $Z(S_1)$ and $Z(S_2)$ are disjoint." This is not clear and it seems false... – Leafar Feb 7 at 19:08
• Let $S_3$ be the union of $S_1$ and one element of $S_2$ that is not in $S_1$. Then $|S_3| = t$. If $j \in Z(S_1) \cap Z(S_2)$, then $j \in Z(S_3)$, which is impossible. – Robert Israel Feb 7 at 20:02
• Ok, I agree. Now I have another question... Is this matrix unique, up to the order of the subsets and having an arbitrary number of columns of all 1's? From your answer it seems so... – Leafar Feb 8 at 8:18

This is very similar to Robert Israel's answer, but reworded.

For each subset $$S$$ of size $$t-1$$, there must be at least one column, $$c$$, where all the entries in $$c$$ whose row is in $$S$$ are $$0$$. Furthermore, all the other entries in $$c$$ must be $$1$$, since for every superset $$S'$$ of $$S$$ of size $$t$$, there is at least one $$1$$ in some row in $$S'$$ in $$c$$, and it cannot occur in $$S$$.

Therefore, for each of the $$\binom{n}{t-1}$$ possibilities for $$S$$, a particular column must exist; one with zeroes in $$S$$ and ones elsewhere. This means there must be at least $$\binom{n}{t-1}$$ columns. In particular, a simple algorithm to construct the matrix is this; list all of the subsets of $$S$$, and for each one, add a column to the matrix which is zero for the rows in $$S$$ and one elsewhere. Then pad the matrix to $$m$$ columns by adding columns of ones.