Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot
 
PerlMonks  

Re^2: decomposing binary matrices

by hv (Parson)
on Feb 16, 2007 at 15:16 UTC ( #600455=note: print w/ replies, xml ) Need Help??


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:

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


Comment on Re^2: decomposing binary matrices
Select or Download Code
Re^3: decomposing binary matrices
by BrowserUk (Pope) on Feb 16, 2007 at 15:55 UTC

    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, ], );

    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.

      Yes: labelling the columns A..F and the rows 1..6, we know variables {B, D, E} must consume values {1, 2, 3} between them, and likewise {A, C, F} must consume {4, 5, 6}. In this example, however, the latter can be further decomposed: C can only be 5, so {A, F] are left with {4, 6}.

      Hugo

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://600455]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (6)
As of 2014-08-29 19:44 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (287 votes), past polls