Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Reconstruction of matrices from submatrices

Authors: Géza Kós, Péter Ligeti and Péter Sziklai
Journal: Math. Comp. 78 (2009), 1733-1747
MSC (2000): Primary 05B20; Secondary 11B83
Published electronically: January 23, 2009
MathSciNet review: 2501072
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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.

References [Enhancements On Off] (What's this?)

  • 1. P. Borwein, T. Erdélyi, G. Kós, Littlewood-type problems on $ [0,1]$. Proc. London Math. Soc. 79, No. 1 (1999), 22-46. MR 1687555 (2000c:11111)
  • 2. M. Dudik, L. J. Schulman, Reconstruction from subsequences. J. Combin. Theory Ser. A 103, No. 2 (2003), 337-348. MR 1996071 (2005a:05005)
  • 3. W. H. Foster, I. Krasikov, Inequalities for real-root polynomials and entire functions. Adv. Appl. Math. 29, No. 1 (2002), 102-114. MR 1921546 (2004a:39055)
  • 4. L. O. Kalashnik, The reconstruction of a word from fragments. Numer. Math. and Comp. Tech., Akad. Nauk. Ukrain. SSR Inst. Mat. IV (1973), 56-57. MR 0485573 (58:5399)
  • 5. P. J. Kelly, On isometric transformations. Ph.D. Thesis, University of Wisconsin (1942).
  • 6. I. Krasikov, Y. Roditty, On a reconstruction problem for sequences. J. Combin. Theory Ser. A 77 No. 2 (1997), 344-348. MR 1429086 (97m:05186)
  • 7. B. Manvel, P. K. Stockmeyer, On reconstruction of matrices. Mathematics Magazine 44, No. 4 (1971), 218-221. MR 0295937 (45:4998)
  • 8. A. Marcus, G. Tardos, Excluded permutation matrices and the Stanley-Wilf conjecture. J. Combin. Theory Ser. A 107, No. 1 (2004), 153-160. MR 2063960 (2005b:05009)
  • 9. J. Pach, G. Tardos, Forbidden patterns and unit distances. SCG '05: Proc. 21st Annual Symposium on Computational Geometry, Pisa, Italy (2005), 1-9.
  • 10. G. Tardos, On 0-1 matrices and small excluded submatrices. J. Combin. Theory Ser. A 111, No. 2 (2005), 266-288. MR 2156213 (2006e:05176)
  • 11. S. M. Ulam, A collection of mathematical problems. Interscience Tracts in Pure and Applied Mathematics 8 (1960). MR 0120127 (22:10884)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 05B20, 11B83

Retrieve articles in all journals with MSC (2000): 05B20, 11B83

Additional Information

Géza Kós
Affiliation: Mathematical Institute, Loránd Eötvös University, Pázmány P. s. 1/c, Budapest, Hungary H-1117; Computer and Automation Research Institute, Kende u. 13–17, Budapest, Hungary H-1111

Péter Ligeti
Affiliation: Department of Computer Algebra and Department of Computer Science, Loránd Eötvös University, Pázmány P. s. 1/c, Budapest, Hungary H-1117; Alfréd Rényi Institute of Mathematics, Reáltanoda u. 13-15, Budapest, Hungary H-1053

Péter Sziklai
Affiliation: Mathematical Institute, Loránd Eötvös University, Pázmány P. s. 1/c, Budapest, Hungary H-1117

Received by editor(s): February 15, 2008
Received by editor(s) in revised form: August 8, 2008
Published electronically: January 23, 2009
Additional Notes: The first and the third authors were supported in part by the Bolyai Grant of the Hungarian Academy of Sciences.
The third author was partially supported by the OTKA T-67867 grant.
Article copyright: © Copyright 2009 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society