Minimal givens of a Fill-a-Pix/Mosaic Puzzles

Question

Recently, I solved some Fill-a-Pix Puzzles (or also called Mosaic Puzzles) and got fascinated by the techniques to solve a puzzle. For those who don't know the rules to solve such a puzzle, you can follow this link or just comprehend the following mathematical description of the problem (which I need to formulate my problem):

Definition Let $A = (a_{ij}) \in M_{m,n}(\{0,1\})$ and $\mathcal{M}_A = (m_{ij}) \in M_{m,n}(\{0,\dots,9\})$ be the matrix defined by $$m_{ij} = \Big| \big\{ a_{kl} \, \big| \, |k-i|\leq 1, |l-j|\leq 1, a_{kl} = 1 \big\} \Big|.$$ Let us call $A$ the picture matrix and $\mathcal{M}_A$ the corresponding data matrix.

Example

If $$A = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix},$$ then $$ \mathcal{M}_A = \begin{pmatrix} 2 & 3 & 2 \\ 4 & 5 & 3 \\ 3 & 4 & 2 \end{pmatrix}. $$

Observations and Thoughts

1. Not every matrix can be a data matrix, for instance there is no picture matrix $A \in M_{1,2}(\{0,1\})$ such that $ \mathcal{M}_A = \begin{pmatrix} 0 & 2 \end{pmatrix} $.
2. It is not hard to show that if $\require{enclose} \enclose{horizontalstrike}{M}$ is a data matrix, then there is a unique matrix $\require{enclose} \enclose{horizontalstrike}{A}$ such that $\require{enclose} \enclose{horizontalstrike}{M = \mathcal{M}_A}$. A proof via induction is the key. (This observation is wrong, see 5.)
3. Let $M$ be a data matrix. Sometimes it suffices to not even know all entries of $M$ and still get a unique picture matrix corresponding to $M$ (this is exactly how this puzzle works). For example, if $$ M = \begin{pmatrix}* & * & * \\ * & 9 & * \\ * & * & * \end{pmatrix},$$ then the unique matrix $A$ with $M = \mathcal{M}_A$ is $$ A = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{pmatrix}. $$
4. This does not always work though. To be more explicit: If we only know few entries of the data matrix, it can correspond to more than one possible picture matrices. An example is $$ M = \begin{pmatrix} * & * & * \\ * & 8 & * \\ * & * & * \end{pmatrix}. $$ Here, both $M = \mathcal{M}_A$ and $M = \mathcal{M}_B$ where $$ A = \begin{pmatrix} 1 & 0 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{pmatrix} \quad \text{or} \quad B = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{pmatrix} $$ are possible solutions, depending, for instance, on the upper left entry of $M$.
5. Even if we know all entries of the data matrix $M$, there might be different matrices $A$ and $B$ with $\mathcal{M}_A = M = \mathcal{M}_B$ as Jaap Scherphuis pointed out in the comments (and this is why observation 2. is wrong). I will put his example here: If $M = \begin{pmatrix} 1 & 1 \end{pmatrix}$, then both $A = \begin{pmatrix} 0 & 1 \end{pmatrix}$ and $A = \begin{pmatrix} 1 & 0 \end{pmatrix}$ satisfy $\mathcal{M}_A = M = \mathcal{M}_B$ despite $A \neq B$.

Assumption: From now on, we suppose $M$ is a data matrix for which there is exactly one corresponding picture matrix.

Question Given a data matrix $M$, what is the minimal number of entries of $M$ I need to know, such that I can find a unique picture matrix $A$ such that $M = \mathcal{M}_A$?

Is there any mathematics done on this problem already? If not, is there a similar problem where people have done research on it?

Thank you in advance!

Answer 1

Not an answer / just a long comment on non-uniqueness.

In fact, if the number of rows $m$, or the number of columns $n$, is of the form $3k+2$, then there exists $M$ matrices with multiple $A$ solutions. E.g. for $n=8$ here are three $A$ matrices:

01001001
01001001
01001001
01001001

10010010
10010010
10010010
10010010

10010010
10010010
01001001
10010010

which have the same $M$ matrix:

2222222
3333333
3333333
2222222

The underlying reason is that when $n=3k+2$, the $mn$ equations are not linearly dependent, since a single row (of length $n$) can be "decomposed" in two ways:

(..)(...)(...)
      vs
(...)(...)(..)

so we have $M_{i1} + M_{i4} + M_{i7} = M_{i2} + M_{i5} + M_{i8}$ for every row $i$. Now, the $mn$ equations being linearly dependent means there can be multiple solutions in $\mathbb{R}^{m\times n}$, but the examples show there can also be multiple solutions even in $\{0,1\}^{m\times n}$.

---

Obviously, this doesn't answer the OP question, but in light of this, we might have to find a way to characterize which $M$ admits a unique solution $A$, before we ask the further question of when a partial view of such an $M$ also admits a unique solution $A$...?