Reverse cartesian product matching all given rows
Unfortunately the problem is NP-hard when the number of columns ($n$) is unlimited.  In particular, consider the case with $n$ columns and where every number in every row is either 0 or 1.  Then your problem is equivalent to: given a truth table for a boolean function, find a minimal DNF formula (with the minimum number of clauses) for that function.  This is NP-hard.

I know you said you'll have at most 8 columns, so this theoretical result doesn't necessarily imply there is no hope for your specific situation, but it does suggest that you shouldn't expect an efficient algorithm that will generalize to a large number of columns.

One approach you could use that might work well enough in your situation is to use a SAT solver.  Encode each of the sets $A_{i,j}$ with a one-hot encoding; i.e., you have variables $x_{i,j,t}$, which is true if $t \in A_{i,j}$ or false otherwise.  Then it is easy to write down a bunch of constraints (clauses) that enforce that these $A_{i,j}$ form a solution to your problem.  For instance, for each row $r$ that isn't in the input (each $r \notin S$), you get a constraint that $r_1 \notin A_{i,1} \lor r_2 \notin A_{i,2} \lor \dots$ for each $i$, i.e., $(\neg x_{i,1,r_1}\lor \neg x_{i,2,r_2} \lor \dots)$.  And so on.  In this way, for any $k$, you can set up a SAT instance that will be satisfiable iff it is possible to express your input using $k$ reverse cartesian products.  Then you can use binary search on $k$ to find the minimal $k$ such that this is possible.

Because SAT is NP-hard, this won't scale to very large inputs, but it's possible it might work well enough on the problem sizes you mention.  The only way to know for sure is to try it and see.