# Disjunct matrix

Disjunct and separable matrices play a pivotal role in the mathematical area of non-adaptive group testing. This area investigates efficient designs and procedures to identify 'needles in haystacks' by conducting the tests on groups of items instead of each item alone. The main concept is that if there are very few special items (needles) and the groups are constructed according to certain combinatorial guidelines, then one can test the groups and find all the needles. This can reduce the cost and the labor associated with of large scale experiments.

The grouping pattern can be represented by a ${\displaystyle t\times n}$ binary matrix, where each column represents an item and each row represents a pool. The symbol '1' denotes participation in the pool and '0' absence from a pool. The d-disjunctness and the d-separability of the matrix describe sufficient condition to identify d special items.

In a matrix that is d-separable, the Boolean sum of every d columns is unique. In a matrix that is d-disjunct the Boolean sum of every d columns does not contain any other column in the matrix. Theoretically, for the same number of columns (items), one can construct d-separable matrices with fewer rows (tests) than d-disjunct. However, designs that are based on d-separable are less applicable since the decoding time to identify the special items is exponential. In contrast, the decoding time for d-disjunct matrices is polynomial.

## d-separable

Definition: A ${\displaystyle t\times n}$ matrix ${\displaystyle M}$ is ${\displaystyle d}$-separable if and only if ${\displaystyle \forall S_{1}\neq S_{2}\subseteq [n]}$ where ${\displaystyle |S_{1}|,|S_{2}|\leq d}$ such that ${\displaystyle \bigcup _{j\in S_{1}}M_{j}\neq \bigcup _{i\in S_{2}}M_{i}}$

### Decoding algorithm

First we will describe another way to look at the problem of group testing and how to decode it from a different notation. We can give a new interpretation of how group testing works as follows:

Group testing: Given input ${\displaystyle M}$ and ${\displaystyle \mathbf {r} }$ such that ${\displaystyle \mathbf {r} =M\mathbf {x} }$ output ${\displaystyle \mathbf {x} }$

• Take ${\displaystyle M_{j}}$ to be the ${\displaystyle j^{th}}$ column of ${\displaystyle M}$
• Define ${\displaystyle S_{M_{j}}\subseteq [t]}$ so that ${\displaystyle M_{j}(i)=1}$ if and only if ${\displaystyle i\in S_{M_{j}}}$
• This gives that ${\displaystyle S_{\mathbf {r} }=\bigcup _{j\in [n],\mathbf {x} _{j}=1}S_{M_{j}}}$

This formalizes the relation between ${\displaystyle \mathbf {x} }$ and the columns of ${\displaystyle M}$ and ${\displaystyle \mathbf {r} }$ in a way more suitable to the thinking of ${\displaystyle d}$-separable and ${\displaystyle d}$-disjunct matrices. The algorithm to decode a ${\displaystyle d}$-separable matrix is as follows:

Given a ${\displaystyle t\times n}$ matrix ${\displaystyle M}$ such that ${\displaystyle M}$ is ${\displaystyle d}$-separable:

1. For each ${\displaystyle T\subseteq [n]}$ such that ${\displaystyle |T|\leq d}$ check if ${\displaystyle S_{\mathbf {r} }=\bigcup _{j\in T}S_{M_{j}}}$

This algorithm runs in time ${\displaystyle n^{{\mathcal {O}}(d)}}$.

## d-disjunct

In literature disjunct matrices are also called super-imposed codes and d-cover-free families.

Definition: A ${\displaystyle t}$ x ${\displaystyle n}$ matrix ${\displaystyle M}$ is d-disjunct if ${\displaystyle \forall S\subseteq [n]}$ such that ${\displaystyle |S|\leq d}$, ${\displaystyle \forall j\notin S}$ ${\displaystyle \exists i}$ such that ${\displaystyle M_{i,j}=1}$ but ${\displaystyle \forall k\in S,M_{i,k}=0}$. Denoting ${\displaystyle M_{a}}$ is the ${\displaystyle a^{th}}$ column of ${\displaystyle M}$ and ${\displaystyle S_{M_{a}}\subseteq [t]}$ where ${\displaystyle M_{a}(b)=1}$ if and only if ${\displaystyle b\in S_{M_{a}}}$ gives that ${\displaystyle M}$ is ${\displaystyle d}$-disjunct if and only if ${\displaystyle S_{M_{j}}\not \subset \cup _{k\in S}S_{M_{k}}}$

