Solving Square-Submatrix Equation Systems

We consider systems of submatrix equations, that is, sets of equality constraints over square submatrices of the input. By generalising the recursive algorithm of Gawrychowski et al. [Universal reconstruction of a string, Theoretical Computer Science 2020] to two dimensions, we obtain a linear-time procedure that finds a solution for any such input system. As an immediate by-product, this yields an optimal-time algorithm for decompressing any two-dimensional macro scheme based on copy operations of sub-squares.