in reply to decomposing binary matrices

Can you be more specific? I don't understand what is the goal and where is the issue... For instance, your two (split?) tables do not contain 1 for B4... For me it is possible to represent that structure as
$possible_values = {A=>[2,4],B=>[3,4,5],...,E=>[2,4]};
but it could mean nothing for your problem.