This is probably more of a mathematical question than an Octave question,
per se, but someone here might be interested...
Here's the problem, in a simple form: I have a square symmetrix matrix,
M, with all elements either zero or one. All diagonal elements are zero.
I want to find a set of indices, I, such that M(I,I) is a zero matrix of
the largest possible size. There will usually be more than one I that
maximizes size(M), but they are all equally good for my purposes, so I
would choose one arbitrarily. Maybe if I always delete one of the
rows/cols with the largest number of ones, and repeat, that will do it,
but I'm not sure of that. Any ideas?
Background: I have a bunch of subjects, some of whom are genetically
related. The rows and columns of matrix M correspond to subjects and a 1
in cell i,j means that subjects i and j are genetically related strongly
enough that I don't want to include both of them in a certain analysis I'm
doing. So I want to find the largest set of subjects who are not too
closely genetically related.
We ascertained families, so we know about a lot of genetic relatives, but
it turns out that when we collect thousands of nuclear families, some of
the independently-ascertained families are very closely related (e.g., the
parents are siblings). These relationships are discovered, in our data,
by comparing 550,000 genotypes of every possible pair of 8,000 subjects
(which would take forever but I run 120 processes concurrently and then
it's about 4 hours).
Mike
___