I was wondering if the following problem has been studied/has a name:

Given a matrix of numbers (may assume to be integers), find the smallest number of rules which define the matrix. Three kinds of rules may be used:

  • row rules: row[i, x] - the value of any cell in row i is x
  • column rules: col[j, x] - the value of any cell in column j is x
  • cell rules: cell[i, j, x] - the value of cell at [i,j] is x

The rules have a precedence order: first cell rules are considered, then row rules, then column rules.


Given the 3 x 3 matrix:

2 2 2
1 2 3
1 3 3

one set of rules which describe the matrix is:

row[1,2], col[3,3], col[1,1], cell[2,2,2], cell[3,2,3]

Edit: I would be interested in getting opinions on what the complexity is of this problem. I have a polynomial time algorithm which does well enough for my use cases, but it would nice to know if the general case is not in P.

  • 2
    $\begingroup$ A slightly different way of thinking about the problem is that $row[i,x]$ means that all entries in row $i$ have value $x$, similarly for $col[j,x]$ and, rather than having a precedence order, simply have that later 'operations' override earlier ones. Thus your example could be given by $row[3,3], col[1,1], col[3,3], row[1,2], cell[2,2,2]$. Of course, this is a different problem than the one you state. $\endgroup$ – Dave Clarke May 29 '11 at 7:19
  • 2
    $\begingroup$ The points being: 1) you probably mean "all" instead of "any", and 2) applying the rules in order rather than using the given precedence makes the problem more natural. Consider matrix $[1, 2, 3; 1, 2, 3; 1, 4, 4]$. With my scheme this is $col[1,1],row[3,4],col[2,2],col[3,3]$, but in your scheme I'm forced to apply the $row$ operation first. $\endgroup$ – Dave Clarke May 29 '11 at 7:31
  • 3
    $\begingroup$ While this is not your problem, (or even Dave's reformulation) a related question where the only "rule" is the ability to cover a subrectangle, and the only "values" are 0 and 1, was considered by Applegate et al: cs.cornell.edu/~katrina/papers/acl.pdf $\endgroup$ – Suresh Venkat May 29 '11 at 7:42
  • 1
    $\begingroup$ I think that Dave’s problem becomes equivalent to this problem if we add the (arguably unnatural) constraint to Dave’s problem that operations must appear in the order of col, row and cell. $\endgroup$ – Tsuyoshi Ito Jun 1 '11 at 23:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.