Claim: ${\displaystyle M}$ is ${\displaystyle d}$-disjunct implies ${\displaystyle M}$ is ${\displaystyle d}$-separable

Proof: (by contradiction) Let ${\displaystyle M}$ be a ${\displaystyle t}$ x ${\displaystyle n}$ ${\displaystyle d}$-disjunct matrix. Assume for contradiction that ${\displaystyle M}$ is not ${\displaystyle d}$-separable. Then there exists ${\displaystyle T_{1},T_{2}\in [n]}$ and ${\displaystyle T_{1}\neq T_{2}}$ with ${\displaystyle |T_{1}|,|T_{2}|\leq d}$ such that ${\displaystyle \bigcup _{i\in T_{1}}M_{i}=\cup _{i\in T_{2}}S_{M_{i}}}$. This implies that ${\displaystyle \exists j\in T_{2}\setminus T_{1}}$ such that ${\displaystyle S_{M_{j}}\subseteq \bigcup _{k\in T_{1}}T_{M_{k}}}$. This contradicts the fact that ${\displaystyle M}$ is ${\displaystyle d}$-disjunct. Therefore ${\displaystyle M}$ is ${\displaystyle d}$-separable. ${\displaystyle \Box }$

### Decoding algorithm

The algorithm for ${\displaystyle d}$-separable matrices was still a polynomial in ${\displaystyle n}$. The following will give a nicer algorithm for ${\displaystyle d}$-disjunct matrices which will be a ${\displaystyle d}$ multiple instead of raised to the power of ${\displaystyle d}$ given our bounds for ${\displaystyle t}$. The algorithm is as follows in the proof of the following lemma:

Lemma 1: There exists an ${\displaystyle {\mathcal {O}}(nt)}$ time decoding for any ${\displaystyle d}$-disjunct ${\displaystyle t}$ x ${\displaystyle n}$ matrix.

• Observation 1: For any matrix ${\displaystyle M}$ and given ${\displaystyle M\mathbf {x} =\mathbf {r} }$ if ${\displaystyle \mathbf {r} _{i}=1}$ it implies ${\displaystyle \exists j}$ such that ${\displaystyle M_{i,j}=1}$ and ${\displaystyle \mathbf {x} _{j}=1}$ where ${\displaystyle 1\leq i\leq t}$ and ${\displaystyle 1\leq j\leq n}$. The opposite is also true. If ${\displaystyle \mathbf {r} _{i}=0}$ it implies ${\displaystyle \forall j}$ if ${\displaystyle M_{i,j}=1}$ then ${\displaystyle \mathbf {x} _{j}=0}$. This is the case because ${\displaystyle \mathbf {r} }$ is generated by taking all of the logical or of the ${\displaystyle \mathbf {x} _{j}}$'s where ${\displaystyle M_{i,j}=1}$.
• Observation 2: For any ${\displaystyle d}$-disjunct matrix and every set ${\displaystyle T=\{j|\mathbf {x} _{j}=1\}}$ where ${\displaystyle |T|\leq d}$ and for each ${\displaystyle j\notin T}$ where ${\displaystyle 1\leq j\leq n}$ there exists some ${\displaystyle i}$ where ${\displaystyle 1\leq i\leq t}$ such that ${\displaystyle M_{i,j}=1}$ but ${\displaystyle M_{i,l}=0{\text{ }}\forall l\in T}$. Thus, if ${\displaystyle \mathbf {r} _{i}=0}$ then ${\displaystyle \mathbf {x} _{j}=0}$.

Proof of Lemma 1: Given as input ${\displaystyle \mathbf {r} \in \{0,1\}^{t},M}$ use the following algorithm:

1. For each ${\displaystyle j\in [n]}$ set ${\displaystyle \mathbf {x} _{j}=1}$
2. For ${\displaystyle i=1\ldots t}$, if ${\displaystyle \mathbf {r} _{i}=0}$ then for all ${\displaystyle j\in [n]}$, if ${\displaystyle M_{i,j}=1}$ set ${\displaystyle \mathbf {x} _{j}=0}$

