Treat each column as a bitstring. Walk each column and push the column index into a hash key (the bitstring itself). At the end, walk the hash looking for hash keys with a value count that is the same as the number of bits in the key. Since the value is an array of the column indices, you know what columns to extract.

Sticking with the bitstring concept, I think rather that you are looking for a subset of n bitstrings such that the bitwise-OR of the bitstrings has only n distinct bits set.

Note that some or all of those bitstrings may have fewer than n bits set; you may even have two bitstrings that have no bit set in common in a qualifying subset (though you'd need a minimum of 4 elements in the subset to avoid it being further decomposable).

Hugo

hv,
I understand now that to be considered for extraction, a variable need not have the exact same 1s and 0s in common. I need to go but I still think this sounds like a good logic programming candidate.

Cheers - L~R

I was thinking of storing the string 'A' as the value for the key which consists of, for this example, the byte that has bits '01010000' (the last three zeros padding).

I don't think that is sufficient: a submatrix need not have all ones, as for example in the 3x3 submatrix of the example. Indeed, a 3x3 submatrix could have bit-patterns 110, 101, 011 such that no two rows or column are the same, nor is any row or column all ones.

Hugo