Reconstruction of matrices from submatrices

Abstract:

For an arbitrary matrix $A$ of $n\times n$ symbols, consider its submatrices of size $k\times k$, obtained by deleting $n-k$ rows and $n-k$ columns. Optionally, the deleted rows and columns can be selected symmetrically or independently. We consider the problem of whether these multisets determine matrix $A$.

Following the ideas of Krasikov and Roditty in the reconstruction of sequences from subsequences, we replace the multiset by the sum of submatrices. For $k>cn^{2/3}$ we prove that the matrix $A$ is determined by the sum of the $k\times k$ submatrices, both in the symmetric and in the nonsymmetric cases.