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 [math]\displaystyle{ \overline{d} }[/math]-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 [math]\displaystyle{ \overline{d+1} }[/math]-separable matrix is also [math]\displaystyle{ d }[/math]-disjunct.[2]
- Every [math]\displaystyle{ d }[/math]-disjunct matrix is also [math]\displaystyle{ \overline{d} }[/math]-separable.[2]
- Every [math]\displaystyle{ \overline{d} }[/math]-separable matrix is also [math]\displaystyle{ d }[/math]-separable (by definition).
Concrete examples
The following [math]\displaystyle{ 6\times 8 }[/math] 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 [math]\displaystyle{ 110000\or 001100 = 111100 }[/math]; 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 [math]\displaystyle{ 111111 }[/math]) equals the sum of columns 1, 4, and 5.
This matrix is also not [math]\displaystyle{ \overline{2} }[/math]-separable, because the sum of columns 1 and 8 (namely [math]\displaystyle{ 110000 }[/math]) equals the sum of column 1 alone. In fact, no matrix with an all-zero column can possibly be [math]\displaystyle{ \overline{d} }[/math]-separable for any [math]\displaystyle{ d\ge 1 }[/math].
[math]\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] }[/math]
The following [math]\displaystyle{ 6\times 4 }[/math] matrix is [math]\displaystyle{ \overline{3} }[/math]-separable (and thus 2-disjunct) but not 3-disjunct.
[math]\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] }[/math]
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 [math]\displaystyle{ 111111 }[/math]) is a superset of column 1 (namely [math]\displaystyle{ 110000 }[/math]), 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 [math]\displaystyle{ d }[/math]-separable matrix with [math]\displaystyle{ t }[/math] rows and [math]\displaystyle{ n }[/math] 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 [math]\displaystyle{ d }[/math]-disjunct matrix (or, more generally, any [math]\displaystyle{ \overline{d} }[/math]-separable matrix) with [math]\displaystyle{ t }[/math] rows and [math]\displaystyle{ n }[/math] 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 [math]\displaystyle{ t\times n }[/math] matrix will tend to be smaller than the number of rows t in the smallest d-disjunct [math]\displaystyle{ t\times n }[/math] 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 [math]\displaystyle{ 111100 }[/math]) 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 [math]\displaystyle{ O(nt) }[/math].[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 [math]\displaystyle{ O(nt) }[/math]-time algorithm for constructing a d-disjoint matrix with n columns and [math]\displaystyle{ \Theta(d^2\ln n) }[/math] rows.[4]
See also
- Group testing
- Concatenated code
- Compressed sensing
References
- ↑ Paul Erdős; Péter Frankl; Zoltán Füredi (1985). "Families of finite sets in which no set is covered by the union of r others". Israel Journal of Mathematics 51 (1–2): 79–89. doi:10.1007/BF02772959. ISSN 0021-2172. http://bsmath.hu/~p_erdos/1985-14.pdf.
- ↑ 2.0 2.1 2.2 2.3 Hong-Bin Chen; Frank Hwang (2006-12-21). "Exploring the missing link among d-separable, d-separable and d-disjunct matrices". Discrete Applied Mathematics 155 (5): 662–664. doi:10.1016/j.dam.2006.10.009.
- ↑ Piotr Indyk; Hung Q. Ngo; Atri Rudra (2010). "Efficiently Decodable Non-adaptive Group Testing". Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA). ISSN 1071-9040.
- ↑ Ely Porat; Amir Rothschild (2008). "Explicit Non-Adaptive Combinatorial Group Testing Schemes". Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP): 748–759. Bibcode: 2007arXiv0712.3876P.
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 (1996). "On r-Cover-free Families". Journal of Combinatorial Theory. Series A 73 (1): 172–173. doi:10.1006/jcta.1996.0012.
![]() | Original source: https://en.wikipedia.org/wiki/Disjunct matrix.
Read more |