Reconstruction of matrices from submatrices
Géza Kós, Péter Ligeti, Péter Sziklai · Mathematics of Computation · 2009
For an arbitrary matrix A A of n × n n\times n symbols, consider its submatrices of size k × k k\times k , obtained by deleting n − k n-k rows and n − k 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 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 > c n 2 / 3 k>cn^{2/3} we prove that the matrix A A is determined by the sum of the k × k k\times k submatrices, both in the symmetric and in the nonsymmetric cases.