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

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

.. 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