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 nelement submatrix need not have n bits set. The sparsest counterexample is:
.. which can decompose into two 3element 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. Update: swapped 2 bits in the last row of the sparse matrix, so it actually represents what I'm sayingmy @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, ], );
Hugo


Replies are listed 'Best First'.  

Re^3: decomposing binary matrices
by BrowserUk (Pope) on Feb 16, 2007 at 15:55 UTC  
by hv (Parson) on Feb 16, 2007 at 16:06 UTC 
In Section
Seekers of Perl Wisdom