Disjunct Matrix

In mathematics, a logical matrix may be described as ''d''-disjunct and/or ''d''-separable. These concepts play a pivotal role in the mathematical area of non-adaptive group testing.

In the mathematical literature, ''d''-disjunct matrices may also be called superimposed codes or ''d''-cover-free families.

According to Chen and Hwang (2006),

* A matrix is said to be ''d''-separable if no two sets of ''d'' columns have the same boolean sum.
* A matrix is said to be $\overline$-separable (that's ''d'' with an overline) if no two sets of ''d''-or-fewer columns have the same boolean sum.
* A matrix is said to be ''d''-disjunct if no set of ''d'' columns has a boolean sum which is a superset of any other single column.

The following relationships are "well-known":

* Every $\overline$-separable matrix is also $d$-disjunct.
* Every $d$-disjunct matrix is also $\overline$-separable.
* Every $\overline$-separable matrix is also $d$-separable (by definition).

Concrete examples

The following $6\times 8$ matrix is 2-separable, because each pair of columns has a distinct sum. For example, the boolean sum (that is, the bitwise OR) of the first two columns is $110000\or 001100 = 111100$; that sum is not attainable as the sum of any other pair of columns in the matrix.

However, this matrix is not 3-separable, because the sum of columns 1, 2, and 3 (namely $111111$) equals the sum of columns 1, 4, and 5.

This matrix is also not $\overline$-separable, because the sum of columns 1 and 8 (namely $110000$) equals the sum of column 1 alone. In fact, no matrix with an all-zero column can possibly be $\overline$-separable for any $d\ge 1$.

$\quad\left[ \begin 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 \\ \end \right]$

The following $6\times 4$ matrix is $\overline$-separable (and thus 2-disjunct) but not 3-disjunct.

$\quad\left[ \begin 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end \right]$

There are 15 possible ways to choose 3-or-fewer columns from this matrix, and each choice leads to a different boolean sum:

However, the sum of columns 2, 3, and 4 (namely $111111$) is a superset of column 1 (namely $110000$), which means that this matrix is not 3-disjunct.

Application of ''d''-separability to group testing

The non-adaptive group testing problem postulates that we have a test which can tell us, for any set of items, whether that set contains a ''defective'' item. We are asked to come up with a series of groupings that can exactly identify all the defective items in a batch of ''n'' total items, some ''d'' of which are defective.

A $d$-separable matrix with $t$ rows and $n$ columns concisely describes how to use ''t'' tests to find the defective items in a batch of ''n'', where the number of defective items is known to be exactly ''d''.

A $d$-disjunct matrix (or, more generally, any $\overline$-separable matrix) with $t$ rows and $n$ columns concisely describes how to use ''t'' tests to find the defective items in a batch of ''n'', where the number of defective items is known to be no more than ''d''.

Practical concerns and published results

For a given ''n'' and ''d'', the number of rows ''t'' in the smallest ''d''-separable $t\times n$ matrix may (according to current knowledge) be smaller than the number of rows ''t'' in the smallest ''d''-disjunct $t\times n$ matrix, but in asymptotically they are within a constant factor of each other. Additionally, if the matrix is to be used for practical testing, some algorithm is needed that can "decode" a test result (that is, a boolean sum such as $111100$) into the indices of the defective items (that is, the unique set of columns that produce that boolean sum). For arbitrary ''d''-disjunct matrices, polynomial-time decoding algorithms are known; the naïve algorithm is $O(nt)$. For arbitrary ''d''-separable but non-''d''-disjunct matrices, the best known decoding algorithms are exponential-time.

Porat and Rothschild (2008) present a deterministic $O(nt)$-time algorithm for constructing a ''d''-disjoint matrix with ''n'' columns and $\Theta(d^2\ln n)$ rows.

See also

* Group testing
* Concatenated code
* Compressed sensing

References

Further reading

* Atri Rudra's book on Error Correcting Codes: Combinatorics, Algorithms, and Applications (Spring 201), Chapte
17

* Dýachkov, A. G., & Rykov, V. V. (1982). Bounds on the length of disjunctive codes. ''Problemy Peredachi Informatsii'' roblems of Information Transmission 18(3), 7–13.
* Dýachkov, A. G., Rashad, A. M., & Rykov, V. V. (1989). ''Superimposed distance codes. Problemy Upravlenija i Teorii Informacii'' roblems of Control and Information Theory 18(4), 237–250.
* {{cite journal , last1=Füredi , first1=Zoltán , authorlink1=Zoltán Füredi , year=1996 , title=On r-Cover-free Families , journal=Journal of Combinatorial Theory , series=Series A , volume=73 , issue=1 , pages=172–173 , doi=10.1006/jcta.1996.0012, doi-access=free

Combinatorics