Here is one approach. It won't survive JPEG compression, though, so probably you can do better.
Let $m$ be an integer large enough that $2^m$ is significantly larger than both the width and height of the matrix. Choose a maximum-period $m$-bit LFSR; this generates a sequence of bits of length $2^m-1$, say $s_1,s_2,s_3,\dots,s_{2^m-1}$, where each $s_i \in \{0,1\}$.
Now, construct the original matrix as follows: at coordinate $(i,j)$, the value will be $s_i \oplus s_j$.
Given a submatrix, we can find coordinates as follows. First note that given a consecutive range of the sequence $s$ of length at least $$, we can find where in the sequence it was taken from. In other words, given $s_i,s_{i+1},\dots,s_{i+m-1}$, we can recover the value of $i$. (How? Simply trying all possible values of $i$ will work; one property of LFSR sequences is that the map $i \mapsto (s_i,s_{i+1},\dots,s_{i+m-1})$ is bijective, so $i$ will be uniquely determined.)
Now given the submatrix, we'll try to find the coordinates of its upper-left corner, say $(i,j)$. We'll start by looking at the first row of the submatrix, and examine the sequence of values that appear in its grid. This either takes the form $s_i,s_{i+1},s_{i+2},\dots$ or $s_i \oplus 1, s_{i+1} \oplus 1, \dots$ according to whether $s_j=0$ or $s_j=1$. We can try both possibilities for $s_j$, and get two candidates for $i$. Then we look at the first column of the submatrix, and obtain two candidates for $j$ in the same way. This gives us two candidates for $(i,j)$, we can check which one is correct by looking at a few other positions in the submatrix.
Then, you can recover the coordinates of its lower-right corner in the same way.
All in all, this will enable you to recover the coordinates of the submatrix, as long as the submatrix is at least $m$ pixels wide and $m$ pixels high.
There are other ways as well. For instance, one very simple approach is to fill in the original matrix randomly, and remember how you filled it in. Then given a submatrix it is straightforward to find where it came from (e.g., by checking all possibilities; this can be sped up by precomputing a hash table).
In practice, if you plan to print out the original matrix and then take a scan or photo of it, then you might want a different approach that is more robust to the kind of transformations that will typically occur during printing and scanning. That will lead to a very different kind of problem. So if you want to know about how to do that, you should probably ask a separate question focused on those considerations.
