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 super-imposed codes^{[citation needed]} or d-cover-free families.^{[citation needed]}

According to Chen and Hwang (2006),^[1]

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 {d}}$ -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":^[1]

Every ${\overline {d+1}}$ -separable matrix is also $d$ -disjunct.^[1]
Every $d$ -disjunct matrix is also ${\overline {d}}$ -separable.^[1]
Every ${\overline {d}}$ -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\lor 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 {2}}$ -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 {d}}$ -separable for any $d\geq 1$ .

$\quad \left[{\begin{array}{cccccccc}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{array}}\right]$

The following $6\times 4$ matrix is ${\overline {3}}$ -separable (and thus 2-disjunct) but not 3-disjunct. There are 15 possible ways to choose 3-or-fewer columns from this matrix, and each choice leads to a different boolean sum: 000000, 110000, 001100, 011010, 100001, 111100, 111010, 110001, 011110, 101101, 111011, 111110, 111101, 111011, 111111. 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.

$\quad \left[{\begin{array}{cccc}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{array}}\right]$

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 {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 no more than d.

In the limit, for a given n and d, the number of rows t in the smallest d-separable $t\times n$ matrix will tend to be smaller than the number of rows t in the smallest d-disjunct $t\times n$ matrix.^{[citation needed]} However, 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 d-disjunct matrices, polynomial-time decoding algorithms are known.^{[citation needed]} For d-separable but non-d-disjunct matrices, the best known decoding algorithms are exponential-time.^{[citation needed]}