in reply to Re: decomposing binary matrices

in thread decomposing binary matrices

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:

.. which can decompose into two 3-element submatrices.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, ], );

The least sparse version of that is:

.. which can decompose the same way.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, ], );

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

Hugo

In Section
Seekers of Perl Wisdom