By Observation 1 we get that any position where ${\displaystyle \mathbf {r} _{i}=0}$ the appropriate ${\displaystyle \mathbf {x} _{j}}$'s will be set to 0 by step 2 of the algorithm. By Observation 2 we have that there is at least one ${\displaystyle i}$ such that if ${\displaystyle \mathbf {x} _{j}}$ is supposed to be 1 then ${\displaystyle M_{i,j}=1}$ and, if ${\displaystyle \mathbf {x} _{j}}$ is supposed to be 1, it can only be the case that ${\displaystyle \mathbf {r} _{i}=1}$ as well. Therefore step 2 will never assign ${\displaystyle \mathbf {x} _{j}}$ the value 0 leaving it as a 1 and solving for ${\displaystyle \mathbf {x} }$. This takes time ${\displaystyle {\mathcal {O}}(nt)}$ overall. ${\displaystyle \Box }$

## de-disjunct

Definition:A matrix ${\displaystyle M}$ is ${\displaystyle d^{e}}$-disjunct if for any ${\displaystyle d+1}$ columns ${\displaystyle M_{0}'}$, ${\displaystyle M_{1}',\ldots ,M_{d}'}$ of ${\displaystyle M}$ there are at least ${\displaystyle e+1}$ elements ${\displaystyle 1}$ in ${\displaystyle M_{0}'-\bigcup _{i=1}^{d}M_{i}'}$.

Definition:Let ${\displaystyle M}$ be a ${\displaystyle t\times n}$ ${\displaystyle d^{e}}$-disjunct matrix. The output ${\displaystyle o(S)}$ of ${\displaystyle S}$ in ${\displaystyle M}$ is the union of those columns indexed by ${\displaystyle S}$, where ${\displaystyle S}$ is a subset of ${\displaystyle \{1,2,\ldots ,n\}}$with at most size ${\displaystyle d}$.

Proposition: Let ${\displaystyle M}$ be a ${\displaystyle d^{e}}$-disjunct matrix. Let ${\displaystyle S,T\subseteq \{1,2,\ldots ,n\}}$ be two distinct subsets with each at most ${\displaystyle d}$ elements. Then the Hamming distance of the outputs ${\displaystyle o(S)}$ and ${\displaystyle o(T)}$ is at least ${\displaystyle e+1}$.

Proof: Without loss of generality, we may assume ${\displaystyle \exists j}$ s.t. ${\displaystyle j\in S}$ and ${\displaystyle j\notin T}$. We consider the ${\displaystyle j}$-th column of ${\displaystyle M}$ and those columns of ${\displaystyle M}$ indexed by ${\displaystyle T}$, then we can find ${\displaystyle e+1}$ different ${\displaystyle \ell }$ such that ${\displaystyle M_{\ell j}=1}$ and ${\displaystyle M_{\ell k}=0}$ for all ${\displaystyle k\in T}$, because the definition of ${\displaystyle d^{e}}$-disjunct. Hence we complete the proof.

Then we have the following corollary.

Corollary We can detect ${\displaystyle e}$ errors and correct ${\displaystyle \left\lfloor {\dfrac {e}{2}}\right\rfloor }$ errors on the outcome of ${\displaystyle d^{e}}$-disjunct matrix.

## Upper bounds for non-adaptive group testing

The results for these upper bounds rely mostly on the properties of ${\displaystyle d}$-disjunct matrices. Not only are the upper bounds nice, but from Lemma 1 we know that there is also a nice decoding algorithm for these bounds. First the following lemma will be proved since it is relied upon for both constructions:

Lemma 2: Given ${\displaystyle 1\leq d\leq n}$ let ${\displaystyle M}$ be a ${\displaystyle t\times n}$ matrix and:

1. ${\displaystyle \forall j\in [n]{\text{, }}|S_{M_{j}}|\geq w_{\min }}$
2. ${\displaystyle \forall i\neq j\in [n],|S_{M_{i}}\cap S_{M_{j}}|\leq a_{\max }}$

for some integers ${\displaystyle a_{\max }\leq w_{\min }\leq t}$ then ${\displaystyle M}$ is ${\displaystyle \geq d'\left\lfloor {\frac {w_{\min }-1}{a_{\max }}}\right\rfloor }$-disjunct.

Note: these conditions are stronger than simply having a subset of size ${\displaystyle d}$ but rather applies to any pair of columns in a matrix. Therefore no matter what column ${\displaystyle i}$ that is chosen in the matrix, that column will contain at least ${\displaystyle w_{\min }}$ 1's and the total number of shared 1's by any two columns is ${\displaystyle a_{\max }}$.

Proof of Lemma 2: Fix an arbitrary ${\displaystyle S\subseteq [n],|S|\leq d,j\notin S}$ and a matrix ${\displaystyle M}$. There exists a match between ${\displaystyle i\in S{\text{ and }}j\notin S}$ if column ${\displaystyle i}$ has a 1 in the same row position as in column ${\displaystyle j}$. Then the total number of matches is ${\displaystyle \leq a_{\max }\cdot d\leq a_{\max }\cdot \left({\frac {w_{\min }-1}{a_{\max }}}\right)=w_{\min }-1, i.e. a column ${\displaystyle j}$ has a fewer number of matches than the number of ones in it. Therefore there must be a row with all 0s in ${\displaystyle S}$ but a 1 in ${\displaystyle j}$. ${\displaystyle \Box }$

We will now generate constructions for the bounds.

Constructions can be either randomized (brute-force), explicit or strongly explicit. This concerns the time in which the incidence matrix can be generated. An explicit construction for a ${\displaystyle n\times m}$ matrix has a complexity ${\displaystyle {\mathcal {O}}(\operatorname {poly} (n+m))}$, whereas a randomized construction takes more than that. For a strongly explicit construction, one can find a single entry of the matrix in ${\displaystyle \operatorname {poly} (m)}$ time.

### Randomized construction

This first construction will use a probabilistic argument to show the property wanted, in particular the Chernoff bound. Using this randomized construction gives that ${\displaystyle t(d,n)\leq {\mathcal {O}}(d^{2}\log n)}$. The following lemma will give the result needed.

Theorem 1: There exists a random ${\displaystyle d}$-disjunct matrix with ${\displaystyle {\mathcal {O}}(d^{2}\log n)}$ rows.

Proof of Theorem 1: Begin by building a random ${\displaystyle t\times n}$ matrix ${\displaystyle M}$ with ${\displaystyle t=cd^{2}\log n}$ (where ${\displaystyle c}$ will be picked later). It will be shown that ${\displaystyle M}$ is ${\displaystyle \Omega (d)}$-disjunct. First note that ${\displaystyle M_{i,j}\in \{0,1\}}$ and let ${\displaystyle M_{i,j}=1}$ independently with probability ${\displaystyle {\frac {1}{d}}}$ for ${\displaystyle i\in [t]}$ and ${\displaystyle j\in [n]}$. Now fix ${\displaystyle j\in [n]}$. Denote the ${\displaystyle j^{\text{th}}}$ column of ${\displaystyle M}$ as ${\displaystyle T_{j}\subseteq [t]}$. Then the expectancy is ${\displaystyle \mathbb {E} [|T_{j}|]={\frac {t}{d}}}$. Using the Chernoff bound, with ${\displaystyle \mu ={\frac {1}{2}}}$, gives ${\displaystyle \Pr[|T_{j}|<{\frac {t}{2d}}]\leq e^{\frac {-t}{12d}}=e^{\frac {-cd\log n}{12}}\leq n^{-2d}[}$if ${\displaystyle c\geq 24]}$. Taking the union bound over all columns gives ${\displaystyle \Pr \left[\exists j\ |T_{j}|<{\frac {t}{2d}}\right]\leq n\cdot n^{-2d}\leq n^{-d}}$. This gives ${\displaystyle \Pr \left[\forall j\ |T_{j}|\geq {\frac {t}{2d}}\right]\geq 1-n^{-d}}$. Therefore ${\displaystyle w_{\min }\geq {\frac {t}{2d}}}$ with probability ${\displaystyle \geq 1-n^{-d}}$.

Now suppose ${\displaystyle j\neq k\in [n]}$ and ${\displaystyle i\in [t]}$ then ${\displaystyle \Pr[M_{i,j}=M_{i,k}=1]={\frac {1}{d^{2}}}}$. So ${\displaystyle \operatorname {E} [|T_{j}\cap T_{k}|]={\frac {t}{d^{2}}}}$. Using the Chernoff bound on this gives ${\displaystyle \Pr[|T_{j}\cap T_{k}|>{\frac {2t}{d^{2}}}]\leq e^{\frac {-t}{3d^{2}}}=e^{-2\log n}\leq n^{-4}[}$if ${\displaystyle c\geq 12]}$. By the union bound over ${\displaystyle (j,k)}$ pairs ${\displaystyle \Pr[\exists (j,k)}$ such that ${\displaystyle |T_{j}\cap T_{k}|>{\frac {2t}{d^{2}}}]\leq n^{2}\cdot n^{-4}=n^{-2}}$. This gives that ${\displaystyle a_{\max }\leq {\frac {2t}{d^{2}}}}$ and ${\displaystyle w_{\min }\geq {\frac {t}{2d}}}$ with probability ${\displaystyle \geq 1-n^{-d}-n^{-2}\geq 1-{\frac {1}{n}}}$. Note that by changing ${\displaystyle c}$ the probability ${\displaystyle 1-{\frac {1}{n}}}$ can be made to be ${\displaystyle 1-{\frac {1}{\operatorname {poly} (n)}}}$. Thus ${\displaystyle d'=\left\lfloor {\frac {{\frac {t}{2d}}-1}{\frac {2t}{d^{2}}}}\right\rfloor \approx {\frac {d}{4}}}$. By setting ${\displaystyle d}$ to be ${\displaystyle 4d}$, the above argument shows that ${\displaystyle M}$ is ${\displaystyle d}$-disjunct.

Note that in this proof ${\displaystyle t=d^{2}\log n}$ thus giving the upper bound of ${\displaystyle t(d,n)\leq {\mathcal {O}}(d^{2}\log n)}$. ${\displaystyle \Box }$

### Strongly explicit construction

It is possible to prove a bound of ${\displaystyle t(d,n)\leq {\mathcal {O}}(d^{2}\log ^{2}{n})}$ using a strongly explicit code. Although this bound is worse by a ${\displaystyle \log n}$ factor, it is preferable because this produces a strongly explicit construction instead of a randomized one.

Theorem 2: There exists a strongly explicit ${\displaystyle d}$-disjunct matrix with ${\displaystyle {\mathcal {O}}(d^{2}\log ^{2}{n})}$ rows.

This proof will use the properties of concatenated codes along with the properties of disjunct matrices to construct a code that will satisfy the bound we are after.

Proof of Theorem 2: Let ${\displaystyle C\subseteq \{0,1\}^{t},|C|=n}$ such that ${\displaystyle C=\{\mathbf {c} _{1},\ldots ,\mathbf {c} _{n}\}}$. Denote ${\displaystyle M_{C}}$ as the matrix with its ${\displaystyle i^{\text{th}}}$ column being ${\displaystyle \mathbf {c} _{i}}$. If ${\displaystyle C^{*}}$ can be found such that

1. ${\displaystyle \forall i\in C^{*}{\text{, }}|\mathbf {c} _{i}|\geq w_{\min }}$
2. ${\displaystyle \forall \mathbf {c} ^{1}\neq \mathbf {c} ^{2}\in C^{*}{\text{, }}|\{i|\mathbf {c} _{i}^{1}=\mathbf {c} _{i}^{2}=1\}|\leq a_{\max }}$,

then ${\displaystyle M_{C^{*}}}$ is ${\displaystyle \lfloor {\frac {w_{\min }-1}{a_{\max }}}\rfloor }$-disjunct. To complete the proof another concept must be introduced. This concept uses code concatenation to obtain the result we want.

Kautz-Singleton '64

Let ${\displaystyle C^{*}=C_{\text{out}}\circ C_{\text{in}}}$. Let ${\displaystyle C_{\text{out}}}$ be a ${\displaystyle [q,k]_{q}}$-Reed–Solomon code. Let ${\displaystyle C_{\text{in}}=[q]\rightarrow \{0,1\}^{q}}$ such that for ${\displaystyle i\in [q]}$, ${\displaystyle c_{\text{in}}(i)=(0,\ldots ,0,1,0,\ldots ,0)}$ where the 1 is in the ${\displaystyle i^{\text{th}}}$ position. Then ${\displaystyle n=q^{k}}$, ${\displaystyle t=q^{2}}$, and ${\displaystyle w_{\min }=q}$.

---

Example: Let ${\displaystyle k=1,q=3,C_{\text{out}}=\{(0,0,0),(1,1,1),(2,2,2)\}}$. Below, ${\displaystyle M_{C}}$ denotes the matrix of codewords for ${\displaystyle C_{\text{out}}}$ and ${\displaystyle M_{C^{*}}}$ denotes the matrix of codewords for ${\displaystyle C^{*}=C_{\text{out}}\circ C_{\text{in}}}$, where each column is a codeword. The overall image shows the transition from the outer code to the concatenated code.

${\displaystyle M_{C}={\begin{bmatrix}0&1&2\\0&1&2\\0&1&2\end{bmatrix}}\quad \Rightarrow \quad M_{C^{*}}={\begin{bmatrix}0&0&1\\0&1&0\\1&0&0\\0&0&1\\0&1&0\\1&0&0\\0&0&1\\0&1&0\\1&0&0\end{bmatrix}}}$

---

Divide the rows of ${\displaystyle M_{C^{*}}}$ into sets of size ${\displaystyle q}$ and number them as ${\displaystyle (i,j)\in [q]\times [q]}$ where ${\displaystyle i}$ indexes the set of rows and ${\displaystyle j}$ indexes the row in the set. If ${\displaystyle M_{(i,j),k_{1}}=M_{(i,j),k_{2}}=1}$ then note that ${\displaystyle \mathbf {c} _{k_{1}}(i)=\mathbf {c} _{k_{2}}(i)=j}$ where ${\displaystyle \mathbf {c} _{k_{1}},\mathbf {c} _{k_{2}}\in C_{\text{out}}}$. So that means ${\displaystyle |M_{k_{1}}\cap M_{k_{2}}|=q-\Delta (\mathbf {c} _{k_{1}},\mathbf {c} _{k_{2}})}$. Since ${\displaystyle \Delta (\mathbf {c} _{k_{1}},\mathbf {c} _{k_{2}})\geq q-k+1}$ it gives that ${\displaystyle |M_{k_{1}}\cap M_{k_{2}}|\leq k-1}$ so let ${\displaystyle a_{\max }=k-1}$. Since ${\displaystyle t=q^{2}}$, the entries in each column of ${\displaystyle M_{C^{*}}}$ can be looked at as ${\displaystyle q}$ sets of ${\displaystyle q}$ entries where only one of the entries is nonzero (by definition of ${\displaystyle C_{\text{in}}}$) which gives a total of ${\displaystyle q}$ nonzero entries in each column. Therefore ${\displaystyle w_{\min }=q}$ and ${\displaystyle d=_{\text{def}}\left\lfloor {\frac {w_{\min }-1}{a_{\max }}}\right\rfloor }$ (so ${\displaystyle M_{C^{*}}}$ is ${\displaystyle d}$-disjunct).

Now pick ${\displaystyle q}$ and ${\displaystyle k}$ such that ${\displaystyle \left\lfloor {\frac {q-1}{k-1}}\right\rfloor =d}$ (so ${\displaystyle \left\lfloor {\frac {q}{k}}\right\rfloor \approx d}$). Since ${\displaystyle q^{k}=n}$ we have ${\displaystyle k={\frac {\log n}{\log q}}\leq \log n}$. Since ${\displaystyle q\approx kd}$ and ${\displaystyle t=q^{2}}$ it gives that ${\displaystyle t=q^{2}\approx (kd)^{2}\leq (d\log n)^{2}}$. ${\displaystyle \Box }$

Thus we have a strongly explicit construction for a code that can be used to form a group testing matrix and so ${\displaystyle t(d,n)\leq (d\log n)^{2}}$.

For non-adaptive testing we have shown that ${\displaystyle \Omega (d\log n)\leq t(d,n)}$ and we have that (i) ${\displaystyle t(d,n)\leq {\mathcal {O}}(d^{2}\log ^{2}{n})}$ (strongly explicit) and (ii) ${\displaystyle t(d,n)\leq {\mathcal {O}}(d^{2}\log n)}$ (randomized). As of recent work by Porat and Rothscheld, they presented an explicit method construction (i.e. deterministic time but not strongly explicit) for ${\displaystyle t(d,n)\leq {\mathcal {O}}(d^{2}\log n)}$,[1] however it is not shown here. There is also a lower bound for disjunct matrices of ${\displaystyle t(d,n)\geq \Omega ({\frac {d^{2}}{\log d}}\log n)}$[2][3][4] which is not shown here either.

## Examples

Here is the 2-disjunct matrix ${\displaystyle M_{9\times 12}}$:

${\displaystyle M_{9\times 12}=\left[{\begin{array}{cccccccccccc}0&0&0&0&0&0&1&1&1&1&0&0\\0&0&0&1&1&1&0&0&0&1&0&0\\1&1&1&0&0&0&0&0&0&1&0&0\\0&0&1&0&0&1&0&0&1&0&1&0\\0&1&0&0&1&0&0&1&0&0&1&0\\1&0&0&1&0&0&1&0&0&0&1&0\\0&1&0&1&0&0&0&0&1&0&0&1\\0&0&1&0&1&0&1&0&0&0&0&1\\1&0&0&0&0&1&0&1&0&0&0&1\end{array}}\right]}$