Finding an algorithm to fill in a matrix subject to conditions

Question

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.

Thanks in advance.

Answer 1

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.

Answer 2

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.