http://qs1969.pair.com?node_id=600449

in reply to decomposing binary matrices

I think this does the job, but it needs testing on some more demanding sample data.

```c:\test>600418.pl
This input

0 0 1 1 0
1 0 1 1 1
0 1 0 1 0
1 1 0 0 1
0 1 1 1 0

Inverted looks like this

0 : 01010
1 : 00111
2 : 11001
3 : 11101
4 : 01010

This subset can be removed from the main group:

0 : 01010
4 : 01010

c:\test>600418.pl
This input

0 0 0 1 1 0 0 0
0 1 0 1 1 1 1 0
1 0 1 0 1 0 1 1
1 1 1 0 0 1 1 1
1 0 1 1 1 0 0 1

Inverted looks like this

0 : 00111
1 : 01010
2 : 00111
3 : 11001
4 : 11101
5 : 01010
6 : 01110
7 : 00111

This subset can be removed from the main group:

1 : 01010
5 : 01010

This subset can be removed from the main group:

0 : 00111
2 : 00111
7 : 00111

Relating the subset numbering back to the pre-inversion set is left as an exercise.

```#! perl -slw
use strict;

=comment
my @grid = (
[ 0,   0,   1,   1,   0 ],
[ 1,   0,   1,   1,   1 ],
[ 0,   1,   0,   1,   0 ],
[ 1,   1,   0,   0,   1 ],
[ 0,   1,   1,   1,   0 ],
);
=cut

my @grid = (
# 0  1  2  3  4  5  6  7
[ 0, 0, 0, 1, 1, 0, 0, 0, ],
[ 0, 1, 0, 1, 1, 1, 1, 0, ],
[ 1, 0, 1, 0, 1, 0, 1, 1, ],
[ 1, 1, 1, 0, 0, 1, 1, 1, ],
[ 1, 0, 1, 1, 1, 0, 0, 1, ],
);
print "This input\n";
print "\t@\$_" for @grid;

my @inverted;
for my \$i ( 0 .. \$#grid ) {
\$inverted[ \$_ ] .= \$grid[ \$i ][ \$_ ] for 0 .. \$#{ \$grid[ \$i ] };
}
print "\nInverted looks like this\n";
print "\t\$_ : \$inverted[ \$_ ]" for 0 .. \$#inverted;

my @bitCounts;
push @{ \$bitCounts[ \$inverted[ \$_ ] =~ tr[1][1] ] }, \$_ for 0 .. \$#inv
+erted;

#print @{ \$_||[] } for @bitCounts;

for my \$c ( 2 .. \$#bitCounts ) {
#print( "skipping \$c elements < \${ \ scalar @{ \$bitCounts[ \$c ] }
+} bits" ),
next unless @{ \$bitCounts[ \$c ] } >= \$c;

my @set = @{ \$bitCounts[ \$c ] };

for my \$offset ( 0 .. @set - \$c ) {

my \$matches = grep{
\$inverted[ \$set[ \$offset ] ] eq \$_
} @inverted[ @set[ \$offset .. \$#set ] ];
#print "set:@set matches:\$matches";

last unless \$c <= \$matches;

print "\nThis subset can be removed from the main group:\n";
print "\t\$_ : \$inverted[ \$_ ]" for grep{
\$inverted[ \$set[ \$offset ] ] eq \$inverted[ \$_ ]
} @set[ \$offset .. \$#set ];
}
}

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.

Replies are listed 'Best First'.
Re^2: decomposing binary matrices
by hv (Parson) on Feb 16, 2007 at 15:16 UTC

Thanks. First, I should note that there must be at least as many values as variables, since each variable must take a distinct value within the set of possible values.

Second, variables that are part of an n-element submatrix need not have n bits set. The sparsest counterexample is:

```my @grid = (
# 0  1  2  3  4  5
[ 0, 0, 0, 1, 1, 0, ],
[ 0, 0, 0, 1, 0, 1, ],
[ 0, 0, 0, 0, 1, 1, ],
[ 1, 1, 0, 0, 0, 0, ],
[ 1, 0, 1, 0, 0, 0, ],
[ 0, 1, 1, 0, 0, 0, ],
);
.. which can decompose into two 3-element submatrices.

The least sparse version of that is:

```my @grid = (
# 0  1  2  3  4  5
[ 0, 0, 0, 1, 1, 1, ],
[ 0, 0, 0, 1, 1, 1, ],
[ 0, 0, 0, 1, 1, 0, ],
[ 1, 1, 1, 1, 1, 1, ],
[ 1, 1, 1, 1, 1, 1, ],
[ 1, 1, 0, 1, 1, 1, ],
);
.. which can decompose the same way.

Update: swapped 2 bits in the last row of the sparse matrix, so it actually represents what I'm saying

Hugo

Hm. Sorry to have wasted your time. I'd picked up on this bit of the OP

... since A and E are restricted to only two values between them, they must consume those two values;

... and hung my hat on it, but that obviously doesn't apply in the same way to the two examples above.

Question: Would this example also decompose into the (same?) two groups as the above?

```my @grid = (
[ 0, 1, 0, 1, 0, 0, ],
[ 0, 0, 0, 1, 1, 0, ],
[ 0, 1, 0, 0, 1, 0, ],
[ 1, 0, 0, 0, 0, 1, ],
[ 1, 0, 1, 0, 0, 0, ],
[ 1, 0, 0, 0, 0, 1, ],
);