Talk:Disjunct matrix
Add topic | This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
| |||||||||||
Example of 2-disjunct matrix with 12 columns
[edit]The current article says, without further explanation,
| “ | Here is the 2-disjunct matrix :
|
” |
![{\displaystyle M_{9\times 12}=\left[{\begin{array}{cccccccccccc}0&0&0&0&0&0&1&1&1&1&0&0\\0&0&0&1&1&1&0&0&0&1&0&0\\1&1&1&0&0&0&0&0&0&1&0&0\\0&0&1&0&0&1&0&0&1&0&1&0\\0&1&0&0&1&0&0&1&0&0&1&0\\1&0&0&1&0&0&1&0&0&0&1&0\\0&1&0&1&0&0&0&0&1&0&0&1\\0&0&1&0&1&0&1&0&0&0&0&1\\1&0&0&0&0&1&0&1&0&0&0&1\end{array}}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/676681bd1d0fcb308b3ef5c60d9eb1e1d1157852)
If I understand correctly, this matrix encodes a way to detect 2 defective items among 12, in only 9 tests. However, there is a more efficient solution that uses only 8 tests instead of 9 tests. Namely, you can do this:
![{\displaystyle M_{8\times 12}=\left[{\begin{array}{cccccccccccc}1&1&1&0&0&0&0&0&0&0&0&0\\1&0&0&1&1&0&0&0&0&0&0&0\\0&1&0&1&0&1&0&0&0&0&0&0\\1&0&0&0&0&0&1&1&0&0&0&0\\0&1&0&0&0&0&1&0&1&0&0&0\\0&0&0&0&0&1&0&1&0&1&0&0\\0&0&0&0&1&0&0&0&1&0&1&0\\0&0&1&0&0&0&0&0&0&1&1&0\\\end{array}}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2f0468fbfa748c9ec2131dfeb4f45f259313ffb7)
So what I don't understand about the current article is: What's the significance of ? Does it relate somehow to the preceding text in the article, e.g. was it constructed using some interesting algorithm? Or is it just a completely arbitrary example? (Or, it's possible that I've misunderstood the terms here and my matrix is "2-separable but not 2-disjunct," or something like that. I'm not clear on why we need two different terms; it seems like maybe only one of them has physical significance in non-adaptive group testing?) --Quuxplusone (talk) 05:51, 27 April 2019 (UTC)
- Answering my own question from last year: Indeed, the 8x12 matrix I provided above is "2-separable but not 2-disjunct." That is, in group-testing terms, my 8x12 matrix can find exactly 2 defective items among 12 in only 8 tests; but the article's 9x12 matrix can find 0, 1, or 2 defective items among 12 — it turns out that we need an extra test if we want to accomplish that slightly harder goal.
- I've radically rewritten the article to make the distinction between "d-separable" and "d-disjunct" more clear, and given it some fresh (and smaller) examples. --Quuxplusone (talk) 21:36, 2 January 2020 (UTC)
6x4 matrix is not 2-disjunct
[edit]column set (3,4) has a boolean sum that is a superset of column 1.