Disjunct matrix explained

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 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{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":

• Every

\overline{d +1 } -separable matrix is also d -disjunct.

• Every

d -disjunct matrix is also \overline{d} -separable.

• Every

\overline{d} -separable matrix is also d -separable (by definition).

Concrete examples

The following

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

See main article: 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.

Practical concerns and published results

For a given n and d, the number of rows t in the smallest d-separable

t x n matrix may (according to current knowledge) be smaller than the number of rows t in the smallest d-disjunct t x 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 ^{2ln} n) rows.

See also

• Group testing
• Concatenated code
• Compressed sensing

References

^[1]

^[2]

^[3]

^[4]

^[5]

Further reading

• Atri Rudra's book on Error Correcting Codes: Combinatorics, Algorithms, and Applications (Spring 201), Chapter 17
• 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.
• Füredi . Zoltán . Zoltán Füredi . 1996 . On r-Cover-free Families . . Series A . 73 . 1 . 172–173 . 10.1006/jcta.1996.0012. free .

Notes and References

1. Hong-Bin Chen . Frank Hwang . 2006-12-21 . Exploring the missing link among d-separable, -separable and d-disjunct matrices. . 155 . 5 . 662–664 . 10.1016/j.dam.2006.10.009 . free . 10.1.1.848.5161 . 2303978.
2. De Bonis . Annalisa . Vaccaro . Ugo . 10.1016/S0304-3975(03)00281-0 . 1-3 . Theoretical Computer Science . 2000175 . 223–243 . Constructions of generalized superimposed codes with applications to group testing and conflict resolution in multiple access channels . 306 . 2003.
3. . . . Families of finite sets in which no set is covered by the union of r others . . 51 . 1–2 . 79–89 . 1985 . 0021-2172. 10.1007/BF02772959 . free .
4. . Hung Q. Ngo . Atri Rudra . Efficiently Decodable Non-adaptive Group Testing . Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA) . 2010 . 1071-9040 . 1721.1/63167.
5. Ely Porat . Amir Rothschild . Explicit Non-Adaptive Combinatorial Group Testing Schemes . Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP) . 748–759 . 2008 . 0712.3876 . 2007arXiv0712.3876P .