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.^[1]

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

• 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 ${\displaystyle {\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":^[2]

• Every ${\displaystyle {\overline {d+1}}}$-separable matrix is also ${\displaystyle d}$-disjunct.^[2]
• Every ${\displaystyle d}$-disjunct matrix is also ${\displaystyle {\overline {d}}}$-separable.^[2]
• Every ${\displaystyle {\overline {d}}}$-separable matrix is also ${\displaystyle d}$-separable (by definition).

Concrete examples

The following ${\displaystyle 6\times 8}$ matrix is 2-separable, because each pair of columns has a distinct sum. For example, the boolean sum (that is, the

) of the first two columns is ${\displaystyle 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 ${\displaystyle 111111}$) equals the sum of columns 1, 4, and 5.

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

${\displaystyle \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 ${\displaystyle 6\times 4}$ matrix is ${\displaystyle {\overline {3}}}$-separable (and thus 2-disjunct) but not 3-disjunct.

${\displaystyle \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]}$

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

columns	boolean sum		columns	boolean sum
none	000000		2,3	011110
1	110000		2,4	101101
2	001100		3,4	111011
3	011010		1,2,3	111110
4	100001		1,2,4	111101
1,2	111100		1,3,4	111011
1,3	111010		2,3,4	111111
1,4	110001

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

Application of d-separability to group testing

The

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 ${\displaystyle d}$-separable matrix with ${\displaystyle t}$ rows and ${\displaystyle 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 ${\displaystyle d}$-disjunct matrix (or, more generally, any ${\displaystyle {\overline {d}}}$-separable matrix) with ${\displaystyle t}$ rows and ${\displaystyle 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

In the limit, for a given n and d, the number of rows t in the smallest d-separable ${\displaystyle t\times n}$ matrix will tend to be smaller than the number of rows t in the smallest d-disjunct ${\displaystyle 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 ${\displaystyle 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,

decoding algorithms are known; the naïve algorithm is ${\displaystyle O(nt)}$.^[3] For arbitrary d-separable but non-d-disjunct matrices, the best known decoding algorithms are exponential-time.^{[citation needed]}

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

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), Chapter 17 Archived 2015-04-02 at the Wayback Machine
• Dýachkov, A. G., & Rykov, V. V. (1982). Bounds on the length of disjunctive codes. Problemy Peredachi Informatsii [Problems 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 [Problems of Control and Information Theory], 18(4), 237–250.
• doi:10.1006/jcta.1996.0012
  .