Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister
 
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
Replies are listed 'Best First'.
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 rifling through the Monastery: (5)
As of 2015-07-28 04:43 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (252 votes), past polls